Conteneurs uniques et ordonnés en C++

6, 10, 2, 8, 4 est un ensemble ; 2, 4, 6, 8, 10 est un ensemble des mêmes nombres entiers, classés par ordre croissant. En mathématiques, un ensemble a des éléments uniques (éléments distincts), c'est-à-dire qu'aucun élément n'apparaît plus d'une fois. De plus, un multi-ensemble est un ensemble, où n'importe quel élément peut apparaître plus d'une fois. 6, 6, 10, 2, 2, 8, 4, 4, 4 est un multi-ensemble. 2, 2, 4, 4, 4, 6, 6, 8, 10 est le même multi-ensemble, mais avec les éléments classés par ordre croissant. Cet article ne traite pas du multiset. Il traite de la structure de données C++ appelée, set.

Une carte dans un logiciel est comme un tableau, mais c'est un tableau avec deux colonnes au lieu d'une. La première colonne a les clés et la deuxième colonne a les valeurs. Chaque ligne est une paire, faisant une paire clé/valeur. Une clé est directement liée à sa valeur.

Un exemple de carte est 'c',30, 'b',20, 'd',30, 'e',40, 'a',10. La première paire clé/valeur insérée ici est 'c',3, où 'c' est la clé et 30 est la valeur. Cette carte n'est pas ordonnée par clés. Le classement de cette carte par clés produit 'a',10, 'b',20, 'c',30, 'd',30, 'e',40. Notez qu'il peut y avoir des valeurs dupliquées, mais pas des clés dupliquées. Une carte ordonnée est une carte ordonnée par clés.

Un multi-ensemble est à un ensemble, comme un multi-carte est à une carte. Cela signifie qu'il existe des cartes avec des clés en double. Un exemple de multimap est 'a',10, 'b',20, 'b',20, 'c',30, 'c',30, 'd ',30, 'e',40. Et comme indiqué ci-dessus, cet article ne traite pas du multimap, il traite plutôt de la structure de données C++ appelée map.

En C++, une structure de données est une structure avec des propriétés (membres de données) et des méthodes (fonctions membres). Les données de la structure sont une liste ; un ensemble est une liste ; une carte est une liste de paires clé/valeur.

Cet article traite des bases des ensembles et des cartes en C++, et pour mieux comprendre cet article, le lecteur doit avoir des connaissances de base en C++.

Contenu de l'article :

Classe et ses objets
Création d'un ensemble ou d'une carte
Notions de base sur l'itérateur
Accès aux éléments pour l'ensemble et la carte
Ordre des éléments dans un ensemble ou une carte
Autres fonctions membres couramment utilisées
Conclusion

Classe et ses objets :

En C++, l'ensemble, la carte et d'autres structures similaires sont appelés conteneurs. Une classe est une unité généralisée avec des données membres, qui sont des variables, et des fonctions membres qui sont liées. Lorsque les données membres reçoivent des valeurs, un objet est formé. Cependant, un objet est formé dans un processus appelé, l'instanciation. Comme une classe peut conduire à des valeurs différentes pour les mêmes variables membres de données, différents objets peuvent alors être instanciés à partir de la même classe.

En C++, un ensemble inutilisable est une classe, ainsi qu'une map inutilisable. Lorsqu'un objet est instancié à partir de l'ensemble inutilisable ou de la carte inutilisable, l'objet devient la véritable structure de données. Avec les structures de données set et map, le membre de données principal est une liste. Eh bien, l'ensemble et la carte forment un groupe de conteneurs appelés conteneurs associatifs ordonnés. L'ensemble non ordonné et la carte non ordonnée existent également, mais ceux-ci ne sont malheureusement pas abordés dans cet article.

Création d'un ensemble ou d'une carte :

Instancier un ensemble à partir de sa classe d'ensembles, c'est créer un ensemble ; instancier une carte à partir de sa classe de carte crée une carte. L'objet ainsi créé se voit attribuer un nom au choix du programmeur.

Afin de créer un ensemble, le programme doit commencer par :

#inclure
#inclure
en utilisant l'espace de noms std ;

Notez la directive "#include ”, qui inclut la bibliothèque d'ensembles qui a la classe d'ensembles à partir de laquelle les structures de données d'ensembles seront instanciées.

Afin de créer une carte, le programme doit commencer par :

#inclure
#inclure
en utilisant l'espace de noms std ;

Notez la directive "#include ”, qui inclut la bibliothèque de cartes contenant la classe de carte à partir de laquelle les structures de données cartographiques seront instanciées.

La syntaxe pour créer un ensemble vide est :

ensemble nom de l'objet

Exemple:

ensemble setObj;

Un exemple pour créer un ensemble avec du contenu est :

ensemble setObj(6, 10, 2, 8, 4);

La syntaxe pour créer une carte vide est :

carte nom de l'objet

Exemple:

carte mapObj;

Un exemple pour créer une carte avec du contenu est :

carte mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Notions de base sur l'itérateur :

Un itérateur est un pointeur élaboré, qui peut être utilisé pour parcourir la liste de la structure de données du début à la fin.

La fonction membre begin()

La fonction membre begin() renvoie un itérateur qui pointe vers le premier élément de la liste. L'exemple suivant illustre cela pour l'ensemble :

ensemble setObj(6, 10, 2, 8, 4);
ensemble:: iterator iter = setObj.commencer();
cout << *iter << '\n';

Notez la façon dont begin() a été utilisé avec setObj et l'opérateur point. iter est l'objet itérateur renvoyé. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection. Utilisé avec iter, il renvoie le premier élément de l'ensemble ; le premier élément est 2 au lieu de 6 - voir explication ci-dessous.

L'exemple suivant illustre l'utilisation de la fonction begin() pour la carte :

carte mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carte:: iterator iter = mapObj.commencer();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Notez la façon dont begin() a été utilisé avec mapObj et l'opérateur point. iter est l'objet itérateur renvoyé. Notez également la façon dont il a été déclaré. « premier », tel qu'il est utilisé ici, fait référence à la clé. « seconde » fait référence à la valeur correspondant à la clé. Observez comment ils ont été utilisés avec iter pour obtenir les composants de l'élément de départ de la liste. Le premier élément est a,10 au lieu de c,30 - voir explication ci-dessous.

La fonction membre "begin() const"

La fonction membre "begin() const" renvoie un itérateur qui pointe vers le premier élément de la liste lorsque la déclaration de l'ensemble commence par const (pour constante). Dans cette condition, la valeur de la liste, référencée par l'itérateur renvoyé, ne peut pas être modifiée par l'itérateur. L'exemple suivant illustre son utilisation pour l'ensemble :

ensemble de const setObj(6, 10, 2, 8, 4);
ensemble::const_iterator iter = setObj.commencer();
cout << *iter << '\n';

Notez la façon dont begin() a été utilisé avec setObj et l'opérateur point. Aucun "const" n'a été tapé juste après begin(). Cependant, « const » a précédé la déclaration. iter ici est l'objet itérateur constant renvoyé, qui est différent de l'itérateur normal. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection ; comme utilisé avec iter, il renvoie le premier élément de l'ensemble. Le premier élément est 2 au lieu de 6 - voir explication ci-dessous.

L'exemple suivant illustre l'utilisation de la fonction "begin() const" pour la carte :

carte de const mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carte::const_iterator iter = mapObj.commencer();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Notez la façon dont begin() a été utilisé avec mapObj et l'opérateur point. Aucun "const" n'a été tapé juste après begin(). Cependant, « const » a précédé la déclaration. iter ici est l'objet itérateur constant renvoyé, qui est différent de l'itérateur normal. Notez également la façon dont il a été déclaré. « premier », tel qu'il est utilisé ici, fait référence à la clé ; "second", tel qu'utilisé ici, fait référence à la valeur correspondant à la clé. Observez comment ils ont été utilisés avec iter pour obtenir les composants de l'élément de départ de la liste. Le premier élément est a,10 au lieu de c,30 - voir explication ci-dessous.

La fonction membre end()

La fonction membre end() renvoie un itérateur qui pointe juste après la fin de la liste. L'exemple suivant illustre cela pour l'ensemble :

ensemble setObj(6, 10, 2, 8, 4);
ensemble:: iterator iter = setObj.finir();
cout << *iter << '\n';

Notez la façon dont end() a été utilisé avec setObj et l'opérateur point. iter est l'objet itérateur renvoyé. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection ; comme utilisé avec iter, il renvoie le dernier +1 élément de l'ensemble. Dans l'ordinateur de l'auteur, ce dernier +1 élément est 5, ce qui n'est pas sur la liste. Attention donc à ne pas utiliser cet élément.

L'exemple suivant illustre l'utilisation de la fonction end() pour la carte :

carte mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carte:: iterator iter = mapObj.finir();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Notez la façon dont end() a été utilisé avec mapObj et l'opérateur point. iter est l'objet itérateur renvoyé. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection ; comme utilisé avec iter, il renvoie le dernier +1 élément de la carte. Dans l'ordinateur de l'auteur, ce dernier +1 élément est ,0, qui n'est pas dans la liste. Attention donc à ne pas utiliser cet élément.

La fonction membre "end() const"

