Ассоциативные контейнеры: map, set, unordered_map

Узнайте об упорядоченных и неупорядоченных ассоциативных контейнерах — map, set и их multi- и unordered-вариантах. Поймите, когда выбирать деревья, а когда хеш-таблицы.

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

STL предоставляет два семейства ассоциативных контейнеров:

Упорядоченные (реализованы как красно-чёрные деревья):
- std::map — отсортированные пары ключ-значение, уникальные ключи
- std::set — отсортированные уникальные ключи
- std::multimap — отсортированные пары ключ-значение, допускаются дубликаты ключей
- std::multiset — отсортированные ключи, допускаются дубликаты

Неупорядоченные (реализованы как хеш-таблицы):
- std::unordered_map — на основе хеширования, уникальные ключи
- std::unordered_set — на основе хеширования, уникальные ключи
- std::unordered_multimap — на основе хеширования, дубликаты ключей
- std::unordered_multiset — на основе хеширования, дубликаты

Упорядоченные контейнеры хранят элементы в отсортированном виде и обеспечивают O(log n) поиск, вставку и удаление. Неупорядоченные контейнеры используют хеширование для O(1) в среднем случае, но O(n) в худшем случае при множестве коллизий.

Использование map и set

std::map хранит пары ключ-значение, отсортированные по ключу. std::set хранит уникальные отсортированные значения. Оба реализованы как самобалансирующиеся красно-чёрные деревья, гарантирующие O(log n) операций.

map_set.cpp

#include <map>
#include <set>
#include <string>
#include <iostream>

int main() {
    // std::map — sorted key-value pairs
    std::map<std::string, int> ages;
    ages["Alice"] = 30;              // insert or update
    ages["Bob"]   = 25;
    ages.insert({"Charlie", 35});    // insert only if key absent
    ages.emplace("Diana", 28);       // construct in-place

    // Lookup
    if (auto it = ages.find("Bob"); it != ages.end()) {
        std::cout << it->first << " is " << it->second << '\n';
    }

    // C++17 structured bindings — elegant map iteration
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << '\n';
    }
    // Output is sorted by key: Alice, Bob, Charlie, Diana

    // std::set — sorted unique values
    std::set<int> primes = {2, 3, 5, 7, 11, 13};
    primes.insert(5);                // no effect — 5 already present
    primes.insert(17);               // inserted

    if (primes.contains(7)) {        // C++20
        std::cout << "7 is prime\n";
    }

    // count() — returns 0 or 1 for set (useful pre-C++20)
    if (primes.count(4) == 0) {
        std::cout << "4 is not prime\n";
    }

    // lower_bound / upper_bound — range queries
    auto lo = primes.lower_bound(5);
    auto hi = primes.upper_bound(11);
    for (auto it = lo; it != hi; ++it) {
        std::cout << *it << ' ';     // 5 7 11
    }
    std::cout << '\n';
}

Неупорядоченные контейнеры и пользовательские хеш-функции

Неупорядоченные контейнеры используют хеш-таблицы для O(1) поиска в среднем случае. Для пользовательских типов ключей необходимо предоставить хеш-функцию и оператор равенства.

unordered_custom.cpp

#include <unordered_map>
#include <unordered_set>
#include <string>
#include <iostream>

// Custom type as key
struct Point {
    int x, y;
    bool operator==(const Point&) const = default;  // C++20
};

// Custom hash function
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // Combine hashes — a common pattern
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // simple combine (consider better hashes in production)
    }
};

int main() {
    // Basic unordered_map — O(1) average lookup
    std::unordered_map<std::string, double> prices;
    prices["apple"]  = 1.50;
    prices["banana"] = 0.75;
    prices["cherry"] = 3.00;

    // try_emplace (C++17) — only constructs value if key is absent
    prices.try_emplace("apple", 9.99);   // no-op, "apple" exists
    prices.try_emplace("date", 4.50);    // inserted

    // extract and insert (C++17 node API)
    auto node = prices.extract("banana");
    if (!node.empty()) {
        node.key() = "plantain";          // rename key without copy
        prices.insert(std::move(node));
    }

    for (const auto& [fruit, price] : prices) {
        std::cout << fruit << ": $" << price << '\n';
    }

    // Custom type as key
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2});   // duplicate — not inserted
    std::cout << "Unique points: " << points.size() << '\n';  // 2
}

