Na czym polega różnica między kontenerami map i unordered_map w C++?

Główna różnica polega na tym, jak elementy są przechowywane i odczytywane:

• std::map: Przechowuje elementy w posortowanej kolejności według klucza. Zazwyczaj jest implementowana na podstawie drzewa czerwono-czarnego. Wyszukiwanie, wstawianie i usuwanie mają złożoność logarytmiczną O(log N), gdzie N to liczba elementów.
• std::unordered_map: Przechowuje elementy w tabeli haszującej. Kolejność elementów jest dowolna. Średnio, wyszukiwanie, wstawianie i usuwanie mają stałą złożoność O(1). W najgorszym przypadku, przy kolizjach, złożoność może sięgać O(N).

Cecha	std::map	std::unordered_map
Porządkowanie	Według klucza (rosnąco)	Nie
Struktura bazowa	Drzewo czerwono-czarne	Tablica haszująca
Średnia złożoność	O(log N)	O(1)
Najgorszy przypadek	O(log N)	O(N)
Wymagania dotyczące klucza	Operator <	Funkcja haszująca i ==

Przykład użycia:

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

int main() {
    // std::map: elementy posortowane według klucza
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Wyjście: apple 1, banana 3, cherry 2 (kolejność ma znaczenie)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

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

    // std::unordered_map: kolejność elementów nie jest gwarantowana
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // Wyjście może się różnić (np. cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}