Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::unordered_map — zgoščevalna tabela z enoličnimi ključi

std::unordered_map shranjuje pare ključ–vrednost brez zagotovljenega vrstnega reda. Spoznajte iskanje brez vstavljanja, razliko med operator[] in at ter vpliv upravljanja z vedri na veljavnost iteratorjev.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

#include <unordered_map>
std::unordered_map<Key, T> map;

std::unordered_map<Key, T> iz <unordered_map> shrani največ eno vrednost za vsak enakovreden ključ. Vrstni red iteriranja ni določen. Iskanje in vstavljanje imata povprečno zahtevnost O(1), v najslabšem primeru pa O(n). Enakovredni ključi morajo imeti enak hash; enak hash ne pomeni, da sta ključa enakovredna.

find(key) ne vstavi ničesar: vrne iterator ali end(), iterator za zadnjim elementom, ki ga ne smemo dereferencirati. operator[] vrne sklic na vrednost in vstavi manjkajoči ključ; pri privzetem alokatorju se nova vrednost inicializira z vrednostjo, zato je za int enaka 0. at(key) ne vstavi ničesar in ob manjkajočem ključu sproži std::out_of_range. emplace(...) vrne par iteratorja in oznake vstavljanja; podvojeni ključ ne prepiše vrednosti.

size() pove število elementov, bucket_count() število vedrov, load_factor() pa povprečno število elementov na vedro. max_load_factor() prebere prag obremenitve; max_load_factor(z) zahteva pozitivno vrednost z. Prag nastavi pred klicem reserve(n), ki načrtuje prostor za skupno n elementov, ne za dodatnih n elementov. Enakovreden je klicu rehash(ceil(n / max_load_factor())). rehash(n) zagotovi vsaj n vedrov in dovolj vedrov za trenutne elemente in prag; natančno število je odvisno od implementacije.

Ponovno zgoščevanje razveljavi iteratorje, ne pa kazalcev ali sklicev na elemente. Sproži ga lahko vstavljanje, tudi prek operator[]. clear() odstrani vse elemente, nastavi size() na 0 in razveljavi sklice na odstranjene elemente; ne obravnavaj ga kot zagotovilo, da bo sproščen ves pomnilnik vsebnika.

Obseg tega zapisa: C++23. Zastavica prevajalnika v repozitoriju ne potrjuje produkcijskega izvajalnega okolja. Izvorno besedilo je razvijajoči se delovni osnutek, ne zamrznjeno besedilo C++23; ta zapis se ne opira na novejše razširitve, prikazane v njem.

Referenčni identifikatorji, zajeti v tem geslu: std::unordered_map::find, std::unordered_map::end, std::unordered_map::clear, std::unordered_map::operator[], std::unordered_map::max_load_factor, std::unordered_map::reserve, std::unordered_map::rehash, std::unordered_map::size, std::unordered_map::load_factor, std::unordered_map::bucket_count, std::unordered_map::at, std::unordered_map::emplace.

Primeri

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

int main() {
    std::unordered_map<std::string, int> counts;
    counts.max_load_factor(0.75f);
    counts.reserve(8);

    counts.emplace("apple", 2);
    ++counts["apple"];
    ++counts["pear"];
    const bool inserted = counts.emplace("apple", 99).second;

    if (auto it = counts.find("apple"); it != counts.end()) {
        std::cout << "apple=" << it->second << '\n';
    }
    std::cout << std::boolalpha << "duplicate inserted=" << inserted << '\n';
    std::cout << "pear=" << counts.at("pear") << '\n';
    std::cout << "size=" << counts.size() << '\n';

    counts.rehash(32);
    std::cout << "buckets>=32=" << (counts.bucket_count() >= 32) << '\n';
    std::cout << "load within limit="
              << (counts.load_factor() <= counts.max_load_factor()) << '\n';

    counts.clear();
    std::cout << "size after clear=" << counts.size() << '\n';
}

Rezultat

apple=3
duplicate inserted=false
pear=1
size=2
buckets>=32=true
load within limit=true
size after clear=0

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri