Mis vahe on map ja unordered_map vahel C++-s?

std::map — assotsiatiivne konteiner, mis hoiab paare "võti-väärtus" ja on sorteeritud võtme järgi. Põhineb punane-must puu struktuuril. Juurdepääs, sisestus ja kustutamine on logaritmilised (O(log n)).

std::unordered_map — assotsiatiivne konteiner, mis hoiab paare "võti-väärtus" hash-tabelis. Elemente ei ole sorteeritud. Keskmine juurdepääs, sisestus ja kustutamine on konstantne (O(1)), kuid halvim juhul võib olla lineaarne (O(n)) kolleeziote tõttu. Nõuab hash-funktsiooni võtmetüübile ja võrdlusoperaatorit (operator==).

Omadus	std::map	std::unordered_map
Põhjus	Punane-must puu	Hash-tabel
Elementide sorteerimine	Võtme järgi	Ei ole
Keskmine operatsioonide keerukus (juurdepääs, sisestus, kustutamine)	O(log n)	O(1)
Halvim operatsioonide keerukus (juurdepääs, sisestus, kustutamine)	O(log n)	O(n) (kolleeziote korral)
Võtme nõuded	< operaator	Hash-funktsioon, == operaator
Mälu kasutus	Rohkem	Vähem (keskmiselt, kuid võib varieeruda)

Näide kasutamisest:

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

int peamine() {
    // Kasutades std::map
    std::map<std::string, int> minu_map;
    minu_map["apple"] = 1;
    minu_map["banana"] = 2;
    minu_map["orange"] = 3;
    // Elementid on sorteeritud võtme järgi (apple, banana, orange)

    // Kasutades std::unordered_map
    std::unordered_map<std::string, int> minu_kaardistamata_map;
    minu_kaardistamata_map["apple"] = 1;
    minu_kaardistamata_map["banana"] = 2;
    minu_kaardistamata_map["orange"] = 3;
    // Elementid on ilma kindla järjekorrata
    
    return 0;
}