🧱 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ón | Costo | Notas |
|---|---|---|
| insert / find / erase | O(1) promedio | ⚠️ O(n) en el peor caso |
| count | O(1) promedio | |
| Recorrer | O(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.