Docs executáveis de C++: unordered_map

Q: Qual é a diferença entre map e unordered_map em C++?

std::map é uma árvore binária balanceada: as chaves ficam ordenadas e as operações são O(log n). std::unorderedmap é uma tabela hash: as chaves não seguem nenhuma ordem específica, mas a inserção e a busca são em média O(1). Use unorderedmap quando só precisar de busca rápida por chave e não se importar com a ordem; use map quando precisar de iteração ordenada ou consultas por intervalo.

Q: O unordered_map[] insere uma chave se ela não existir?

Sim. m[key] constrói por padrão e insere a chave se ela estiver ausente e, então, retorna uma referência a ela. Isso significa que até um if (m[key] == ...) que parece uma leitura faz o map crescer silenciosamente. Para verificar a existência sem inserir, use m.count(key) ou m.find(key).

Q: O unordered_map é sempre mais rápido que o map em C++?

Não. Ele é O(1) em média, mas o hashing tem um custo extra e um hash ruim (ou chaves adversárias) pode degradar as buscas para O(n). Para maps pequenos, os fatores constantes e o pior comportamento de cache podem fazer um map ordenado ser tão rápido quanto ou mais rápido. Meça o desempenho se isso importar, mas recorra ao unordered_map por padrão quando só precisar de busca por chave.

Quando a ordem não importa

Você acabou de ver std::map, que mantém suas chaves ordenadas usando uma árvore balanceada e oferece operações em O(log n). Mas ordenar tem um custo, e muitas vezes você não se importa com a ordem em que as chaves saem - você só quer perguntar "esta chave está aqui e qual é o seu valor?" o mais rápido possível.

É para isso que serve o std::unordered_map. Ele é uma tabela hash: passa cada chave por uma função hash para decidir onde armazená-la, o que torna a inserção, a busca e a remoção O(1) em média em vez de O(log n). O preço é que a ordem de iteração não é especificada - as chaves saem na ordem em que os buckets as mantiverem.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

A interface é quase idêntica à de map de propósito - muitas vezes você pode trocar uma pela outra apenas mudando o tipo. Inclua <unordered_map> (não <map>), e as chaves saem sem ordenação.

Inserindo e atualizando

Há algumas formas de colocar entradas, e nem todas se comportam da mesma maneira. As duas que você mais vai usar são operator[] e insert:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // criar ou sobrescrever
    votes["alice"] = 5;              // sobrescreve -> 5
    votes.insert({"bob", 2});        // insere apenas se "bob" estiver ausente
    votes.insert({"bob", 99});       // ignorado, "bob" já existe

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, não 99
}

A diferença principal: operator[] sobrescreve um valor existente, enquanto insert deixa intacta uma chave que já exista. Se você estiver em C++17, insert_or_assign(key, value) dá a semântica de "defina isto de qualquer jeito", e try_emplace(key, args...) constrói o valor no local apenas quando a chave é nova - útil para valores caros de construir.

A pegadinha do operator[]: ele insere ao ler

Este é o bug mais comum com unordered_map, então ele ganha sua própria seção. m[key] não é uma leitura pura. Se a chave estiver ausente, ele a constrói por padrão e a insere (um int vira 0, uma string vira "") e então retorna uma referência. Então um código que parece uma busca faz o map crescer sem que você perceba:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // Só queríamos VERIFICAR "y", mas [] o inseriu:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, não 1!
}

seen["y"] criou uma entrada "y" -> 0 só por ser mencionada. Para testar a existência sem alterar o map, use count (retorna 0 ou 1) ou find:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() lê melhor do que count()
    if (seen.contains("x")) cout << "x is here\n";
}

Regra prática: use [] apenas quando pretender criar ou atualizar. Para leituras puras, use count, contains (C++20) ou find.

find e at: buscas seguras

find retorna um iterador para a entrada, ou end() se a chave estiver ausente. Ele nunca insere e permite alcançar tanto a chave quanto o valor por meio de it->first e it->second em uma única busca:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

Quando você sabe que a chave deveria existir e quer uma falha incisiva caso não exista, use at. Diferente de [], at não insere - ele lança std::out_of_range para uma chave ausente:

int p = prices.at("pen");   // ok
int q = prices.at("hat");   // lança std::out_of_range - chave ausente

Então você tem três estilos de busca: [] (insere), at (lança) e find/count (informam a presença sem tocar no map). Escolha aquele cujo modo de falha combine com a sua intenção.

Iterando e removendo

Um laço for baseado em intervalo com structured bindings é a forma limpa de percorrer cada entrada. Lembre-se de que a ordem é arbitrária - nunca confie nela:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // a ordem não é especificada
    }
}

Para remover uma entrada, erase recebe uma chave diretamente e retorna quantas foram removidas (0 ou 1). Uma pegadinha importante: remover durante a iteração invalida apenas o iterador do elemento removido em um unordered_map, então use o valor de retorno de erase(it) para avançar com segurança:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Remove todo time com pontuação abaixo de 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase retorna o próximo iterador válido
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

Escrever no estilo wins.erase(it++) ou fazer ++it depois de um erase(it) simples é a clássica armadilha do iterador inválido - o iterador removido está morto, então sempre pegue o iterador retornado por erase.

map ou unordered_map?

Ambos armazenam pares chave-valor com uma API similar, então a escolha se resume ao que você precisa:

// std::map            -> chaves ordenadas, O(log n), consultas por intervalo (lower_bound)
// std::unordered_map  -> sem ordem,        O(1) médio, busca simples mais rápida

Recorra ao unordered_map quando só precisar de busca rápida por chave e a ordem for irrelevante (contar frequências de palavras, cache, deduplicação). Escolha map quando precisar das chaves em ordem, quiser iterar ordenadamente ou fazer consultas por intervalo. Duas ressalvas para unordered_map: seu O(1) é uma média - um hash ruim pode degradá-lo - e um tipo de chave personalizado precisa de uma especialização de hash ou um functor de hash, enquanto o map só precisa de operator<.

A seguir: Set

Você já viu as duas variações de contêiner chave-valor. Às vezes, porém, você não precisa de um valor - só importa se algo está presente, como uma coleção de tags únicas ou IDs visitados. A seguir, vamos ver std::set (e seu primo baseado em hash unordered_set), que armazenam apenas chaves e as mantêm únicas automaticamente.

Perguntas frequentes

Qual é a diferença entre map e unordered_map em C++?

std::map é uma árvore binária balanceada: as chaves ficam ordenadas e as operações são O(log n). std::unordered_map é uma tabela hash: as chaves não seguem nenhuma ordem específica, mas a inserção e a busca são em média O(1). Use unordered_map quando só precisar de busca rápida por chave e não se importar com a ordem; use map quando precisar de iteração ordenada ou consultas por intervalo.

O unordered_map[] insere uma chave se ela não existir?

Sim. m[key] constrói por padrão e insere a chave se ela estiver ausente e, então, retorna uma referência a ela. Isso significa que até um if (m[key] == ...) que parece uma leitura faz o map crescer silenciosamente. Para verificar a existência sem inserir, use m.count(key) ou m.find(key).

O unordered_map é sempre mais rápido que o map em C++?

Não. Ele é O(1) em média, mas o hashing tem um custo extra e um hash ruim (ou chaves adversárias) pode degradar as buscas para O(n). Para maps pequenos, os fatores constantes e o pior comportamento de cache podem fazer um map ordenado ser tão rápido quanto ou mais rápido. Meça o desempenho se isso importar, mas recorra ao unordered_map por padrão quando só precisar de busca por chave.

Conceitos relacionados