CKTIS / C++
std::unordered_set — un ensemble de clés uniques
std::unordered_set stocke des clés uniques à l’aide du hachage. Il permet de vérifier la présence, d’insérer et de supprimer des éléments sans garantir l’ordre d’itération. Les opérations courantes ont une complexité moyenne constante, mais linéaire dans le pire des cas.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <unordered_set>
std::unordered_set<Key, Hash, Pred, Allocator> values;
// Defaults: Hash = std::hash<Key>, Pred = std::equal_to<Key>,
// Allocator = std::allocator<Key>std::unordered_set, défini dans <unordered_set>, est un conteneur associatif non ordonné : chaque élément est aussi sa clé, et l’ensemble contient au plus un élément de chaque classe d’équivalence. Les paramètres Hash et Pred définissent le hachage et l’équivalence ; par défaut, il s’agit de std::hash<Key> et de std::equal_to<Key>. Des clés équivalentes doivent avoir le même hachage ; des hachages identiques n’impliquent pas que les clés soient équivalentes.
insert(value).second indique si un élément a été ajouté. contains(value) vérifie la présence d’un élément, find(value) renvoie un itérateur ou end(), et erase(value) renvoie le nombre d’éléments supprimés : ici, 0 ou 1. La recherche, l’insertion d’un élément et la suppression par clé ont une complexité moyenne en O(1) et une complexité en O(n) dans le pire des cas.
L’ordre d’itération n’est pas spécifié. Il n’est pas possible de modifier les clés au moyen d’itérateurs ; il faut plutôt supprimer l’ancienne clé et insérer la nouvelle. Un rehash invalide les itérateurs, mais pas les pointeurs ni les références vers les éléments. Une insertion peut déclencher un rehash ; reserve(n) prépare suffisamment de compartiments pour n éléments avec le facteur de charge maximal actuel, et peut aussi invalider les itérateurs. La suppression d’un élément invalide ses itérateurs, pointeurs et références.
L’exemple n’affiche pas les éléments en les parcourant : la sortie attendue ne dépend donc pas de leur ordre. Cette entrée cible C++23 ; une option du compilateur dans le dépôt ne garantit pas l’environnement de production. Le projet de norme fourni est mis à jour au fil du temps et peut contenir des fonctionnalités postérieures à C++23.
Exemples
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> values{3, 1, 3};
const bool inserted = values.insert(1).second;
std::cout << std::boolalpha;
std::cout << "inserted: " << inserted << '\n';
std::cout << "contains 3: " << values.contains(3) << '\n';
std::cout << "erased: " << values.erase(3) << '\n';
std::cout << "size: " << values.size() << '\n';
}
Résultat
inserted: false contains 3: true erased: 1 size: 1
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.