Контейнеры STL и их сложность операций: шпаргалка для собеседований и практики

Введение

Выбор правильного контейнера — это решение, которое влияет на производительность кода сильнее, чем большинство микрооптимизаций. На собеседованиях регулярно спрашивают о сложности операций у vector, list, map, unordered_map и других контейнеров — и это не формальность: незнание этих характеристик часто оборачивается на практике медленным кодом, который «просто работает» на маленьких данных и разваливается на больших.

Концепция

Кратко по основным контейнерам (n — текущий размер контейнера):

| Контейнер | Доступ по индексу | Вставка/удаление в конец | Вставка/удаление в середину | Поиск | |—|—|—|—|—| | std::vector | O(1) | O(1) амортизированно | O(n) | O(n) (O(log n) если отсортирован + binary_search) | | std::deque | O(1) | O(1) (оба конца) | O(n) | O(n) | | std::list (двусвязный) | O(n) | O(1) | O(1) при наличии итератора | O(n) | | std::forward_list | O(n) | O(1) (только начало) | O(1) при наличии итератора | O(n) | | std::map/std::set | — | — | O(log n) | O(log n) | | std::unordered_map/set | — | — | O(1) средн., O(n) худш. | O(1) средн., O(n) худш. | | std::array | O(1) | нельзя менять размер | нельзя | O(n) |

Главное правило: vector — контейнер по умолчанию почти всегда (хорошая локальность данных в кэше, простота, дешёвый доступ по индексу). list нужен редко — почти всегда vector + erase/remove оказывается быстрее на практике из-за кэш-локальности, даже при формально худшей сложности.

Пример кода

#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <iostream>
#include <algorithm>

template <typename Func>
long long measureMs(Func&& f) {
    auto start = std::chrono::high_resolution_clock::now();
    f();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

int main() {
    constexpr int N = 200'000;

    // Вставка в начало: vector O(n) для каждой вставки, list O(1)
    auto vectorFrontInsert = measureMs([&]() {
        std::vector<int> v;
        for (int i = 0; i < N / 20; ++i) { // меньше итераций — иначе слишком долго
            v.insert(v.begin(), i);
        }
    });
    std::cout << "vector insert at front: " << vectorFrontInsert << " msn";

    auto listFrontInsert = measureMs([&]() {
        std::list<int> l;
        for (int i = 0; i < N / 20; ++i) {
            l.push_front(i);
        }
    });
    std::cout << "list push_front:        " << listFrontInsert << " msn";

    // Поиск: map O(log n) vs unordered_map O(1) средн.
    std::map<int, int> ordered;
    std::unordered_map<int, int> hashed;
    for (int i = 0; i < N; ++i) {
        ordered[i] = i;
        hashed[i] = i;
    }

    auto mapLookup = measureMs([&]() {
        long long sum = 0;
        for (int i = 0; i < N; ++i) sum += ordered[i];
    });
    auto hashLookup = measureMs([&]() {
        long long sum = 0;
        for (int i = 0; i < N; ++i) sum += hashed[i];
    });
    std::cout << "map lookup:        " << mapLookup << " msn";
    std::cout << "unordered_map lookup: " << hashLookup << " msn";

    // erase-remove идиома для vector — O(n), но с прекрасной кэш-локальностью
    std::vector<int> nums(N);
    std::iota(nums.begin(), nums.end(), 0);
    auto eraseRemoveTime = measureMs([&]() {
        nums.erase(std::remove_if(nums.begin(), nums.end(),
                                   [](int x) { return x % 2 == 0; }),
                   nums.end());
    });
    std::cout << "vector erase-remove (filter): " << eraseRemoveTime << " ms, "
              << "remaining=" << nums.size() << "n";

    return 0;
}

Пояснения к коду

Вставка в начало vector требует сдвига всех существующих элементов — поэтому при росте N время растёт квадратично, тогда как list::push_front остаётся стабильно быстрым (O(1) на операцию). Однако на реальных задачах с произвольным доступом и обходом vector почти всегда выигрывает за счёт непрерывной памяти и эффективного использования кэша процессора — даже там, где по Big O он «хуже».

Сравнение map и unordered_map показывает классическую разницу O(log n) против O(1) в среднем случае — на большом N unordered_map обычно заметно быстрее на чистый поиск, но требует качественной хеш-функции и достаточного количества buckets.

Идиома erase-remove — стандартный способ удаления элементов по условию из vector: remove_if перемещает «ненужные» элементы в конец и возвращает итератор-границу, а erase действительно укорачивает контейнер. Несмотря на формальную сложность O(n), это один линейный проход по памяти — на практике эффективнее, чем многократные erase по одному элементу.

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

1. На собеседовании важно не только назвать сложность, но и объяснить, почему vector часто быстрее list на практике — из-за локальности данных в кэше процессора, несмотря на худшую формальную сложность вставки в середину. 2. unordered_map — это не бесплатный O(1): при плохом хешировании или больших load factor сложность деградирует до O(n). Резервируйте размер заранее (reserve), если знаете примерное количество элементов. 3. map/set гарантируют порядок обхода, unordered_map/unordered_set — нет. Выбор зависит от того, нужен ли порядок. 4. Помните про итераторную инвалидацию: вставка в vector может инвалидировать все итераторы/указатели на элементы (если произошла реаллокация), вставка в list/map инвалидирует только указатели на удалённые элементы. 5. Если нужен и быстрый поиск, и сохранение порядка вставки — рассмотрите комбинацию vector + unordered_map<Key, индекс> или используйте boost::multi_index.

================================================================================