Docs ejecutables de C++: unordered_map

Q: ¿Cuál es la diferencia entre map y unordered_map en C++?

std::map es un árbol binario balanceado: las claves se mantienen ordenadas y las operaciones son O(log n). std::unorderedmap es una tabla hash: las claves no siguen ningún orden concreto, pero la inserción y la búsqueda son en promedio O(1). Usa unorderedmap cuando solo necesites búsquedas rápidas por clave y el orden te dé igual; usa map cuando necesites iteración ordenada o consultas por rangos.

Q: ¿unordered_map[] inserta una clave si no existe?

Sí. m[key] construye por defecto e inserta la clave si falta, y luego devuelve una referencia a ella. Eso significa que incluso un if (m[key] == ...) que parece una simple lectura hace crecer el map de forma silenciosa. Para comprobar la pertenencia sin insertar, usa m.count(key) o m.find(key).

Q: ¿unordered_map es siempre más rápido que map en C++?

No. Es O(1) en promedio, pero el hashing tiene una sobrecarga y un mal hash (o claves adversariales) puede degradar las búsquedas a O(n). Para maps pequeños, los factores constantes y un peor comportamiento de caché pueden hacer que un map ordenado sea igual de rápido o incluso más. Mide el rendimiento si te importa, pero recurre a unordered_map por defecto cuando solo necesites búsquedas por clave.

Cuando el orden no importa

Acabas de ver std::map, que mantiene sus claves ordenadas usando un árbol balanceado y te ofrece operaciones en O(log n). Pero ordenar tiene un coste, y muchas veces no te importa en qué orden salen las claves: solo quieres preguntar "¿está esta clave aquí y cuál es su valor?" lo más rápido posible.

Para eso sirve std::unordered_map. Es una tabla hash: pasa cada clave por una función hash para decidir dónde almacenarla, lo que hace que la inserción, la búsqueda y el borrado sean O(1) en promedio en lugar de O(log n). El precio es que el orden de iteración no está especificado: las claves salen en el orden en que los buckets las tengan almacenadas.

#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";
}

La interfaz es casi idéntica a la de map a propósito: a menudo puedes cambiar una por otra solo modificando el tipo. Incluye <unordered_map> (no <map>), y las claves saldrán sin ordenar.

Insertar y actualizar

Hay varias formas de meter entradas, y no todas se comportan igual. Las dos que más usarás son operator[] e insert:

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

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

    votes["alice"] = 3;              // crear o sobrescribir
    votes["alice"] = 5;              // sobrescribe -> 5
    votes.insert({"bob", 2});        // inserta solo si "bob" no está
    votes.insert({"bob", 99});       // ignorado, "bob" ya existe

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

La diferencia clave: operator[] sobrescribe un valor existente, mientras que insert deja intacta una clave que ya exista. Si usas C++17, insert_or_assign(key, value) te da la semántica de "ponlo pase lo que pase", y try_emplace(key, args...) construye el valor en su sitio solo cuando la clave es nueva, algo práctico para valores costosos de construir.

La trampa de operator[]: inserta al leer

Este es el error más común con unordered_map, así que tiene su propia sección. m[key] no es una lectura pura. Si la clave falta, la construye por defecto y la inserta (un int pasa a ser 0, un string pasa a ser "") y luego devuelve una referencia. Así que un código que parece una búsqueda hace crecer el map sin que te des cuenta:

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

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

    // Solo queríamos COMPROBAR "y", pero [] la insertó:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

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

seen["y"] creó una entrada "y" -> 0 solo por mencionarla. Para probar la pertenencia sin mutar el map, usa count (devuelve 0 o 1) o 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() se lee mejor que count()
    if (seen.contains("x")) cout << "x is here\n";
}

Regla práctica: usa [] solo cuando quieras crear o actualizar. Para lecturas puras, usa count, contains (C++20) o find.

find y at: búsquedas seguras

