Обзор структур данных в C++

Здравствуйте! Предлагаю обзор основных контейнеров C++ STL с пояснением их внутренней структуры, сложности операций и типичных сценариев применения.

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

STL содержит набор контейнеров для разных задач: от упорядоченных последовательностей до ассоциативных и хеш-структур. Давайте кратко рассмотрим их классификацию и особенности.

Классификация контейнеров STL

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

std::vector

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

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

В основе — три указателя: begin, end заполненной части и end выделенного буфера. При исчерпании ёмкости происходит реаллокация с расширением в ≈1.5–2× и перемещением элементов.

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

std::deque

Двусторонняя очередь, устроенная как массив мелких блоков под управлением таблицы указателей. Обеспечивает O(1) вставки/удаления на обоих концах.

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

• Блоки могут храниться негомогенно, ниже кэш-локальность, чем у vector.
• Итераторы в большинстве случаев остаются валидными.
• Используется внутри queue и stack по умолчанию.

std::list

Двусвязный список, где каждый узел хранит ссылки на соседей. Поддерживает O(1) вставку и удаление по итератору.

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

• Итераторы стабильны, кроме удаляемого элемента.
• Нет доступа по индексу, значительные накладные расходы памяти.
• Применяется при частых изменениях в середине и в алгоритмах LRU-кэша.

std::forward_list

Односвязный список с минимальным оверхедом: каждый элемент хранит указатель только на следующий узел.

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

• Подходит для однопроходных алгоритмов и встраиваемых систем.
• Не поддерживает двунаправленный обход и размер за O(1).

std::array

Статический массив фиксированного размера, обёртка над C-массивом с интерфейсом STL.

std::array a = {1, 2, 3};
a[1] = 42;

• Совместим с алгоритмами STL, at() проверяет границы.
• Отличная кэш-локальность без динамики.

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

Базируются на сбалансированных деревьях (обычно красно-чёрных), гарантируют отсортированный порядок и O(log n) для основных операций.

std::set / std::multiset

std::set хранит уникальные ключи, std::multiset допускает дубликаты.

std::set s = {3, 1, 2};
s.insert(4);
// s.insert(2) не добавит дубликат

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

• Итераторы стабильны при вставках.
• Используется для рейтингов, топ-N, поиска по диапазону.

std::map / std::multimap

std::map — ассоциативный массив ключ→значение с уникальными ключами, std::multimap — допускает множественные значения на один ключ.

std::map m = {{"Alice",25}, {"Bob",30}};
m["Charlie"] = 28;

std::multimap mm;
mm.insert({"Alice",90});
mm.insert({"Alice",95});
auto range = mm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it)
    std::cout << it->first << ": " << it->second << "\n";

• operator[] создаёт элемент по ключу, если не существует.
• Можно задавать свой компаратор.
• Подходит для словарей, конфигураций, иерархических данных.

Хеш-контейнеры

Реализованы через хеш-таблицы, средняя сложность операций O(1), в худшем при коллизиях O(n).

std::unordered_set / std::unordered_multiset

unordered_set хранит уникальные элементы, unordered_multiset — допускает дубликаты.

std::unordered_set us = {"Alice","Bob"};
us.insert("Charlie");
if (us.contains("Bob")) std::cout<<"Bob есть\n";

std::unordered_multiset ums;
ums.insert(10); ums.insert(10);
std::cout<<"Число 10: "<

std::unordered_map um = {{"Alice",25},{"Bob",30}};
um["Charlie"] = 28;
for (auto& [k,v]:um) std::cout<

std::stack st;
st.push(10); st.push(20);
std::cout<

std::queue q;
q.push(10); q.push(20);
std::cout<

std::priority_queue pq;
pq.push(5); pq.push(10);
std::cout<, std::greater> minq;
minq.push(50); minq.push(10);
while(!minq.empty()){
  std::cout<