Какая сложность чтения в std::map?

Временная сложность чтения в std::map

Ответ: O(log n)

std::map имеет временную сложность O(log n) для операции чтения (поиска), где n — количество элементов в контейнере. Это обусловлено тем, что std::map реализована как красно-чёрное дерево (self-balancing binary search tree).

Почему именно O(log n)?

Красно-чёрное дерево — это сбалансированное бинарное дерево поиска, которое гарантирует, что высота дерева никогда не превышает 2 * log(n). При поиске элемента нужно пройти от корня к листу, что требует посещения O(log n) узлов.

#include <map>
#include <iostream>
#include <chrono>

int main() {
    std::map<int, std::string> m;
    
    // Вставляем 10000 элементов
    for (int i = 0; i < 10000; i++) {
        m[i] = "value_" + std::to_string(i);
    }
    
    // Поиск элемента: O(log n)
    // log(10000) ≈ 13.3, значит максимум ~14 сравнений
    auto start = std::chrono::high_resolution_clock::now();
    auto it = m.find(5000);  // O(log n)
    auto end = std::chrono::high_resolution_clock::now();
    
    std::cout << "Найдено: " << it->second << std::endl;
    std::cout << "Время поиска: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << " нс" << std::endl;
    
    return 0;
}

Все основные операции std::map

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

#include <map>
#include <iostream>

int main() {
    std::map<std::string, int> phonebook;
    
    phonebook["Alice"] = 123456;
    phonebook["Bob"] = 234567;
    phonebook["Charlie"] = 345678;
    phonebook["David"] = 456789;
    phonebook["Eve"] = 567890;
    
    // Способ 1: find() - O(log n)
    auto it = phonebook.find("Charlie");
    if (it != phonebook.end()) {
        std::cout << "Найден номер: " << it->second << std::endl;  // 345678
    }
    
    // Способ 2: operator[] - O(log n)
    std::cout << "Номер Alice: " << phonebook["Alice"] << std::endl;  // 123456
    
    // Способ 3: count() - O(log n)
    if (phonebook.count("Bob")) {
        std::cout << "Bob есть в справочнике" << std::endl;
    }
    
    // Способ 4: at() - O(log n), выбросит исключение если ключа нет
    try {
        std::cout << "Eve: " << phonebook.at("Eve") << std::endl;  // 567890
    } catch (const std::out_of_range& e) {
        std::cout << "Ключ не найден" << std::endl;
    }
    
    return 0;
}

Различие между поиском и доступом

std::map<int, std::string> m;
m[1] = "one";
m[2] = "two";

// find() - не создаёт новый элемент если ключа нет
auto it = m.find(3);  // Возвращает end(), ничего не изменяет

// operator[] - создаёт новый элемент, если ключа нет
std::string val = m[3];  // Создаёт новый элемент с пустым значением!
// Теперь m содержит ключ 3 с значением ""

Сравнение std::map с другими контейнерами

Красно-чёрное дерево

std::map использует красно-чёрное дерево, которое гарантирует:

1. Все листья на одном уровне по чёрной высоте
2. Чёрная высота = количество чёрных узлов от корня к листу
3. Цвета узлов распределяются по строгим правилам
4. Высота дерева = O(log n)

// Пример структуры красно-чёрного дерева:
//
//        (B:5)
//       /      \
//     (R:3)    (R:7)
//    /    \    /    \
// (B:1) (B:4) (B:6) (B:9)
//
// B = Black, R = Red
// log(7) ≈ 2.8, высота дерева = 3

Практические примеры использования

Поиск по диапазону

std::map<int, std::string> m;
for (int i = 1; i <= 10; i++) {
    m[i] = "value_" + std::to_string(i);
}

// Найти все элементы с ключами от 3 до 7
auto start = m.lower_bound(3);  // O(log n)
auto end = m.upper_bound(7);    // O(log n)

for (auto it = start; it != end; ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
    // 3: value_3
    // 4: value_4
    // ...
    // 7: value_7
}

Оптимальный выбор между std::map и std::unordered_map

// Используй std::map если:
// 1. Нужен порядок элементов
// 2. Нужны операции lower_bound, upper_bound
// 3. Предсказуемая O(log n) важнее средней O(1)
// 4. Итерирование должно быть в порядке

std::map<int, std::string> sorted_map;
for (auto& p : sorted_map) {
    // Элементы проходят в порядке ключей
}

// Используй std::unordered_map если:
// 1. Нужна максимальная скорость поиска
// 2. Порядок элементов не важен
// 3. Хеш-функция хорошая (нет коллизий)

std::unordered_map<int, std::string> hash_map;  // O(1) средн.

Ключевые моменты

• std::map использует красно-чёрное дерево
• Поиск: O(log n) — доступ, поиск, вставка, удаление
• Дерево всегда сбалансировано — гарантирует O(log n) в худшем случае
• Элементы отсортированы по ключам
• std::unordered_map быстрее (O(1) средн.), но без гарантий и порядка
• lower_bound/upper_bound — O(log n) бинарный поиск
• Итерирование остаётся O(n)