C++ std::unordered_map

O std::map guarda pares chave → valor sempre em ordem alfabética. Manter essa ordem tem um custo: a cada busca, ele compara a chave com várias outras. O std::unordered_map ("map não ordenado") abre mão da ordem e, em troca, acha a chave quase de uma vez só, com uma conta. Por fora, os dois se usam do mesmo jeito: [], at, find, contains, erase. Por dentro, é outra máquina: uma tabela de espalhamento.

Todos os programas desta aula foram compilados com o g++ 15.2 na máquina fictícia da Ana, na pasta ~/cpp/umap, com g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa. Leia antes a aula std::map: esta aula se apoia nela.

A ideia: o vestiário com armários numerados

No clube, o vestiário tem 13 armários numerados de 0 a 12. A regra para escolher o armário é uma conta com o nome da pessoa: some o "valor" das letras do nome e pegue o resto da divisão por 13. A Ana sempre cai no armário 5, o Bruno sempre no 10. Para achar as coisas da Ana, ninguém procura armário por armário: faz a conta com "Ana", dá 5, abre o 5.

Repare em três coisas:

• Achar é rápido: uma conta e um armário, não importa se há 10 ou 10 mil sócios.
• Não há ordem alfabética: olhando os armários do 0 ao 12, os nomes aparecem na ordem que a conta decidiu.
• Dois nomes podem cair no mesmo armário (uma "colisão"). Tudo bem: o armário guarda os dois, e você confere qual é qual. Se começar a encher demais, o clube constrói um vestiário maior e redistribui todo mundo, e aí cada um pode cair num número diferente.

1. A ordem "bagunçada"

A Ana pôs o mesmo estoque num map e num unordered_map e mostrou as chaves dos dois:

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>

int main() {
    std::map<std::string, int> m{
        {"maçã", 12}, {"banana", 30}, {"pera", 8}, {"uva", 40}, {"kiwi", 5}};
    std::unordered_map<std::string, int> u{
        {"maçã", 12}, {"banana", 30}, {"pera", 8}, {"uva", 40}, {"kiwi", 5}};

    std::cout << "map:           ";
    for (const auto& [nome, qtd] : m) {
        std::cout << nome << ' ';
    }
    std::cout << "\nunordered_map: ";
    for (const auto& [nome, qtd] : u) {
        std::cout << nome << ' ';
    }
    std::cout << '\n';
}

#include <unordered_map>

O unordered_map tem cabeçalho próprio (não vem com o <map>).

std::unordered_map<std::string, int>

Os mesmos dois tipos do map: chave e valor.

$ g++ -std=c++23 -Wall -Wextra ordem.cpp -o ordem
$ ./ordem
map:           banana kiwi maçã pera uva
unordered_map: uva pera banana kiwi maçã

O map saiu em ordem alfabética. O unordered_map saiu em uma ordem que não é alfabética, nem a de inserção, nem a contrária: é a ordem das gavetas. Dá para espiar as contas:

#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> estoque{
        {"maçã", 12}, {"banana", 30}, {"pera", 8}};

    std::cout << "gavetas: " << estoque.bucket_count() << '\n';

    std::hash<std::string> espalhar;
    for (const auto& [nome, qtd] : estoque) {
        std::cout << nome << ": hash = " << espalhar(nome)
                  << ", gaveta " << estoque.bucket(nome) << '\n';
    }
}

$ g++ -std=c++23 -Wall -Wextra gavetas.cpp -o gavetas
$ ./gavetas
gavetas: 13
pera: hash = 12384757184466199296, gaveta 10
banana: hash = 4209850087293805843, gaveta 5
maçã: hash = 13674847098208160434, gaveta 11

bucket_count()

Quantas gavetas a tabela tem agora: 13.

std::hash<std::string>

A função de hash que o unordered_map usa para textos (cabeçalho <functional>). Ela transforma "pera" num número enorme. O mesmo texto dá sempre o mesmo número; textos parecidos dão números bem diferentes ("espalhados").

bucket(nome)

Em qual gaveta a chave está. Confira: 12384757184466199296 dividido por 13 deixa resto 10, e a pera está na gaveta 10.

E quando a tabela enche, ela cresce e redistribui tudo. A Ana acrescentou 11 frutas às 3 que já havia:

