Jaka jest różnica między map a unordered_map w C++?

std::map — kontener asocjacyjny przechowujący pary "klucz-wartość", posortowane według klucza. Oparty na drzewie czerwono-czarnym. Czas dostępu, wstawiania i usuwania elementów jest logarytmiczny (O(log n)).

std::unordered_map — kontener asocjacyjny przechowujący pary "klucz-wartość" w tabeli haszującej. Elementy nie są posortowane. Średni czas dostępu, wstawiania i usuwania elementów jest stały (O(1)), ale w najgorszym przypadku może być liniowy (O(n)) z powodu kolizji. Wymaga funkcji haszującej dla typu klucza i operatora porównania równości (operator==).

Charakterystyka	std::map	std::unordered_map
Podstawa	Drzewo czerwono-czarne	Tablica haszująca
Sortowanie elementów	Według klucza	Brak
Średnia złożoność operacji (dostęp, wstawianie, usuwanie)	O(log n)	O(1)
Najgorsza złożoność operacji	O(log n)	O(n) (w przypadku kolizji)
Wymagania dotyczące klucza	< operator	Funkcja haszująca, == operator
Zużycie pamięci	Większe	Mniejsze (średnio, może się różnić)

Przykład użycia:

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

int main() {
    // Użycie std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Elementy są posortowane według klucza (apple, banana, orange)

    // Użycie 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;
    // Elementy są nieposortowane
    
    return 0;
}