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

std::map — asocijativni kontejner koji čuva parove "ključ-vrednost", sortirane po ključu. Baziran na crveno-crnom stablu. Vreme pristupa, umetanja i brisanja elemenata je logaritamsko (O(log n)).

std::unordered_map — asocijativni kontejner koji čuva parove "ključ-vrednost" u hash tabeli. Elementi nisu sortirani. U proseku, vreme pristupa, umetanja i brisanja je konstantno (O(1)), ali u najgorem slučaju može biti linearno (O(n)) zbog kolizija. Zahteva funkciju heširanja za tip ključa i operator za poređenje jednakosti (operator==).

Karakteristike	std::map	std::unordered_map
Osnova	Crveno-črno stablo	Hash tabela
Sortiranje elemenata	Po ključu	Ne
Prosečna složenost operacija (pristup, umetanje, brisanje)	O(log n)	O(1)
Najgora složenost	O(log n)	O(n) (pri kolizijama)
Zahtevi za ključ	< operator	Funkcija heširanja, == operator
Potrošnja memorije	Više	Manje (prosečno, može varirati)

Primer upotrebe:

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

int main() {
    // Upotreba std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Elementi su sortirani po ključu (apple, banana, orange)

    // Upotreba 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;
    // Elementi nisu sortirani
    
    return 0;
}