Éléments uniques avec std::set et std::multiset en C++

Dans la bibliothèque standard C++, set et multiset sont des conteneurs associatifs qui stockent les éléments de manière triée et reposent sur une structure arborescente. La différence principale est que set ne stocke chaque élément qu’une seule fois, tandis que multiset permet plusieurs occurrences du même élément. Les deux sont implémentés à l’aide d’un arbre rouge-noir et assurent un tri automatique.

1) Qu’est-ce que set ?

std::set est un conteneur qui stocke chaque élément une seule fois et les maintient automatiquement dans un ordre trié.

• Les éléments sont toujours triés par ordre croissant.
• Aucun doublon n’est autorisé.
• Insertion, recherche et suppression : O(log n)
• Aucun accès aléatoire → itération nécessaire.

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

int main() {
    set<int> numbers;

    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(10); // les doublons sont ignorés

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

Sortie : 10 20 30

2) Caractéristiques de set

• Stockage trié
• Éléments uniques
• O(log n) pour insertion et recherche
• Prise en charge de lower_bound / upper_bound

// Recherche d’un élément
set<int> s = {10, 20, 30};

if (s.contains(20))
    cout << "Trouvé !";

3) Qu’est-ce que multiset ?

std::multiset fonctionne de manière similaire à set, mais permet plusieurs occurrences du même élément.

• Les éléments sont triés automatiquement.
• Les doublons sont autorisés.
• Insertion, recherche et suppression : O(log n)
• Aucun accès aléatoire.

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

int main() {
    multiset<int> nums;

    nums.insert(20);
    nums.insert(10);
    nums.insert(20);  // doublon accepté
    nums.insert(30);

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

Sortie : 10 20 20 30

4) Compter les éléments dans multiset

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

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

Sortie : Nombre de 20 : 2

5) Comparaison entre set et multiset

Conclusion : Si vous devez empêcher les doublons → utilisez set. Si vous devez autoriser plusieurs occurrences → utilisez multiset.

6) Accès trié et recherche par intervalle

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

auto it = s.lower_bound(25); // premier élément >= 25
cout << *it << endl;

it = s.upper_bound(30); // premier élément > 30
cout << *it << endl;

7) Opérations de suppression

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

s.erase(20);        // suppression par clé
s.erase(s.begin()); // suppression via itérateur

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

ms.erase(20); // supprime TOUS les éléments égaux à 20

8) Exemple pratique – Analyse de fréquence des mots

Compter les mots avec multiset

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

int main() {
    multiset<string> words;

    words.insert("bonjour");
    words.insert("monde");
    words.insert("bonjour");
    words.insert("cpp");

    cout << "Nombre de 'bonjour' : " << words.count("bonjour") << endl;

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

9) Quand utiliser quel conteneur ?

• Éléments uniques requis → set
• Doublons autorisés → multiset
• Les deux conviennent pour des données triées
• Les deux offrent des performances O(log n)

Résumé :
set = éléments uniques
multiset = éléments multiples
les deux trient automatiquement leurs éléments.

10) TL;DR

Articles connexes