🧱 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ónCostoNotas
insertO(log n)si ya estaba, el set lo ignora
findO(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) amortizadoborra solo el elemento de un iterador válido
lower_bound / upper_boundO(log n)el vecino ≥ x / > x
*s.begin() / *s.rbegin()O(1)menor y mayor; requiere no estar vacío
Recorrer en ordenO(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.

🔗 Relacionados