Итераторы

Итератор — объект, который указывает на элемент контейнера. Для вектора это почти обычный указатель, для дерева — гораздо более хитрая штука, но снаружи они выглядят одинаково, и в этом весь смысл: алгоритмы пишутся один раз и работают со всем.

Полуинтервалы

Все стандартные функции принимают пару итераторов: начало включительно, конец не включительно.

sort(a.begin(), a.end());              // весь контейнер
sort(a.begin() + 2, a.begin() + 7);    // элементы с 2-го по 6-й

a.end() указывает не на последний элемент, а на место за ним. Разыменовывать его нельзя.

Соглашение выбрано не случайно: при нём длина диапазона — это просто разность границ, пустой диапазон записывается как [i, i), и в циклах почти не появляется плюс-минус единиц. Привыкнуть к нему стоит и в своём коде тоже.

Индекс из итератора

Функции вроде min_element и lower_bound возвращают итератор, а не индекс. Индекс получается вычитанием:

int i = min_element(a.begin(), a.end()) - a.begin();

Работает это только для итераторов с произвольным доступом — вектора, массива, дека. У set вычитать нельзя, там расстояние считается функцией distance за линейное время.

Сдвиг итератора: advance, next, prev

У вектора итератор двигают арифметикой: it + 5, it += 5. У set и map так нельзя — там доступны только ++ и --, по одному шагу за раз.

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

	что делает	аналог для числа
advance(it, 5)	двигает it на месте, ничего не возвращает	i += 5
next(it, 5)	возвращает новый итератор, it не трогает	j = i + 5
prev(it, 5)	то же назад	j = i - 5

Второй аргумент можно опустить, тогда шаг равен единице. Отсюда самые частые применения:

int first  = *s.begin();          // первый элемент
int second = *next(s.begin());    // второй
int last   = *prev(s.end());      // последний — s.end() разыменовать нельзя

prev(s.end()) стоит запомнить: у set нет back(), и это стандартный способ добраться до максимума.

Чего они стоят

Для вектора все три работают за $O(1)$: под капотом обычное сложение указателей. Для set и map — за $O(k)$, где $k$ — величина сдвига: функция честно делает $k$ инкрементов.

То же и с distance: у вектора это вычитание, у set — проход по дереву от одного итератора до другого.

Измерено на множестве из 200 000 элементов: 200 вызовов distance(s.begin(), it) со случайным it заняли 132 мс. Те же 200 вызовов на векторе — меньше миллисекунды.

Практический вывод: distance и advance с большим шагом внутри цикла превращают решение в квадратичное. Если по set нужен доступ по индексу, значит, выбрана не та структура.

Стрелка против звёздочки

Разыменование — *it. Если в контейнере лежит пара, к её полям обращаются так:

cout << (*it).second;    // работает, но неудобно
cout << it->second;      // то же самое, короче
cout << *it.second;      // ОШИБКА КОМПИЛЯЦИИ

Последняя строка не работает из-за приоритета операторов: точка выполняется раньше звёздочки, и компилятор пытается взять поле second у самого итератора, а не у того, на что он указывает.

Стрелка -> делает оба действия сразу и потому спасает не только от лишних скобок, но и от этой ошибки. Особенно заметно, когда обращений несколько подряд: node->left->value против (*(*node).left).value.

Обход словаря

for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->first << " " << it->second << "\n";

for (auto& [key, value] : m)          // с C++17 — короче и понятнее
    cout << key << " " << value << "\n";

Второй вариант — структурное связывание. Амперсанд нужен, если значения меняются; без него будет копия.

Когда итератор ломается

Итератор перестаёт быть годным, если контейнер изменился. Правила разные:

Контейнер	Что портит итераторы
vector	любое изменение размера (перевыделение памяти)
deque	добавление в середину; концы безопаснее
set, map	только удаление самого элемента

Отсюда классическая ошибка — удаление во время обхода:

for (auto it = s.begin(); it != s.end(); ++it)
    if (bad(*it)) s.erase(it);        // it испорчен, ++it — обращение к мусору

for (auto it = s.begin(); it != s.end(); )
    if (bad(*it)) it = s.erase(it);   // правильно: erase вернул следующий
    else ++it;

Первый вариант иногда даже «работает» — и это худшее, что может быть: ошибка проявится на другом наборе данных или на другом компиляторе.

Префиксный инкремент

Для чисел i++ и ++i одинаковы. Для итераторов постфиксная форма обязана вернуть копию прежнего значения, а для сложных итераторов копия не бесплатна.

Разница обычно мала, но привычка писать ++it ничего не стоит.