Что такое STL? Назовите ключевые контейнеры и их характеристики производительности.

Что такое STL

STL (Standard Template Library) — часть стандартной библиотеки C++, содержащая обобщённые контейнеры, алгоритмы и итераторы. Все алгоритмы работают через итераторы и не зависят от конкретного контейнера.

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

• std::vector<T> — динамический массив. Random access O(1). push_back амортизированно O(1). Вставка/удаление в середину O(n). Лучшая кэш-локальность.
• std::deque<T> — двусторонняя очередь. push_front/push_back O(1). Random access O(1), но хуже кэш-локальность (блоки памяти).
• std::list<T> — двусвязный список. Вставка/удаление O(1) при наличии итератора. Нет random access. Плохая кэш-локальность — в реальных задачах часто медленнее vector даже для вставки.
• std::array<T, N> — массив фиксированного размера на стеке. Zero overhead, random access O(1).

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

• std::map<K, V> — красно-чёрное дерево, ключи отсортированы. Insert/find/erase O(log n). Требует operator<.
• std::set<K> — то же, без значений. O(log n) операции.
• std::multimap / std::multiset — допускают дубликаты ключей.

Хеш-контейнеры (C++11)

• std::unordered_map<K, V> — хеш-таблица. Амортизированно O(1) insert/find/erase. Worst case O(n) при коллизиях. Требует std::hash<K>.
• std::unordered_set<K> — то же, без значений.

Адаптеры

• std::stack — обёртка над deque (или vector). LIFO.
• std::queue — обёртка над deque. FIFO.
• std::priority_queue — бинарная куча (max-heap по умолчанию). push O(log n), top/pop O(log n).

#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>

int main() {
    // vector — рабочая лошадь
    std::vector<int> v = {5, 3, 1, 4, 2};
    std::sort(v.begin(), v.end());  // O(n log n)
    v.push_back(6);                 // амортизированно O(1)
    v.insert(v.begin() + 2, 99);   // O(n) — сдвигает элементы

    // reserve — избегаем реаллокаций
    std::vector<int> big;
    big.reserve(1'000'000);  // одно выделение памяти

    // unordered_map — O(1) lookup
    std::unordered_map<std::string, int> freq;
    for (const auto& word : {"a", "b", "a", "c", "b", "a"}) {
        freq[word]++;
    }
    // freq["a"] == 3

    // map — если нужен порядок ключей
    std::map<int, std::string> ordered;
    ordered[3] = "three";
    ordered[1] = "one";
    ordered[2] = "two";
    for (const auto& [k, v2] : ordered) {
        std::cout << k << " " << v2 << '\n';  // 1, 2, 3
    }

    // set — уникальные элементы, отсортированы
    std::set<int> s = {5, 3, 1, 3, 5};
    // s == {1, 3, 5}

    // lower_bound — бинарный поиск в map/set O(log n)
    auto it = ordered.lower_bound(2);
    std::cout << it->first << '\n';  // 2
}

Подводные камни

• vector vs list: list проигрывает vector по скорости вставки в середину на реальных данных из-за плохой кэш-локальности — L1/L2 промахи дороже, чем O(n) сдвиг в vector.
• Инвалидация итераторов vector: любая операция, вызывающая реаллокацию (push_back без reserve), инвалидирует все итераторы, указатели и ссылки.
• unordered_map порядок не гарантирован: итерация даёт произвольный порядок; не полагайтесь на него в тестах.
• std::map operator[]: map[key] создаёт элемент с нулевым значением, если ключа нет — используйте find() или count() для проверки без вставки.
• Хеш-коллизии: при атаке на хеш (DoS) unordered_map деградирует до O(n) — используйте рандомизированный seed или robin-hood hashing в продакшне.
• reserve для unordered_map: без reserve таблица перехеширует данные при заполнении — для известного числа элементов вызовите m.reserve(n) заранее.
• emplace vs insert/push_back: emplace_back конструирует элемент на месте, insert — создаёт временный объект; для нетривиальных типов разница ощутима.

• Объяснять STL контейнеры и сложность только по синтаксису, без жизненного цикла и стоимости.
• Игнорировать ошибки, null/empty состояния, порядок инициализации или режим сборки.
• Давать пример, который работает в демо, но ломается при изменении владельца ресурса.
• Показывать сырой указатель без объяснения владельца и момента освобождения.

• Кандидат формулирует точную модель для STL контейнеры и сложность, а не только определение.
• Пример компилируем, безопасен по lifetime и соответствует версии технологии.
• Названы trade-off, ограничения и диагностируемые симптомы ошибки.