Как работает std::map и std::unordered_map в C++?

Sobes Copilot

Получайте ответы в реальном времени

Ответ от нейросети

sobes.tech AI

std::map реализует ассоциативный массив на основе красно-черного дерева. Элементы хранятся в отсортированном порядке по ключу. Операции вставки, удаления и поиска имеют логарифмическую сложность (O(log n)).

std::unordered_map реализует ассоциативный массив на основе хеш-таблицы. Элементы хранятся без определенного порядка. В среднем, операции вставки, удаления и поиска имеют константную сложность (O(1)), но в худшем случае (при плохой хеш-функции или большом количестве коллизий) могут достигать линейной сложности (O(n)). Требуется, чтобы тип ключа имел реализованную хеш-функцию (std::hash) и оператор сравнения на равенство.

Сравнение:

Признак	`std::map`	`std::unordered_map`
Внутренняя структура	Красно-черное дерево	Хеш-таблица
Порядок элементов	Сортированы по ключу	Нет фиксированного порядка
Сложность поиска	O(log n)	В среднем O(1), в худшем O(n)
Сложность вставки	O(log n)	В среднем O(1), в худшем O(n)
Сложность удаления	O(log n)	В среднем O(1), в худшем O(n)
Требования к ключу	`<` оператор сравнения	Хеш-функция (`std::hash`) и `==` оператор сравнения
Использование памяти	Может быть больше для небольших элементов из-за накладных расходов дерева	Может быть больше из-за хеш-таблицы и потенциальных коллизий

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

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

// Пример использования std::map
int main() {
    std::map<int, std::string> my_map;
    my_map[1] = "один";
    my_map[3] = "три";
    my_map[2] = "два";

    for (const auto& pair : my_map) {
        std::cout << pair.first << ": " << pair.second << std::endl; // Вывод в отсортированном порядке: 1, 2, 3
    }

    auto it = my_map.find(2);
    if (it != my_map.end()) {
        std::cout << "Найден ключ 2: " << it->second << std::endl;
    }

    return 0;
}

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

#include <unordered_map>
#include <string>
#include <iostream>

// Пример использования std::unordered_map
int main() {
    std::unordered_map<int, std::string> my_unord_map;
    my_unord_map[1] = "один";
    my_unord_map[3] = "три";
    my_unord_map[2] = "два";

    for (const auto& pair : my_unord_map) {
        std::cout << pair.first << ": " << pair.second << std::endl; // Порядок вывода может отличаться
    }

    auto it = my_unord_map.find(2);
    if (it != my_unord_map.end()) {
        std::cout << "Найден ключ 2: " << it->second << std::endl;
    }

    return 0;
}