В чем разница между std::map и std::unordered_map в C++?

std::map:

• Хранит элементы в отсортированном порядке по ключам.
• Реализована на основе красно-черного дерева.
• Время доступа, вставки и удаления в среднем логарифмическое: O(log n).
• Ключи должны иметь оператор <.
• Подходит, когда важен упорядоченный обход элементов или частые операции поиска диапазона.

std::unordered_map:

• Не хранит элементы в каком-либо определенном порядке.
• Реализована на основе хэш-таблицы.
• Среднее время доступа, вставки и удаления: O(1). В худшем случае (при плохом хэшировании и большом количестве коллизий): O(n).
• Ключи должны быть хэшируемыми (предоставлять хэш-функцию) и иметь оператор ==.
• Подходит, когда главный приоритет — быстрое присутствие (lookup) элементов по ключу и порядок неважен.

Сравнительная таблица:

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

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

// Пример использования std::map
std::map<int, std::string> my_map;
my_map[5] = "five";
my_map[2] = "two";
my_map[8] = "eight";

// Элементы будут выведены в отсортированном порядке по ключу
for (const auto& pair : my_map) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

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

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

// Пример использования std::unordered_map
std::unordered_map<int, std::string> my_unordered_map;
my_unordered_map[5] = "five";
my_unordered_map[2] = "two";
my_unordered_map[8] = "eight";

// Порядок вывода элементов не гарантируется
for (const auto& pair : my_unordered_map) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}