Итераторы

Итератор — это объект, указывающий на элемент какого-то контейнера.

Итератор является абстракцией над концепцией указателей. Если указатели работают только с последовательными данными (массивами), то итераторы работают с любыми контейнерами — например со связными списками или деревьями поиска — причём в единообразном синтаксисе, что сильно помогает разработчикам библиотек избегать дублирования кода.

#Синтаксис

Чтобы получить элемент, на который указывает итератор it, необходимо воспользоваться оператором разыменования: *it. Если нужно перейти к следующему элементу надо использовать инкремент: ++it (постфиксного инкремента у итераторов нет).

У всех контейнеров есть какой-то первый и последний элемент. Итератор на первый элемент можно получить через a.begin(), а через a.end() можно получить итератор на некий фиктивный элемент, следующий последним. Таким образом, если проходить от a.begin() до a.end() не включительно, ты мы пройдём по всем элементам контейнера.

vector<int> a = {1, 2, 3, 4, 5};

// в типе итератора должна содержаться информация о контейнере
// поэтому в случае вектора интов это "vector<int>::iterator"
for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;

// в современном C++ можно вместо него использовать "auto"
for (auto it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;

// также если нужно пройтись по всему массиву, можно сжать до такого
for (int x : a)
    cout << x << endl;

// если нужно как-то изменить элемент, его можно передать по ссылке
for (int &x : a)
    x *= 2;

for (x : a)
    cout << x << endl;

for (const int &x : a)
    cout << x << endl;

// (также можно вместо int писать auto)

// the initializer may be a braced-init-list
for (int x : {1, 2, 3, 4, 5})
    cout << x << endl;

// the initializer may be an array
int b[] = {1, 2, 3, 4, 5};
for (int x : b)
    cout << x << endl;

array<int, 5> c = {1, 2, 3, 4, 5};
for (int x : c)
    cout << x << endl;

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

Итераторы — очень важная часть интерфейса контейнера. Итераторы можно передавать в различные алгоритмы стандартной библиотеки, которым не обязательно знать про внутреннее устройство контейнера, но нужно знать про то, какие паттерны доступа к данным возможны.

Поэтому в зависимости от внутренней структуры, итераторы контейнера могут отвечать к одному из нескольких абстрактных классов с разными уровнями гарантий:

• input_iterator, поддерживающий только операции разыменования и инкремента — причём даже без гарантии, что после того, как был произведён инкремент, его предыдущие значения остались валидными. Как можно догадаться из названия, используется для потокового ввода.

• forward_iterator, помимо предыдущего гарантирующий что итераторы на какой-то конкретный элемент можно инкрементировать сколько угодно раз не опасаясь, что они исчезнут (что позволяет их использовать в алгоритмах, проходящих по данным несколько раз).

• bidirectional_iterator, помимо предыдущего поддерживающий возможность декремента (it--) — то есть перехода к предыдущему элементу.

• random_access_iterator, помимо предыдущего поддерживающий возможность переходить к элементу, который находится на каком-то расстоянии $k$ — it + k, it - k, it += k, it -= k — и находить расстояние между позициями, на которые указывают два итератора: например, выражение a - b вернет целое число — расстояние между двумя элементами коллекции, соответствующим итераторам a и b.

#Алгоритмы из STL

Например, итераторы std::vector относятся к random_access_iterator, и если вызвать функцию lower_bound из стандартной библиотеки, то она произведет бинарный поиск по элементам (предполагая, что они отсортированы в порядке неубывания):

vector<int> a = {1, 2, 3, 5, 8, 13};

// вернет 8
cout << *lower_bound(a.begin(), a.end(), 7) << endl;

Функция lower_bound возвращает итератор на первый элемент, не меньший заданного. Также есть upper_bound, возвращающий первый элемент, строго больший (в случае с int это то же самое, что найти lower_bound от x + 1).

Зная, что итераторы вектора поддерживают произвольный доступ, бинарный поиск будет работать за $O(n \log n)$, но для других структур это, возможно, будет не так.

Также по этой причине часто имеет смысл вместо сишных массивов использовать std::array, который является точно таким же массивом фиксированной длины, но поддерживает итераторы и вместе с ними все алгоритмы STL:

array<int, 3> a = {4, 2, 1, 3};

// вернет 1
cout << *min_element(a.begin(), a.end()) << endl;