Итераторы и сложность операций STL

Вопрос-крючок: «Почему вставка элемента в середину list — O(1), а в середину vector — O(n)? Ведь оба это просто "вставить один элемент"?»

#include <vector>
#include <list>
#include <iostream>
#include <chrono>

int main() {
    std::vector<int> v(100000, 1);
    std::list<int> l(100000, 1);

    auto vit = v.begin() + 50000;
    auto lit = l.begin();
    std::advance(lit, 50000);

    v.insert(vit, 99);   // вставка в середину vector
    l.insert(lit, 99);   // вставка в середину list

    std::cout << "done" << std::endl;
}

Вывод:

done

Код выполнится и там, и там — но если засечь время, вставка в vector окажется заметно медленнее на большом объёме данных. Дело не в самой операции insert, а в том, как устроена память под капотом у каждого контейнера — и здесь на сцену выходит понятие итератора и его категории.

Что происходит и почему. Итератор — это объект, который умеет «указывать» на элемент контейнера и перемещаться по контейнеру, не зная деталей его внутреннего устройства. Но возможности итераторов у разных контейнеров разные, и STL формально делит их на категории. Для нашего вопроса важны две: итератор произвольного доступа (random access iterator) — есть у vector, deque, array — и двунаправленный итератор (bidirectional iterator) — есть у list, map, set.

У vector элементы лежат в памяти строго подряд, как в обычном массиве. Итератор произвольного доступа может мгновенно «прыгнуть» на N позиций вперёд — это просто арифметика с адресом (ptr + N), O(1). Но именно эта непрерывность в памяти и есть причина, почему вставка в середину дорогая: чтобы освободить место для нового элемента на позиции 50000, нужно физически сдвинуть все элементы после неё на одну позицию вправо — это O(n) операций копирования.

У list — двусвязного списка — всё наоборот. Каждый элемент хранится в своей отдельной ячейке памяти («узле»), и эти узлы связаны указателями: у каждого узла есть указатель на следующий и на предыдущий элемент. Физически узлы могут быть раскиданы по памяти как угодно. Вставка нового узла — это просто «перевесить» пару указателей у соседних узлов, O(1), сдвигать ничего не нужно. Но расплата в другом: чтобы просто добраться до элемента номер 50000, list вынужден пройти по цепочке узлов один за другим — O(n). Итератор list не умеет прыгать сразу на 50000 позиций, только шаг за шагом.

Как это работает под капотом. В нашем примере оба insert формально «вставляют один элемент за раз», O(1) — но получить итератор на нужную позицию стоит по-разному: у vector быстрый доступ по индексу (O(1)) компенсируется дорогим сдвигом при вставке (O(n)); у list дешёвая вставка (O(1)) компенсируется дорогим доступом к нужной позиции (O(n)). Именно поэтому в реальном коде выбор контейнера — это всегда вопрос «что чаще происходит в вашей программе: доступ по индексу или вставки/удаления в середину».

Частые ошибки на собеседовании. Говорят «list всегда быстрее для вставки» — забывая, что сначала нужно ДОБРАТЬСЯ до места вставки, а это тоже стоит времени. Если вставка происходит в начало или конец, у обоих контейнеров есть быстрые операции (push_back у vector — амортизированно O(1), push_front/push_back у list — гарантированно O(1)) — вопрос именно про середину. Ещё одна ошибка — путать деструктивность операций: после vector::insert все итераторы после точки вставки становятся недействительными (сдвинулась память), а у list вставка не портит итераторы на другие элементы вообще — только сам новый узел появляется. И третья: забывают, что vector — самый кэш-дружелюбный контейнер (данные лежат подряд, процессор загружает их пачками), а list из-за раскиданности узлов по памяти на практике часто медленнее по «сырому» времени работы, даже когда алгоритмическая сложность на его стороне.

Итоги-шпаргалка. vector: O(1) доступ по индексу, O(n) вставка/удаление в середине, кэш-дружелюбный. list: O(n) доступ к произвольной позиции, O(1) вставка/удаление при уже имеющемся итераторе, не портит итераторы при вставке. Категория итератора (random access vs bidirectional) — это не абстракция ради абстракции, а прямое отражение того, как контейнер хранит данные в памяти.