std::setDocente: Tomás Assenza
Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe
std::set? Conceptos Generales• 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)).
• 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.
set<T>Elementos ordenados automáticamente y sin repetidos. Inserción, búsqueda y borrado en O(log N).
unordered_set<T>Funciona igual (sin repetidos), pero los elementos no están ordenados. Opera en O(1) promedio.
multiset<T>Mantiene los elementos ordenados, pero permite múltiples claves iguales (admite repetidos) en O(log N).
unordered_multiset<T>Permite repetidos y no mantiene orden. Permite inserción, búsqueda y eliminación en O(1) promedio.
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
std::set
if (set1 == set2) {
// True si tienen el mismo tamaño y todos
// los elementos de set1 son iguales
// lexicograficamente a los de set2
}
for (string elemento : miSet) {
cout << elemento << " ";
}
// Si es una estructura (struct), accedemos
// a sus atributos antes de imprimir.
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.
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.
"Leer un número N de palabras y mostrarlas en pantalla sin repetidos y en orden alfabético."
#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;
}
std::set
Con esto dominás vector, map y set. Ahora pasamos a los adaptadores de secuencia: empezamos por std::stack.