🧱 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ón | Costo | Notas |
|---|---|---|
| m[clave] (leer o crear) | O(log n) | ⚠️ crea la entrada si no existía |
| count / find | O(log n) | consultar sin crear |
| erase | O(log n) | |
| Recorrer | O(n) | sale ordenado por clave |
| lower_bound sobre claves | O(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.