🧱 unordered_set y unordered_map

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

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Las versiones sin orden de set y map: prometen O(1) promedio en vez de O(log n), a cambio de no mantener las claves ordenadas.

Operaciones y costo

OperaciónCostoNotas
insert / find / eraseO(1) promedio⚠️ O(n) en el peor caso
countO(1) promedio
RecorrerO(n)en orden arbitrario, no ordenado
lower_bound✗no existe: sin orden no hay vecinos

Por dentro

Una tabla de hash: la clave se convierte en un número que dice en qué ‘balde’ guardarla. Si muchas claves caen en el mismo balde, las operaciones degeneran a recorrer una lista.

Cuándo usarla

Cuando solo necesitas ‘¿está?’ o contar, con muchísimas operaciones y sin necesidad alguna de orden. En la duda, set/map: su O(log n) es garantía.

Cómo se usa (C++)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    unordered_map<string,int> conteo;
    conteo["sol"]++;                       // igual que map, pero sin orden
    cout << conteo.count("sol") << "\n";
 
    unordered_set<long long> vistos;
    vistos.insert(1000000000000LL);
    // recorrerlo NO sale ordenado, y no existe lower_bound
    cout << vistos.size() << "\n";
}
 

⚠️ Notas

⚠️ En Codeforces circulan tests anti-hash hechos para que el hash por defecto colisione y la solución se caiga por TLE. Si las usas, mézclale una semilla aleatoria al hash; si no, quédate con set/map. El Syllabus IOI además deja las tablas hash fuera del conocimiento exigido.

🔗 Relacionados