Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::unordered_map — hash mapa s jedinstvenim ključevima

std::unordered_map pohranjuje parove ključ-vrijednost bez zajamčenog redoslijeda. Saznajte kako pretraživati bez umetanja, koja je razlika između operator[] i at te kako upravljanje spremnicima utječe na valjanost iteratora.

Verzija: 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> pohranjuje najviše jednu vrijednost za svaki ekvivalentan ključ. Redoslijed iteracije nije određen. Pretraživanje i umetanje imaju prosječan trošak O(1), a u najgorem slučaju O(n). Ekvivalentni ključevi moraju imati isti hash; isti hash ne znači da su ključevi ekvivalentni.

find(key) ne umeće ništa: vraća iterator ili end(), iterator iza posljednjeg elementa koji se ne smije dereferencirati. operator[] vraća referencu na vrijednost i umeće ključ koji nedostaje; uz zadani alokator nova se vrijednost inicijalizira vrijednošću, pa je za int jednaka 0. at(key) ne umeće ništa i baca std::out_of_range ako ključ nedostaje. emplace(...) vraća par iteratora i oznake umetanja; duplikat ne prepisuje vrijednost.

size() daje broj elemenata, bucket_count() broj spremnika, a load_factor() prosječan broj elemenata po spremniku. max_load_factor() čita prag opterećenja; max_load_factor(z) zahtijeva pozitivan z. Postavite prag prije reserve(n), koji planira prostor za ukupno n elemenata, a ne za dodatnih n. To je ekvivalentno pozivu rehash(ceil(n / max_load_factor())). rehash(n) osigurava najmanje n spremnika i dovoljno spremnika za postojeće elemente i prag; točan broj ovisi o implementaciji.

Ponovno hashiranje poništava iteratore, ali ne i pokazivače ni reference na elemente. Umetanje, uključujući putem operator[], može ga pokrenuti. clear() uklanja sve elemente, postavlja size() na 0 i poništava reference na uklonjene elemente; nemojte ga smatrati jamstvom da će se osloboditi sva memorija spremnika.

Opseg ovog zapisa: C++23. Zastavica prevoditelja u repozitoriju ne potvrđuje produkcijsko okruženje izvođenja. Izvorni tekst razvojni je nacrt, a ne zamrznuti tekst C++23; ovaj se zapis ne oslanja na novija proširenja prikazana u njemu.

Referentni identifikatori obuhvaćeni ovim unosom: 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.

Primjeri

#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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori