Итераторы: связующее звено STL

Разберитесь в категориях итераторов — от итераторов ввода до непрерывных итераторов. Изучите арифметику итераторов, конвенцию begin/end и то, как итераторы связывают контейнеры с алгоритмами.

Абстракция итераторов

Итераторы — это связующее звено между контейнерами и алгоритмами STL. Вместо написания N алгоритмов для M контейнеров (N*M реализаций) STL определяет общий интерфейс итераторов. Каждый контейнер предоставляет итераторы, а каждый алгоритм оперирует диапазонами итераторов — давая N+M реализаций, которые работают вместе.

Итератор — это объект, который:
1. Указывает на элемент в последовательности
2. Может быть разыменован (*it) для доступа к элементу
3. Может быть инкрементирован (++it) для перехода к следующему элементу
4. Может быть сравнён (it != end) для определения конца последовательности

Различные категории итераторов поддерживают различные наборы операций, образуя иерархию от самых слабых к самым сильным.

Категории итераторов

Категории итераторов C++ образуют иерархию (каждый уровень включает возможности всех нижних уровней):

| Категория | Операции | Примеры контейнеров |
|---|---|---|
| Ввода | Чтение, однопроходный вперёд (++, *, ==) | istream_iterator |
| Вывода | Запись, однопроходный вперёд (++, *=) | ostream_iterator, back_inserter |
| Прямой | Чтение/запись, многопроходный вперёд | forward_list, unordered_set |
| Двунаправленный | Прямой + назад (--) | list, set, map |
| Произвольного доступа | Двунаправленный + прыжки (+n, -n, [], <) | deque |
| Непрерывный (C++17) | Произвольный доступ + элементы расположены рядом в памяти | vector, array, string |

Алгоритмы объявляют минимальную необходимую категорию. std::sort требует итераторы произвольного доступа, поэтому он работает с vector, но не с list (который предоставляет собственную функцию-член sort()).

Конвенция begin/end

Каждый контейнер STL предоставляет begin() и end() — полуоткрытый диапазон [begin, end), где end указывает на один элемент за последним. Свободные функции std::begin() и std::end() работают с контейнерами, массивами C и любым типом, предоставляющим члены .begin() и .end().

begin_end.cpp

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};

    // Member functions
    auto first = vec.begin();   // points to 5
    auto last  = vec.end();     // points past 2

    // Free functions — preferred for generic code
    auto first2 = std::begin(vec);
    auto last2  = std::end(vec);

    // Works with C-arrays too
    int arr[] = {10, 20, 30};
    std::sort(std::begin(arr), std::end(arr));

    // const iterators — read-only access
    auto cit = vec.cbegin();     // const_iterator
    // *cit = 99;                // ERROR: cannot modify through const_iterator

    // Reverse iterators — iterate backward
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << ' ';  // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
    }
    std::cout << '\n';
}

Утилиты итераторов: next, prev, advance, distance

Заголовок предоставляет утилитные функции, которые работают со всеми категориями итераторов, автоматически выбирая наиболее эффективную реализацию.

iterator_utils.cpp

#include <iterator>
#include <vector>
#include <list>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // std::next — returns iterator n positions forward (default 1)
    auto it = std::next(vec.begin(), 2);   // points to 30
    std::cout << *it << '\n';              // 30

    // std::prev — returns iterator n positions backward
    auto it2 = std::prev(vec.end());       // points to 50
    std::cout << *it2 << '\n';             // 50

    // std::advance — modifies iterator in place (no return)
    auto it3 = vec.begin();
    std::advance(it3, 3);                  // now points to 40
    std::cout << *it3 << '\n';             // 40

    // std::distance — number of increments from first to last
    auto d = std::distance(vec.begin(), vec.end());  // 5
    std::cout << "Distance: " << d << '\n';

    // These work with non-random-access iterators too
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = std::next(lst.begin(), 2);  // O(n) for list, O(1) for vector
    std::cout << *lit << '\n';             // 3

    auto ld = std::distance(lst.begin(), lst.end());  // O(n) for list
    std::cout << "List distance: " << ld << '\n';     // 5
}

Вставочные итераторы и потоковые итераторы

Вставочные итераторы позволяют алгоритмам вставлять в контейнеры вместо перезаписи существующих элементов. Потоковые итераторы адаптируют потоки ввода-вывода к интерфейсу итераторов.

insert_stream_iterators.cpp

#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst;

    // back_inserter — calls push_back on each assignment
    std::copy(src.begin(), src.end(), std::back_inserter(dst));
    // dst: {1, 2, 3, 4, 5}

    // front_inserter — calls push_front (works with deque, list)
    // inserter — calls insert at a given position

    // ostream_iterator — write to an output stream
    std::copy(dst.begin(), dst.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << '\n';  // 1, 2, 3, 4, 5,

    // istream_iterator — read from an input stream
    std::istringstream iss("10 20 30 40");
    std::vector<int> from_stream(
        std::istream_iterator<int>(iss),
        std::istream_iterator<int>()   // end-of-stream sentinel
    );
    // from_stream: {10, 20, 30, 40}
}

Подводный камень

Инкрементирование итератора за end() или декрементирование за begin() — это неопределённое поведение. То же касается разыменования end() — это страж, а не валидный элемент.

Частая ошибка — написание it + 1 без проверки, не находится ли it уже на конце или рядом с ним:

auto it = vec.end();
++it;    // UB — за пределами конца
*it;     // UB — разыменование end()

Всегда проверяйте валидность итератора перед операциями. Используйте std::next и std::prev с проверкой расстояния или range-based for циклы, которые автоматически обрабатывают границы.

Лучшая практика

При написании обобщённых функций, работающих с последовательностями:

1. Принимайте пары итераторов (или диапазоны в C++20) вместо конкретных контейнеров
2. Используйте typename или auto для типа итератора
3. Используйте std::distance вместо вычитания (которое требует произвольный доступ)
4. Используйте std::next/std::prev вместо арифметики +/-
5. В C++20 предпочитайте концепты для ограничения требований к итераторам:

template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }

Это гарантирует, что ваш код работает с максимально широким набором контейнеров.

Ключевые выводы

Итераторы отделяют контейнеры от алгоритмов — основной принцип проектирования STL
Существует шесть категорий итераторов: ввода, вывода, прямой, двунаправленный, произвольного доступа, непрерывный
Используйте свободные функции std::begin() / std::end() для обобщённого кода, работающего с контейнерами и массивами C
std::next, std::prev, std::advance, std::distance работают со всеми категориями итераторов
Вставочные итераторы (back_inserter, front_inserter, inserter) позволяют алгоритмам расширять контейнеры
Никогда не разыменовывайте end() и не инкрементируйте за него — и то и другое является неопределённым поведением

Тест — проверьте свои знания

(15 XP)

1. Какую категорию итераторов требует `std::sort`?

2. Что создаёт `std::back_inserter(vec)`?

3. Какова временная сложность `std::distance(first, last)` на `std::list`?

Адаптеры контейнеров и специальные контейнеры

Алгоритмы STL: мощь <algorithm>