Всем привет! Давно хотел собрать пост по структурам данным, которые есть в C++ и кратенько описать преимущество каждой из них.
В первой итерации статьи начнем с тех, что есть в стандартной библиотеке STL.

Начнем с того, что структура данных — это формальный способ организации и хранения информации в памяти компьютера, который определяет, как данные располагаются, как к ним обращаются и какие операции над ними выполняются наиболее эффективно.
Выбор структуры данных напрямую определяет производительность программы.
Если операция выполняется миллионы раз в секунду — даже незначительное отличие во времени вставки или доступа может стать решающим.

Стандартная библиотека C++ (STL) предоставляет широкий набор структур данных, каждая из них решает определённый класс задач: от линейного хранения элементов до ассоциативных структур с поиском по ключу.
В этой статье мы кратко рассмотрим основные контейнеры, их внутреннюю организацию и типичные сценарии применения.

1. Общая классификация контейнеров STL

Начнем с последовательных контейнеров:

1) std::vector - Динамический массив с непрерывным размещением элементов в памяти.

std::vector<int> v {1, 2, 3};
v.push_back(4);
v.emplace_back(5);

Внутреннее устройство:
Контейнер поддерживает три указателя:

• на начало массива,

• на конец заполненной части,

• и на конец выделенной памяти (capacity).

Когда текущая ёмкость (capacity) исчерпана, при следующем push_back происходит реаллокация — выделяется новый участок памяти, обычно увеличенный в 1.5–2 раза, и все элементы копируются или перемещаются в него и тут внимание на таблицу с асимптотикой:

Особенности:

• При реаллокации все итераторы, указатели и ссылки на элементы становятся недействительными.

• Гарантируется непрерывное размещение элементов (&v[0] — указатель на блок памяти).

• Отличная кэш-локальность: последовательный обход элементов максимально эффективен.

Лучше использовать когда нужен быстрый доступ по индексу и частые добавления в конец, а вставки в середину и удаление в начале редкие.

2) std::deque - Двусторонняя очередь(double-ended queue) реализована как массив блоков фиксированного размера, управляемый таблицей указателей. Это позволяет эффективно добавлять и удалять элементы с обоих концов, не перемещая весь контейнер.

std::deque<int> d {1, 2, 3};
d.push_front(0);
d.push_back(4);

Особенности:

• Элементы могут храниться в непоследовательных блоках памяти (в отличие от vector).

• Кэш-локальность ниже, чем у vector.

• Итераторы стабильнее: добавление элементов не инвалидирует существующие, кроме редких случаев при перераспределении блоков.

• Используется как базовый контейнер для std::queue и std::stack(о них ниже).

Используется когда важны операции добавления и удаления с обоих концов, а произвольный доступ в середину всё ещё нужен.

3) std::list - Двусвязный список реализована так, что каждый элемент хранит указатели на предыдущий и следующий узел. Элементы не лежат в непрерывной памяти, что делает вставки и удаления эффективными, но ухудшает кэш-локальность.

std::list<int> l {1, 2, 3};
auto it = l.begin();
std::advance(it, 1);
l.insert(it, 42);

Внутреннее устройство:

• Каждый узел содержит три поля: prev, next, value.

• Хранение разрознено в памяти: каждый элемент выделяется отдельно.

Особенности:

• Итераторы не инвалидируются при вставках/удалениях (кроме удалённого элемента).

• Нет доступа по индексу.

• Высокие накладные расходы по памяти (указатели на соседей).

• Плохая кэш-локальность: CPU часто промахивается по кэшу.

Используется когда когда важна стабильность итераторов и часто удаляются элементы в середине, также для реализации LRU-кэшей, очередей задач, логов с удалением из середины.

4) std::forward_list - односвязный список, реализован как двусвязный список, с итерацией только вперед.

std::forward_list<int> fl {1, 2, 3};
fl.push_front(0);

Внутреннее устройство:

• Каждый элемент хранит только указатель на следующий.

• Нет size() и двунаправленных итераторов.

• Добавление возможно только через push_front() или insert_after().

Особенности:

• Минимальные накладные расходы (1 указатель).

• Хорош для потоковых или однопроходных алгоритмов.

• Не поддерживает произвольный доступ. Сценарии, где важен малый объём памяти и предсказуемость (embedded, сетевые пайплайны), реализация простых цепочек, например, списков свободных блоков памяти.

5) std::array - статический массив, безопасная обёртка над обычным C-массивом с интерфейсом STL. Размер задаётся на этапе компиляции, динамических аллокаций нет.

std::array<int, 3> arr  {1, 2, 3};
arr[1] = 42;

Внутреннее устройство:

• Элементы располагаются в непрерывной области памяти (аналог T[N]).

• Размер — часть типа (std::array<int, 3> и std::array<int, 4> — разные типы).

• Не выделяет память динамически.

Особенности:

• Полностью совместим с алгоритмами STL.

• at() проверяет границы (выбрасывает std::out_of_range).

• Отличная кэш-локальность.

Банальная обертка над статическим массивом, применение как и у него.

Ассоциативные контейнеры (упорядоченные)

Ассоциативные контейнеры основаны на сбалансированных деревьях поиска (обычно красно-чёрных). Они обеспечивают упорядоченность элементов и логарифмическое время поиска.

1) std::set - множество уникальных элементов, отсортированных по ключу. Реализовано на сбалансированном красно-чёрном дереве. Обеспечивает логарифмический доступ (O(log n)). Подходит для хранения уникальных данных с упорядоченным обходом.

 std::set<int> s = {3, 1, 2};
    s.insert(4);              // добавляем элемент
    s.insert(2);              // дубликат игнорируется

std::multiset - вариант set, допускающий дубликаты ключей. Сохраняет отсортированный порядок и аналогичную асимптотику (O(log n)). Применяется при необходимости хранить повторяющиеся элементы с автоматической сортировкой.

std::multiset<int> ms = {1, 2, 2, 3};
    ms.insert(2);
    ms.erase(2); // удалит только один экземпляр

Внутреннее устройство:

• Каждый элемент — узел дерева, хранящий ключ и указатели на потомков.

• При вставке/удалении дерево автоматически ребалансируется.

• multiset допускает дубликаты элементов, set — нет.

Особенности:

• Элементы всегда отсортированы.

• Итераторы стабильны при вставке.

• Использует больше памяти (каждый элемент — отдельный узел).

Использовать если надо: Хранение уникальных значений с автоматической сортировкой или
реализация таблиц лидеров, рейтингов, топ-N списков, или алгоритмы, где важен поиск по диапазону (lower_bound, upper_bound).

2) std::map - ассоциативный массив «ключ → значение», реализованный через красно-чёрное дерево. Все ключи уникальны, элементы хранятся отсортированными. Доступ и вставка выполняются за O(log n).

 std::map<std::string, int> ages = {
        {"Alice", 25}, {"Bob", 30}
    };
    ages["Charlie"] = 28;

std::multimap - вариант map, допускающий несколько значений для одного ключа. Удобен при моделировании связей “один-ко-многим” (например, индексных таблиц или группировок).

// multimap: несколько значений для одного ключа
std::multimap<std::string, int> scores;
    scores.insert({"Alice", 90});
    scores.insert({"Alice", 95});
    scores.insert({"Bob", 88});

    auto range = scores.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it)
        std::cout << it->first << ": " << it->second << "\n";

Внутреннее устройство:

• То же сбалансированное дерево, что и в set.

• Каждый элемент — пара (ключ, значение).

• В map ключи уникальны, multimap допускает несколько элементов с одинаковыми ключами.

Особенности:

• operator[] создаёт новый элемент, если ключ не найден.

• Поддерживает пользовательский компаратор.

• Итераторы не инвалидируются при вставке.

Использовать если надо: Ассоциативные словари, индексы и конфигурационные таблицы, когда нужен отсортированный порядок ключей, гуд еще при работе с диапазонами или иерархическими данными (например, интервалы времени).

Неупорядоченные контейнеры (хеш-таблицы)

Неупорядоченные контейнеры (семейство unordered_) реализованы через хеш-таблицы, где доступ к элементу осуществляется по вычисленному хешу ключа.
Средняя сложность основных операций (insert, find, erase) — O(1), но в худшем случае (при коллизиях) может достигать O(n).*

1) std::unordered_set - множество уникальных элементов, реализованное через хеш-таблицу. Среднее время доступа — O(1), худшее — O(n) при коллизиях. Элементы не сортируются, порядок не определён.

std::unordered_set<std::string> users = {"Alice", "Bob"};
    users.insert("Charlie");

    if (users.contains("Bob"))
        std::cout << "Bob найден!\n";

    for (auto& u : users)
        std::cout << u << " ";

std::unordered_multiset - аналог unordered_set, но допускает дубликаты. Эффективен при частом поиске и подсчёте повторяющихся значений без необходимости сортировки.

std::unordered_multiset<int> nums;
    nums.insert(10);
    nums.insert(10);
    nums.insert(20);

    std::cout << "Количество 10: " << nums.count(10) << "\n";

Внутреннее устройство:

• Массив корзин (buckets), каждая содержит список элементов с одинаковым хешем.

• При увеличении числа элементов выполняется rehash() — перераспределение элементов между корзинами.

• Хеш-функция (std::hash) определяет, в какую корзину попадёт элемент.

Особенности:

• Элементы не сортируются.

• Итераторы инвалидируются при rehash().

• Качество хеш-функции влияет на производительность.

Быстрые проверки наличия элементов, реализация кэшей, множеств токенов, фильтров,используется вместо set, когда порядок не важен.

2) std::unordered_map - ассоциативный контейнер «ключ → значение», построенный на хеш-таблице. Обеспечивает средний доступ O(1). Порядок элементов не гарантируется. Используется для быстрых словарей и кэшей.

std::unordered_map<std::string, int> ages = {
        {"Alice", 25}, {"Bob", 30}
    };
    ages["Charlie"] = 28;

    for (auto& [name, age] : ages)
        std::cout << name << ": " << age << "\n";

std::unordered_multimap - аналог unordered_map, допускающий несколько значений на один ключ. Применяется для реализации индексных структур и групп данных.

std::unordered_multimap<std::string, int> scores;
    scores.insert({"Alice", 90});
    scores.insert({"Alice", 95});
    scores.insert({"Bob", 88});

    auto range = scores.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it)
        std::cout << it->first << ": " << it->second << "\n";

Внутреннее устройство:

• Таблица корзин, каждая хранит список пар (ключ, значение).

• При росте размера выполняется rehash() для перераспределения элементов.

• Хеш-функция и оператор == используются для сравнения ключей.

Особенности:

• Порядок элементов не определён.

• При rehash() итераторы становятся недействительными.

• Поддерживает собственные хешеры и компараторы.

Реализация словарей, кэшей и таблиц сопоставлений, структуры данных для парсинга, анализа логов, игровых сцен, лучше используется в системах, где важна скорость доступа по ключу.

Адаптеры контейнеров STL

Адаптеры контейнеров — это обёртки над другими контейнерами (vector, deque, list), которые ограничивают интерфейс и предоставляют специализированное поведение. Они не хранят данные напрямую, а используют внутренний контейнер, скрывая лишние операции.
Типы адаптеров:

• std::stack — стек (LIFO)

• std::queue — очередь (FIFO)

• std::priority_queue — очередь с приоритетами (heap)

1) std::stack - реализует стек (LIFO — Last In, First Out): последний добавленный элемент извлекается первым. По умолчанию использует std::deque, но можно указать и другой контейнер (например, std::vector или std::list).

std::stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);

    std::cout << "Top: " << st.top() << "\n"; // 30
    st.pop();
    std::cout << "Now top: " << st.top() << "\n"; // 20

Пример со std::vector как базовым контейнером

std::stack<int, std::vector<int>> st;
    for (int i = 1; i <= 5; ++i)
        st.push(i * 10);

    while (!st.empty()) {
        std::cout << st.top() << " ";
        st.pop();
    }
    // Вывод: 50 40 30 20 10

