Итераторы в C++: begin, end и типы итераторов

Что такое итератор на самом деле

Каждый стандартный контейнер — vector, string, map, set, list — хранит свои элементы внутри по-разному. vector — это непрерывный блок, map — сбалансированное дерево, list — связанные узлы. И всё же обходить их все можно одинаково. Делает это возможным итератор: небольшой объект, который «указывает на» один элемент и знает, как шагнуть к следующему.

Считайте итератор обобщённым указателем. Вы получаете его из begin(), читаете элемент, на который он указывает, через *, и продвигаете его вперёд через ++. Части складываются вот так:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30};

    vector<int>::iterator it = v.begin();
    cout << *it << "\n";   // 10 - разыменование читает элемент

    ++it;                  // продвигаемся к следующему элементу
    cout << *it << "\n";   // 20
}

v.begin() возвращает итератор на первый элемент; *it даёт вам этот элемент; ++it переходит к следующему. Эта тройка — разыменовать, продвинуть, сравнить — и есть вся ментальная модель.

begin(), end() и полуоткрытый диапазон

Вторая половина картины — это end(). Принципиально важно: end() не указывает на последний элемент — он указывает на ячейку сразу за последним элементом. Это намеренный «полуоткрытый» диапазон [begin, end): begin включён, end — сигнал остановки.

Такая конструкция делает стандартный цикл чистым — вы идёте, пока итератор не станет равен end():

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5};

    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << "\n";
}

Обратите внимание: it != v.end(), а не it < v.end(). Большинство итераторов контейнеров (например, map или list) не поддерживают <, только == и !=, поэтому != — переносимый выбор. А auto избавляет вас от написания vector<int>::iterator вручную — компилятор выводит тип сам.

Случай пустого контейнера разрешается естественным образом: когда контейнер пуст, begin() == end(), поэтому тело цикла ни разу не выполняется. Никакой особой обработки не нужно.

Никогда не разыменовывайте end()

Самая частая ошибка с итераторами — разыменование end(). Поскольку он указывает на одну позицию за последним элементом, *v.end() читает память, которая вам не принадлежит, — это неопределённое поведение, то есть аварийное завершение или молчаливый мусор, а не дружелюбная ошибка:

vector<int> v = {1, 2, 3};
cout << *v.end();   // НЕОПРЕДЕЛЁННОЕ ПОВЕДЕНИЕ - end() не является элементом

Та же ловушка подстерегает функции поиска. std::find возвращает end(), когда не находит значение, поэтому перед разыменованием нужно проверить результат:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {2, 4, 6, 8};

    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        cout << "Found: " << *it << "\n";
    } else {
        cout << "5 is not in the vector\n";   // выполняется именно это
    }
}

Всегда сравнивайте возвращённый итератор с end(), прежде чем его разыменовывать. Забыть этот if — одна из самых частых причин аварий в STL-коде новичков.

const, cbegin и обратные (reverse) итераторы

Контейнеры выдают разные разновидности итераторов в зависимости от ваших нужд:

• begin() / end() — обычные итераторы для чтения/записи (*it = ... работает).
• cbegin() / cend() — const_iterator; через них можно читать, но нельзя изменять элемент.
• rbegin() / rend() — обратные итераторы, идущие с конца к началу; ++ на самом деле движется назад.

Обратные итераторы — это чистый способ пройти в обратном порядке без возни с индексной арифметикой:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4};

    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << *it << " ";   // 4 3 2 1
    }
    cout << "\n";
}

С обратными итераторами вы по-прежнему пишете ++it, чтобы продвигаться, — итератор сам обрабатывает «обратное» направление внутри. Используйте cbegin()/cend() (или const-ссылку на контейнер), когда цикл должен только читать, чтобы компилятор не дал вам случайно записать.

Итераторы map выдают pairs

Не каждый итератор — это тонкая обёртка над указателем. Итератор std::map обходит дерево, и его разыменование даёт вам std::pair из ключа и значения, доступных через ->first и ->second (как и указатель, итератор поддерживает ->):

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages = {{"Ada", 36}, {"Grace", 85}};

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

Цикл for на основе диапазона построен прямо на begin()/end(), поэтому для обычного прохода вперёд вы обычно будете тянуться именно к нему. Явные итераторы оправдывают себя, когда вам нужен обратный обход, позиция элемента или передача диапазона в алгоритм.

Главная ловушка: инвалидация итераторов

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

Для vector метод push_back может перевыделить весь буфер для роста, инвалидировав каждый действующий итератор. Удаление во время обхода ещё более печально знаменито — это классическая авария:

vector<int> v = {1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0)
        v.erase(it);   // ОШИБКА - erase инвалидирует it, и тогда ++it — это UB
}

Решение в том, что erase возвращает действительный итератор на элемент после удалённого. Продвигайтесь только тогда, когда не удаляли:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};

    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0)
            it = v.erase(it);   // erase возвращает следующий действительный итератор
        else
            ++it;               // продвигаемся только если ничего не удалили
    }

    for (int x : v) cout << x << " ";   // 1 3 5
    cout << "\n";
}

Заметьте, что в заголовке for нет ++it — тело само решает, продвигаться ли. (В реальном коде идиома erase-remove или std::erase_if из C++20 делают это одной строкой.) Правило, которое стоит запомнить: любая операция, добавляющая или удаляющая элементы, может инвалидировать итераторы, поэтому не держите старый итератор через такое изменение.

Далее: алгоритмы

Теперь, когда вы умеете описывать диапазон парой begin/end, вы открыли для себя всю библиотеку алгоритмов STL. Функциям вроде sort, find, count и accumulate всё равно, какой у вас контейнер, — они работают с диапазонами итераторов, так что один и тот же вызов работает на vector, массиве или их фрагменте. Дальше мы заставим эти итераторы работать и позволим стандартной библиотеке выполнять циклы за вас.