La fonction membre « end() const » renvoie un itérateur qui pointe juste après la fin de la liste lorsque la déclaration de l'ensemble commence par const (pour constant). Dans cette condition, la valeur de la liste, référencée par l'itérateur renvoyé, ne peut pas être modifiée par l'itérateur. L'exemple suivant illustre son utilisation pour l'ensemble :

ensemble de const setObj(6, 10, 2, 8, 4);
ensemble::const_iterator iter = setObj.finir();
cout << *iter << '\n';

Notez la façon dont end() a été utilisé avec setObj et l'opérateur point. Aucun "const" n'a été tapé juste après la fin (). Cependant, « const » a précédé la déclaration. iter est l'objet itérateur renvoyé. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection ; comme utilisé avec iter, il renvoie le dernier +1 élément de l'ensemble.

L'exemple suivant illustre l'utilisation de la fonction « end() const » pour la carte :

carte de const mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
carte::const_iterator iter = mapObj.finir();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Notez la façon dont end() a été utilisé avec mapObj et l'opérateur point. Aucun "const" n'a été tapé juste après la fin (). Cependant, « const » a précédé la déclaration. iter est l'objet itérateur constant renvoyé, qui est différent de l'itérateur normal. Aussi, observez attentivement la façon dont il a été déclaré.

Accès aux éléments pour l'ensemble et la carte :

Ensemble

Avec l'ensemble, l'élément est lu à l'aide de l'opérateur d'indirection. Les deux premiers éléments d'un ensemble sont lus dans l'exemple suivant :

ensemble setObj(6, 10, 2, 8, 4);
ensemble:: iterator iter = setObj.commencer();
cout << *iter << '\n';
++iter;
cout << *iter << '\n';

La sortie est 2, puis suivie de 4 - voir explication ci-dessous. Pour pointer sur l'élément suivant de la liste, l'itérateur est incrémenté.

Remarque : Un élément ne peut pas être modifié à l'aide de l'opérateur d'indirection de l'ensemble. Par exemple, « * iter = 9 ; » n'est pas possible.

carte

Une carte se compose de paires clé/valeur. Une valeur peut être lue à l'aide de la clé correspondante, et modifiée à l'aide de la même clé. Le segment de code suivant illustre cela :

carte mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj['b'] << '\n';
mapObj['b'] = 55;
cout << mapObj['b'] << '\n';

La sortie est :

20
55

L'opérateur point n'a pas été utilisé ici. Au lieu de cela, c'est l'opérateur crochets, qui prend la clé comme contenu, qui a été utilisé.

Ordre des éléments dans un ensemble ou une carte :

Les éléments peuvent être insérés dans un ensemble, dans n'importe quel ordre. Cependant, une fois inséré, l'ensemble réorganise ses éléments dans l'ordre croissant. L'ordre croissant est l'ordre par défaut. Si l'ordre décroissant est nécessaire, alors l'ensemble doit être déclaré comme dans l'exemple suivant :

ensemble > setObj(6, 10, 2, 8, 4);

Donc, après le type, e.g., int, pour le modèle, il y a une virgule, suivie de "plus" dans les parenthèses angulaires.

Les éléments peuvent être insérés dans une carte dans n'importe quel ordre. Cependant, une fois insérée, la carte réorganise ses éléments dans l'ordre croissant par clé (uniquement) tout en conservant la relation entre chaque clé et sa valeur. L'ordre croissant est l'ordre par défaut ; si l'ordre décroissant est nécessaire, alors la carte doit être déclarée comme dans l'exemple suivant :

carte > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);

Donc, après la paire de types, e.g., "char, int", pour le modèle, il y a une virgule, suivie de "plus" dans les parenthèses angulaires.

Traverser un ensemble

La boucle while ou for avec l'itérateur peut être utilisée pour parcourir un ensemble. L'exemple suivant utilise une boucle for pour parcourir un ensemble qui a été configuré dans l'ordre décroissant :

ensemble > setObj(6, 10, 2, 8, 4);
pour (définir:: iterator iter = setObj.commencer(); itérer != setObj.finir(); ++iter)

cout << *iter << ";

La sortie est :

10 8 6 4 2

L'incrémentation d'un itérateur le pointe vers l'élément suivant.

Parcourir une carte

La boucle while ou for avec l'itérateur peut être utilisée pour parcourir une carte. L'exemple suivant utilise une boucle for pour parcourir une carte qui a été configurée dans l'ordre décroissant :

carte > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
pour (carte:: iterator iter = mapObj.commencer(); itérer != mapObj.finir(); ++iter)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

La sortie est :

e, 40, d, 30, c, 30, b, 20, a, 10,

L'incrémentation d'un itérateur le pointe vers l'élément suivant. « premier », dans le code, fait référence à la clé et « deuxième » fait référence à la valeur correspondante. Notez comment ces valeurs ont été obtenues pour la sortie.

Autres fonctions membres couramment utilisées :

La fonction size()

Cette fonction renvoie un entier, qui est le nombre d'éléments dans la liste. Exemple de jeu :

ensemble > setObj(6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

La sortie est de 5.

Exemple de carte :

carte > mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
cout << mapObj.size() << '\n';

La sortie est de 5.

La fonction insert()

ensemble

l'ensemble n'autorise pas les doublons. Ainsi, tout doublon inséré est silencieusement rejeté. Avec l'ensemble, l'argument de la fonction insert() est la valeur à insérer. La valeur est ajustée dans une position, dans laquelle l'ordre dans l'ensemble reste croissant ou décroissant. Exemple:

ensemble setObj(6, 10, 2, 8, 4);
setObj.insérer (6) ;
setObj.insérer (9) ;
setObj.insérer(12);
pour (définir:: iterator iter = setObj.commencer(); itérer != setObj.finir(); ++iter)

cout << *iter << ";

La sortie est :

2 4 6 8 9 10 12

Remarque : La fonction membre insert() peut être utilisée pour remplir un ensemble vide.

carte

la carte n'autorise pas la duplication par clé. Ainsi, tout doublon inséré est silencieusement rejeté. Avec la carte, l'argument de la fonction insert() est la paire clé/valeur entre accolades. L'élément est inséré dans une position par clé, dans laquelle l'ordre dans la carte reste croissant ou décroissant. Exemple:

carte mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
mapObj.insert('e',80);
mapObj.insert('f',50);
mapObj.insert('g',60);
pour (carte:: iterator iter = mapObj.commencer(); itérer != mapObj.finir(); ++iter)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

La sortie est :

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

Remarque : La fonction membre insert() peut être utilisée pour remplir une carte vide.

La fonction vide()

Cette fonction retourne vrai si la liste est vide, et faux sinon. Exemple de jeu :

ensemble setObj(6, 10, 2, 8, 4);
bool ret = setObj.vider();
cout << ret << '\n';

La sortie est 0 pour false, ce qui signifie que l'ensemble ici n'est pas vide.

Exemple de carte :

carte mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
bool ret = mapObj.vider();
cout << ret << '\n';

La sortie est 0 pour false, ce qui signifie que la carte ici n'est pas vide.

La fonction d'effacement ()

ensemble

Considérez le segment de code suivant :

ensemble setObj(10, 20, 30, 40, 50);
ensemble:: iterator iter = setObj.commencer();
ensemble:: iterator itr = setObj.effacer(iter);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
itr = setObj.effacer(itr);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';

La sortie est :

nouvelle taille: 4
valeur suivante : 20
nouvelle taille : 3
valeur suivante : 30

La fonction d'effacement () prend un itérateur qui pointe vers un élément comme argument. Après avoir effacé l'élément, la fonction effacer() renvoie un itérateur qui pointe vers l'élément suivant.

carte

Considérez le segment de code suivant :

carte mapObj('a',10,'b',20,'c',30,'d',40,'e',50);
carte:: iterator iter = mapObj.commencer();
carte::iterator itr = mapObj.effacer(iter);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
itr = mapObj.effacer(itr);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

La sortie est :

nouvelle taille: 4
paire de valeurs suivante : b,20
nouvelle taille : 3
paire de valeurs suivante : c,30

La fonction clear()

La fonction clear() supprime tous les éléments de la liste. Exemple de jeu :

ensemble setObj(6, 10, 2, 8, 4);
setObj.dégager();
cout << setObj.size() << '\n';

La sortie est 0.

exemple de carte :

carte mapObj('c',30,'b',20,'d',30,'e',40,'a',10);
mapObj.dégager();
cout << mapObj.size() << '\n';

La sortie est 0.

Conclusion:

Une structure de données définie en C++ est une structure dans laquelle la liste des éléments est stockée par ordre croissant par défaut, ou par ordre décroissant au choix du programmeur. Tous les éléments de l'ensemble sont uniques. Une structure de données de carte en C++ est une structure dans laquelle la liste est un hachage de paires clé/valeur, stockées dans l'ordre croissant des clés par défaut, ou dans l'ordre décroissant des clés par choix du programmeur. Les clés sont également uniques, et il peut y avoir des valeurs dupliquées. La principale donnée membre de l'une ou l'autre des structures est la liste. Chaque structure a des fonctions membres, dont certaines sont couramment utilisées.