Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::unordered_map — hašovací mapa s jedinečnými klíči

std::unordered_map ukládá dvojice klíč–hodnota bez zaručeného pořadí. Zjistěte, jak vyhledávat bez vložení, jaký je rozdíl mezi operator[] a at a jak správa bucketů ovlivňuje platnost iterátorů.

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

Syntaxe

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

std::unordered_map<Key, T> z <unordered_map> ukládá pro každý ekvivalentní klíč nejvýše jednu hodnotu. Pořadí iterace není určeno. Vyhledávání a vkládání mají průměrnou složitost O(1) a v nejhorším případě O(n). Ekvivalentní klíče musí mít stejný hash; shodný hash ale neznamená, že jsou klíče ekvivalentní.

find(key) nic nevkládá: vrací iterátor nebo end(), iterátor za posledním prvkem, který se nesmí dereferencovat. operator[] vrací referenci na hodnotu a vloží chybějící klíč; při použití výchozího alokátoru se nová hodnota inicializuje hodnotou, takže pro int je to 0. at(key) nic nevkládá a při chybějícím klíči vyvolá std::out_of_range. emplace(...) vrací dvojici iterátoru a příznaku vložení; duplicitní klíč hodnotu nepřepíše.

size() udává počet prvků, bucket_count() počet bucketů a load_factor() průměrný počet prvků na bucket. max_load_factor() čte limit zatížení; max_load_factor(z) vyžaduje kladné z. Limit nastavte před reserve(n), které plánuje místo pro celkem n prvků, nikoli pro dalších n prvků. Odpovídá volání rehash(ceil(n / max_load_factor())). rehash(n) zajistí alespoň n bucketů a dostatek bucketů pro současné prvky a limit; přesný počet závisí na implementaci.

Rehashování zneplatňuje iterátory, nikoli však ukazatele ani reference na prvky. Může k němu dojít při vkládání, včetně vkládání pomocí operator[]. clear() odstraní všechny prvky, nastaví size() na 0 a zneplatní odkazy na odstraněné prvky; nepovažujte jej za záruku uvolnění veškeré paměti kontejneru.

Rozsah tohoto záznamu: C++23. Příznak kompilátoru v repozitáři nepotvrzuje produkční běhové prostředí. Zdrojový text je vyvíjející se pracovní návrh, nikoli zmrazený text C++23; tento záznam se neopírá o novější rozšíření, která jsou v něm uvedena.

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.

Pří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ýsledek

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ýsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje