Kāda ir atšķirība starp map un unordered_map C++?

std::map — asociatīvs konteineris, kas glabā pārus "atslēga-vērtība" un ir sakārtots pēc atsleģas. Balstīts uz sarkanu-melnu koku. Piekļuve, pievienošana un dzēšana ir logaritmiskas (O(log n)).

std::unordered_map — asociatīvs konteineris, kas glabā pārus "atslēga-vērtība" hash tabulā. Elementi nav sakārtoti. Vidējais piekļuves, pievienošanas un dzēšanas laiks ir konstants (O(1)), bet sliktākajā gadījumā var būt lineārs (O(n)) kolīziju dēļ. Prasa hash funkciju atslēgas tipam un vienādojuma operatoru (operator==).

Raksturlielums	std::map	std::unordered_map
Pamats	Sarkanu-melns koks	Hash tabula
Elementu kārtošana	Pēc atslēgas	Nav
Vidējais operāciju sarežģītums (piekļuve, pievienošana, dzēšana)	O(log n)	O(1)
Sliktākais operāciju sarežģītums (piekļuve, pievienošana, dzēšana)	O(log n)	O(n) (kolīziju gadījumā)
Atslēgas prasības	< operators	Hash funkcija, == operators
Atmiņas patēriņš	Lielāks	Mazāks (vidēji, bet var atšķirties)

Piemērs lietošanai:

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

int galva() {
    // Izmantošana ar std::map
    std::map<std::string, int> mans_map;
    mans_map["apple"] = 1;
    mans_map["banana"] = 2;
    mans_map["orange"] = 3;
    // Elementi ir sakārtoti pēc atslēgas (apple, banana, orange)

    // Izmantošana ar std::unordered_map
    std::unordered_map<std::string, int> mans_neizkārtots_map;
    mans_neizkārtots_map["apple"] = 1;
    mans_neizkārtots_map["banana"] = 2;
    mans_neizkārtots_map["orange"] = 3;
    // Elementi ir bez noteiktas kārtības
    
    return 0;
}