Hub Taller STL
Taller de Estructuras Dinámicas (STL) • Módulo 3

std::set
Conjuntos Ordenados y Sin Duplicados

Docente: Tomás Assenza

Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe

¿Qué es std::set? Conceptos Generales

Sin Acceso Aleatorio

• No podemos acceder de forma aleatoria: está prohibido el uso de corchetes miSet[i].

• Para consultar o recorrer sus elementos usamos iteradores o un bucle por rango (for (auto x : miSet)).

Ordenado y Sin Repetidos

• Es un conjunto automáticamente ordenado de elementos de un mismo tipo.

• Todos los elementos son distintos: si intentás insertar un valor que ya existe, el set simplemente lo ignora.

Ingresos con insert():
"pan" "agua" "pan" "café" "agua"
Estado interno del set<string>:
"agua" "café" "pan"

Las 4 Variantes de Conjuntos en la STL

1. set<T>

Elementos ordenados automáticamente y sin repetidos. Inserción, búsqueda y borrado en O(log N).

2. unordered_set<T>

Funciona igual (sin repetidos), pero los elementos no están ordenados. Opera en O(1) promedio.

3. multiset<T>

Mantiene los elementos ordenados, pero permite múltiples claves iguales (admite repetidos) en O(log N).

4. unordered_multiset<T>

Permite repetidos y no mantiene orden. Permite inserción, búsqueda y eliminación en O(1) promedio.

Declaración, Inicialización e Inserción

Cabeceras: #include <set> (para set y multiset) o #include <unordered_set>.


// 1. DECLARACION DE LAS VARIANTES
set<int> nombreDelSet;                               // Ordenado, sin repetidos
unordered_set<int> nombreDelUnorderedSet;            // No ordenado, sin repetidos
multiset<int> nombreDelMultiset;                     // Ordenado, permite repetidos
unordered_multiset<int> nombreDelUnorderedMultiset;  // No ordenado, permite repetidos

// 2. INICIALIZACION DIRECTA
set<int> miSet {8, 3, 5, 3, 1};
// Los elementos se ordenan automaticamente y se eliminan los repetidos:
// miSet queda como {1, 3, 5, 8}

// 3. AGREGAR Y CONSULTAR ELEMENTOS
miSet.insert(4);    // Inserta el 4 y reordena el set -> {1, 3, 4, 5, 8}
miSet.erase(3);     // Elimina el valor 3 del conjunto
miSet.count(5);     // Devuelve 1 si el 5 pertenece al set, o 0 si no esta
miSet.size();       // Devuelve la cantidad de elementos unicos
                    

Comparación y Recorrido de std::set

1. Comparación del Set Completo


if (set1 == set2) {
    // True si tienen el mismo tamaño y todos
    // los elementos de set1 son iguales
    // lexicograficamente a los de set2
}
                            

2. Recorrido por Elementos


for (string elemento : miSet) {
    cout << elemento << " ";
}
// Si es una estructura (struct), accedemos
// a sus atributos antes de imprimir.
                            

Aclaración general sobre contenedores STL

En todas las estructuras dinámicas vistas (vector, map, set), el valor por defecto si no hay una asignación explícita es 0 (o cadena vacía "" en string). A diferencia de los arreglos estáticos de C, los elementos no contienen basura por defecto.

Ejemplo de Aplicación: Lista de Compras

Beecrowd 2729

Valentina es una mujer muy dedicada que trabaja hasta tarde todos los días. Para ahorrar tiempo, ella escribe todos los ítems de supermercado al mismo tiempo que los recuerda en una aplicación móvil.

El problema es que esta aplicación no elimina los ítems duplicados y, como Valentina es distraída, frecuentemente anota el mismo ítem más de una vez y la lista se hace demasiado larga. Tu trabajo consta en mejorar esa aplicación: escribir un programa que excluya ítems duplicados de la lista de compras y los ordene en orden alfabético. La entrada consta de un número N (cantidad de ítems), seguida de N ítems separados por un espacio.

Antes de resolver, simplificamos el problema:

"Leer un número N de palabras y mostrarlas en pantalla sin repetidos y en orden alfabético."

Resolución Paso a Paso: Lista de Valentina


#include <iostream>
#include <set>
#include <string>

using namespace std;

int main() {
    set<string> items;
    int n;
    string palabra;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> palabra;
        items.insert(palabra);
    }

    for (const string &elemento : items)
        cout << elemento << " ";
    cout << endl;
}
                        

Laboratorio en Vivo: Lista sin Duplicados con std::set

OneCompiler - C++ Sandbox (Probá agregar ítems repetidos)

¡Fin del Módulo 3!

Con esto dominás vector, map y set. Ahora pasamos a los adaptadores de secuencia: empezamos por std::stack.

Módulo 2: std::map Volver al Hub Ir al Módulo 4: std::stack