В чем заключается разница между контейнерами map и unordered_map в C++?

Главное различие в том, как элементы хранятся и извлекаются:

• std::map: Хранит элементы в отсортированном порядке ключей. Обычно реализуется на основе красно-черного дерева. Поиск, вставка и удаление имеют логарифмическую сложность O(log N), где N — количество элементов.
• std::unordered_map: Хранит элементы в хэш-таблице. Порядок элементов произвольный. В среднем, поиск, вставка и удаление имеют константную сложность O(1). В худшем случае, при наличии коллизий, сложность может достигать O(N).

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

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

int main() {
    // std::map: элементы упорядочены по ключу
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Вывод: apple 1, banana 3, cherry 2 (порядок важен)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    std::cout << "---" << std::endl;

    // std::unordered_map: порядок элементов не гарантирован
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // Вывод может быть разным (например, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}