ИтераторыIterators

Каждая следующая категория — надмножество возможностей предыдущей. Категория итератора контейнера определяется его внутренней структурой, а не желанием автора STL.Each successive category is a superset of the previous one's capabilities. A container's iterator category is determined by its internal structure, not by the STL author's preference.

std::list — двусвязный список, поэтому переход к произвольному элементу требует прохода по ссылкам за O(n); отсюда Bidirectional, а не Random Access, несмотря на то что "назад-вперёд" список умеет. std::vector хранит элементы непрерывно, поэтому it + 5 — это просто ptr + 5 * sizeof(T), одна арифметическая операция.std::list is a doubly-linked list, so reaching an arbitrary element requires walking links in O(n); hence Bidirectional, not Random Access, despite being able to go both ways. std::vector stores elements contiguously, so it + 5 is just ptr + 5 * sizeof(T) — one arithmetic op.

Инвалидация — не произвольное правило стандарта, а прямое следствие того, что физически происходит с памятью контейнера при модификации.Invalidation isn't an arbitrary standard rule — it's a direct consequence of what physically happens to the container's memory on modification.

std::vector<int> v{1, 2, 3};
auto it = v.begin();
v.push_back(4);    // если capacity исчерпана — реаллокация,// if capacity is exhausted — reallocation,
                     // it указывает на старый (уже освобождённый) буфер: UB// it points into the old (now freed) buffer: UB

std::list<int> l{1, 2, 3};
auto it = l.begin();
l.push_back(4);    // узлы не двигаются в памяти — it остаётся валиден// nodes never move in memory — it stays valid

std::vector: вставка инвалидирует ВСЕ итераторы/указатели/ссылки, если происходит реаллокация (превышена capacity); если реаллокации не было — инвалидирует только итераторы на элементы после точки вставки (сдвиг в памяти). Удаление всегда инвалидирует итератор на удалённый элемент и на всё, что после него (сдвиг влево).std::vector: insertion invalidates ALL iterators/pointers/references if a reallocation happens (capacity exceeded); if no reallocation occurred, it invalidates only iterators to elements after the insertion point (they shifted in memory). Erasure always invalidates the iterator to the erased element and everything after it (shifted left).

std::list: узлы — отдельные аллокации, связанные указателями; вставка/удаление никогда не двигает существующие узлы в памяти. Итератор инвалидируется, только если указывает непосредственно на удалённый узел — все остальные остаются валидны при любых вставках/удалениях в любом месте списка.std::list: nodes are separate allocations linked by pointers; insertion/erasure never moves existing nodes in memory. An iterator is only invalidated if it points directly at the erased node — everything else stays valid across any insert/erase anywhere in the list.

std::unordered_map: вставка может вызвать rehash (если load_factor превышает max_load_factor), который переставляет элементы по новым бакетам — это инвалидирует ВСЕ итераторы, но НЕ указатели/ссылки на сами элементы (узлы, а не сам элемент, переставляются между бакетами). Удаление инвалидирует только итератор на удалённый элемент.std::unordered_map: insertion may trigger a rehash (if load_factor exceeds max_load_factor), which redistributes elements across new buckets — this invalidates ALL iterators, but NOT pointers/references to the elements themselves (nodes, not the element, move between buckets). Erasure invalidates only the iterator to the erased element.

Свой итератор для связного списка требует определить типовые алиасы (или унаследоваться от std::iterator, устаревший подход после C++17) и перегрузить operator*, operator++, operator==/operator!=.A custom iterator for a linked list requires defining the type aliases (or inheriting from std::iterator, deprecated since C++17) and overloading operator*, operator++, operator==/operator!=.

template<typename T>
class ForwardListIterator {
    struct Node { T value; Node* next = nullptr; };
    Node* node;
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer          = T*;
    using reference        = T&;

    explicit ForwardListIterator(Node* n) : node(n) {}

    T& operator*()  const { return node->value; }
    T*  operator->() const { return &node->value; }

    ForwardListIterator& operator++() {              // префиксный// prefix
        node = node->next;
        return *this;
    }
    ForwardListIterator operator++(int) {           // постфиксный// postfix
        ForwardListIterator tmp = *this;
        node = node->next;
        return tmp;
    }

    bool operator==(const ForwardListIterator& other) const { return node == other.node; }
    bool operator!=(const ForwardListIterator& other) const { return node != other.node; }
};

Наличие обоих operator++ (префиксного и постфиксного, различаемых фиктивным параметром int) — минимальное требование для Forward-категории; Bidirectional добавил бы operator--, а Random Access — арифметику (operator+, operator-, operator[], операторы сравнения </>).Having both operator++ forms (prefix and postfix, distinguished by the dummy int parameter) is the minimum requirement for the Forward category; Bidirectional would add operator--, and Random Access would add arithmetic (operator+, operator-, operator[], relational operators </>).

• cppreference — Iterator library
• cppreference — Iterator invalidation