Какая сложность доступа к элементу в std::map?

Поиск и доступ к элементу по ключу в std::map имеют логарифмическую временную сложность O(log n), где n — количество элементов в контейнере.

Почему O(log n)? std::map обычно реализован как красно-черное дерево — сбалансированное бинарное дерево поиска (БДП). В сбалансированном БДП высота дерева пропорциональна log n, и для поиска элемента требуется пройти от корня до листа, выполняя не более log n сравнений.

Примеры доступа:

#include <map>
#include <string>

std::map<int, std::string> employeeMap = {
    {101, "Alice"},
    {102, "Bob"},
    {103, "Charlie"}
};

// 1. Поиск с помощью find() - O(log n)
auto it = employeeMap.find(102);
if (it != employeeMap.end()) {
    // Найден: it->first = 102, it->second = "Bob"
}

// 2. Доступ через operator[] - O(log n)
// Если ключ существует, возвращает значение.
std::string name = employeeMap[102]; // name = "Bob"
// Если ключа нет, он будет вставлен со значением по умолчанию.
std::string newName = employeeMap[104]; // Вставляет {104, ""}, O(log n)

// 3. Проверка наличия ключа с count() - O(log n)
if (employeeMap.count(103) > 0) {
    // Ключ 103 существует
}

Для частого поиска, где порядок элементов не важен, std::unordered_map (хеш-таблица) предлагает среднюю сложность O(1).