Buscas Instantâneas — map, set e suas Versões Hash

Nos artigos O Array que Cresce Sozinho — std::vector a Fundo e Texto como Coleção — std::string Revisitada e o std::string_view dominamos os containers sequenciais contíguos: vector e string. Eles são perfeitos quando você tem uma sequência e quer percorrê-la ou acessá-la por posição. Mas uma classe imensa de problemas não é sobre posição, e sim sobre associação: dado um nome, qual o telefone? Dado um produto, qual o estoque? Este elemento já foi visto? Em C, responder isso rápido exigia construir tabelas hash ou árvores de busca à mão — centenas de linhas de código delicado, com gestão de colisões e balanceamento. A STL entrega tudo isso pronto nos containers associativos. Hoje você conhece os quatro principais — map, set, unordered_map, unordered_set — e, o mais importante, aprende a escolher entre eles com critério.

map: associando chaves a valores

O std::map guarda pares chave→valor, mantidos ordenados pela chave. É o dicionário do C++: você indexa pela chave e obtém o valor, em tempo logarítmico:

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

int main() {
    // map<Chave, Valor>: aqui, nome (string) → idade (int)
    std::map<std::string, int> idade;

    idade["Ana"] = 30;         // insere ou atualiza
    idade["Bruno"] = 25;
    idade["Carla"] = 28;

    // Acesso pela chave:
    std::cout << "Ana tem " << idade["Ana"] << " anos\n";   // 30

    // Percorrer: vem SEMPRE em ordem de chave (alfabética aqui).
    for (const auto& par : idade)
        std::cout << par.first << ": " << par.second << '\n';
    // Ana: 30 / Bruno: 25 / Carla: 28 (ordenado)

    return 0;
}

Cada elemento é um par com .first (a chave) e .second (o valor). A iteração vem sempre ordenada pela chave — uma propriedade útil quando você precisa de ordem, mas que tem um custo. Uma pegadinha importante do operator[]: acessar uma chave que não existe com [] cria a chave com um valor padrão, o que às vezes surpreende. Para só consultar sem criar, use find:

#include <map>
#include <string>
#include <iostream>
int main() {
    std::map<std::string, int> idade = {{"Ana", 30}};

    // find devolve um iterador; se não achar, devolve end()
    auto it = idade.find("Xavier");
    if (it == idade.end())
        std::cout << "Xavier não está no mapa\n";   // não cria a entrada

    // CUIDADO: isto CRIARIA "Yara" com valor 0 só por consultar!
    // if (idade["Yara"] == 0) ...
    return 0;
}

set: apenas as chaves, sem repetição

O std::set é como um map sem valores — guarda apenas chaves únicas e ordenadas. Serve para responder "este elemento já apareceu?" e para eliminar duplicatas:

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> visitados;

    visitados.insert("a.com");
    visitados.insert("b.com");
    visitados.insert("a.com");   // duplicata: ignorada silenciosamente

    std::cout << "sites únicos: " << visitados.size() << '\n';   // 2

    // Testar pertencimento:
    if (visitados.count("a.com"))   // count devolve 0 ou 1 num set
        std::cout << "a.com já foi visitado\n";

    for (const auto& s : visitados)
        std::cout << s << '\n';   // ordenado: a.com, b.com
    return 0;
}

Inserir uma duplicata é simplesmente ignorado — o set garante unicidade. É a estrutura ideal para "conjunto de coisas vistas".

As versões hash: unordered_map e unordered_set

map e set são baseados em árvores balanceadas, o que dá busca em tempo logarítmico e mantém tudo ordenado. Mas se você não precisa de ordem e quer as buscas mais rápidas possíveis, existem as versões hash: std::unordered_map e std::unordered_set. Elas usam tabelas hash internamente — as mesmas que você fazia à mão em C — e oferecem busca em tempo constante em média, ao custo de não manter ordem alguma:

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

int main() {
    // Mesma interface do map, mas SEM ordem e com busca O(1) em média.
    std::unordered_map<std::string, int> estoque;
    estoque["parafuso"] = 500;
    estoque["porca"] = 300;
    estoque["arruela"] = 800;

    std::cout << "parafusos: " << estoque["parafuso"] << '\n';   // 500

    // A iteração vem em ordem ARBITRÁRIA (dependente do hash), não alfabética.
    for (const auto& [item, qtd] : estoque)   // structured bindings (C++17) — Fase 6
        std::cout << item << ": " << qtd << '\n';
    return 0;
}

A interface é quase idêntica à do map — o que você aprendeu se transfere. A diferença é o comportamento: unordered_map é tipicamente mais rápido para buscas, mas itera em ordem imprevisível. (De passagem, usei ali o [item, qtd] — structured bindings, um recurso do C++17 que desempacota o par automaticamente; ele é tema da Fase 6, mas é conveniente demais para esconder.)

