4.4 Итераторы и диапазоны¶

Многие функции стандартной библиотеки C++ работают не «с контейнером целиком», а с итераторами.

Итератор — это переменная, которая «указывает» на элемент структуры данных (похоже на указатель, но абстрактнее).

Диапазон begin–end¶

Почти у каждого контейнера есть два часто используемых итератора:

• begin() — указывает на первый элемент;
• end() — указывает на позицию сразу после последнего элемента.

Например, для множества s = { 3, 4, 6, 8, 12, 13, 14, 17 }:

{ 3, 4, 6, 8, 12, 13, 14, 17 }
  ↑                      ↑
 s.begin()             s.end()

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

flowchart LR
    A[begin] --> B[10]
    B --> C[20]
    C --> D[30]
    D --> E[40]
    E --> F[end]

    G["Диапазон [begin, end)"] --> H["включает 10, 20, 30, 40"]
    G --> I["не включает end"]

Такой стиль очень удобен:

• длина диапазона равна end - begin (для случайного доступа, например, у vector);
• пустой диапазон — это когда begin() == end();
• можно безопасно писать циклы «пока не дошли до end».

Работа с диапазонами¶

Многие алгоритмы STL принимают диапазон в виде пары итераторов.

Пример: сортировка, разворот, перемешивание¶

Допустим, у нас есть вектор:

vector<int> v = {7, 1, 4, 4, 9, 2};

sort(v.begin(), v.end());       // сортируем по возрастанию
reverse(v.begin(), v.end());    // разворачиваем

В старых примерах часто встречается random_shuffle(...), но в современном C++ предпочтительнее shuffle(...) с генератором:

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(v.begin(), v.end(), rng);

То же самое можно делать и с обычным массивом, но там вместо итераторов используются указатели:

int a[] = {7, 1, 4, 4, 9, 2};
int n = 6;

sort(a, a+n);
reverse(a, a+n);

Идея одна и та же: передаём начало и конец диапазона.

Итераторы в set¶

Итераторы особенно полезны для структур вроде set, где нельзя обратиться к элементу по индексу s[i].

Получить итератор на первый элемент¶

set<int> s = {2, 5, 6, 8};

set<int>::iterator it = s.begin();
// или короче:
auto it2 = s.begin();

Доступ к элементу (разыменование)¶

Значение, на которое указывает итератор, получают оператором *:

auto it = s.begin();
cout << *it << "\n"; // выведет 2

Перемещение итератора¶

• ++it — перейти к следующему элементу (вперёд);
• --it — перейти к предыдущему элементу (назад).

Напечатать все элементы по возрастанию:

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

Получить максимальный элемент (аккуратно: end() нельзя разыменовывать):

auto it = s.end();
--it;                 // теперь это последний элемент
cout << *it << "\n";

Поиск в set: find, lower_bound, upper_bound¶

find(x)¶

find(x) возвращает итератор на элемент x, если он есть, иначе возвращает end():

auto it = s.find(x);
if (it == s.end()) {
    // x нет в множестве
}

lower_bound(x)¶

lower_bound(x) — итератор на первый элемент ≥ x.

upper_bound(x)¶

upper_bound(x) — итератор на первый элемент > x.

Если подходящего элемента нет, обе функции возвращают end().

Важно: у unordered_set этих функций нет, потому что оно не поддерживает порядок элементов.

Пример: найти ближайший элемент к x¶

Пусть есть непустое множество s и число x. Хотим вывести элемент из s, который ближе всего к x (по модулю разницы).

Идея:

1. Берём it = s.lower_bound(x) — это кандидат справа (первый ≥ x).
2. Кандидат слева — это элемент перед it (если он существует).
3. Сравниваем, кто ближе.

Пример кода:

set<int> s = {1, 4, 6, 10, 13};
int x = 7;

auto it = s.lower_bound(x);

if (it == s.begin()) {
    // все элементы >= x, ближайший — первый
    cout << *it << "\n";
} else if (it == s.end()) {
    // все элементы < x, ближайший — последний
    auto last = prev(s.end());
    cout << *last << "\n";
} else {
    // есть кандидат справа (*it) и слева (prev(it))
    int right = *it;
    int left = *prev(it);

    if (x - left <= right - x) cout << left << "\n";
    else cout << right << "\n";
}

Например, при x = 7 ближайший будет 6 (разница 1), а не 10 (разница 3).

Короткий чек-лист¶

• Диапазон почти всегда пишется как [begin(), end()).
• end() нельзя разыменовывать.
• Для set/map итераторы — основной способ «гулять» по элементам.
• lower_bound/upper_bound — мощные операции для поиска «границы».