Estructuras clave-valor con std::map y std::unordered_map en C++

En C++, map y unordered_map son los dos contenedores asociativos principales que proporcionan estructuras de datos basadas en pares clave–valor, similares a los diccionarios. Ambos permiten asociar una clave con un valor de manera eficiente, pero difieren considerablemente en sus estructuras internas, comportamiento de ordenación, tiempos de búsqueda y rendimiento. En este artículo se explican ambos contenedores en detalle con ejemplos prácticos.

1) ¿Qué es map?

std::map es un contenedor asociativo ordenado, implementado mediante un árbol rojo-negro (red–black tree), es decir, un árbol binario de búsqueda autoequilibrado.

• Los datos se almacenan de forma ordenada según la clave.
• Búsqueda, inserción y eliminación: O(log n)
• Las claves son únicas.
• La iteración siempre sigue el orden creciente de las claves.

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

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

    scores["Ana"] = 90;
    scores["Luis"] = 80;
    scores["Carlos"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Nota: La salida siempre aparece ordenada alfabéticamente.

2) ¿Qué es unordered_map?

std::unordered_map es un contenedor asociativo basado en tablas hash. No garantiza ningún orden, pero ofrece un rendimiento de búsqueda muy rápido en promedio.

• Las claves se almacenan según su hash → no hay orden garantizado.
• Búsqueda, inserción y eliminación: O(1) promedio (peor caso O(n)).
• El orden de iteración es impredecible y puede variar entre ejecuciones.
• En conjuntos de datos grandes, suele ser más rápido que map.

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

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

    scores["Ana"] = 90;
    scores["Luis"] = 80;
    scores["Carlos"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Nota: El orden de salida puede cambiar en cada ejecución.

3) Comparación entre map y unordered_map

Resumen: Si necesitas orden → usa map. Si necesitas velocidad → usa unordered_map.

4) Operaciones básicas

a) Inserción

map<int,string> m;
m.insert({1, "Uno"});
m[2] = "Dos";   // inserta o actualiza

b) Búsqueda

auto it = m.find(1);
if (it != m.end())
    cout << "Encontrado: " << it->second;

c) Eliminación

m.erase(2);          // eliminar por clave
m.erase(m.begin());  // eliminar por iterador

d) Tamaño y comprobación de existencia

cout << m.size();
cout << m.count(1);   // devuelve 0 o 1

5) Funciones hash personalizadas para unordered_map

Los tipos básicos (int, string, double…) ya disponen de funciones hash. Para tipos definidos por el usuario, es necesario crear un hash y un comparador personalizados.

#include <unordered_map>
#include <string>

struct Usuario {
    string nombre;
    int id;
};

struct UsuarioHash {
    size_t operator()(Usuario const& u) const noexcept {
        return hash<string>{}(u.nombre) ^ hash<int>{}(u.id);
    }
};

struct UsuarioEq {
    bool operator()(Usuario const& a, Usuario const& b) const noexcept {
        return a.id == b.id && a.nombre == b.nombre;
    }
};

int main() {
    unordered_map<Usuario, int, UsuarioHash, UsuarioEq> usuarios;
}

6) Buckets y factor de carga en unordered_map

En un unordered_map, los elementos se almacenan en buckets. Las claves que producen el mismo valor hash caen en el mismo bucket (colisión).

unordered_map<int,string> um;

cout << um.bucket_count() << endl;
cout << um.load_factor() << endl;

Cuando el factor de carga aumenta, el rendimiento disminuye. Puedes mejorar el rendimiento mediante rehash(n).

7) Ejemplo práctico — Sistema de notas

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

int main() {
    unordered_map<string, double> grades;

    grades["Camila"] = 85.5;
    grades["Julio"] = 92.0;
    grades["Sofia"] = 78.0;

    if (grades.contains("Julio"))
        cout << "Nota de Julio: " << grades["Julio"] << endl;

    grades.erase("Sofia");

    for (auto& g : grades)
        cout << g.first << ": " << g.second << endl;
}

8) ¿Cuál deberías usar?

• Usa map → si necesitas orden, o para volúmenes pequeños/medios.
• Usa unordered_map → si lo más importante es la velocidad.
• Búsquedas por rango (lower_bound, upper_bound) → sólo disponibles en map.
• Para conjuntos muy grandes → unordered_map suele ser mucho más rápido.

Recomendación general: Si no necesitas orden → utiliza unordered_map. Si necesitas iteración ordenada → utiliza map.

9) TL;DR

Artículos relacionados