C++ set: elementos únicos y ordenados con std::set

Una bolsa de valores únicos y ordenados

Ya viste cómo unordered_map almacena pares clave-valor con una búsqueda rápida basada en hash. Un std::set es el primo más sencillo: almacena solo valores —sin datos asociados— y aplica dos reglas de forma automática. Cada elemento es único (los duplicados se descartan en silencio) y los elementos se mantienen siempre en orden.

Eso hace que set sea la elección natural para preguntas como «¿he visto esto antes?» o «dame los elementos distintos en orden». Insertas sin preocuparte por los duplicados e iteras sin ordenar primero.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // duplicado - ignorado

    for (int x : s) cout << x << " ";   // 10 30 40 (ordenado, sin repetir)
}

Fíjate en que insertamos 10 dos veces y desordenado, y aun así la salida está ordenada y 10 aparece una sola vez. El set hizo la contabilidad por ti.

Insertar y eliminar

insert añade un valor si no está ya presente. Devuelve un pair cuyo .second es un bool que te indica si la inserción realmente ocurrió, útil cuando quieres saber si un valor era nuevo:

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Para eliminar un valor, llama a erase con el propio valor: devuelve el número de elementos eliminados (0 o 1 para un set). Eliminar algo que no está es inofensivo, no es un error:

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

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // elimina el 3
    s.erase(99);         // no hace nada, devuelve 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

Comprobar la pertenencia

El objetivo principal de un set son las pruebas rápidas de «¿está esto aquí?». La forma más clara es count, que devuelve 1 o 0:

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

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Desde C++20 hay una opción aún más legible, contains, que devuelve un bool directamente:

if (primes.contains(7)) { /* ... */ }   // C++20

Un error común es recurrir a operator[] como harías con un map. Un set no tiene operator[]: no hay ningún valor que recuperar, solo presencia que comprobar. Usa count o contains, no s[7].

Si necesitas la posición concreta (para eliminarla o mirar los vecinos), usa find, que devuelve un iterador o end():

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

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // eliminar por iterador - sin una segunda búsqueda
    }
    cout << "size now " << s.size() << "\n";
}

Iteración ordenada y consultas por rango

Como un set está ordenado, iterar siempre produce los elementos de menor a mayor, y obtienes gratis los trucos de los contenedores ordenados. lower_bound(x) da el primer elemento no menor que x, y upper_bound(x) el primer elemento estrictamente mayor que x; juntos te permiten recorrer un rango numérico sin comprobar cada elemento:

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

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // imprime todo lo que esté en [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

Una regla sutil pero importante: los elementos de un set son inmutables. El iterador te entrega una referencia const, así que no puedes cambiar un elemento en su sitio; hacerlo podría romper el orden del que depende el contenedor. Para «cambiar» un valor, elimina el antiguo e inserta el nuevo.

Por defecto el orden es ascendente (std::less). Para orden descendente, proporciona un comparador distinto como segundo argumento de plantilla:

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

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set es uno de tres parientes cercanos, y elegir el correcto importa:

set<int>            // valores únicos, ordenados, O(log n)
multiset<int>       // permite duplicados, ordenados, O(log n)
unordered_set<int>  // valores únicos, SIN orden, O(1) en promedio

Recurre a unordered_set cuando solo necesites pruebas de pertenencia y no te importe el orden: sus búsquedas basadas en hash son más rápidas en promedio que el O(log n) basado en árbol del set. Elige set cuando necesites elementos en orden, consultas por rango con lower_bound/upper_bound o un comportamiento estable de los iteradores. Usa multiset solo cuando los duplicados sean significativos (por ejemplo, un histograma de valores repetidos): en un multiset, count(x) puede devolver más de 1, y erase(x) elimina todas las copias salvo que elimines por un único iterador.

Un uso clásico de set: eliminar duplicados y ordenar un vector en un solo paso.

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

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Construir el set a partir de los iteradores del vector descarta cada duplicado y ordena el resto: sin bucle manual, sin el baile de std::sort más std::unique.

Siguiente: pair y tuple

Ya has visto cómo aparecen .first y .second en el pair que devuelve insert, y cómo los enlaces estructurados (auto [it, inserted]) lo desempaquetan limpiamente. Esos tipos ligeros para «agrupar unos pocos valores» están por todas partes en la STL. A continuación veremos pair y tuple directamente: cómo construirlos, desempaquetarlos y devolver varios valores desde una función sin definir una estructura completa.