$ g++ -std=c++23 -Wall -Wextra muda.cpp -o muda
$ ./muda
pera banana maçã (13 gavetas)
acerola kiwi jaca maçã banana pera melão abacate uva limão caqui manga goiaba figo (29 gavetas)

Com 14 itens em 13 gavetas, a tabela passou para 29 gavetas e reorganizou tudo. Repare que até a ordem de pera, banana e maçã entre si mudou.

2. A mesma interface do map

Tudo o que você aprendeu na aula std::map vale aqui: [] (que cria a chave), at (que lança std::out_of_range), contains, find, count, erase, insert, emplace, size. O contador de palavras da aula anterior, trocando só o tipo:

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> contagem;
    std::string palavra;

    while (std::cin >> palavra) {
        ++contagem[palavra];
    }

    std::cout << "Quantos \"o\"? " << contagem.at("o") << '\n';
    std::cout << std::boolalpha << "Tem \"cão\"? " << contagem.contains("cão") << '\n';

    for (const auto& [p, vezes] : contagem) {
        std::cout << p << ": " << vezes << '\n';
    }
}

$ g++ -std=c++23 -Wall -Wextra contar.cpp -o contar
$ echo "o gato e o rato e o queijo" | ./contar
Quantos "o"? 3
Tem "cão"? false
queijo: 1                « as mesmas contagens do map, em outra ordem
rato: 1
e: 2
gato: 1
o: 3

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, std::string> agenda;
    agenda["Ana"] = "9999-1111";
    agenda["Carla"] = "9888-2222";

    std::cout << "Ana: " << agenda.at("Ana") << '\n';
    if (!agenda.contains("Bruno")) {
        std::cout << "Bruno não está na agenda\n";
    }
}

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, std::string> agenda;
    agenda["Ana"] = "9999-1111";
    agenda["Carla"] = "9888-2222";

    std::cout << "Ana: " << agenda.at("Ana") << '\n';
    if (!agenda.contains("Bruno")) {
        std::cout << "Bruno não está na agenda\n";
    }
}

O que o unordered_map tem a mais são os métodos das gavetas (bucket_count, bucket, load_factor, reserve). O que ele tem a menos: as buscas por faixa que dependem de ordem, como lower_bound ("a primeira chave a partir de "m""), que só o map tem.

3. Mais rápido em média

Para achar uma chave, o map desce por uma árvore ordenada: compara com a chave do meio, vai para a esquerda ou para a direita, compara de novo… Com 100 mil chaves, são umas 17 comparações de texto por busca. O unordered_map faz uma conta de hash, vai na gaveta e compara com o que estiver lá (normalmente um ou dois itens). A Ana mediu 100 mil buscas em cada um:

#include <chrono>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    const int N = 100000;
    std::vector<std::string> nomes;
    for (int i = 0; i < N; ++i) {
        nomes.push_back("produto" + std::to_string(i));
    }

    std::map<std::string, int> m;
    std::unordered_map<std::string, int> u;
    for (const auto& n : nomes) {
        m[n] = 1;
        u[n] = 1;
    }

    using relogio = std::chrono::steady_clock;
    using ms = std::chrono::duration<double, std::milli>;
    long long achados = 0;

    auto t0 = relogio::now();
    for (const auto& n : nomes) achados += m.count(n);
    auto t1 = relogio::now();
    for (const auto& n : nomes) achados += u.count(n);
    auto t2 = relogio::now();

    std::cout << "100 mil buscas no map:           " << ms(t1 - t0).count() << " ms\n";
    std::cout << "100 mil buscas no unordered_map: " << ms(t2 - t1).count() << " ms\n";
    std::cout << "achados: " << achados << '\n';
}

$ g++ -std=c++23 -Wall -Wextra rapidez.cpp -o rapidez
$ ./rapidez
100 mil buscas no map:           176.942 ms
100 mil buscas no unordered_map: 36.7346 ms
achados: 200000

Umas 5 vezes mais rápido, nessa máquina, sem otimização (-O2 deixaria os dois mais rápidos). Os tempos mudam a cada execução; o que vale é a proporção. Em termos de custo (aula list e deque): o map busca em tempo logarítmico, O(log n), que cresce bem devagar; o unordered_map busca em tempo constante em média, O(1).

4. A chave precisa saber "se espalhar"

