Каква е разликата между map и unordered_map в C++?

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

std::unordered_map — асоциативен контейнер, който съхранява двойки "ключ-стойност" в хеш таблица. Елементите не са сортирани. Средното време за достъп, вмъкване и изтриване е константно (O(1)), но в най-лошия случай може да бъде линейно (O(n)) поради колизии. Изисква хеш функция за типа на ключа и оператор за сравнение за равенство (operator==).

Характеристика	std::map	std::unordered_map
Основа	Червено-черно дърво	Хеш таблица
Сортиране на елементите	По ключ	Не
Средна сложност на операции (достъп, вмъкване, изтриване)	O(log n)	O(1)
Най-лоша сложност	O(log n)	O(n) (при колизии)
Изисквания към ключа	< оператор	Хеш функция, == оператор
Памет консумация	Повече	По-малко (средно, може да варира)

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

#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;
}