std::map, set, pilas y colas

Ya sabes guardar una secuencia en un std::vector. Pero muchos problemas no piden una secuencia: piden responder «¿cuántas veces aparece esta palabra?», «¿qué elementos son únicos?» o «¿cuál es el siguiente trabajo más urgente?». Para eso están los contenedores asociativos y los adaptadores.

La decisión entre ellos no es estética. Cada contenedor ofrece un orden distinto de recorrido y un coste distinto por operación. Elegir mal convierte un bucle de un segundo en uno de un minuto, o hace que tu programa imprima resultados en un orden impredecible.

¿Qué es un contenedor asociativo?

Un contenedor asociativo guarda elementos identificados por una clave y permite encontrarlos sin recorrer todo. std::map<Clave, Valor> almacena pares y ordena por clave; std::set<Clave> almacena solo claves únicas, también ordenadas. std::unordered_map y std::unordered_set hacen lo mismo con una tabla hash, sin orden de recorrido.

Los adaptadores son otra cosa: no guardan datos con una clave, sino que limitan por dónde entran y salen. std::stack es LIFO (el último que entra es el primero que sale), std::queue es FIFO (el primero que entra es el primero que sale) y std::priority_queue siempre entrega el elemento de mayor prioridad. Stack y queue no son contenedores completos: envuelven un std::deque por debajo y exponen solo unas operaciones.

¿Para qué sirven?

• Contar frecuencias: un map<std::string, int> asocia cada palabra con su número de apariciones.
• Eliminar duplicados: insertar en un set descarta automáticamente lo repetido y mantiene el orden.
• Buscar por identificador: un unordered_map<int, Registro> pasa de una búsqueda lineal a una consulta directa.
• Procesar en orden inverso: una pila resuelve la evaluación de expresiones y el retroceso en un laberinto.
• Atender por turnos: una cola mantiene el orden de llegada en una simulación o en un recorrido BFS.
• Priorizar: una priority_queue entrega siempre el mayor puntaje, el trabajo más urgente o el camino más corto en Dijkstra.

En Machine Learning aparecen constantemente: un vocabulario es un map<string, int> que asigna un índice a cada token; un conjunto de etiquetas únicas es un set; la búsqueda en anchura de un grafo usa una queue; y los mejores candidatos de una búsqueda se guardan en una priority_queue. Saber qué operación domina el algoritmo te dice qué contenedor necesitas.

¿Cómo funciona por dentro?

std::map y std::set se implementan típicamente como árboles rojo-negro, un árbol binario de búsqueda que se rebalancea al insertar y borrar. Por eso todas las operaciones de búsqueda, inserción y borrado cuestan O(log n): la altura del árbol se mantiene logarítmica aunque los datos lleguen ordenados. El recorrido begin() a end() devuelve las claves de menor a mayor.

std::unordered_map y std::unordered_set usan una tabla hash: convierten la clave en un número con std::hash, lo reducen a un índice de un arreglo de buckets y guardan ahí el elemento. Si la función hash reparte bien, cada bucket tiene pocos elementos y la búsqueda es O(1) en promedio. Si muchas claves caen en el mismo bucket, la búsqueda degenera a O(n). Por eso el estándar no garantiza O(1) en el peor caso.

Un std::stack no es más que un deque con la interfaz limitada a push, pop y top. Un std::queue expone push, pop, front y back. Una priority_queue mantiene un montículo: el elemento mayor está siempre en la raíz, top() lo devuelve en O(1) y push/pop reorganizan en O(log n).

Sintaxis

123456789101112131415161718192021222324252627282930313233

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>

