Контейнеры STL: глубокое погружение
Выберите правильную структуру данных — и программа станет быстрее и понятнее без лишних усилий
Главная идея: Стандартная библиотека шаблонов даёт готовые контейнеры —
vector, list, map, set и их хеш-родственники unordered_map / unordered_set. Все они хранят данные, но каждый идёт на свой компромисс между быстрым доступом, быстрым поиском, упорядоченностью и памятью. Умение выбирать правильно — один из главных навыков, отличающих новичка от программиста среднего уровня.
К концу урока вы сможете:
- описать, как
vector,list,map,set,unordered_mapиunordered_setхранят данные, - читать таблицу Big-O и выбирать контейнер под свой шаблон доступа,
- объяснить, когда важен порядок, а когда лучше подойдёт хеш-таблица,
- избегать классических ловушек производительности (вставки в середину, лишние копии, отсутствие
reserve).
1. Три семейства
Каждый стандартный контейнер относится к одному из трёх семейств. Зная семейство, вы уже понимаете почти всё ещё до того, как прочтёте название хотя бы одного метода.
- Последовательные контейнеры (
vector,list,deque) хранят элементы в том порядке, в каком вы их добавили. Важна позиция. - Упорядоченные ассоциативные контейнеры (
map,set) хранят элементы отсортированными по ключу и построены на сбалансированном двоичном дереве поиска. Важен отсортированный поиск. - Неупорядоченные ассоциативные контейнеры (
unordered_map,unordered_set) хранят элементы в хеш-таблице. Порядка нет вообще, но средний поиск — O(1). Важна чистая скорость.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
std::vector<int> v; // dynamic array, contiguous memory
std::list<int> l; // doubly linked list
std::map<std::string, int> m; // sorted key -> value (tree)
std::set<int> s; // sorted, unique keys (tree)
std::unordered_map<int, int> um; // hashed key -> value
std::unordered_set<int> us; // hashed, unique keys