Docs C++ exécutables : set

Q: Qu'est-ce qu'un set en C++ ?

Un std::set est un conteneur associatif qui stocke des valeurs uniques dans l'ordre trié. Insérer une valeur déjà présente ne fait rien, et l'itération parcourt les éléments du plus petit au plus grand. Les recherches, insertions et suppressions sont toutes en O(log n) car il repose sur un arbre binaire de recherche équilibré.

Q: Comment vérifier si un élément existe dans un set C++ ?

Utilisez s.count(x), qui renvoie 1 si x est présent et 0 sinon, ou s.contains(x) en C++20, qui renvoie un bool. Évitez s.find(x) != s.end() sauf si vous avez réellement besoin de l'itérateur : c'est le même coût mais plus verbeux.

Q: Quelle est la différence entre set et unordered_set en C++ ?

std::set garde les éléments triés et offre des opérations en O(log n) ; std::unorderedset les conserve dans un ordre quelconque grâce à une table de hachage, avec des opérations en O(1) en moyenne. Utilisez set quand vous avez besoin d'une itération ordonnée ou de requêtes par plage, et unorderedset quand vous n'avez besoin que de tests d'appartenance rapides et que l'ordre vous est indifférent.

Un sac de valeurs uniques et triées

Vous avez vu unordered_map stocker des paires clé-valeur avec une recherche rapide fondée sur le hachage. Un std::set est le cousin plus simple : il ne stocke que des valeurs — aucune donnée associée — et il applique deux règles automatiquement. Chaque élément est unique (les doublons sont supprimés silencieusement) et les éléments sont toujours maintenus dans l'ordre trié.

Cela fait du set le choix naturel pour des questions comme « ai-je déjà vu ceci ? » ou « donne-moi les éléments distincts dans l'ordre ». Vous insérez sans vous soucier des doublons et vous itérez sans trier au préalable.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // doublon - ignoré

    for (int x : s) cout << x << " ";   // 10 30 40 (trié, sans répétition)
}

Remarquez que nous avons inséré 10 deux fois et dans le désordre, et pourtant la sortie est triée et 10 n'apparaît qu'une fois. Le set a fait la comptabilité à votre place.

Insérer et supprimer

insert ajoute une valeur si elle n'est pas déjà présente. Il renvoie une pair dont le .second est un bool qui vous indique si l'insertion a réellement eu lieu — pratique quand vous voulez savoir si une valeur était nouvelle :

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Pour supprimer une valeur, appelez erase avec la valeur elle-même : il renvoie le nombre d'éléments supprimés (0 ou 1 pour un set). Supprimer quelque chose qui n'est pas là est sans danger, ce n'est pas une erreur :

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

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // supprime 3
    s.erase(99);         // ne fait rien, renvoie 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

Vérifier l'appartenance

Tout l'intérêt d'un set, ce sont les tests rapides « est-ce que c'est là-dedans ? ». La manière la plus claire est count, qui renvoie 1 ou 0 :

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

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Depuis C++20, il existe une option encore plus lisible, contains, qui renvoie directement un bool :

if (primes.contains(7)) { /* ... */ }   // C++20

Une erreur fréquente consiste à recourir à operator[] comme on le ferait avec une map. Un set n'a pas d'operator[] : il n'y a aucune valeur à récupérer, seulement une présence à tester. Utilisez count ou contains, pas s[7].

Si vous avez besoin de la position réelle (pour la supprimer ou regarder les voisins), utilisez find, qui renvoie un itérateur ou end() :

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

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

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // supprime par itérateur - pas de seconde recherche
    }
    cout << "size now " << s.size() << "\n";
}

Itération ordonnée et requêtes par plage

Comme un set est trié, l'itération produit toujours les éléments du plus petit au plus grand, et vous obtenez gratuitement les astuces des conteneurs ordonnés. lower_bound(x) donne le premier élément non inférieur à x, et upper_bound(x) le premier élément strictement supérieur à x — ensemble, ils vous permettent de parcourir une plage numérique sans vérifier chaque élément :

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

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // affiche tout ce qui se trouve dans [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

Une règle subtile mais importante : les éléments d'un set sont immuables. L'itérateur vous donne une référence const, vous ne pouvez donc pas modifier un élément sur place — le faire pourrait casser l'ordre de tri dont dépend le conteneur. Pour « modifier » une valeur, supprimez l'ancienne et insérez la nouvelle.

Par défaut, l'ordre est croissant (std::less). Pour un ordre décroissant, fournissez un comparateur différent comme deuxième argument de template :

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

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set est l'un de trois proches parents, et choisir le bon a son importance :

set<int>            // valeurs uniques, triées, O(log n)
multiset<int>       // autorise les doublons, triées, O(log n)
unordered_set<int>  // valeurs uniques, AUCUN ordre, O(1) en moyenne

Tournez-vous vers unordered_set quand vous n'avez besoin que de tests d'appartenance et que l'ordre vous est indifférent — ses recherches fondées sur le hachage sont en moyenne plus rapides que le O(log n) fondé sur un arbre du set. Choisissez set quand vous avez besoin d'éléments dans l'ordre, de requêtes par plage avec lower_bound/upper_bound, ou d'un comportement stable des itérateurs. N'utilisez multiset que lorsque les doublons sont significatifs (par exemple, un histogramme de valeurs répétées) : dans un multiset, count(x) peut renvoyer plus de 1, et erase(x) supprime toutes les copies sauf si vous supprimez par un itérateur unique.

Une utilisation classique du set : dédupliquer et trier un vector d'un seul geste.

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

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Construire le set à partir des itérateurs du vector écarte chaque doublon et trie le reste — pas de boucle manuelle, pas de chorégraphie std::sort plus std::unique.

Ensuite : pair et tuple

Vous avez maintenant vu .first et .second apparaître sur la pair que renvoie insert, et les liaisons structurées (auto [it, inserted]) la décomposer proprement. Ces types légers qui « regroupent quelques valeurs » sont partout dans la STL. Ensuite, nous examinerons directement pair et tuple : comment les construire, les décomposer et renvoyer plusieurs valeurs depuis une fonction sans définir une struct complète.

Questions fréquentes

Qu'est-ce qu'un set en C++ ?

Un std::set est un conteneur associatif qui stocke des valeurs uniques dans l'ordre trié. Insérer une valeur déjà présente ne fait rien, et l'itération parcourt les éléments du plus petit au plus grand. Les recherches, insertions et suppressions sont toutes en O(log n) car il repose sur un arbre binaire de recherche équilibré.

Comment vérifier si un élément existe dans un set C++ ?

Utilisez s.count(x), qui renvoie 1 si x est présent et 0 sinon, ou s.contains(x) en C++20, qui renvoie un bool. Évitez s.find(x) != s.end() sauf si vous avez réellement besoin de l'itérateur : c'est le même coût mais plus verbeux.

Quelle est la différence entre set et unordered_set en C++ ?

std::set garde les éléments triés et offre des opérations en O(log n) ; std::unordered_set les conserve dans un ordre quelconque grâce à une table de hachage, avec des opérations en O(1) en moyenne. Utilisez set quand vous avez besoin d'une itération ordonnée ou de requêtes par plage, et unordered_set quand vous n'avez besoin que de tests d'appartenance rapides et que l'ordre vous est indifférent.

Concepts liés