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

В C++ STL предоставляет несколько категорий контейнеров:

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

• std::vector — динамический массив с произвольным доступом. Основной выбор для большинства случаев.
• std::deque — двусторонняя очередь, позволяет эффективно добавлять/удалять элементы с обоих концов.
• std::list — двусвязный список. Эффективные вставка и удаление в любой позиции, но нет произвольного доступа.
• std::forward_list (C++11) — односвязный список с меньшим overhead.
• std::array (C++11) — статический массив фиксированного размера, обёрнутый в STL-интерфейс.

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

• std::set / std::multiset — хранят ключи (значения) в отсортированном порядке, обычно на основе красно-чёрного дерева.
• std::map / std::multimap — хранят пары ключ-значение, отсортированные по ключу.

3. Ассоциативные контейнеры (неупорядоченные, хэш-таблицы, C++11):

• std::unordered_set / std::unordered_multiset — реализация на основе хэш-таблицы, обеспечивают амортизированное O(1) для поиска.
• std::unordered_map / std::unordered_multimap — хэш-таблица для пар ключ-значение.

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

• std::stack — LIFO (последним пришёл — первым ушёл).
• std::queue — FIFO (первым пришёл — первым ушёл).
• std::priority_queue — очередь, где элемент с наивысшим приоритетом извлекается первым.

Пример использования std::vector и std::unordered_map:

#include <vector>
#include <unordered_map>
#include <string>

int main() {
    // Последовательный контейнер
    std::vector<int> numbers = {10, 20, 30};
    numbers.push_back(40); // Добавление в конец

    // Ассоциативный неупорядоченный контейнер
    std::unordered_map<std::string, int> phoneBook;
    phoneBook["Alice"] = 12345;
    phoneBook["Bob"] = 67890;

    // Быстрый поиск по ключу
    auto it = phoneBook.find("Alice");
    if (it != phoneBook.end()) {
        // Найдено: it->first = "Alice", it->second = 12345
    }
    return 0;
}

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