El contenedor std::set de la Biblioteca Estándar de C++ (STL) implementa el concepto matemático de un conjunto, garantizando que cada elemento sea único. std::multiset permite elementos duplicados. Ambos están internamente basados en árboles rojo-negro y ofrecen funcionalidades similares, siendo std::set útil para verificar la existencia de elementos en una colección.

Inclusión de Cabecera y Declaración

Para utilizar std::set, es necesario incluir la cabecera <set>.

#include <set>
#include <vector>
#include <utility> // Para std::pair

// Conjunto de enteros
std::set<int> conjuntoEnteros;

// Conjunto de pares de enteros
std::set<std::pair<int, int>> conjuntoPares;

// Conjuntos anidados son posibles
std::set<std::set<int>> conjuntoAnidado;

// Se puede definir para tipos personalizados
std::set<std::vector<int>> conjuntoVectores;

Si se desea almacenar objetos de una clase personalizada en un std::set, es necesario sobrecargar el operador menor que (<) para definir el orden.

struct MiEstructura {
    int valor;
    // ... otros miembros ...

    // Sobrecarga del operador < para definir el orden
    // Nota: Este ejemplo ordena de forma descendente por 'valor'
    bool operator<(const MiEstructura& otro) const {
        return valor > otro.valor;
    }
};

std::set<MiEstructura> conjuntoEstructuras;

Funciones Integradas

size()Devuelve el número de elementos en el conjunto. La complejidad es O(1).

size_t cantidadElementos = conjuntoEnteros.size();

empty()Verifica si el conjunto está vacío. Devuelve true si está vacío, false en caso contrario. La complejidad es O(1).

if (conjuntoEnteros.empty()) {
    // El conjunto está vacío
}

clear()Elimina todos los elementos del conjunto. No devuelve ningún valor.

conjuntoEnteros.clear();

count(clave)Devuelve el número de ocurrencias de un elemento específico. Para std::set, este valor será 0 o 1. Para std::multiset, puede ser mayor. La complejidad es O(log n).

if (conjuntoEnteros.count(5) > 0) {
    // El elemento 5 existe en el conjunto
}

Iteradores std::set proporciona iteradores de acceso bidireccional, lo que significa que no admiten acceso aleatorio. Solo se pueden usar los operdaores de pre/post-incremento (++) y pre/post-decremento (--).

// Declaración de un iterador
std::set<int>::iterator it;

// Asignación al inicio
it = conjuntoEnteros.begin();

// Avance al siguiente elemento (según el orden del conjunto)
++it;

// Retroceso al elemento anterior
--it;

Las operaciones de incremento y decremento tienen una complejidad de O(log n).

Recorrido y Acceso a Elementos

Se puede recorrer un std::set utilizando iteradores.

// Recorrer un conjunto de enteros
for (std::set<int>::iterator it = conjuntoEnteros.begin(); it != conjuntoEnteros.end(); ++it) {
    // Acceder al elemento apuntado por el iterador
    std::cout << *it << " ";
}
std::cout << std::endl;

// Recorrer un conjunto anidado
for (auto it_exterior = conjuntoAnidado.begin(); it_exterior != conjuntoAnidado.end(); ++it_exterior) {
    // it_exterior apunta a un std::set<int> interno
    for (auto it_interior = (*it_exterior).begin(); it_interior != (*it_exterior).end(); ++it_interior) {
        std::cout << *it_interior << " ";
    }
    std::cout << std::endl;
}

begin()Devuelve un iterador que apunta al primer elemento del conjunto (el de menor valor). La complejidad es O(1).

std::set<int>::iterator primerElemento = conjuntoEnteros.begin();

end()Devuelve un iterador que apunta a la posición después del último elemento del conjunto. La complejidad es O(1).

// Para obtener el último elemento, se decrementa el iterador devuelto por end()
if (!conjuntoEnteros.empty()) {
    int ultimo = *(--conjuntoEnteros.end());
}

insert(valor)Inserta un elemento en el conjunto. Devuelve un std::pair que contiene un iterador a la posición del elemento insertado (o existente) y un booleano indicendo si la inserción tuvo éxito (es decir, si el elemento era nuevo). La complejidad es O(log n). std::set no permite duplicados.

auto resultado = conjuntoEnteros.insert(10);
if (resultado.second) {
    // La inserción fue exitosa
}

erase(parametro)Elimina elementos del conjunto. El parámetro puede ser un valor o un iterador. Si se pasa un valor, se elimina la primera ocurrencia (para std::set, esto elimina el elemento si existe). Si se pasa un iterador, se elimina el elemento al que apunta. Devuelve un iterador al siguiente elemento. Para std::multiset, erase(valor) elimina todas las ocurrencias del valor. También se puede usar erase con un rango de iteradores [inicio, fin) para eliminar múltiples elementos. La complejidad es O(log n) para eliminar un solo elemento, y O(N) para eliminar un rango de N elementos.

// Eliminar un elemento por iterador
std::set<int>::iterator it_a_eliminar = conjuntoEnteros.find(5);
if (it_a_eliminar != conjuntoEnteros.end()) {
    conjuntoEnteros.erase(it_a_eliminar);
}

// Eliminar un elemento por valor
conjuntoEnteros.erase(10);

// Eliminar un rango de elementos
auto inicio_rango = conjuntoEnteros.begin();
auto fin_rango = conjuntoEnteros.end();
// ... ajustar inicio_rango y fin_rango según sea necesario ...
// conjuntoEnteros.erase(inicio_rango, fin_rango);

find(clave)Busca un elemento con el valor especificado. Devuelve un iterador al elemento si se encuentra, o conjunto.end() si no se encuentra. La complejidad es O(log n).

if (conjuntoEnteros.find(7) != conjuntoEnteros.end()) {
    // El elemento 7 está presente
}

lower_bound(clave) y upper_bound(clave)Estas funciones son útiles para buscar rangos de elementos. Ambas tienen una complejidad de O(log n).

• lower_bound(clave): Devuelve un iterador al primer elemento que es no menor que clave (es decir, mayor o igual a clave).
• upper_bound(clave): Devuelve un iterador al primer elemento que es estrictamente mayor que clave.

Considerando el conjunto {3, 5, 7, 8, 13, 16}:

• conjunto.lower_bound(8): Devuelve un iterador a 8.
• conjunto.upper_bound(8): Devuelve un iterador a 13.
• conjunto.lower_bound(12): Devuelve un iterador a 13 (el primer elemento >= 12).
• conjunto.upper_bound(12): Devuelve un iterador a 13 (el primer elemento > 12).
• Si clave es mayor que todos los elementos (ej. 20), ambas funcionse devuelven conjunto.end().