Elementos únicos con std::set y std::multiset en C++

En la biblioteca estándar de C++, set y multiset son contenedores asociativos que almacenan los elementos en forma ordenada y se basan en una estructura de árbol. La diferencia principal es que set almacena cada elemento solo una vez, mientras que multiset permite múltiples apariciones del mismo elemento. Ambos están implementados mediante un árbol rojo-negro y proporcionan ordenación automática.

1) ¿Qué es set?

std::set es un contenedor que almacena cada elemento una sola vez y los mantiene automáticamente en orden ascendente.

• Los elementos siempre están ordenados de forma creciente.
• No se permiten elementos duplicados.
• Inserción, búsqueda y eliminación: O(log n)
• No hay acceso aleatorio → se requiere iteración.

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

int main() {
    set<int> numbers;

    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(10); // los duplicados se ignoran

    for (int n : numbers)
        cout << n << " ";
}

Salida: 10 20 30

2) Características de set

• Almacenamiento ordenado
• Elementos únicos
• O(log n) para inserción y búsqueda
• Compatible con lower_bound / upper_bound

// Búsqueda de elementos
set<int> s = {10, 20, 30};

if (s.contains(20))
    cout << "¡Encontrado!";

3) ¿Qué es multiset?

std::multiset es similar a set, pero permite múltiples ocurrencias del mismo elemento.

• Los elementos se almacenan en orden creciente.
• Los duplicados están permitidos.
• Inserción, búsqueda y eliminación: O(log n)
• No ofrece acceso aleatorio.

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

int main() {
    multiset<int> nums;

    nums.insert(20);
    nums.insert(10);
    nums.insert(20);  // duplicado permitido
    nums.insert(30);

    for (int n : nums)
        cout << n << " ";
}

Salida: 10 20 20 30

4) Contar elementos en multiset

multiset<int> ms = {10, 20, 20, 30};

cout << "Cantidad de 20: " << ms.count(20) << endl;

Salida: Cantidad de 20: 2

5) Comparación entre set y multiset

Conclusión: Si necesitas elementos únicos → usa set. Si necesitas permitir duplicados → usa multiset.

6) Acceso ordenado y búsqueda por rango

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

auto it = s.lower_bound(25); // primer elemento >= 25
cout << *it << endl;

it = s.upper_bound(30); // primer elemento > 30
cout << *it << endl;

7) Operaciones de eliminación

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

s.erase(20);        // elimina por clave
s.erase(s.begin()); // elimina mediante iterador

multiset<int> ms = {10, 20, 20, 30};

ms.erase(20); // elimina TODOS los elementos iguales a 20

8) Ejemplo práctico – Análisis de frecuencia de palabras

Contar palabras usando multiset

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

int main() {
    multiset<string> words;

    words.insert("hola");
    words.insert("mundo");
    words.insert("hola");
    words.insert("cpp");

    cout << "Cantidad de 'hola': " << words.count("hola") << endl;

    for (auto& w : words)
        cout << w << " ";
}

9) ¿Cuándo usar cada uno?

• Si necesitas solo elementos únicos → set
• Si se permiten duplicados → multiset
• Ambos sirven para datos ordenados
• Ambos tienen complejidad O(log n)

Resumen:
set = elementos únicos
multiset = múltiples elementos iguales
ambos ordenan automáticamente los elementos.

10) TL;DR

Artículos relacionados