Как устроен контейнер map в C++?

std::map - это ассоциативный контейнер, который хранит элементы, состоящие из пары ключ-значение, отсортированные по ключу.

Основные характеристики:

• Элементы хранятся в отсортированном порядке по ключу.
• Ключи уникальны. Каждый ключ может встречаться только один раз.
• Время доступа, вставки и удаления в среднем логарифмическое: $O(\log n)$, где $n$ - количество элементов.
• Реализован, как правило, на основе самобалансирующегося бинарного дерева поиска, чаще всего красно-чёрного дерева.

Внутреннее устройство (красно-чёрное дерево):

Каждый узел дерева хранит:

1. Пару ключ-значение (std::pair<const Key, T>). Ключ константный, чтобы избежать его изменения и сохранения свойства упорядоченности.
2. Указатели на левого и правого потомков.
3. Указатель на родителя.
4. Цвет узла (красный или чёрный).

Свойства красно-чёрного дерева, поддерживаемые при операциях вставки и удаления с помощью вращений и перекрашиваний, обеспечивают логарифмическую высоту дерева и, как следствие, логарифмическую сложность операций.

Операции:

• operator[]: Доступ по ключу. Если ключ не найден, вставляет новый элемент с ключом и значением по умолчанию для типа значения.
• at(): Доступ по ключу. Если ключ не найден, бросает исключение std::out_of_range.
• insert(): Вставляет новый элемент-пару. Игнорирует вставку, если ключ уже существует.
• erase(): Удаляет элемент по ключу или итератору.
• find(): Ищет элемент по ключу и возвращает итератор на него или end(), если элемент не найден.

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

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

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

    // Вставка элементов
    my_map[1] = "one";
    my_map[3] = "three";
    my_map.insert({2, "two"}); // Другой способ вставки

    // Доступ к элементам
    std::cout << "Value for key 1: " << my_map[1] << std::endl;

    // Итерирование по элементам (будут выведены в порядке ключей)
    for (const auto& pair : my_map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // Поиск элемента
    auto it = my_map.find(2);
    if (it != my_map.end()) {
        std::cout << "Found element with key 2: " << it->second << std::endl;
    }

    // Удаление элемента
    my_map.erase(1);

    return 0;
}

Отличие от std::unordered_map:

Feature	std::map	std::unordered_map
Ordering	Sorted by key	Unordered
Implementation	Red-black tree	Hash table
Complexity (Avg)	$O(\log n)$	$O(1)$
Complexity (Worst)	$O(\log n)$	$O(n)$
Key Requirements	Less than comparison	Hash function & equality