🧱 set y multiset
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
Colección ordenada sin repetidos (set) o con repetidos (multiset). Responde ‘¿está?’, mantiene todo en orden mientras insertas y borras, y encuentra el vecino más cercano a un valor.
Operaciones y costo
| Operación | Costo | Notas |
|---|---|---|
| insert | O(log n) | si ya estaba, el set lo ignora |
| find | O(log n) | end() si no existe |
| count(x) | O(log n + k) | k copias: a lo más 1 en set |
| erase(x) | O(log n + k) | borra las k copias; a lo más una en set |
| erase(it) | O(1) amortizado | borra solo el elemento de un iterador válido |
| lower_bound / upper_bound | O(log n) | el vecino ≥ x / > x |
| *s.begin() / *s.rbegin() | O(1) | menor y mayor; requiere no estar vacío |
| Recorrer en orden | O(n) |
Por dentro
Se suele implementar mediante un árbol de búsqueda balanceado. Las claves menores quedan antes que las mayores; las búsquedas y las inserciones individuales tienen costo logarítmico garantizado. Contar o borrar muchas copias también depende de cuántas hay.
Cuándo usarla
Cuando necesitas orden y además insertas o borras sobre la marcha. Si solo ordenas una vez datos que no cambian, sort sobre un vector es más rápido y más simple.
Cómo se usa (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
set<int> s;
s.insert(5); s.insert(1); s.insert(5); // el 5 repetido NO entra dos veces
if (s.count(1)) cout << "el 1 esta\n";
cout << *s.begin() << " " << *s.rbegin() << "\n"; // el menor y el mayor: 1 5
auto it = s.lower_bound(4); // primer elemento >= 4
if (it != s.end()) cout << "vecino: " << *it << "\n"; // 5
multiset<int> ms{3, 3, 7};
auto pos = ms.find(3);
if (pos != ms.end()) ms.erase(pos); // borra UNA copia, si existe
cout << ms.size() << "\n"; // 2
}
⚠️ Notas
Sobre la sintaxis: s.lower_bound(x) y s.find(x) devuelven un iterador (una posición dentro del set); *it lee el valor que hay ahí, y compararlo con s.end() es la forma de preguntar ¿encontró algo?. Los verás desde el módulo 08 de la ruta. ⚠️ En multiset, ms.erase(x) borra todas las copias de x; para borrar una sola, busca auto it = ms.find(x) y llama ms.erase(it) solo si it != ms.end(). Y no se puede indexar: s[i] no existe (para eso, ordena un vector).
Sigue las operaciones. Insertar 5,1,5 deja {1,5} en un set y {1,5,5} en un multiset. lower_bound(4) apunta al 5; lower_bound(6) devuelve end(), que no se puede desreferenciar. Borrar por valor 5 deja {1} en ambos. Como alternativa, partiendo otra vez del multiset {1,5,5}, borrar por iterador una copia de 5 deja {1,5}. El orden es por valor, no por llegada.
Elegir la estructura. Si solo importa si un código apareció, usa set. Si cada copia puede consumirse por separado, multiset conserva la cantidad. Para guardar un dato asociado a cada código, consulta map.