Multimap и Multiset

std::multimap и std::multiset допускают дубликаты ключей. Используйте equal_range() для поиска всех записей с данным ключом.

multimap_multiset.cpp

#include <map>
#include <set>
#include <iostream>
#include <string>

int main() {
    // multimap — multiple values per key
    std::multimap<std::string, std::string> phone_book;
    phone_book.insert({"Alice", "555-0100"});
    phone_book.insert({"Alice", "555-0101"});  // duplicate key OK
    phone_book.insert({"Bob",   "555-0200"});

    // equal_range returns a pair of iterators [first, last)
    auto [begin, end] = phone_book.equal_range("Alice");
    std::cout << "Alice's numbers:\n";
    for (auto it = begin; it != end; ++it) {
        std::cout << "  " << it->second << '\n';
    }

    // multiset — count duplicates
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
    std::cout << "Count of 3: " << ms.count(3) << '\n';  // 3
}

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

Упорядоченные контейнеры по умолчанию используют std::less (по возрастанию). Вы можете задать пользовательский компаратор как третий аргумент шаблона:

std::set<int, std::greater<int>> descending = {1, 5, 3};
// порядок итерации: 5, 3, 1

Для пользовательских типов можно либо определить operator< в классе, либо передать функтор-компаратор или лямбду:

auto cmp = [](const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
};
std::set<Point, decltype(cmp)> point_set(cmp);

В C++20 можно использовать оператор «космический корабль» (operator<=>) для автоматической генерации всех операторов сравнения.

Подводный камень

Использование operator[] на std::map или std::unordered_map вставляет значение, сконструированное по умолчанию, если ключ не существует. Это частый источник неочевидных ошибок:

std::map<std::string, int> m;
int val = m["missing"];  // вставляет {"missing", 0} в map!

Используйте find(), count() или contains() (C++20) для поиска без модификации. Используйте at(), если хотите получить исключение при отсутствии ключа.

Лучшая практика

Используйте unordered_map/unordered_set, когда вам нужен только поиск, вставка и удаление — O(1) в среднем случае превосходит O(log n) для больших коллекций.

Используйте map/set, когда вам нужны:
- Отсортированный порядок итерации
- Запросы по диапазонам (lower_bound, upper_bound, equal_range)
- Гарантированный O(log n) в худшем случае (без патологических коллизий хешей)

Для маленьких коллекций (менее ~100 элементов) отсортированный std::vector с std::lower_bound может превзойти оба варианта благодаря локальности кэша.

Ключевые выводы

std::map и std::set используют красно-чёрные деревья — O(log n) операций с сохранением порядка сортировки
std::unordered_map и std::unordered_set используют хеш-таблицы — O(1) в среднем, но требуют хеш-функцию
Используйте структурные привязки C++17 (auto& [key, val]) для удобной итерации по map
operator[] на map молча вставляет значения по умолчанию — используйте find() или contains() для безопасного поиска
Пользовательские типы в качестве ключей требуют operator< (упорядоченные) или хеш-функцию + operator== (неупорядоченные)
try_emplace (C++17) избегает конструирования значения, если ключ уже существует

Тест — проверьте свои знания

(15 XP)

1. Какова средняя временная сложность поиска в `std::unordered_map`?

2. Что происходит при использовании `operator[]` с несуществующим ключом в `std::map`?

3. Какой контейнер следует выбрать, если вам нужна отсортированная итерация И запросы по диапазонам (lower_bound/upper_bound)?

Последовательные контейнеры: vector, deque, list, array

Адаптеры контейнеров и специальные контейнеры