Когда стоит использовать каждый контейнер из STL?

# Выбор контейнеров STL

Правильный выбор контейнера критичен для производительности. Вот детальный путеводитель с примерами.

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

std::vector

Используй: В 90% случаев это твой выбор по умолчанию.

// Отлично для:
// - Случайный доступ O(1)
// - Стабильная память (iterator invalidation predictable)
// - Удалению в конце (амортизированная O(1))

std::vector<int> v = {1, 2, 3};
v.push_back(4);           // O(1) амортизированная
int x = v[500];           // O(1)
v.erase(v.end() - 1);     // O(1)
v.erase(v.begin());       // O(n) - плохо!

Избегай: Удалений в начале/середине часто. Память: Динамический массив, capacity растёт 1.5x или 2x.

std::deque

Используй: Когда нужны операции O(1) в обоих концах.

// Отлично для:
// - push_back/pop_back O(1)
// - push_front/pop_front O(1) (vector не может!)
// - Случайный доступ O(1)

std::deque<Task> queue;
queue.push_back(task);      // O(1)
queue.push_front(urgent);   // O(1)
Task t = queue[0];          // O(1)
queue.pop_front();          // O(1)

Примеры: Очереди с приоритетом, sliding window algorithms. Память: Разбит на блоки (chunks), чуть сложнее кэш-локальности чем vector.

std::list

Используй: Редко. Только если нужны вставки/удаления O(1) в середине.

// Отлично для:
// - Вставка/удаление O(1) если есть iterator
std::list<Node> nodes;
auto it = nodes.begin();
nodes.erase(++it);          // O(1) если уже знаем позицию

// Плохо для случайного доступа:
// nodes[500];  // ОШИБКА - нет operator[]
for (auto& n : nodes) {}    // O(n) - плохо для кэша

Почему избегать: Плохая кэш-локальность, итераторы двусвязного списка — это 2 указателя в памяти. Современная альтернатива: Обычно можно пересмотреть алгоритм или использовать vector + lazy deletion.

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

std::map (Red-Black Tree)

Используй: Когда нужен порядок ключей.

// Отлично для:
// - Сортированный итератор O(n)
// - Все операции O(log n) гарантированно
// - Стабильные итераторы (не инвалидируются)

std::map<int, std::string> config;
config[10] = "value1";
config[5] = "value2";      // автоматически сортирует
for (auto& [key, val] : config) {  // всегда по ключам!
    // печать: 5, 10
}

Когда: Кэши с LRU eviction, конфиги, range queries. Худший случай: Идеален для балансирующего дерева.

std::unordered_map (Hash Table)

Используй: Когда нужен быстрый lookup и порядок неважен.

// Отлично для:
// - Средний случай O(1) lookup
// - Высокая производительность для простых типов

std::unordered_map<std::string, int> cache;
cache["key"] = 42;          // O(1) в среднем
if (cache.count("key")) {}  // O(1) в среднем

// Но худший случай O(n)!
// Плохой хэш функция → все коллизии → O(n) lookup

Важно: Custom hash функция для типов вроде pair<int,int>:

struct PairHash {
    size_t operator()(const std::pair<int,int>& p) const {
        return std::hash<long long>()(((long long)p.first << 32) | p.second);
    }
};
std::unordered_map<std::pair<int,int>, int, PairHash> m;

Худший случай: Doable but requires careful hash function design.

std::set

Используй: Когда нужна коллекция уникальных отсортированных элементов.

std::set<int> unique_ids;
unique_ids.insert(1);
unique_ids.insert(1);       // дублирование не добавится

// Отлично для:
for (int id : unique_ids) {}  // отсортированный обход O(n)

std::unordered_set

Используй: Быстрое членство без порядка.

std::unordered_set<std::string> visited;
if (visited.count(url)) {    // O(1) в среднем
    return;
}
visited.insert(url);

Адаптеры (построены на других контейнерах)

std::stack

Используй: LIFO структура.

std::stack<int> s;  // обычно на базе deque
s.push(1); s.push(2);
s.top();    // 2
s.pop();

std::queue

Используй: FIFO структура.

std::queue<Task> q;  // обычно на базе deque
q.push(task);
Task t = q.front();
q.pop();

std::priority_queue

Используй: Элементы с приоритетом.

std::priority_queue<int> pq;  // max heap по умолчанию
pq.push(5); pq.push(10);
pq.top();   // 10

// Min heap:
std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;

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

LRU Cache

std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;
std::list<int> lru;  // order of access
// insert/update O(1), evict O(1)

Event scheduling

std::priority_queue<Event, std::vector<Event>, std::greater<>> events;
// always process earliest event O(log n)

Session deduplication

std::unordered_set<std::string> active_sessions;
// O(1) check if session exists

Правило выбора

1. Нужен порядок? → std::map / std::set
2. Нужен быстрый lookup? → std::unordered_map / std::unordered_set
3. Нужен LIFO/FIFO? → std::stack / std::queue
4. Случайный доступ нужен? → std::vector / std::deque
5. Вставки/удаления в середине? → Перепроектируй алгоритм (обычно можно избежать)

Таблица сложности

*амортизированная или в среднем, †требует iterator