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

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

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

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

#include <map>
#include <unordered_map>
#include <string>

int main() {
    // Использование std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Элементы хранятся в отсортированном порядке по ключу (apple, banana, orange)

    // Использование std::unordered_map
    std::unordered_map<std::string, int> my_unordered_map;
    my_unordered_map["apple"] = 1;
    my_unordered_map["banana"] = 2;
    my_unordered_map["orange"] = 3;
    // Элементы хранятся без определенного порядка
    
    return 0;
}