Les conteneurs associatifs
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 deux classes principales
set (ensemble)
La classe set est un conteneur associatif dans lequel la clé et la valeur sont le même élément de données.
map (dictionnaire)
La classe map est un conteneur associatif dans lequel la clé et la valeur sont des éléments distincts.
La norme a récemment ajouté le multiset et le multimap pour permettre des valeurs dupliquées et des clés dupliquées.
La classe 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 d'un ensemble
Nous pouvons créer un nouvel ensemble de plusieurs manières :
| Syntaxe | Description |
|---|---|
set <type> set1; | Créer un ensemble vide |
set <type> set2(pos1, pos2); | Créer un ensemble en copiant les éléments d'un autre ensemble dans la plage [pos1, pos2] |
set <type> set3(set2); | Créer un ensemble par copie (constructeur de copie) |
set4 = set3; | Créer un ensemble par affectation |
Taille d'un ensemble
Il existe trois fonctions membres pour vérifier la taille, la taille maximale et le vide :
| Syntaxe | Description |
|---|---|
set1.size(); | Renvoie la taille actuelle (nombre d'éléments) |
set1.max_size(); | Renvoie la taille maximale possible |
set1.empty(); | Renvoie true si l'ensemble 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 forme d'arbre binaire. Elle fournit les mêmes huit itérateurs internes que les conteneurs de séquence :
| Syntaxe | Description |
|---|---|
set1.begin() | Retourne un itérateur au premier élément |
set1.end() | Renvoie un itérateur à 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 |
set1.cbegin() | Version constante de begin() |
set1.cend() | Version constante de end() |
set1.crbegin() | Version constante de rbegin() |
set1.crend() | Version constante de rend() |
Recherche dans un ensemble
Comme les éléments d'un ensemble sont triés, la recherche est possible et efficace (complexité logarithmique).
| Syntaxe | Description |
|---|---|
set1.count(k) | Renvoie le nombre d'éléments égaux à k (0 ou 1 pour un set) |
set1.find(k) | Retourne un itérateur pointant sur l'élément k trouvé, ou set1.end() si non trouvé |
set1.lower_bound(k) | Renvoie la première position où k peut être inséré (premier élément >= k) |
set1.upper_bound(k) | Renvoie la dernière position où k peut être inséré (premier élément > k) |
set1.equal_range(k) | Renvoie une paire d'itérateurs [lower_bound, upper_bound] pour la valeur k |
- La fonction count(k) pour un ensemble renvoie 0 ou 1 (pas de doublons).
- 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, elle renvoie end().
- La fonction lower_bound() renvoie la première position où la valeur peut être insérée.
- La fonction upper_bound() renvoie la dernière position où la valeur peut être insérée.
- equal_range() renvoie un objet paire combinant lower_bound et upper_bound.
La classe set n'a aucune opération pour accéder aux éléments à l'aide d'un opérateur d'index [] ou de la fonction at(). Nous devons utiliser la clé pour le faire via les fonctions de recherche.
Insertion dans un ensemble
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 <itérateur, bool> indiquant la position et le succès |
set1.insert(position, k) | Insère k en utilisant position comme indice (optimisation), renvoie un itérateur |
set1.insert(pos1, pos2) | Insère une plage d'éléments [pos1, pos2) d'un autre conteneur |
- La première fonction membre insère la clé k et renvoie un itérateur indiquant la position et une valeur booléenne (true si succès, false si l'élément existait déjà).
- La deuxième fonction membre insère également k, mais l'utilisateur peut donner un indice (itérateur position) pour réduire la recherche.
- La troisième fonction membre copie une plage [pos1, pos2) d'un autre ensemble et l'insère à l'endroit approprié.
Suppression dans un ensemble
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 l'élément avec la valeur k (renvoie le nombre d'éléments supprimés : 0 ou 1) |
set1.erase(pos) | Supprime l'élément pointé par l'itérateur pos |
set1.erase(premier, dernier) | Supprime les éléments dans la plage [premier, dernier) |
set1.clear() | Supprime tous les éléments (vide l'ensemble) |
Tout comme les conteneurs de séquence, l'opération swap() est définie pour les ensembles. De plus, nous pouvons comparer deux ensembles avec des opérateurs relationnels (==, !=, <, etc.).
Exemple complet
Voici un programme complet illustrant les principales opérations sur un set.
#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;
// Insertion d'éléments
set1.insert(5);
set1.insert(15);
set1.insert(10);
set1.insert(3);
set1.insert(10); // Doublon : sera ignoré
set1.insert(8);
cout << "Les éléments de l'ensemble : ";
afficher(set1);
cout << "Nombre d'éléments dans set1 : " << set1.size() << '\n';
// Recherche avec count
cout << "Nombre d'éléments égaux à 10 : " << set1.count(10) << '\n';
cout << "Nombre d'éléments égaux à 30 : " << set1.count(30) << '\n';
cout << "\n";
// Parcours avec itérateurs
set<int>::iterator it = set1.begin();
cout << "Les éléments avec les itérateurs begin et end : ";
while (it != set1.end()) {
cout << *it << " ";
it++;
}
cout << "\n\n";
// Suppression
set1.erase(10);
cout << "Les éléments après suppression de 10 : ";
afficher(set1);
// Vidage complet
set1.clear();
cout << "Les éléments après clear : ";
afficher(set1);
return 0;
}Les éléments de l'ensemble : 3 5 8 10 15 Nombre d'éléments dans set1 : 5 Nombre d'éléments égaux à 10 : 1 Nombre d'éléments égaux à 30 : 0 Les éléments avec les itérateurs begin et end : 3 5 8 10 15 Les éléments après suppression de 10 : 3 5 8 15 Les éléments après clear :
Explication de l'exemple :
- Les éléments sont automatiquement triés par ordre croissant : 3, 5, 8, 10, 15.
- Le doublon
10est ignoré (taille = 5, pas 6). count(10)renvoie 1,count(30)renvoie 0 (élément non présent).- Le parcours avec itérateurs permet d'accéder à tous les éléments dans l'ordre.
erase(10)supprime l'élément 10 de l'ensemble.clear()vide complètement l'ensemble.
- Un set est un conteneur associatif qui stocke des valeurs uniques et triées.
- Les éléments sont automatiquement triés par ordre croissant.
- Les doublons sont automatiquement ignorés (insertion sans effet).
- Implémentation sous-jacente : arbre binaire de recherche équilibré.
- Complexité logarithmique pour les opérations de recherche, insertion et suppression.
- Pas d'accès par index
[]ouat()comme pour les conteneurs séquentiels. - Principales méthodes :
insert(),erase(),find(),count(),size(),empty(),clear(). - Les itérateurs sont bidirectionnels (pas d'accès aléatoire).
- Le parcours se fait dans l'ordre trié des éléments.
- Opérations supplémentaires :
swap(), comparaisons entre ensembles.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.