find devuelve un iterador a la entrada, o end() si la clave no está. Nunca inserta, y te permite acceder tanto a la clave como al valor mediante it->first e it->second en una sola búsqueda:

#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";
    }
}

Cuando sabes que la clave debería existir y quieres un fallo rotundo si no es así, usa at. A diferencia de [], at no inserta: lanza std::out_of_range si la clave falta:

int p = prices.at("pen");   // bien
int q = prices.at("hat");   // lanza std::out_of_range - la clave no existe

Así que tienes tres estilos de búsqueda: [] (inserta), at (lanza) y find/count (informan de la presencia sin tocar el map). Elige el que tenga el modo de fallo acorde a tu intención.

Iterar y borrar

Un bucle for basado en rangos con structured bindings es la forma limpia de recorrer cada entrada. Recuerda que el orden es arbitrario: nunca dependas de él:

#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";   // el orden no está especificado
    }
}

Para eliminar una entrada, erase toma una clave directamente y devuelve cuántas se eliminaron (0 o 1). Una trampa importante: borrar mientras iteras invalida solo el iterador del elemento borrado en un unordered_map, así que usa el valor de retorno de erase(it) para avanzar con seguridad:

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

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

    // Elimina todos los equipos con una puntuación menor que 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase devuelve el siguiente iterador válido
        else
            ++it;
    }

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

Escribir el estilo wins.erase(it++) o hacer ++it después de un erase(it) simple es la clásica trampa del iterador colgante: el iterador borrado está muerto, así que toma siempre el iterador que devuelve erase.

¿map o unordered_map?

Ambos almacenan pares clave-valor con una API similar, así que la elección se reduce a lo que necesites:

// std::map            -> claves ordenadas, O(log n), consultas por rangos (lower_bound)
// std::unordered_map  -> sin orden,        O(1) prom., búsqueda simple más rápida

Recurre a unordered_map cuando solo necesites búsquedas rápidas por clave y el orden sea irrelevante (contar frecuencias de palabras, caché, deduplicación). Elige map cuando necesites las claves en orden, quieras iterar ordenadamente o hacer consultas por rangos. Dos advertencias para unordered_map: su O(1) es un promedio (un mal hash puede degradarlo) y un tipo de clave personalizado necesita una especialización de hash o un functor de hash, mientras que a map le basta con operator<.

Siguiente: Set

Ya has visto los dos sabores de contenedor clave-valor. Sin embargo, a veces no necesitas un valor en absoluto: solo te importa si algo está presente, como una colección de etiquetas únicas o IDs visitados. A continuación veremos std::set (y su primo basado en hash unordered_set), que almacenan solo claves y las mantienen únicas automáticamente.

Preguntas frecuentes

¿Cuál es la diferencia entre map y unordered_map en C++?

std::map es un árbol binario balanceado: las claves se mantienen ordenadas y las operaciones son O(log n). std::unordered_map es una tabla hash: las claves no siguen ningún orden concreto, pero la inserción y la búsqueda son en promedio O(1). Usa unordered_map cuando solo necesites búsquedas rápidas por clave y el orden te dé igual; usa map cuando necesites iteración ordenada o consultas por rangos.

¿unordered_map[] inserta una clave si no existe?

Sí. m[key] construye por defecto e inserta la clave si falta, y luego devuelve una referencia a ella. Eso significa que incluso un if (m[key] == ...) que parece una simple lectura hace crecer el map de forma silenciosa. Para comprobar la pertenencia sin insertar, usa m.count(key) o m.find(key).

¿unordered_map es siempre más rápido que map en C++?

No. Es O(1) en promedio, pero el hashing tiene una sobrecarga y un mal hash (o claves adversariales) puede degradar las búsquedas a O(n). Para maps pequeños, los factores constantes y un peor comportamiento de caché pueden hacer que un map ordenado sea igual de rápido o incluso más. Mide el rendimiento si te importa, pero recurre a unordered_map por defecto cuando solo necesites búsquedas por clave.

Conceptos relacionados