Map y Unordered Map

La analogía: un diccionario real

Piensa en un diccionario de español. Tienes una palabra (clave) y su definición (valor). No buscas la definición recorriendo todas las páginas; vas directo a la letra correspondiente. Un map en C++ funciona igual: asocias una clave con un valor y puedes buscar por clave de forma eficiente.

map: ordenado y confiable

map usa un árbol balanceado internamente. Mantiene las claves ordenadas y cada operación toma $O(\log n)$.

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

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

    // Insertar
    edades["Ana"] = 15;
    edades["Carlos"] = 17;
    edades["Beatriz"] = 16;

    // Acceder
    cout << "Ana tiene " << edades["Ana"] << " años" << endl;

    // Verificar si existe
    if (edades.count("Carlos")) {
        cout << "Carlos está en el mapa" << endl;
    }

    // Recorrer (las claves salen en orden alfabético)
    for (auto &[nombre, edad] : edades) {
        cout << nombre << ": " << edad << endl;
    }
    // Beatriz: 16, Ana: 15, Carlos: 17
    // ¡No! Sale: Ana: 15, Beatriz: 16, Carlos: 17 (ordenado)

    // Borrar
    edades.erase("Carlos");

    // Tamaño
    cout << "Personas: " << edades.size() << endl;

    return 0;
}

unordered_map: más rápido pero desordenado

unordered_map usa una tabla hash. Las operaciones son $O(1)$ en promedio (¡constante!), pero las claves no tienen orden.

#include <unordered_map>
using namespace std;

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

    // La interfaz es idéntica a map
    frecuencia["hola"] = 3;
    frecuencia["mundo"] = 1;
    frecuencia["hola"]++;  // Ahora es 4

    // Recorrer (sin orden particular)
    for (auto &[palabra, freq] : frecuencia) {
        cout << palabra << ": " << freq << endl;
    }
}

¿Cuándo usar cuál?

Aplicación estrella: conteo de frecuencias

El uso más común en competencias:

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

int main() {
    int n;
    cin >> n;

    map<int, int> freq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;  // Incrementa el contador de x
    }

    // ¿Cuál es el elemento más frecuente?
    int maxFreq = 0, moda = 0;
    for (auto &[valor, f] : freq) {
        if (f > maxFreq) {
            maxFreq = f;
            moda = valor;
        }
    }

    cout << "Moda: " << moda << " (aparece " << maxFreq << " veces)" << endl;

    return 0;
}

Más operaciones útiles

map<int, string> m;
m[1] = "uno";
m[3] = "tres";
m[5] = "cinco";

// find: buscar una clave
auto it = m.find(3);
if (it != m.end()) {
    cout << it->first << ": " << it->second << endl;  // 3: tres
}

// lower_bound y upper_bound funcionan en map
auto lb = m.lower_bound(2);  // Apunta al 3 (primer clave >= 2)
auto ub = m.upper_bound(3);  // Apunta al 5 (primera clave > 3)

// Primer y último elemento
cout << m.begin()->first << endl;   // 1 (menor clave)
cout << m.rbegin()->first << endl;  // 5 (mayor clave)

Ejercicio de práctica

Dado un texto con N palabras, imprime cada palabra y cuántas veces aparece, en orden alfabético.

Entrada:

7
hola mundo hola como estas hola mundo

Salida:

como 1
estas 1
hola 3
mundo 2

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

int main() {
    int n;
    cin >> n;

    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        freq[s]++;
    }

    for (auto &[palabra, f] : freq) {
        cout << palabra << " " << f << endl;
    }

    return 0;
}

Siguiente paso

Aprende sobre Set y Multiset, las estructuras que almacenan solo claves (sin valores) de forma ordenada.