Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::unordered_map — hašovacia mapa s jedinečnými kľúčmi

std::unordered_map ukladá dvojice kľúč–hodnota bez zaručeného poradia. Zistite, ako vyhľadávať bez vloženia, aký je rozdiel medzi operator[] a at a ako správa bucketov ovplyvňuje platnosť iterátorov.

Verzia: C++23; repository compiler flag, production runtime not attested

Syntax

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

std::unordered_map<Key, T> z <unordered_map> ukladá pre každý ekvivalentný kľúč najviac jednu hodnotu. Poradie iterácie nie je určené. Vyhľadávanie a vkladanie majú priemernú zložitosť O(1) a v najhoršom prípade O(n). Ekvivalentné kľúče musia mať rovnaký hash; rovnaký hash však neznamená, že kľúče sú ekvivalentné.

find(key) nič nevkladá: vráti iterátor alebo end(), iterátor za posledným prvkom, ktorý sa nesmie dereferencovať. operator[] vracia referenciu na hodnotu a vloží chýbajúci kľúč; pri predvolenom alokátore sa nová hodnota inicializuje hodnotou, takže pre int je to 0. at(key) nič nevkladá a pri chýbajúcom kľúči vyhodí std::out_of_range. emplace(...) vráti dvojicu iterátora a príznaku vloženia; duplicitný kľúč hodnotu neprepíše.

size() udáva počet prvkov, bucket_count() počet bucketov a load_factor() priemerný počet prvkov na bucket. max_load_factor() číta limit zaťaženia; max_load_factor(z) vyžaduje kladné z. Limit nastavte pred reserve(n), ktoré plánuje miesto pre celkovo n prvkov, nie pre ďalších n prvkov. Zodpovedá volaniu rehash(ceil(n / max_load_factor())). rehash(n) zabezpečí aspoň n bucketov a dostatok bucketov pre súčasné prvky a limit; presný počet závisí od implementácie.

Rehashovanie zneplatňuje iterátory, nie však ukazovatele ani referencie na prvky. Môže ho vyvolať vkladanie vrátane vkladania cez operator[]. clear() odstráni všetky prvky, nastaví size() na 0 a zneplatní odkazy na odstránené prvky; nepovažujte ho za záruku uvoľnenia celej pamäte kontajnera.

Rozsah tohto záznamu: C++23. Príznak kompilátora v repozitári nepotvrdzuje produkčné runtime prostredie. Zdrojový text je vyvíjajúci sa pracovný návrh, nie zmrazený text C++23; tento záznam sa neopiera o novšie rozšírenia, ktoré sú v ňom uvedené.

Referenčné identifikátory zahrnuté v tomto hesle: 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.

Príklady

#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';
}

Výsledok

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

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje