🧱 map (clave-valor)

Estructura de datos · Viene en la librería estándar (STL) · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras

📍 Dónde se aprende: módulo 06 de la Ruta de Aprendizaje.

Qué hace

Asocia cada clave con un valor, manteniendo las claves ordenadas. Su uso estrella en competencia es contar frecuencias de cosas que no son índices chicos: palabras, números gigantes, coordenadas dispersas.

Operaciones y costo

OperaciónCostoNotas
m[clave] (leer o crear)O(log n)⚠️ crea la entrada si no existía
count / findO(log n)consultar sin crear
eraseO(log n)
RecorrerO(n)sale ordenado por clave
lower_bound sobre clavesO(log n)

Por dentro

El mismo árbol balanceado del set, pero cada nodo guarda un par (clave, valor).

Cuándo usarla

Cuando las claves son palabras o valores dispersos. Si son enteros de un rango pequeño, un vector de frecuencias permite acceso O(1), pero reserva una casilla por valor posible, aunque no aparezca.

Cómo se usa (C++)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    map<string,int> veces;
    veces["sol"]++;                       // si no existía, parte en 0 y suma 1
    veces["mar"] += 2;
 
    if (veces.count("sol")) cout << veces["sol"] << "\n";   // 1
    for (pair<string,int> par : veces)    // recorre ordenado por clave
        cout << par.first << "=" << par.second << " ";      // mar=2 sol=1
    cout << "\n";
    veces.erase("mar");
}
 

⚠️ Notas

Clave y valor son cosas distintas. Al contar sol,mar,sol, el mapa pasa por {sol:1}, {mar:1,sol:1} y {mar:1,sol:2}. Tiene dos claves (size() == 2) y tres apariciones en total. Recorrerlo visita mar antes que sol, porque ordena por clave, no por frecuencia.

Consultar sin insertar. En map<string,int>, m[clave] crea un entero inicializado en 0 si la clave no existía; m.count(clave) solo dice si la clave existe (0 o 1), no su frecuencia. find devuelve un iterador: si es distinto de end(), it->second permite leer el valor sin crear claves. Para otros tipos de valor, la inicialización no significa necesariamente el número cero: un string, por ejemplo, queda vacío.

Elegir la representación. Para cien códigos entre 0 y mil millones, el mapa guarda a lo más cien entradas; un vector indexado por código necesitaría más de mil millones de casillas. Si todos los códigos están entre 0 y 100, el vector de 101 frecuencias es sencillo. Un map necesita memoria adicional por entrada; no estimes su espacio solo sumando los tamaños de clave y valor.

🔗 Relacionados