STL-контейнеры

Контейнеры стандартной библиотеки — это готовые, отлаженные и оптимизированные структуры данных, на которых держится почти весь прикладной код на C++. Понимать их асимптотику, гарантии по памяти и правила инвалидации итераторов важнее, чем уметь писать собственный связный список. Выбор между std::vector и std::map часто определяет производительность программы сильнее, чем любые микрооптимизации, поэтому этот раздел — обязательный фундамент для любого C++-разработчика.

Как это работает

Контейнеры делятся на три семейства. Последовательные — std::vector, std::deque, std::list, std::forward_list, std::array — хранят элементы в заданном порядке. Ассоциативные упорядоченные — std::map, std::set и их multi-варианты — реализованы как красно-чёрные деревья с логарифмическим поиском. Неупорядоченные — std::unordered_map, std::unordered_set — это хеш-таблицы с амортизированным константным доступом. Поверх них построены адаптеры std::stack, std::queue и std::priority_queue.

std::vector хранит элементы в одном непрерывном блоке памяти. При исчерпании ёмкости он выделяет новый блок в полтора-два раза больше и перемещает элементы, поэтому push_back работает за амортизированную константу, а reserve позволяет заранее избежать перевыделений. std::deque держит массив блоков и даёт быструю вставку с обоих концов. std::list платит за каждый элемент отдельной аллокацией и двумя указателями, зато не инвалидирует итераторы при вставке.

Все контейнеры принимают аллокатор как параметр шаблона, поддерживают единый интерфейс begin()/end(), size(), empty() и работают с алгоритмами через итераторы. Начиная с C++17 доступны try_emplace, insert_or_assign и извлечение узлов через extract, а C++20 добавил contains и erase_if.

Когда применять

По умолчанию берите std::vector: непрерывная память дружелюбна к кешу процессора, и на практике он обгоняет std::list даже на вставках в середину для небольших объёмов. std::deque нужен для очередей с двусторонним доступом. std::map выбирайте, когда важен отсортированный обход или диапазонные запросы; std::unordered_map — когда нужен только поиск по ключу и допустим неупорядоченный обход. std::array заменяет C-массивы фиксированного размера без накладных расходов. std::list оправдан редко: когда требуется стабильность адресов элементов и частые сращивания через splice.

Типичные ошибки

Главная ловушка — инвалидация итераторов и ссылок: после push_back в std::vector все ранее полученные указатели могут стать висячими, а удаление элемента в цикле через устаревший итератор приводит к неопределённому поведению. Используйте идиому erase-remove или std::erase_if. Вторая ошибка — operator[] у std::map, который молча создаёт элемент по отсутствующему ключу; для чтения используйте find или at. Третья — std::vector<bool>, который не является настоящим контейнером bool и не даёт ссылок на элементы. Наконец, хеш-таблицы с плохой хеш-функцией деградируют до линейного поиска, а без reserve многократно перестраиваются.

Связанные понятия

• Стандартная библиотека
• Алгоритмы STL
• Итераторы
• Строки в STL
• Кеш-дружелюбный код