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

Galvenā atšķirība ir tajā, kā elementi tiek glabāti un iegūti:

• std::map: Glabā elementus pēc atslēgas sakārtotā secībā. Parasti realizēts uz sarkanmelnu koka bāzes. Meklēšana, pievienošana un dzēšana ir logaritmiskas sarežģītības O(log N), kur N ir elementu skaits.
• std::unordered_map: Glabā elementus haštabulā. Kārtība ir nejauša. Vidēji, meklēšana, pievienošana un dzēšana ir konstantes sarežģītības O(1). Sliktākajā gadījumā, kolīziju dēļ, sarežģītība var sasniegt O(N).

Raksturlielums	std::map	std::unordered_map
Kārtība	Pēc atslēgas (augšana)	Nav
Pamatstruktūra	Sarkanmelnu koka struktūra	Haštabula
Vidējā sarežģītība	O(log N)	O(1)
Sliktākā sarežģītība	O(log N)	O(N)
Atslēgas prasības	Operator <	Hašfunkcija un ==

Piemērs lietošanai:

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

int galvenais() {
    // std::map: elementi sakārtoti pēc atslēgas
    std::map<std::string, int> sakārtots_map;
    sakārtots_map["banāns"] = 3;
    sakārtots_map["ābols"] = 1;
    sakārtots_map["ķirsis"] = 2;

    // Izvade: ābols 1, banāns 3, ķirsis 2 (kārtība ir svarīga)
    for (const auto& pāris : sakārtots_map) {
        std::cout << pāris.first << " " << pāris.second << std::endl;
    }

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

    // std::unordered_map: elementu kārtība nav garantēta
    std::unordered_map<std::string, int> brīvs_map;
    brīvs_map["banāns"] = 3;
    brīvs_map["ābols"] = 1;
    brīvs_map["ķirsis"] = 2;

    // Izvade var būt dažāda (piemēram, ķirsis 2, ābols 1, banāns 3)
    for (const auto& pāris : brīvs_map) {
        std::cout << pāris.first << " " << pāris.second << std::endl;
    }

    return 0;
}