6. map e set¶
Vídeos
13 - Maps Parte 1 · 14 - Maps Parte 2 · 15 - Maps Parte 3 · 16-19 - Sets
O problema que std::map resolve¶
Em C, "associar uma chave a um valor" normalmente vira dois vetores paralelos (um de chaves, um de valores) que você percorre em paralelo torcendo para nunca dessincronizar:
char* nomes[100];
int idades[100];
int quantidade = 0;
// buscar a idade de "Ana" = percorrer nomes[] procurando "Ana", depois olhar idades[] no mesmo indice
std::map<Chave, Valor> guarda pares chave→valor diretamente, ordenados pela chave, com busca eficiente (O(log n), bem mais rápido que percorrer um vetor):
#include <map>
#include <string>
#include <iostream>
std::map<std::string, int> idades;
idades["Ana"] = 25;
idades["Bruno"] = 30;
idades["Carla"] = 22;
std::cout << idades["Ana"] << "\n"; // 25
Por baixo dos panos, cada elemento de um map é um std::pair<const Chave, Valor> — o mesmo pair do capítulo 3.
Operações essenciais¶
std::map<std::string, int> estoque;
estoque["parafuso"] = 100; // insere ou atualiza
estoque["prego"] = 50;
estoque.size(); // 2
estoque.count("parafuso"); // 1 (existe) ou 0 (nao existe)
// count() e a forma segura de checar existencia: nao cria nada
if (estoque.count("parafuso") == 1) {
std::cout << "parafuso: " << estoque["parafuso"] << "\n"; // parafuso: 100
}
estoque.erase("prego"); // remove pela chave
Repare que o erase do map recebe a chave, e não uma posição — é por isso
que ele funciona sem nada novo: basta dizer qual chave tirar, e se ela não
existir não acontece nada. O erase de vector é diferente, porque num vector
não há chave, só posição, e posição se indica com um iterador; esse fica para o
capítulo 8.
Cuidado com [] em map: estoque["arruela"] — se a chave "arruela" não existir, o map a cria automaticamente com valor padrão (0 para int). Isso é conveniente para inserir/atualizar, mas perigoso se sua intenção era só checar se a chave existe: if (estoque["algo"] > 0) cria a entrada "algo" mesmo que você só quisesse ler. Para checar existência sem criar nada, use .count().
Percorrendo um map¶
Um map itera em ordem crescente de chave, automaticamente:
Padrão estruturado (C++17, o mesmo padrão do curso):
Exemplo completo: contagem de frequência¶
Um dos usos mais comuns de map é contar ocorrências:
#include <map>
#include <string>
#include <vector>
std::map<std::string, int> conta_palavras(const std::vector<std::string>& palavras) {
std::map<std::string, int> contagem;
for (const std::string& palavra : palavras) {
contagem[palavra]++; // cria com 0 se nao existe, depois soma 1
}
return contagem;
}
// conta_palavras({"pao", "leite", "pao"}) -> {"leite": 1, "pao": 2}
Repare que a contagem inteira cabe em contagem[palavra]++. Isso funciona graças ao comportamento de [] que descrevemos com cuidado acima — na primeira vez que uma palavra aparece, contagem[palavra] cria a entrada com valor 0, e o ++ logo em seguida a leva para 1. Sem esse detalhe, seria preciso checar antes se a chave já existe e tratar os dois casos separadamente.
(Partir um texto corrido em palavras é outro assunto — isso vem no capítulo 7, junto com a leitura de arquivos.)
std::set: só chaves, sem valor associado¶
std::set<T> é como um map<T, /* sem valor */> — guarda um conjunto de valores únicos, ordenados, sem duplicatas:
#include <set>
std::set<int> numeros;
numeros.insert(5);
numeros.insert(3);
numeros.insert(5); // ja existe -- ignorado, set continua com um so 5
numeros.insert(8);
numeros.size(); // 3, nao 4
numeros.count(5); // 1
numeros.count(100); // 0
for (int n : numeros) {
std::cout << n << " "; // 3 5 8 -- em ordem crescente, automaticamente
}
Use set quando o que importa é "esse valor já apareceu?" e não precisa de nenhuma informação associada — por exemplo, remover duplicatas de uma lista, ou verificar se um CPF já foi cadastrado.
std::set<std::string> visitados;
std::vector<std::string> paginas = {"home", "sobre", "home", "contato"};
for (const auto& p : paginas) {
if (visitados.count(p) == 0) {
std::cout << "primeira vez em: " << p << "\n";
visitados.insert(p);
}
}
unordered_map/unordered_set: quando a ordem não importa¶
std::map/std::set mantêm as chaves ordenadas, o que tem um custo: O(log n) por operação. Se você não precisa da ordem (só quer buscar rápido), std::unordered_map/std::unordered_set (de <unordered_map>/<unordered_set>) usam uma tabela hash e são O(1) em média:
#include <unordered_map>
std::unordered_map<std::string, int> cache;
cache["resultado_caro"] = 42; // mesma interface do map, sem garantia de ordem
Regra prática: comece com map/set (mais previsível, ordem determinística facilita depurar e testar). Troque para a versão unordered_ só se performance for medida e for um gargalo real — otimização prematura tende a trocar clareza por um ganho que você nem precisava.
Erros comuns¶
Usar estoque["chave"] para checar existência e criar entradas indesejadas sem perceber — descrito acima. Use .count() para checagem pura.
"error: no match for ‘operator[]’" com chave que não é comparável — map/set ordenados exigem que a chave suporte < (comparação de "menor que"). Tipos básicos (int, std::string) já suportam; uma struct sua só suporta se você definir operator< (você vai ver sobrecarga de operadores na Unidade 5) ou usar unordered_map/unordered_set com uma função de hash.
Esperar que unordered_map preserve ordem de inserção — ele não preserva nada, nem ordem alfabética nem ordem de inserção. Se a ordem importa, use map.
Resumo¶
std::map<K, V>associa chave a valor, mantendo ordem crescente de chave, busca O(log n).[]cria a chave se ela não existir — ótimo para inserir/atualizar, perigoso para só checar existência..count()checa existência sem criar nada.std::set<T>guarda valores únicos ordenados — útil para "já vi isso?" sem informação associada.unordered_map/unordered_settrocam ordem por velocidade média O(1); comece com a versão ordenada e só troque se performance for um problema medido.