Koja je razlika između kontejnera map i unordered_map u C++?

Главна разлика је у начину на који се елементи чувају и преузимају:

• std::map: Чува елементе у сортираном реду по кључу. Обично се реализује на основу црвено-црног стабла. Проналажење, уметање и брисање имају логаритамску сложеност O(log N), где N представља број елемената.
• std::unordered_map: Чува елементе у хеш табели. Редослед елемената је произвољан. У просеку, проналажење, уметање и брисање имају константну сложеност O(1). У најгорем случају, при колизијама, сложеност може достићи O(N).

Карактеристика	std::map	std::unordered_map
Поредак	По кључу (растући)	Не
Основна структура	Црвено-црно стабло	Хеш табела
Просечна сложеност	O(log N)	O(1)
Најгоре случај	O(log N)	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;
}