Set y Multiset

La analogía: una lista de asistencia

Imagina una lista de asistencia donde cada nombre solo puede aparecer una vez. No importa cuántas veces alguien diga "presente", su nombre aparece solo una vez en la lista. Eso es un set: una colección de elementos únicos y ordenados.

Si quisieras una lista donde sí pueda haber nombres repetidos (por ejemplo, contar cuántas veces llegó cada persona), usarías un multiset.

Set: elementos únicos y ordenados

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;

    // Insertar
    s.insert(5);
    s.insert(3);
    s.insert(7);
    s.insert(3);  // Duplicado: no se inserta
    s.insert(1);

    cout << "Tamaño: " << s.size() << endl;  // 4 (no 5)

    // Recorrer (siempre en orden)
    for (int x : s) cout << x << " ";  // 1 3 5 7
    cout << endl;

    // Buscar
    if (s.count(5)) cout << "5 está en el set" << endl;

    // Borrar
    s.erase(3);  // Elimina el 3

    // Primer y último elemento
    cout << "Mínimo: " << *s.begin() << endl;    // 1
    cout << "Máximo: " << *s.rbegin() << endl;    // 7

    return 0;
}

Multiset: permite duplicados

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms;

    ms.insert(5);
    ms.insert(3);
    ms.insert(5);  // ¡Sí se inserta!
    ms.insert(3);
    ms.insert(5);

    cout << "Tamaño: " << ms.size() << endl;  // 5

    // Contar ocurrencias de un valor
    cout << "Cantidad de 5's: " << ms.count(5) << endl;  // 3

    // Recorrer (ordenado, con repeticiones)
    for (int x : ms) cout << x << " ";  // 3 3 5 5 5
    cout << endl;

    // ⚠️ CUIDADO: erase(valor) borra TODAS las copias
    ms.erase(5);  // Borra los tres 5's
    cout << "Después de erase(5): " << ms.size() << endl;  // 2

    // Para borrar solo UNA copia:
    ms.insert(5);
    ms.insert(5);
    auto it = ms.find(5);
    if (it != ms.end()) {
        ms.erase(it);  // Borra solo UNA copia del 5
    }

    return 0;
}

Operaciones con iteradores

set<int> s = {10, 20, 30, 40, 50};

// lower_bound: primer elemento >= x
auto it1 = s.lower_bound(25);
cout << *it1 << endl;  // 30

// upper_bound: primer elemento > x
auto it2 = s.upper_bound(30);
cout << *it2 << endl;  // 40

// Avanzar y retroceder iteradores
auto it = s.find(30);
auto sig = next(it);    // 40
auto ant = prev(it);    // 20

// Borrar un rango
s.erase(s.lower_bound(20), s.upper_bound(40));
// s = {10, 50}

Complejidad

Aplicaciones en competencias

1. Eliminar duplicados

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
set<int> unicos(v.begin(), v.end());
// unicos = {1, 2, 3, 4, 5, 6, 9}

2. Mantener los K menores elementos

// Mantener un multiset con los K valores más pequeños vistos hasta ahora
multiset<int> menores;
int k = 3;

void agregar(int x) {
    menores.insert(x);
    if (menores.size() > k) {
        menores.erase(prev(menores.end()));  // Borra el mayor
    }
}

3. Mediana dinámica (dos multisets)

multiset<int> izq, der;  // izq: mitad menor, der: mitad mayor

void insertar(int x) {
    if (izq.empty() || x <= *izq.rbegin()) {
        izq.insert(x);
    } else {
        der.insert(x);
    }

    // Balancear: izq puede tener a lo más 1 elemento más que der
    while (izq.size() > der.size() + 1) {
        der.insert(*izq.rbegin());
        izq.erase(prev(izq.end()));
    }
    while (der.size() > izq.size()) {
        izq.insert(*der.begin());
        der.erase(der.begin());
    }
}

int mediana() {
    return *izq.rbegin();
}

4. Coordenadas comprimidas

vector<int> v = {100, 50000, 3, 100, 7};
set<int> unicos(v.begin(), v.end());

map<int, int> comprimido;
int idx = 0;
for (int x : unicos) {
    comprimido[x] = idx++;
}
// comprimido = {3:0, 100:1, 7:2, 50000:3}
// Pero como set ordena: {3:0, 7:1, 100:2, 50000:3}

Unordered set

Si no necesitas orden y quieres velocidad $O(1)$:

#include <unordered_set>
using namespace std;

unordered_set<int> us;
us.insert(5);
us.count(5);  // 1
us.erase(5);

Ejercicio de práctica

Dada una secuencia de N operaciones, cada operación es:

• 1 x: insertar x al conjunto
• 2 x: borrar una copia de x del conjunto
• 3: imprimir el menor y mayor elemento

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;

    multiset<int> ms;

    while (n--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            ms.insert(x);
        } else if (op == 2) {
            int x;
            cin >> x;
            auto it = ms.find(x);
            if (it != ms.end()) ms.erase(it);
        } else {
            if (ms.empty()) {
                cout << "Vacío" << endl;
            } else {
                cout << *ms.begin() << " " << *ms.rbegin() << endl;
            }
        }
    }

    return 0;
}

Siguiente paso

Descubre las aplicaciones prácticas de diccionarios y conjuntos en problemas reales de competencia.