Какой контейнер лежит в основе map?

Какой контейнер лежит в основе map?

map в C++ Standard Library строится на основе красно-чёрного дерева (Red-Black Tree). Это самобалансирующееся бинарное дерево поиска, которое обеспечивает эффективность операций благодаря поддержанию баланса.

Почему именно красно-чёрное дерево?

Красно-чёрное дерево выбрано потому, что оно гарантирует:

• O(log n) для поиска, вставки и удаления элементов
• Автоматическая балансировка при каждой модификации
• Предсказуемая производительность — нет деградации к O(n) как в несбалансированных деревьях
• Итераторы остаются валидными после операций (за исключением удаляемого элемента)
• Упорядоченный обход в отсортированном порядке ключей

Структура узла красно-чёрного дерева

struct Node {
    Key key;
    Value value;
    Node* left;
    Node* right;
    Node* parent;
    Color color;  // RED или BLACK
};

Правила красно-чёрного дерева

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

Операции в map

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m;
    
    // Вставка O(log n)
    m[1] = "один";
    m.insert({2, "два"});
    
    // Поиск O(log n)
    auto it = m.find(1);
    
    // Удаление O(log n)
    m.erase(1);
    
    // Итерация в отсортированном порядке
    for (const auto& [key, value] : m) {
        std::cout << key << ": " << value << '\n';
    }
    
    return 0;
}

Альтернативы

• unordered_map — построена на хеш-таблице, O(1) в среднем, но без сортировки
• multimap — тоже красно-чёрное дерево, но допускает дублирующиеся ключи
• std::set — красно-чёрное дерево без значений, только ключи

Практический пример

std::map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 87;
scores["Charlie"] = 92;

// Автоматически отсортировано
for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << '\n';
}
// Вывод: Alice, Bob, Charlie (в лексикографическом порядке)

Красно-чёрное дерево — это оптимальный выбор для упорядоченного доступа с быстрыми операциями модификации, что и является главной целью std::map.