1. Зачем нужны категории итераторов
Если вы до этого воспринимали итератор как «почти указатель», то вы не одиноки: так делает половина человечества, включая меня в мои первые дни с C++. Но в STL итератор — это не “адрес в памяти”, а контракт возможностей: что точно можно делать с этим итератором и что нельзя ожидать.
Категории итераторов нужны ровно для того, чтобы стандартизировать эти возможности. Тогда STL-алгоритм может честно сказать: «мне достаточно уметь делать ++it и читать *it» — или наоборот: «нет, ребята, без it + n и it2 - it1 я сортировать не буду».
Чтобы было ближе к жизни: итератор — это как транспорт. На велосипеде можно ехать вперёд, иногда можно аккуратно откатиться назад, но “телепортироваться на 10 километров вперёд” нельзя. А вот метро (условный vector) позволяет “прыгнуть” на нужную станцию быстро.
Итератор и диапазон [first, last)
Прежде чем делить итераторы по категориям, важно освежить базовую модель: STL почти везде использует полуинтервал [first, last). Это означает, что first указывает на первый элемент диапазона, а last указывает на позицию после последнего. То есть last разыменовывать нельзя — он как табличка «дальше обрыв».
Мини-демо на нашем учебном примере: пусть у нас есть список задач (мы будем использовать его как “контекст” в примерах):
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> tasks{"Read", "Code", "Sleep"};
for (auto it = tasks.begin(); it != tasks.end(); ++it) {
std::cout << *it << '\n';
}
}
// Read
// Code
// Sleep
Здесь вы видите базовые операции, которые почти всегда ассоциируются с итераторами: сравнение !=, разыменование *it и продвижение ++it. Но дальше начинается самое интересное: не каждый итератор поддерживает “продвинутые” операции, вроде it + 5 или --it.
Лестница возможностей итераторов
Категория итератора — это, по сути, ответ на вопрос: какие операции гарантированно работают (и что они означают). В стандарте это не просто вкусовщина: это требования к корректности, на которые опираются алгоритмы стандартной библиотеки.
Удобно держать в голове “лестницу возможностей”: чем выше категория, тем больше операций разрешено. Ниже — практическая таблица (это не формальная таблица стандарта, а учебная шпаргалка).
| Категория | Можно читать *it | Можно писать *it = ... | Можно ++it | Можно --it | Можно it + n, it[n] | Типичная ассоциация |
|---|---|---|---|---|---|---|
|
да | иногда (но обычно “только чтение”) | да | нет | нет | поток данных, чтение “по мере поступления” |
|
да | обычно да | да | нет | нет | многопроходный “вперёд-вперёд” |
|
да | да | да | да | нет | можно шагнуть назад |
|
да | да | да | да | да | почти как массив по возможностям |
Смысл этой таблички не в том, чтобы выучить её наизусть, а в том, чтобы перестать писать код из серии «ну на vector же работало». В STL очень ценится мышление гарантиями: что обещает итератор, а не “что получилось в одном контейнере”.
2. Категории итераторов на практике
input
: чтение по мере движения и однопроходность
inputInput-итераторы обычно встречаются там, где данные не лежат у вас в контейнере целиком, а приходят последовательно: как вода из крана. Вы можете подставить стакан (прочитать текущее значение), потом повернуть кран на следующий шаг (сделать ++it) — но “вернуться к прошлой капле воды” уже нельзя. Поэтому input-итераторы часто однопроходные: вы не можете надёжно сделать второй проход по тем же данным.
Самый классический пример — std::istream_iterator<T>, который читает значения из потока. Он хорош тем, что делает “поток” похожим на контейнер, но при этом остаётся потоком: прочитал — и всё, назад уже не откатишь.
#include <iostream>
#include <iterator>
#include <sstream>
int main() {
std::istringstream in("10 20 30");
std::istream_iterator<int> it(in);
std::istream_iterator<int> end;
std::cout << *it << '\n'; // 10
++it;
std::cout << *it << '\n'; // 20
}
Обратите внимание на психологический момент: istream_iterator выглядит как обычный итератор, но его природа ближе к “сканеру”. Вы не говорите: «дай мне элемент №5» — вы говорите: «дай следующий».
Если вы попытаетесь мыслить input-итераторами как random-access (“а давай-ка я прыгну на 100 вперёд”), компилятор довольно честно скажет: “не обещали”.
forward
: только вперёд, но можно несколько проходов
forwardForward-итераторы похожи на input тем, что они двигаются только вперёд (++it), но отличаются важной практической деталью: их обычно можно копировать и переиспользовать для повторного обхода. То есть это уже не “поток, который сгорает”, а “нормальная последовательность”, просто без шага назад.
В реальных контейнерах forward-итераторы часто встречаются там, где структура данных не позволяет дёшево ходить назад. Концептуально это как лист бумаги с задачами, приклеенный к стене: сверху вниз читать можно, назад глазами вернуться можно, но “операция --it” вам никто не гарантировал на уровне интерфейса.
Небольшая “проверка реальности”: даже если вы лично психологически “можете вернуться”, интерфейс итератора может этого не позволять. И это нормально: STL строится на минимальных гарантиях.
В этой лекции мы не будем привязывать forward-итераторы к конкретному новому контейнеру (чтобы не уехать в тему следующего дня), поэтому зафиксируем главное: forward = multi-pass + только ++. Это категория “честный шагомер”: вперёд шагать умеет, назад — нет, но маршрут не исчезает после первого прохождения.
bidirectional
: шаг назад --it
bidirectionalBidirectional-итераторы — это следующий уровень комфорта: к ++it добавляется --it. В голове это обычно “итератор, который умеет назад”, но за этим стоит практический смысл: некоторые алгоритмы требуют уметь двигаться с двух сторон, например “идём с начала и с конца навстречу”.
Очень типичный представитель bidirectional-итераторов — итератор std::map и std::set. Это логично: дерево (на котором обычно устроен map) позволяет переходить к следующему и предыдущему элементу по порядку, но “прыгнуть на +100” всё равно нельзя: дерево не массив.
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<int, std::string> users{{1, "Ann"}, {3, "Bob"}, {5, "Cat"}};
auto it = users.end();
--it; // шаг назад: теперь это последний элемент
std::cout << it->first << " " << it->second << '\n'; // 5 Cat
}
Заметьте, как здесь видно отличие философии: у vector “последний элемент” часто берут через индексы или back(), а у map мы естественно двигаемся итератором, потому что это “контейнер, который про обход”, а не “контейнер, который про индексы”.
И ещё один важный нюанс: --users.end() корректно, потому что end() — позиция “после последнего”, а шаг назад ведёт на последний элемент. Но если вы попробуете --users.begin(), это уже будет выход за границы диапазона (и так делать нельзя).
random-access
: прыжки, индексация и разность
random-accessRandom-access — это “премиум-подписка” итераторов. Здесь появляется всё, что напоминает массив: можно быстро прыгнуть на n вперёд (it + n), можно взять it[n], можно сравнивать “кто раньше в порядке” и даже вычислять расстояние как разность итераторов.
Классические random-access итераторы вы видели постоянно, даже если не называли их так: std::vector<T>::iterator и итераторы строки std::string.
#include <iostream>
#include <vector>
int main() {
std::vector<int> scores{10, 20, 30, 40};
auto it = scores.begin();
std::cout << it[2] << '\n'; // 30
std::cout << *(it + 3) << '\n'; // 40
}
Почему это важно именно для STL? Потому что некоторые алгоритмы, например сортировка std::sort, исторически требуют random-access итераторы (в классической версии STL). То есть если у контейнера итератор не random-access, сортировать его std::sort “в лоб” вы не сможете: не из вредности, а потому что алгоритму нужно уметь быстро адресоваться.
Категория в этом месте — не “ярлычок”, а честное ограничение на допустимые операции и на применимость алгоритмов.
5. Сдвиги и требования алгоритмов
Пример: почему it + n не работает для map
Очень типичный сценарий: вы сделали красивый код на vector, потом решили заменить контейнер на map (потому что “там же ключи”) — и внезапно половина операций перестала существовать. Это не потому что map “плохой”, а потому что у него другая категория итераторов.
Вот пример, который работает для vector, но не обязан работать для map. Я специально оставлю “плохую строку” закомментированной, чтобы код компилировался:
#include <map>
#include <string>
int main() {
std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.begin();
// it = it + 1; // нельзя: итератор map не random-access
(void)it;
}
И вот тут появляется взрослая привычка: если вам надо “сдвинуться на n”, не пишите it + n, пока не уверены в категории. Используйте универсальный инструмент, который работает для разных категорий: std::advance.
std::advance(it, n) и стоимость операции
std::advance выглядит как “просто удобная функция”, но на самом деле она выражает правильную мысль: я хочу сдвинуть итератор на n, но я не хочу предполагать, что этот итератор — random-access. Тогда компилятор и стандартная библиотека сами выберут корректный способ.
На random-access итераторе это обычно будет быстрый прыжок. На более слабых категориях это превратится в n шагов ++it (и это нормально — просто нужно помнить о стоимости).
#include <iostream>
#include <iterator>
#include <map>
#include <string>
int main() {
std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.begin();
std::advance(it, 2);
std::cout << it->second << '\n'; // three
}
С точки зрения “мышления алгоритмами” это очень полезно: вы не привязываете код к одному контейнеру. С точки зрения производительности есть честная цена: если вы advance-ите на 1_000_000 по дереву, вы реально сделаете миллион шагов. Так что универсальность не отменяет здравого смысла, она просто не даёт вам писать некорректный код.
Схема выбора операций по категории
Чтобы не держать всё в голове как “магические правила”, можно мыслить так: вы сначала узнаёте, что у вас за контейнер/итератор по смыслу, потом выбираете допустимые операции. Ниже — схема-напоминалка.
flowchart TD
A["Есть контейнер и итераторы begin/end"] --> B["Какая категория итератора?"]
B --> C["input: читаю, ++"]
B --> D["forward: читаю/пишу, ++, можно несколько проходов"]
B --> E["bidirectional: ++ и --"]
B --> F["random-access: ++/--, it+n, it[n], it2-it1"]
F --> G["Можно использовать алгоритмы, требующие random-access, например sort"]
E --> H["Можно делать алгоритмы, которым нужен шаг назад, например reverse"]
C --> I["Похоже на поток: прочитал и ушёл дальше"]
Эта схема не заменяет практику, но помогает не делать самый частый вывод новичка: “если я однажды видел it[5], значит оно всегда существует”.
6. Типичные ошибки при работе с категориями итераторов
Ошибка №1: воспринимать любой итератор как vector::iterator и ожидать it + n везде.
Это самая распространённая ловушка: вы пишете код “как по массиву”, а потом переносите его на map/set и удивляетесь, что “операторы пропали”. Правильная модель — категория задаёт гарантии. Если нужен универсальный сдвиг, используйте std::advance, а если нужен быстрый доступ по индексу — честно выбирайте контейнер с random-access итераторами.
Ошибка №2: путать “универсально” и “быстро”.
После знакомства с std::advance легко подумать: “О! Значит можно везде спокойно прыгать на 10000 элементов”. Можно, но цена разная. На random-access это ближе к it += 10000, а на более слабых категориях это превращается в многократный ++it. В результате код остаётся корректным, но может стать неожиданно медленным.
Ошибка №3: пытаться делать несколько проходов по input-итератору, как будто это контейнер.
std::istream_iterator и похожие итераторы часто читают данные из потока: это «одноразовый» источник. Если вы “прошли вперёд”, вы уже изменили состояние потока. Поэтому второй проход по тем же данным может быть невозможен или даст пустоту. Если нужен повторный обход, сначала материализуйте данные в контейнер (например, в std::vector), а потом ходите по нему сколько угодно.
Ошибка №4: разыменовывать end() или делать шаги за границы.
end() — это не “последний элемент”, а “позиция после последнего”. Её нельзя разыменовывать. Аналогично, --begin() и ++(--end()) в неверных местах легко превращаются в выход за границы. Это не та ошибка, которая “всегда падает сразу”: иногда она проявляется странными симптомами, и вы потом долго думаете, почему программа печатает “память динозавров”.
Ошибка №5: пытаться использовать алгоритм с итераторами неподходящей категории и воспринимать это как “глюк STL”.
Если std::sort не компилируется с вашими итераторами, это не каприз: у алгоритма есть требования к возможностям итератора. В такой ситуации полезнее не “бороться с компилятором”, а задать себе вопрос: “мой контейнер вообще про случайный доступ или про упорядоченное хранение/поиск?” — и уже от этого выбирать либо другой контейнер, либо другой подход.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