CKTIS / C++
std::set — une collection ordonnée de clés uniques
std::set, défini dans <set>, stocke des clés uniques selon l’ordre du comparateur. Découvrez l’insertion et la recherche, ainsi que les différences entre find, contains, count et equal_range, notamment comment vérifier end() sans risque.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <set>
std::set<Key> values;
auto [it, inserted] = values.insert(key);
auto found = values.find(key);
bool present = found != values.end();
bool exists = values.contains(key);
auto occurrences = values.count(key);
auto [first, last] = values.equal_range(key);std::set<Key> de <set> est un conteneur associatif ordonné. Chaque élément est lui-même une clé ; le comparateur par défaut std::less<Key> classe les entiers par ordre croissant. L’unicité signifie l’équivalence selon le comparateur : !comp(a, b) && !comp(b, a), pas nécessairement a == b. Le comparateur doit définir un ordre strict faible.
La surcharge ordinaire de std::set::insert(key) pour une valeur unique renvoie une paire : un itérateur vers l’élément inséré ou déjà présent et un bool indiquant si l’insertion a eu lieu. Une clé équivalente n’est pas ajoutée une seconde fois. std::set::find(key) renvoie un itérateur vers un élément équivalent ou std::set::end(). end() pointe après le dernier élément : vérifiez it != values.end() avant de déréférencer le résultat d’une recherche.
std::set::contains(key) renvoie un résultat booléen indiquant la présence de la clé. std::set::count(key) renvoie le nombre d’éléments équivalents, ici toujours 0 ou 1. std::set::equal_range(key) renvoie deux itérateurs décrivant l’intervalle semi-ouvert [first, last) des éléments équivalents : vide ou contenant un seul élément. Un intervalle vide signifie first == last, mais pas nécessairement first == values.end().
L’insertion ordinaire d’une valeur unique et les opérations de recherche indiquées ont une complexité O(log n) ; end() prend un temps constant. Il est impossible de modifier les clés par l’intermédiaire d’itérateurs. L’exemple est destiné à être compilé avec -std=c++23. Le document fourni est un brouillon en évolution, et non une publication C++23 définitive ; l’option du compilateur du dépôt ne garantit pas la prise en charge à l’exécution en production.
Exemples
#include <iostream>
#include <set>
int main() {
std::set<int> values{3, 1, 3};
auto [it, inserted] = values.insert(2);
auto duplicate = values.insert(3);
std::cout << std::boolalpha;
std::cout << "insert: " << *it << ' ' << inserted << '\n';
std::cout << "duplicate: " << duplicate.second << '\n';
std::cout << "ordered:";
for (int value : values) {
std::cout << ' ' << value;
}
std::cout << '\n';
auto found = values.find(2);
if (found != values.end()) {
std::cout << "find: " << *found << '\n';
}
std::cout << "contains 4: " << values.contains(4) << '\n';
std::cout << "count 3: " << values.count(3) << '\n';
auto [first, last] = values.equal_range(2);
std::cout << "equal_range 2:";
for (auto current = first; current != last; ++current) {
std::cout << ' ' << *current;
}
std::cout << '\n';
}
Résultat
insert: 2 true duplicate: false ordered: 1 2 3 find: 2 contains 4: false count 3: 1 equal_range 2: 2
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.