Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::unordered_map — mapa haszująca o unikalnych kluczach

std::unordered_map przechowuje pary klucz–wartość bez gwarantowanej kolejności. Poznaj wyszukiwanie bez wstawiania, różnice między operator[] i at oraz sterowanie kubełkami i unieważnianie iteratorów.

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

Składnia

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

std::unordered_map<Key, T> z nagłówka <unordered_map> przechowuje najwyżej jedną wartość dla każdego równoważnego klucza. Kolejność iteracji nie jest określona. Wyszukiwanie i wstawianie mają średnio koszt O(1), a w najgorszym przypadku O(n). Równoważne klucze muszą mieć taki sam hash; jednakowy hash nie oznacza równoważności kluczy.

find(key) nie wstawia elementu: zwraca iterator albo end(), czyli iterator za ostatnim elementem, którego nie wolno dereferencjonować. operator[] zwraca referencję do wartości i wstawia brakujący klucz; przy domyślnym alokatorze nowa wartość jest inicjalizowana przez wartość, więc dla int wynosi 0. at(key) nie wstawia i zgłasza std::out_of_range przy braku klucza. emplace(...) zwraca parę iteratora i flagi wstawienia; duplikat nie nadpisuje wartości.

size() podaje liczbę elementów, bucket_count() liczbę kubełków, a load_factor() średnią liczbę elementów na kubełek. max_load_factor() odczytuje próg obciążenia; max_load_factor(z) wymaga dodatniego z. Ustaw próg przed reserve(n), które planuje miejsce na n elementów łącznie, nie na n dodatkowych. Jest równoważne rehash(ceil(n / max_load_factor())). rehash(n) zapewnia co najmniej n kubełków oraz dość kubełków dla obecnych elementów i progu; dokładna liczba zależy od implementacji.

Rehaszowanie unieważnia iteratory, ale nie wskaźniki ani referencje do elementów. Wstawianie, także przez operator[], może je wywołać. clear() usuwa wszystkie elementy, ustawia size() na 0 i unieważnia uchwyty do usuniętych elementów; nie traktuj go jako gwarancji zwolnienia całej pamięci kontenera.

Zakres wpisu: C++23. Flaga kompilatora w repozytorium nie potwierdza środowiska produkcyjnego. Źródło jest rozwijanym szkicem, nie zamrożonym tekstem C++23; wpis nie korzysta z pokazanych tam nowszych rozszerzeń.

Identyfikatory objęte tym wpisem: 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.

Przykłady

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

Wynik

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

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła