Les ensembles en C++ (Classe set <set> - Bibliothèque STL)
Les éléments d'un conteneur associatif sont stockés et récupérés par une clé. Pour accéder à un élément dans un conteneur associatif, on utilise la clé de l'élément. Les conteneurs associatifs sont normalement implémentés comme un arbre de recherche binaire. Les conteneurs associatifs sont divisés en deux classes (set et map). La norme a récemment ajouté le multiset et le multimap avec des valeurs dupliquées et des clés dupliquées.
- Classe set (ensemble) est un conteneur associatif dans lequel la clé et la valeur sont le même élément de données.
- Classe map (dictionnaire) est un conteneur associatif dans lequel la clé et la valeur sont des éléments de données distincts.
La classe set <set>
La classe set est définie dans le fichier d'en-tête <set>. Dans un set, chaque élément du conteneur stocke une valeur, appelée clé. Les éléments sont triés par ordre croissant et les doublons ne sont pas autorisés.
Création
Nous pouvons créer un nouvel ensemble en utilisant un constructeur par défaut (ensemble vide). Nous pouvons également créer un nouvel ensemble à l'aide d'un constructeur de paramètres en copiant les éléments d'un autre ensemble dans lequel la plage est indiquée par [premier, dernier). Nous pouvons également créer un ensemble en utilisant un constructeur de copie ou un opérateur d'affectation.
Syntaxe | Description |
---|---|
set <type> set1 | Créer un ensemble vide |
set <type>(pos1, pos2) set2 | Créer un ensemble en copiant les éléments d'un autre ensemble |
set <type>(set2) set3 | Créer un ensemble en copiant tous les éléments d'un autre ensemble (set2) |
set4 = set3 | Créer un ensemble en copiant tous les éléments d'un autre ensemble |
Taille d'un ensemble
Il existe trois fonctions membres que nous pouvons utiliser pour vérifier la taille, la taille maximale et le vide. Ils sont les mêmes que ceux discutés pour les conteneurs de séquence.
Syntaxe | Description |
---|---|
set1.size(); | Renvoie la taille actuelle |
set1.max_size(); | Renvoie la taille maximale |
set1.empty(); | Renvoie true si le set est vide |
Itérateurs
La classe set utilise des itérateurs bidirectionnels (et non à accès aléatoire) car elle est normalement implémentée sous la forme d'une liste chaînée non linéaire. Il fournit les mêmes huit itérateurs internes que les conteneurs de séquence, dont quatre sont constants et quatre non constants. Les itérateurs constants et non constants ont la même syntaxe.
Syntaxe | Description |
---|---|
set1.begin() | Retourne un itérateur régulier au premier élément |
set1.end() | Renvoie un itérateur régulier à l'élément après le dernier |
set1.rbegin() | Retourne un itérateur inverse au dernier élément |
set1.rend() | Renvoie un itérateur inverse à l'élément avant le premier |
Recherche
Comme les éléments d'un ensemble sont triés, la recherche est possible et efficace. Il y a cinq membres pour la recherche, comme indiqué ci-dessous :
Syntaxe | Description |
---|---|
set1.count(k) | Renvoie le nombre d'éléments égal à k |
set1.find(k) | Retourne un itérateur pointant sur le premier k trouvé |
set1.lower_bound(k) | Renvoie la première position où k peut être inséré |
set1.upper_bound(k) | Renvoie la dernière position où k peut être inséré |
set1.equal_range(k) | Combinaison de limite inférieure et supérieure |
- La fonction count(k) pour un ensemble renvoie 0 ou 1
- La fonction find() essaie de trouver la valeur dans l'ensemble et renvoie l'itérateur à la valeur si elle est trouvée. Si la valeur n'est pas trouvée dans l'ensemble, elle renvoie end().
- La fonction lower_bound() renvoie la première position où la valeur peut être insérée ; le upper_bound() renvoie la dernière position où la valeur peut être insérée.
- equal_range() renvoie un objet paire montrant la combinaison de lower_bound et upper_bound.
Insertion
Il n'y a pas de membres push pour insérer un élément dans un ensemble. L'insertion doit être effectuée à l'aide de la clé ou via des itérateurs.
Syntaxe | Description |
---|---|
set1.insert(k) | Insère k et renvoie une paire <pos, bool> |
set1.insert(debut, k) | Renvoie un itérateur à l'élément après debut |
set1.insert(pos1, pos2) | Renvoie une paire où k peut être trouvé |
- La première fonction membre insère la clé k et renvoie un itérateur indiquant la position et une valeur booléenne (succès ou échec).
- La deuxième fonction membre insère également k, mais l'utilisateur peut donner un indice (itérateur) à la position pour réduire la recherche (debut).
- La troisième fonction membre copie une plage ouverte [pos1, pos2) d'un autre ensemble et l'insère à l'endroit approprié.
Suppression
Il n'y a pas de membres pop pour supprimer un élément d'un ensemble. La suppression doit être effectuée via la valeur ou l'itérateur.
Syntaxe | Description |
---|---|
set1.erase(k) | Supprime k |
set1.erase(pos) | Supprimer un élément pointé par pos |
set1.erase(premier, dernier) | Supprimer les éléments de la plage [premier, dernier) |
set1.clear() | Vide un ensemble (supprimer tout les éléments |
Le premier membre supprime l'élément avec la clé k et renvoie le nombre d'éléments, qui peut être 0 ou 1 pour un ensemble. La seconde supprime l'élément à la position pos. Le troisième supprime une plage. Le dernier supprime tous les éléments.
Exemple complet
#include <iostream> #include <set> using namespace std; void afficher(set <int> set1) { for (int elem : set1) { cout << elem <<" "; } cout << "\n"; } int main() { set<int> set1; set1.insert(5); set1.insert(15); set1.insert(10); set1.insert(3); set1.insert(10); set1.insert(8); cout<<"Les elements de l'ensemble : "; afficher(set1); cout<< "Nombre d'elements dans set1 : "<<set1.size()<<'\n'; cout<< "nombre d'elements egal a 10 : "<<set1.count(10)<<'\n'; cout<< "nombre d'elements egal a 30 : "<<set1.count(30)<<'\n'; cout << "\n"; set<int>::iterator it = set1.begin(); cout<<"Les elements de l'ensemble avec les iterateurs begin et end : "; while(it != set1.end()){ cout<< *it << " "; it++; } cout << "\n"; set1.erase(10); cout<<"Les elements de l'ensemble apres suppression de 10 : "; afficher(set1); set1.clear(); cout<<"Les elements de l'ensemble apres clear : "; afficher(set1); return 0; }
Les elements de l'ensemble : 3 5 8 10 15 Nombre d'elements dans set1 : 5 nombre d'elements egal a 10 : 1 nombre d'elements egal a 30 : 0 Les elements de l'ensemble avec les iterateurs begin et end : 3 5 8 10 15 Les elements de l'ensemble apres suppression de 10 : 3 5 8 15 Les elements de l'ensemble apres clear :