Контейнеры STL изнутри

На собесе мало знать, что std::map «словарь». Спросят, как он устроен, сколько стоят операции и что происходит с итераторами при вставке. Пройдёмся по основным контейнерам.

vector

Непрерывный массив в куче: указатель на начало, конец данных и конец ёмкости. Доступ по индексу O(1), вставка в конец амортизированно O(1), в середину O(n).

Когда места нет, вектор выделяет новый буфер (libstdc++ и libc++ удваивают ёмкость, MSVC растит в 1,5 раза), переносит элементы и освобождает старый. Перенос идёт перемещением, только если перемещающий конструктор noexcept. После реаллокации все итераторы, указатели и ссылки на элементы недействительны.

• reserve(n) выделяет память без создания элементов, resize(n) создаёт или удаляет элементы.
• shrink_to_fit просит вернуть лишнюю ёмкость, но не обязан.
• erase из середины сдвигает хвост и инвалидирует итераторы начиная с позиции удаления.
• std::vector<bool> особый: хранит биты, operator[] возвращает прокси-объект, а не bool&.

array, deque, list

• std::array<T, N>: обёртка над C-массивом, размер известен при компиляции, данные лежат внутри объекта (на стеке, если объект локальный).
• std::deque: набор блоков фиксированного размера плюс массив указателей на блоки. push_front и push_back O(1), доступ по индексу O(1) (на одно разыменование больше, чем у vector). Вставка в концы инвалидирует итераторы, но не ссылки на элементы.
• std::list: двусвязный список. Вставка и удаление по итератору O(1), splice переносит узлы между списками без копирования. Итераторы на остальные элементы не инвалидируются. Цена: аллокация на каждый узел и плохая локальность, на практике vector часто быстрее даже там, где «по учебнику» нужен список.

Упорядоченные: map и set

std::map, std::set, multimap, multiset построены на сбалансированном двоичном дереве поиска, во всех основных реализациях это красно-чёрное дерево. Поиск, вставка, удаление O(log n), обход в порядке ключей, есть lower_bound и upper_bound. Вставка и удаление не инвалидируют итераторы на другие элементы. Каждый элемент это отдельный узел в куче.

Ловушки:

• m[key] вставляет элемент со значением по умолчанию, если ключа нет. Для чтения используйте find, contains (C++20) или at.
• insert не перезаписывает существующий ключ; для этого есть insert_or_assign, а try_emplace не создаёт значение, если ключ уже есть.
• multiset::erase(value) удаляет все вхождения; чтобы удалить одно, передайте итератор: s.erase(s.find(x)).

Неупорядоченные: unordered_map и unordered_set

Хеш-таблица: массив корзин, в libstdc++ элементы корзины связаны в список (отдельная цепочка). Средняя сложность O(1), худшая O(n), если всё попало в одну корзину. Когда коэффициент заполнения (size / bucket_count) превышает max_load_factor (по умолчанию 1), таблица перехеширует элементы в больший массив корзин: итераторы инвалидируются, а ссылки и указатели на элементы остаются валидными.

Для своего ключа нужны хеш-функция и operator==. Стандартного хеша для std::pair нет, его пишут сами. Если известен размер, reserve(n) убирает лишние перехеширования. На входных данных от пользователя предсказуемый хеш можно атаковать коллизиями.

Адаптеры

stack, queue, priority_queue это интерфейсы поверх других контейнеров (deque или vector). priority_queue двоичная куча: top O(1), push и pop O(log n), по умолчанию на вершине максимум; для минимума std::greater<>.

Итераторы

Категории: input, output, forward, bidirectional, random access, contiguous (C++20). От категории зависят доступные алгоритмы: std::sort требует random access, поэтому у list свой метод sort.

Что спросят на собесе

• Как растёт vector и что инвалидируется.
• map против unordered_map: устройство, сложность, когда что брать.
• Почему m[key] опасен в константном коде и при чтении.
• Чем deque отличается от vector и list.
• Как удалить элементы по условию (erase-remove или std::erase_if).