Что такое iterator и каковы различные категории итераторов?

Итераторы в C++: концепция и иерархия категорий

Итератор — объект, предоставляющий унифицированный интерфейс доступа к элементам контейнера или диапазона. Итераторы обобщают указатели: каждый сырой указатель является валидным итератором.

Иерархия категорий (C++17 и ранее)

Категории образуют иерархию от наименее мощных к наиболее мощным:

• Input Iterator — однопроходное чтение, движение только вперёд. Пример: std::istream_iterator.
• Output Iterator — однопроходная запись, движение только вперёд. Пример: std::ostream_iterator, std::back_insert_iterator.
• Forward Iterator — многопроходное чтение/запись, движение вперёд. Пример: std::forward_list::iterator.
• Bidirectional Iterator — дополнительно поддерживает --. Пример: std::list::iterator, std::map::iterator.
• Random Access Iterator — поддерживает +n, -n, [], сравнение <. Пример: std::vector::iterator, сырые указатели.
• Contiguous Iterator (C++17) — Random Access + гарантия смежного расположения в памяти. Пример: std::vector::iterator, std::array::iterator.

C++20: iterator concepts

В C++20 иерархия переработана через concepts. Стандарт добавил std::input_or_output_iterator, std::forward_iterator, std::bidirectional_iterator, std::random_access_iterator, std::contiguous_iterator. Это позволяет писать constraint-based алгоритмы:

#include <iterator>
#include <vector>
#include <list>
#include <forward_list>
#include <iostream>

// Функция, работающая только с random access итераторами
template<std::random_access_iterator It>
void jump_to_middle(It begin, It end) {
    auto mid = begin + (end - begin) / 2;
    std::cout << "middle value: " << *mid << "\n";
}

// Функция, работающая с любым input iterator
template<std::input_iterator It>
void print_all(It begin, It end) {
    for (auto it = begin; it != end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
}

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::list<int>   l = {10, 20, 30};
    std::forward_list<int> fl = {100, 200};

    jump_to_middle(v.begin(), v.end()); // OK — vector имеет random access
    // jump_to_middle(l.begin(), l.end()); // ОШИБКА компиляции — list bidirectional

    print_all(v.begin(), v.end());
    print_all(l.begin(), l.end());
    print_all(fl.begin(), fl.end());

    // Проверка категории через iterator_traits
    using VecIt = std::vector<int>::iterator;
    static_assert(std::random_access_iterator<VecIt>);
    static_assert(std::contiguous_iterator<VecIt>);

    using ListIt = std::list<int>::iterator;
    static_assert(std::bidirectional_iterator<ListIt>);
    static_assert(!std::random_access_iterator<ListIt>);
}

iterator_traits и tag dispatching (C++17-стиль)

До C++20 категорию итератора определяли через std::iterator_traits<It>::iterator_category:

#include <iterator>

template<typename It>
void advance_impl(It& it, int n, std::random_access_iterator_tag) {
    it += n; // O(1)
}

template<typename It>
void advance_impl(It& it, int n, std::bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++it;
    else        while (n++) --it; // O(n)
}

template<typename It>
void my_advance(It& it, int n) {
    advance_impl(it, n,
        typename std::iterator_traits<It>::iterator_category{});
}

Sentinel и ranges (C++20)

C++20 вводит понятие sentinel — объекта, обозначающего конец диапазона, который может иметь другой тип, чем итератор. Это позволяет, например, использовать нулевой терминатор строки без вычисления длины.

Подводные камни

• Инвалидация итераторов: push_back на vector инвалидирует все итераторы при reallocate — использование старого итератора UB.
• Input iterator — однопроходный: нельзя сохранить копию и пройти диапазон дважды через std::istream_iterator.
• Output iterator не поддерживает разыменование для чтения — *it возвращает прокси-объект, не значение.
• std::advance для non-random-access итератора работает за O(n) — не используйте в горячем цикле.
• std::distance тоже O(n) для bidirectional/forward — лучше хранить размер явно.
• Сравнение итераторов разных контейнеров — UB, даже если типы совпадают.
• В C++20 range-based алгоритмы принимают range, а не пару итераторов — старые алгоритмы из <algorithm> и новые из <algorithm> (ranges::) несовместимы напрямую.

• Объяснять iterator categories только по синтаксису, без жизненного цикла и стоимости.
• Игнорировать ошибки, null/empty состояния, порядок инициализации или режим сборки.
• Давать пример, который работает в демо, но ломается при изменении владельца ресурса.
• Показывать сырой указатель без объяснения владельца и момента освобождения.

• Кандидат формулирует точную модель для iterator categories, а не только определение.
• Пример компилируем, безопасен по lifetime и соответствует версии технологии.
• Названы trade-off, ограничения и диагностируемые симптомы ошибки.