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

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

• std::vector — основной выбор для последовательности элементов. Используется, когда нужен динамический массив с быстрым доступом по индексу (O(1)) и добавлением в конец (амортизированное O(1)). Неэффективен для частых вставок/удалений в середине.

  std::vector<int> vec = {1, 2, 3};
  vec.push_back(4); // Быстро
  int x = vec[2];   // Мгновенный доступ

• std::deque — похож на vector, но позволяет эффективно добавлять и удалять элементы как в начале, так и в конце (O(1)). Доступ по индексу также O(1), но может быть чуть медленнее, чем у vector. Используется для очередей.
• std::list / std::forward_list — используются при очень частых вставках и удалениях в произвольных местах последовательности (O(1) после нахождения позиции). Цена: нет доступа по индексу (только последовательный, O(n)) и большее потребление памяти на хранение указателей.
• std::set / std::map (упорядоченные) — нужны, когда элементы должны храниться отсортированными по ключу или требуется гарантированная уникальность. Основаны на красно-черных деревьях, операции O(log n).
• std::unordered_set / std::unordered_map — используются, когда важнее максимальная скорость доступа, вставки и удаления в среднем случае (O(1)), а порядок элементов не важен. Основаны на хеш-таблицах.
• std::stack / std::queue / std::priority_queue — адаптеры контейнеров. Используются для реализации строгой дисциплины доступа: LIFO, FIFO или очереди с приоритетом. Обычно реализованы поверх deque или vector.

Общее правило: Начинайте с vector. Меняйте его только если профилирование показывает, что он не справляется с вашим паттерном доступа.