Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::unordered_map — mapa de hash com chaves únicas

std::unordered_map armazena pares chave-valor sem garantir uma ordem. Aprende a pesquisar sem inserir, a diferença entre operator[] e at e como a gestão dos buckets afeta a validade dos iteradores.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

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

std::unordered_map<Key, T> de <unordered_map> armazena, no máximo, um valor por cada chave equivalente. A ordem de iteração não é especificada. A pesquisa e a inserção têm um custo médio de O(1) e um custo de O(n) no pior caso. As chaves equivalentes têm de ter o mesmo hash; hashes iguais não implicam que as chaves sejam equivalentes.

find(key) não insere: devolve um iterador ou end(), o iterador a seguir ao último elemento, que não deve ser desreferenciado. operator[] devolve uma referência ao valor e insere uma chave em falta; com o alocador predefinido, o novo valor é inicializado por valor, pelo que é 0 para int. at(key) não insere e lança std::out_of_range se a chave não existir. emplace(...) devolve um par com um iterador e um indicador de inserção; um duplicado não substitui o valor.

size() indica o número de elementos, bucket_count() o número de buckets e load_factor() o número médio de elementos por bucket. max_load_factor() consulta o limite de carga; max_load_factor(z) exige um z positivo. Define o limite antes de reserve(n), que prepara espaço para n elementos no total, e não para mais n elementos. É equivalente a rehash(ceil(n / max_load_factor())). rehash(n) garante pelo menos n buckets e um número suficiente para os elementos atuais e o limite; a quantidade exata depende da implementação.

O rehashing invalida iteradores, mas não ponteiros nem referências aos elementos. Uma inserção, incluindo através de operator[], pode desencadeá-lo. clear() remove todos os elementos, faz com que size() passe a 0 e invalida referências aos elementos removidos; não o consideres uma garantia de libertação de toda a memória do contentor.

Âmbito desta entrada: C++23. Uma opção do compilador no repositório não atesta o ambiente de execução de produção. O texto-fonte é um rascunho em evolução, não um texto C++23 congelado; esta entrada não depende das extensões mais recentes aí apresentadas.

Identificadores de referência abrangidos por esta entrada: 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.

Exemplos

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

Resultado

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

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes