Какие знаешь контейнеры?

Контейнеры в C++ STL

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

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

std::vector — динамический массив с произвольным доступом:

std::vector<int> v = {1, 2, 3};
v.push_back(4);     // O(1) amortized
v[0] = 10;          // O(1) random access
v.erase(v.begin()); // O(n) - сдвиг элементов

std::deque — двусторонняя очередь с доступом O(1) с обоих концов:

std::deque<int> dq;
dq.push_front(1);  // O(1)
dq.push_back(2);   // O(1)
int x = dq[0];     // O(1) random access

std::list — двусвязный список без произвольного доступа:

std::list<int> l = {1, 2, 3};
l.insert(iterator, 5);  // O(1) если знаем позицию
l[0];  // ОШИБКА - нет operator[]
for (auto it = l.begin(); it != l.end(); ++it) {  // O(1) per step
    std::cout << *it;
}

std::forward_list — односвязный список (экономит память):

std::forward_list<int> fl;
fl.push_front(1);  // O(1)
// Итерирование только в одну сторону
// На 40% меньше памяти чем list

Ассоциативные контейнеры

std::set — отсортированное множество уникальных элементов:

std::set<int> s = {3, 1, 2};
s.insert(4);        // O(log n)
bool exists = s.count(3);  // O(log n)
// Автоматически отсортирован: {1, 2, 3, 4}

std::map — отсортированный словарь:

std::map<std::string, int> map = {{"a", 1}, {"b", 2}};
map["c"] = 3;       // O(log n)
int val = map.at("a");  // O(log n)
// Ключи всегда отсортированы

std::unordered_set — хэш-таблица для уникальных элементов:

std::unordered_set<int> us;
us.insert(100);      // O(1) average, O(n) worst
us.count(100);       // O(1) average
// Без гарантии порядка

std::unordered_map — хэш-таблица для пар ключ-значение:

std::unordered_map<int, std::string> um;
um[1] = "one";      // O(1) average
if (um.find(1) != um.end()) {  // безопаснее чем []
    std::cout << um[1];
}

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

std::stack — LIFO структура (Last In First Out):

std::stack<int> stack;
stack.push(1);
stack.push(2);
int top = stack.top();  // 2
stack.pop();

std::queue — FIFO структура (First In First Out):

std::queue<int> q;
q.push(1);
q.push(2);
int front = q.front();  // 1
q.pop();

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

std::priority_queue<int> pq;  // Max-heap
pq.push(3);
pq.push(1);
pq.push(2);
pq.top();  // 3
// Используется для Dijkstra, Prim, медиана потока

Выбор контейнера

Практические примеры

Очередь задач: std::queue Кэш LRU: std::unordered_map + std::list Приоритетные события: std::priority_queue Отсортированные уникальные ID: std::set Быстрый поиск по ID: std::unordered_map

Важные замечания

• vector — выбор по умолчанию (cache-friendly, компактная память)
• list — только если часто удаляешь/вставляешь в середину
• unordered_map — для O(1) поиска, set/map — если нужен порядок
• deque — идеален для очередей обработки
• C++17 добавил std::string_view — неовладающее представление строк

Знание особенностей контейнеров — это залог эффективного кода в production.