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

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

Внутренне std::map обычно реализован как красно-черное дерево.

• Красно-черное дерево (Red-Black Tree): Это самобалансирующееся бинарное дерево поиска. Свойства балансировки гарантируют логарифмическую сложность для большинства операций, таких как вставка, удаление и поиск.

Свойства красно-черного дерева:

1. Каждый узел либо красный, либо черный.
2. Корень всегда черный.
3. Все листья (NULL-узлы) черные.
4. Если узел красный, то оба его потомка черные.
5. Для каждого узла любой простой путь от этого узла к любому из листовых потомков содержит одинаковое количество черных узлов.

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

Ключевые характеристики std::map:

• Уникальность ключей: Нельзя вставить два элемента с одинаковым ключом. Попытка вставки элемента с существующим ключом либо игнорируется, либо обновляет значение (в зависимости от метода вставки).
• Сортировка по ключу: Элементы хранятся в порядке, определяемом функцией сравнения ключей (по умолчанию std::less для типа ключа).
• Ассоциативный доступ: Доступ к элементам происходит по ключу, а не по индексу.
• Логарифмическая сложность: Большинство операций (вставка, удаление, поиск) имеют сложность O(log N), где N - количество элементов в контейнере.

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

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

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

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

    // Доступ к элементу по ключу
    std::cout << "Значение для ключа 2: " << myMap[2] << std::endl; // Вывод: два

    // Итерация по элементам (в отсортированном порядке ключей)
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    /*
    Вывод:
    1: один
    2: два
    3: три
    */

    // Поиск элемента
    auto it = myMap.find(3);
    if (it != myMap.end()) {
        std::cout << "Найден элемент с ключом 3: " << it->second << std::endl; // Вывод: три
    }

    // Удаление элемента по ключу
    myMap.erase(1);

    // Проверка размера
    std::cout << "Размер после удаления: " << myMap.size() << std::endl; // Вывод: 2

    return 0;
}