Контейнеры std::map, std::set

Ассоциативные контейнеры C++

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

• упорядоченные контейнеры на базе сбалансированных деревьев поиска: map, multimap, set, multiset;
• неупорядоченные хеш-структуры: unordered_map, unordered_set.

std::map

std::map — отсортированный словарь (ключ–значение), основанный на красно-чёрном дереве.

Свойства:

• хранит пары (ключ, значение);
• ключи уникальны;
• элементы хранятся в отсортированном порядке (по умолчанию по operator< для ключа);
• основные операции (поиск, вставка, удаление) работают за O(log n).

Основные операции:

• m[key] — доступ по ключу, при отсутствии ключа создаёт элемент со значением по умолчанию (O(log n));
• m[key] = value — вставка нового элемента или изменение существующего (O(log n));
• m.at(key) — доступ по ключу, кидает std::out_of_range, если ключа нет (O(log n));
• m.insert({key, value}) — вставка, если ключа нет; иначе элемент не меняется (O(log n));
• m.erase(key) — удаление по ключу (O(log n));
• m.find(key) — поиск, возвращает итератор или m.end() (O(log n));
• m.count(key) — возвращает 0 или 1 (O(log n));
• m.lower_bound(key) — первый элемент, для которого key <= элемент;
• m.upper_bound(key) — первый элемент, для которого key < элемент.

Пример

#include <map>
#include <iostream>

int main() {
    std::map<std::string, int> m;

    m["apple"] = 1;
    m["apple"] = 2;

    std::cout << m["apple"];
}

std::multimap

std::multimap похож на map, но позволяет хранить несколько значений для одного ключа.

Свойства:

• хранит пары (ключ, значение);
• ключи могут повторяться;
• элементы упорядочены;
• операции — O(log n).

Основные операции:

• mm.insert({key, value});
• mm.find(key) — первый элемент с данным ключом;
• mm.count(key) — количество элементов;
• mm.equal_range(key) — диапазон значений;
• mm.erase(key) — удаление всех значений по ключу.

Пример

#include <map>
#include <iostream>

int main() {
    std::multimap<std::string, int> mm;

    mm.insert({"apple", 1});
    mm.insert({"apple", 2});

    auto range = mm.equal_range("apple");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->first << " = " << it->second << "\n";
    }
}

std::set

std::set — отсортированное множество уникальных элементов.

Свойства:

• хранит только ключи;
• элементы уникальны;
• отсортированы;
• O(log n).

Основные операции:

• s.insert(x);
• s.erase(x);
• s.find(x);
• s.count(x);
• s.lower_bound(x), s.upper_bound(x).

Пример

#include <set>
#include <iostream>

int main() {
    std::set<int> s;

    s.insert(5);
    s.insert(5);

    std::cout << s.size();
}

std::multiset

std::multiset — отсортированное множество с возможными дубликатами.

Свойства:

• дубликаты разрешены;
• отсортировано;
• O(log n).

Основные операции:

• ms.insert(x);
• ms.erase(x);
• ms.find(x);
• ms.count(x);
• ms.lower_bound(x), ms.upper_bound(x).

Пример

#include <set>
#include <iostream>

int main() {
    std::multiset<int> ms;

    ms.insert(5);
    ms.insert(5);

    std::cout << ms.size();
    std::cout << ms.count(5);
}

unordered_map и unordered_set

Основаны на хеш-таблицах.

Свойства:

• элементы не упорядочены;
• доступ через хеш-функцию;
• уникальные ключи/элементы;
• операции — O(1) амортизированно.

Пример unordered_map

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> um;

    um["apple"] = 10;
    um["banana"] = 20;

    std::cout << um["apple"];
}

Пример unordered_set

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> us;

    us.insert(3);
    us.insert(3);

    std::cout << us.size();
}