int main() {
    std::map<std::string, int> edades;
    edades["ana"] = 30;
    edades["luis"] = 25;
    std::cout << edades.size() << '\n';   // 2

    std::set<int> unicos{3, 1, 3, 2};
    std::cout << unicos.size() << '\n';   // 3
    for (int x : unicos) {
        std::cout << x << ' ';            // 1 2 3
    }
    std::cout << '\n';

    std::stack<int> pila;
    pila.push(1);
    pila.push(2);
    std::cout << pila.top() << '\n';      // 2
    pila.pop();

    std::queue<std::string> cola;
    cola.push("primero");
    cola.push("segundo");
    std::cout << cola.front() << '\n';    // primero
    cola.pop();
    return 0;
}

• map[clave] = valor inserta o actualiza. map.at(clave) solo lee y lanza si no existe.
• set.insert(x) devuelve un pair<iterator, bool>: el segundo valor indica si realmente se insertó o ya estaba.
• stack::top() y queue::front() sobre un contenedor vacío son comportamiento indefinido; comprueba empty() antes.
• priority_queue<int> es un montículo de máximos. Para mínimos se declara std::priority_queue<int, std::vector<int>, std::greater<int>>.

Ejemplo básico: contar palabras

123456789101112131415161718

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> palabras{"sol", "mar", "sol", "viento", "mar", "sol"};
    std::map<std::string, int> frecuencia;

    for (const std::string& p : palabras) {
        ++frecuencia[p];   // si no existe, la crea con 0 y suma 1
    }

    for (const auto& [palabra, veces] : frecuencia) {
        std::cout << palabra << ": " << veces << '\n';
    }
    return 0;
}

La salida aparece ordenada alfabéticamente: mar: 2, sol: 3, viento: 1. Ese orden no lo escribiste tú: es una propiedad del std::map. La primera vez que se evalúa frecuencia["sol"], el mapa inserta la clave con valor 0 y luego el ++ lo deja en 1. Las siguientes veces encuentra la clave y solo incrementa. El for con [palabra, veces] es un structured binding que descompone el par en dos variables.

Ejemplo intermedio: intersección de conjuntos

12345678910111213141516171819202122

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> ana{"mate", "fisica", "programacion"};
    std::set<std::string> luis{"programacion", "quimica", "mate"};

    std::set<std::string> comunes;
    for (const std::string& curso : ana) {
        if (luis.count(curso) > 0) {
            comunes.insert(curso);
        }
    }

    std::cout << comunes.size() << '\n';   // 2
    for (const std::string& c : comunes) {
        std::cout << c << ' ';              // mate programacion
    }
    std::cout << '\n';
    return 0;
}

count devuelve 1 si la clave existe y 0 si no; en un set nunca puede devolver más de 1 porque los duplicados no se almacenan. Recorrer el conjunto menor sería más eficiente, pero con tres elementos la diferencia es irrelevante: lo importante es que la consulta es logarítmica en lugar de recorrer el otro conjunto. El resultado comunes también está ordenado y no contiene repetidos.

Caso práctico: los tres mejores puntajes

Una priority_queue mantiene el elemento mayor en la cima sin ordenar todo el vector. Si solo necesitas los k mejores de un conjunto grande, es más barato que ordenar: cada push cuesta O(log n) y cada pop también, mientras que un sort completo cuesta O(n log n) aunque luego descartes casi todo.

123456789101112131415

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::vector<int> puntajes{55, 90, 72, 90, 88, 61};
    std::priority_queue<int> max_heap(puntajes.begin(), puntajes.end());

    for (int i = 0; i < 3 && !max_heap.empty(); ++i) {
        std::cout << max_heap.top() << ' ';
        max_heap.pop();
    }
    std::cout << '\n';   // 90 90 88
    return 0;
}

El constructor que recibe dos iteradores construye el montículo en tiempo lineal. Cada top() devuelve la raíz, el mayor de los restantes; pop() la elimina y reordena. Los dos 90 aparecen porque son dos elementos distintos: la cola de prioridad no elimina duplicados, a diferencia de un set.

Visualización: insertar, actualizar y consultar en un map

Sigue los pasos y observa dos cosas: el mapa mantiene las claves ordenadas y asignar dos veces la misma clave no crea un duplicado, sino que actualiza el valor. El tamaño solo cambia en las dos primeras inserciones.

