C++ std::map: chaves, valores, busca e inserção

Buscar coisas pela chave

Um vector é ótimo quando você indexa por posição: elemento 0, elemento 1, e assim por diante. Mas muitas vezes você não tem uma posição; você tem um nome e quer aquilo que está associado a ele: um usuário e sua pontuação, uma palavra e quantas vezes ela aparece, um código de país e sua capital. Percorrer um vector para encontrar uma correspondência é O(n) e fica lento rapidamente.

std::map resolve isso. Ele armazena pares chave-valor, mantém-nos ordenados pela chave e permite buscar um valor pela sua chave em tempo O(log n). Inclua <map> para usá-lo:

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

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> lê-se como "um map de chaves string para valores int". As chaves são únicas: se você atribuir duas vezes à mesma chave, o segundo valor vence. Internamente, um map é uma árvore binária de busca balanceada, por isso tudo permanece ordenado e as buscas são logarítmicas em vez de constantes.

Inserir elementos

Há algumas formas de adicionar entradas, e a diferença entre elas importa. A mais comum é operator[], que cria a chave se ela não existir e retorna uma referência à qual você pode atribuir:

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

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // criar + atribuir
    inventory["apples"] += 3;     // ler-modificar-escrever, agora 15

    cout << "apples: " << inventory["apples"] << "\n";
}

Se você quer uma inserção que se recuse a sobrescrever uma chave existente, use insert ou emplace. Ambos retornam um pair cujo .second é um bool que informa se a inserção realmente aconteceu:

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada já existe
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, sem mudança
}

Use [] quando "a última escrita vence" for o que você quer, e insert/emplace quando uma chave existente deve ser deixada em paz.

A armadilha do operator[]: ele insere ao ler

Esse é o bug mais comum com map. operator[] não é uma leitura pura: se a chave estiver ausente, ele a insere silenciosamente com um valor construído por padrão (0 para int, "" para string, etc.) e retorna uma referência a esse valor. Então o simples ato de verificar uma chave com [] modifica o map:

map<string, int> m;
if (m["maybe"] == 0) {   // BUG: isso acabou de criar "maybe" -> 0
    // ...
}
cout << m.size();        // 1, não 0 - você inseriu uma chave por acidente

Isso também te pega com um const map, onde operator[] nem sequer compila porque ele pode precisar inserir. Para ler sem inserir, use find, count/contains ou at:

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: retorna um iterador, == end() se ausente
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) ou count (qualquer versão)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: lança std::out_of_range se ausente - nunca insere
    cout << "a = " << m.at("a") << "\n";
}

Regra prática: se sua intenção é ler, nunca recorra a []. Use at quando a chave precisa existir, e find/contains quando ela pode não existir.

Iterar em ordem

Como um map é baseado em árvore, iterá-lo visita as chaves em ordem crescente sempre, e de graça. Cada elemento é um pair<const Key, Value>, então use uma ligação estruturada para desempacotar a chave e o valor de forma limpa:

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // chaves novas começam em 0, depois ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

Repare que a chave na ligação é const: você pode alterar um valor pelo laço com auto&, mas nunca pode alterar uma chave no lugar (isso quebraria a ordenação). A saída sai em ordem alfabética (blue, sea, sky) sem nenhum passo de ordenação, que é exatamente o motivo pelo qual as pessoas escolhem map em vez de uma tabela hash quando a travessia ordenada importa.

Esse idioma wordCount[w]++ é também o uso canônico do comportamento de inserção ao acessar: aqui você quer que uma chave nova comece em 0, então [] é a ferramenta certa.

Remover elementos e medir o tamanho

Remova por chave com erase, que retorna quantos elementos foram removidos (0 ou 1 em um map). Você também pode remover por meio de um iterador obtido com find. Verifique o estado do contêiner com size() e empty():

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (não estava lá)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

Uma armadilha ao remover dentro de um laço: m.erase(it) invalida it, então você não pode fazer ++it depois. O padrão seguro desde C++11 é it = m.erase(it), que retorna um iterador para o próximo elemento. Para uma remoção condicional de uma única passada por todo o map, std::erase_if(m, predicate) (C++20) é mais limpo.

Próximo: unordered_map

std::map te dá chaves ordenadas e operações O(log n) previsíveis, mas você paga por essa ordenação em cada busca. Quando você não se importa com a ordem das chaves e só quer as buscas mais rápidas possíveis, unordered_map troca a árvore ordenada por uma tabela hash: acesso O(1) em média. A seguir veremos como ele funciona, quando seu tempo constante médio supera o logaritmo do map e as armadilhas do hashing (tipos de chave personalizados, colisões no pior caso) que vêm junto.