Escolhendo com critério: a tabela de decisão

Aqui está o valor prático da aula — como decidir, e prometo a honestidade dos trade-offs. A escolha se resume a duas perguntas. Primeira: preciso de associação chave→valor, ou só do conjunto de chaves? Se precisa do valor, é map/unordered_map; se só quer saber quais chaves existem (pertencimento, unicidade), é set/unordered_set. Segunda: preciso que a iteração venha ordenada? Se sim, use as versões ordenadas (map/set, baseadas em árvore, busca O(log n)); se a ordem é irrelevante, use as versões hash (unordered_*, busca O(1) média), que costumam ser mais rápidas. comece com a versão unordered_ quando não precisar de ordem — é a mais rápida na maioria dos casos —, e escolha a versão ordenada quando a ordem por chave for parte do que você precisa. E, como sempre no C++: se o desempenho for crítico, meça as duas com seus dados reais, porque o comportamento do hash depende das suas chaves.

Os containers associativos aposentam de vez as tabelas hash e árvores de busca escritas à mão. A escolha entre as duas famílias é concreta: map e set mantêm a ordem e garantem custo logarítmico, enquanto as versões unordered_ entregam busca praticamente constante em média e nenhuma ordem — com a ressalva de que o pior caso degrada se a função de espalhamento for ruim para os dados em uso. Precisar percorrer em ordem costuma decidir a questão sozinho.

Em três artigos, uma categoria inteira de código artesanal saiu de cena: array dinâmico, texto e associações agora vêm prontos, testados e com gestão de memória automática. É a diferença mais visível entre escrever C e escrever C++ — não o que se pode fazer, mas o quanto já está feito.

Fontes e leituras recomendadas

• cppreference.com/w/cpp/container/map e /w/cpp/container/unordered_map: as referências completas dos containers associativos, com garantias de complexidade.
• cppreference.com/w/cpp/container/set e /w/cpp/container/unordered_set: as referências dos conjuntos ordenados e hash.
• Bjarne Stroustrup, A Tour of C++ (3ª ed.), capítulo sobre containers: a comparação entre containers ordenados e não-ordenados pelo criador.
• Scott Meyers, Effective STL (2001), Itens 19–25 (escolha de containers associativos): conselhos práticos sobre map vs set e quando usar cada um.
• ISO C++ Core Guidelines, regra SL.con: as diretrizes gerais sobre seleção de containers da biblioteca padrão.

Exercícios

Exercício 1

Use um std::map<std::string, int> para contar a frequência de palavras: leia palavras até "fim" e, ao final, imprima cada palavra e sua contagem. (Dica: mapa[palavra]++ funciona porque uma chave nova nasce com 0.)

#include <iostream>
#include <map>
#include <string>
int main() {
    std::map<std::string, int> freq;
    std::string palavra;
    std::cout << "Digite palavras (fim para parar):\n";
    while (std::cin >> palavra && palavra != "fim")
        freq[palavra]++;   // chave nova nasce com 0, então ++ a leva a 1
    for (const auto& [p, n] : freq)   // ordenado alfabeticamente
        std::cout << p << ": " << n << '\n';
    return 0;
}

Exercício 2

Explique o perigo do operator[] do map num contexto de consulta. Reescreva o trecho abaixo para verificar a existência de uma chave sem criá-la acidentalmente.

std::map<std::string, int> m = {{"a", 1}};
if (m["b"] == 0) { /* "b" existe e é 0, ou acabei de criá-la? */ }

std::map<std::string, int> m = {{"a", 1}};
auto it = m.find("b");
if (it != m.end()) {
    // "b" realmente existe; seu valor é it->second
} else {
    // "b" não existe — e NÃO foi criada
}

Exercício 3

Dado um std::vector<int> possivelmente com repetições, escreva uma função que devolva quantos valores distintos ele contém, usando um std::set. Explique por que o set torna isso trivial.

#include <set>
#include <vector>
int distintos(const std::vector<int>& v) {
    std::set<int> unicos(v.begin(), v.end());  // insere todos; duplicatas são ignoradas
    return static_cast<int>(unicos.size());
}

Exercício 4

Você precisa de um container que associe CPF (string) a um objeto Cliente, com buscas as mais rápidas possíveis, e a ordem de iteração é irrelevante. Qual container escolher e por quê? E se você precisasse listar os clientes em ordem alfabética de CPF ao final?

Exercício 5

Explique, em termos de complexidade e de ordenação, o trade-off entre std::map e std::unordered_map. Descreva um cenário concreto em que a versão ordenada é a escolha certa apesar de ser teoricamente mais lenta na busca.