—

Errores comunes

• Usar m[clave] para comprobar: si la clave no existe, se inserta con valor 0 y el mapa crece. Para preguntar sin modificar usa m.contains(clave) o m.find(clave) != m.end().
• Asumir que unordered_map conserva el orden: no lo hace. Si imprimes sus elementos, el orden puede cambiar entre ejecuciones o entre bibliotecas. Usa map cuando el orden importe.
• Olvidar comprobar empty(): top() en una pila vacía o front() en una cola vacía es comportamiento indefinido, no una excepción.
• Confundir el orden de una priority_queue: por defecto es un montículo de máximos. Para el mínimo hay que pasar std::greater<int> como comparador.
• Modificar un elemento de un set: los elementos son const porque cambiar la clave rompería el árbol. Hay que borrar e insertar de nuevo.
• Usar una clave sin operator< o sin hash: std::map necesita comparación; std::unordered_map, std::hash y operator==. Si no existen, el error de compilación ocupa varias pantallas.
• Elegir map para pocos elementos: con diez elementos, un vector ordenado suele ser más rápido por localidad de caché. La notación O grande no cuenta toda la historia.

Buenas prácticas

• Elige unordered_map si no necesitas orden y la búsqueda es el cuello de botella; elige map si necesitas recorrer ordenado o rangos.
• Reserva capacidad en unordered_map con reserve(n) si conoces el número de claves: evita rehacer la tabla varias veces.
• Usa contains (C++20) para preguntar y at para leer cuando la clave debe existir.
• Recorre con for (const auto& [clave, valor] : m); el & evita copiar el par y const documenta que no lo modificas.
• Comprueba empty() antes de top, front o back.
• Usa std::greater<T> para una cola de mínimos y un comparador propio para prioridades complejas.
• Si el número de elementos es pequeño, mide: un vector ordenado puede superar a un mapa en velocidad y en memoria.

12345

frecuencia = {}
for p in ["sol", "mar", "sol"]:
    frecuencia[p] = frecuencia.get(p, 0) + 1
print(frecuencia)   # orden de insercion
print(set(frecuencia))

12345678

std::map<std::string, int> frecuencia;
for (const std::string& p : {"sol", "mar", "sol"}) {
    ++frecuencia[p];
}
// recorrido ordenado por clave
for (const auto& [palabra, veces] : frecuencia) {
    std::cout << palabra << ": " << veces << '\n';
}

Ejercicios

std::stack<int> pila;
pila.(1);
pila.(2);
std::cout << pila.() << '\n';   // 2
pila.();

Soluciones explicadas

En el primer ejercicio, el mapa hace dos trabajos a la vez: asocia cada letra con su contador y garantiza el orden alfabético al recorrerlo. Si hubieras usado un unordered_map, el conteo sería correcto pero las líneas podrían salir en cualquier orden. En el segundo, la cola de prioridad no conserva el orden de llegada: conserva el orden de urgencia. Los dos 1 aparecen dos veces porque son dos elementos distintos, y por eso una priority_queue no sirve para deduplicar. Elegir entre set, map y priority_queue depende de si el problema pide unicidad, asociación o prioridad.

Resumen

• std::map y std::set usan un árbol balanceado: O(log n) y recorrido ordenado por clave.
• std::unordered_map y std::unordered_set usan hash: O(1) promedio, sin orden y con peor caso O(n).
• m[clave] inserta si la clave falta; find, contains y at consultan sin crear.
• std::set elimina duplicados y no permite modificar sus elementos en el lugar.
• stack es LIFO, queue es FIFO y priority_queue entrega primero el mayor por defecto.
• top, front y back requieren comprobar empty() antes.
• La complejidad no lo decide todo: para pocos elementos, un vector ordenado puede ser mejor.
• Elige el contenedor por las operaciones que dominan el algoritmo, no por costumbre.

Evaluación