Внутреннее устройство:

• По умолчанию хранит элементы в std::deque.

• Интерфейс ограничен методами: push(), pop(), top(), empty(), size().

• Нет доступа к элементам, кроме верхнего (top()).

Особенности:

• Не предоставляет итераторов.

• Можно выбрать базовый контейнер при создании.

• Никакой сортировки или поиска по значению.

Используется для: алгоритмы обхода графов (DFS), парсеры выражений и анализаторы синтаксиса, реализация undo/redo стеков и вызовов функций.

2) std::queue - классическая очередь FIFO (First In, First Out). Первый вставленный элемент извлекается первым. По умолчанию использует std::deque как базовый контейнер.

std::queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "Front: " << q.front() << "\n"; // 10
    q.pop();
    std::cout << "Now front: " << q.front() << "\n"; // 20

Очередь строк

std::queue<std::string> q;
    q.push("task_1");
    q.push("task_2");
    q.push("task_3");

    while (!q.empty()) {
        std::cout << "Processing: " << q.front() << "\n";
        q.pop();
    }

Внутреннее устройство:

• Использует std::deque по умолчанию.

• Методы интерфейса: push(), pop(), front(), back(), empty(), size().

• Не поддерживает произвольный доступ и итераторы.

Особенности:

• Принцип работы — FIFO.

• Можно задать базовый контейнер (например, list).

• Безопасен для использования в потоках при внешней синхронизации.

Используется для реализации: Планировщики задач и событий, очереди запросов в многопоточном окружении, буферизация сетевых сообщений и потоков данных.

3) std::priority_queue - очередь с приоритетом, использующая vector и кучу (heap). Элемент с наивысшим приоритетом всегда доступен через top(). Вставка и удаление — O(log n). Применяется в алгоритмах поиска пути и планировании задач.
По умолчанию реализует макс-кучу (max-heap) на базе std::vector. Для обратного порядка можно использовать std::greater.

 std::priority_queue<int> pq;
    pq.push(5);
    pq.push(10);
    pq.push(3);

    std::cout << "Top: " << pq.top() << "\n"; // 10
    pq.pop();
    std::cout << "Now top: " << pq.top() << "\n"; // 5

Очередь с минимальным приоритетом (min-heap)

std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(50);
    min_pq.push(10);
    min_pq.push(30);

    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    // Вывод: 10 30 50

Внутреннее устройство:

• Хранит элементы в std::vector.

• Использует алгоритмы std::make_heap, push_heap, pop_heap.

• Гарантирует, что элемент с наибольшим приоритетом всегда первый.

Особенности:

• Не предоставляет итераторов и прямого доступа к элементам.

• Можно задать произвольный компаратор (std::greater, пользовательский).

• Поддерживает частично отсортированные наборы.

Используется для: алгоритмы поиска кратчайшего пути (Дейкстра, A*), планировщики задач и таймеров, очереди обработки событий по приоритету.

Сводная таблица контейнеров STL

В статье я постарался охватить все контейнеры стандартной библиотеки C++.
Ниже представлю краткое сравнение их характеристик, асимптотики и областей применения.

Последовательные контейнеры

Ассоциативные контейнеры (упорядоченные)

Неупорядоченные контейнеры (на хеш-таблицах)

Адаптеры контейнеров

Итог

Надеюсь, тем, кто раньше не особо разбирался в STL, стало понятнее, какие контейнеры бывают, чем они отличаются и где их лучше использовать.

Я не ставил цель подробно описать весь функционал каждого контейнера — это заняло бы не одну статью. Хотел лишь кратко ввести в курс дела и показать, как устроены основные структуры данных, чтобы при работе с кодом было проще понимать, что происходит “под капотом”. Главное — понимать, как они работают внутри, и тогда выбор подходящего варианта станет очевиден.

Если после прочтения стало хоть немного понятнее, когда стоит брать vector, а когда лучше подойдёт map — значит, цель достигнута

Выбор контейнера, в зависимости от поставленной задачи