C++ std::map: claves, valores, búsqueda e inserción

Buscar cosas por clave

Un vector es ideal cuando indexas por posición: el elemento 0, el elemento 1, etc. Pero a menudo no tienes una posición, sino un nombre y quieres lo que va asociado a él: un usuario y su puntuación, una palabra y su número de apariciones, un código de país y su capital. Recorrer un vector para encontrar una coincidencia es O(n) y se vuelve lento enseguida.

std::map resuelve esto. Almacena pares clave-valor, los mantiene ordenados por clave y te permite buscar un valor por su clave en tiempo O(log n). Incluye <map> para usarlo:

#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> se lee como "un map de claves string a valores int". Las claves son únicas: si asignas dos veces a la misma clave, gana el segundo valor. Internamente, un map es un árbol binario de búsqueda equilibrado, por eso todo se mantiene ordenado y las búsquedas son logarítmicas en lugar de constantes.

Insertar elementos

Hay varias formas de añadir entradas, y la diferencia entre ellas importa. La más común es operator[], que crea la clave si no existe y devuelve una referencia a la que puedes asignar:

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

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

    inventory["apples"] = 12;     // crear + asignar
    inventory["apples"] += 3;     // leer-modificar-escribir, ahora 15

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

Si quieres una inserción que se niegue a sobrescribir una clave existente, usa insert o emplace. Ambas devuelven un pair cuyo .second es un bool que te dice si la inserción ocurrió realmente:

#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 ya existe
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, sin cambios
}

Usa [] cuando quieras que "gane la última escritura", e insert/emplace cuando una clave existente deba quedarse intacta.

El fallo de operator[]: inserta al leer

Este es el error más común con map. operator[] no es una lectura pura: si la clave no existe, la inserta silenciosamente con un valor construido por defecto (0 para int, "" para string, etc.) y devuelve una referencia a ese valor. Así que el simple hecho de comprobar una clave con [] modifica el map:

map<string, int> m;
if (m["maybe"] == 0) {   // BUG: esto acaba de crear "maybe" -> 0
    // ...
}
cout << m.size();        // 1, no 0 - insertaste una clave por accidente

Esto también te muerde con un const map, donde operator[] ni siquiera compila porque podría necesitar insertar. Para leer sin insertar, usa find, count/contains o at:

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

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

    // find: devuelve un iterador, == end() si no existe
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) o count (cualquier versión)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: lanza std::out_of_range si no existe - nunca inserta
    cout << "a = " << m.at("a") << "\n";
}

Regla práctica: si tu intención es leer, nunca recurras a []. Usa at cuando la clave deba existir, y find/contains cuando podría no existir.

Iterar en orden

Como un map está respaldado por un árbol, iterarlo recorre las claves en orden ascendente siempre, y gratis. Cada elemento es un pair<const Key, Value>, así que usa un enlace estructurado para desempaquetar la clave y el valor de forma limpia:

#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]++;   // las claves nuevas empiezan en 0, luego ++
    }

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

Fíjate en que la clave del enlace es const: puedes cambiar un valor en el bucle con auto&, pero nunca puedes cambiar una clave en su sitio (eso rompería el orden). La salida sale en orden alfabético (blue, sea, sky) sin ningún paso de ordenación, que es exactamente por lo que la gente elige map frente a una tabla hash cuando importa recorrer en orden.

Ese idioma wordCount[w]++ es también el uso canónico del comportamiento de inserción al acceder: aquí quieres que una clave nueva empiece en 0, así que [] es la herramienta adecuada.

Eliminar elementos y medir el tamaño

Elimina por clave con erase, que devuelve cuántos elementos se eliminaron (0 o 1 en un map). También puedes borrar mediante un iterador obtenido con find. Comprueba el estado del contenedor con size() y 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 (no estaba)

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

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

Un fallo al borrar dentro de un bucle: m.erase(it) invalida it, así que no puedes hacer ++it después. El patrón seguro desde C++11 es it = m.erase(it), que devuelve un iterador al siguiente elemento. Para una eliminación condicional de una sola pasada por todo el map, std::erase_if(m, predicate) (C++20) es más limpio.

Siguiente: unordered_map

std::map te da claves ordenadas y operaciones O(log n) predecibles, pero pagas ese orden en cada búsqueda. Cuando no te importa el orden de las claves y solo quieres las búsquedas más rápidas posibles, unordered_map cambia el árbol ordenado por una tabla hash: acceso O(1) en promedio. A continuación veremos cómo funciona, cuándo su tiempo constante medio supera al logaritmo de map y las trampas del hashing (tipos de clave personalizados, colisiones en el peor caso) que conlleva.