O map exige que a chave saiba fazer < (para ordenar). O unordered_map exige outra coisa: que exista um std::hash para o tipo da chave (para calcular a gaveta), e que ela saiba fazer == (para conferir dentro da gaveta). Textos, números, char e bool já vêm com hash. Uma struct sua, não:

#include <string>
#include <unordered_map>

struct Produto {
    std::string nome;
    int lote;
};

int main() {
    std::unordered_map<Produto, int> estoque;
    estoque[Produto{"maçã", 1}] = 12;
}

Esse erro tem 84 linhas. Aqui estão as 13 primeiras, que são as que importam:

$ g++ -std=c++23 -Wall -Wextra chave-struct.cpp -o chave-struct 2>&1 | head -n 13
In file included from /usr/include/c++/15/bits/unordered_map.h:33,
                 from /usr/include/c++/15/unordered_map:43,
                 from chave-struct.cpp:2:
/usr/include/c++/15/bits/hashtable.h: In instantiation of ‘class std::_Hashtable<Produto, std::pair<const Produto, int>, std::allocator<std::pair<const Produto, int> >, std::__detail::_Select1st, std::equal_to<Produto>, std::hash<Produto>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >’:
/usr/include/c++/15/bits/unordered_map.h:115:18:   required from ‘class std::unordered_map<Produto, int>’
  115 |       _Hashtable _M_h;
      |                  ^~~~
chave-struct.cpp:10:38:   required from here
   10 |     std::unordered_map<Produto, int> estoque;
      |                                      ^~~~~~~
/usr/include/c++/15/bits/hashtable.h:210:51: error: static assertion failed: hash function must be copy constructible
  210 |       static_assert(is_copy_constructible<_Hash>::value,
      |                                                   ^~~~~

1. required from here: linha 10, a criação do std::unordered_map<Produto, int>.
2. O primeiro error:: static assertion failed: hash function must be copy constructible ("a função de hash precisa poder ser copiada"). Por trás da frase técnica: o std::hash<Produto> não existe de verdade (a biblioteca deixa um "hash desligado" no lugar), então não há hash para copiar.
3. O resto são use of deleted function em cascata, consequência da primeira.

Como consertar, do mais simples ao mais trabalhoso: (1) use como chave um tipo que já tem hash, como um std::string com "maçã-1"; (2) use std::map, ensinando o Produto a fazer < (aula Sobrecarga de Operadores); (3) escreva o seu próprio hash, um assunto mais avançado, que fica para depois.

5. map × unordered_map: qual usar

Regra prática: se você precisa dos itens em ordem (um relatório, uma lista alfabética), ou de buscas por faixa, use map. Se só vai guardar e procurar por chave, e há muitos itens, use unordered_map. Com poucas dezenas de itens, a diferença de velocidade não aparece; escolha pela ordem.

Quando dá errado

Referência rápida

Exercícios

Missão final: a votação da cor da camiseta

azul: 3
verde: 2
rosa: 1
amarelo: 0
cores votadas: 3

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::string voto;
    while (std::cin >> voto) {
        // conte o voto aqui
    }

    std::vector<std::string> cores{"azul", "verde", "rosa", "amarelo"};
    for (const auto& cor : cores) {
        // mostre "cor: votos" sem criar chaves novas
    }

    // mostre "cores votadas: N"
}

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::unordered_map<std::string, int> votos;
    std::string voto;
    while (std::cin >> voto) {
        ++votos[voto];
    }

    std::vector<std::string> cores{"azul", "verde", "rosa", "amarelo"};
    for (const auto& cor : cores) {
        int n = votos.contains(cor) ? votos.at(cor) : 0;
        std::cout << cor << ": " << n << '\n';
    }

    std::cout << "cores votadas: " << votos.size() << '\n';
}

Resumo

• std::unordered_map é uma tabela de espalhamento: um hash da chave decide a gaveta (bucket) onde o par fica.
• Sem ordem: os itens saem na ordem das gavetas, que muda com inserções (rehash) e de uma biblioteca para outra.
• Mais rápido em média (O(1)) que o map (O(log n)) para buscar, inserir e apagar.
• Mesma interface do map: [] (cria a chave!), at, contains, find, erase…
• A chave precisa de std::hash e ==; textos e números já têm.
• Precisa de ordem: map. Só guardar e achar: unordered_map.
• Próximo passo: guardar só chaves, sem valores, em std::set.