Conteneurs uniques et commandés en C ++

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

Une carte dans le logiciel est comme un tableau, mais c'est un tableau avec deux colonnes au lieu d'une. La première colonne a les touches 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 de clés / valeur insérée ici, est 'c', 3, où 'c' est la clé et 30 est la valeur. Cette carte n'est pas commandée par les clés. L'ordre de cette carte par les touches 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 commandée est une carte commandée par les clés.

Un multiset est à un ensemble, car un multimap est à une carte. Cela signifie qu'il y a des cartes avec des clés en double. Un exemple d'un 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 de clés / valeur.

Cet article traite des bases des ensembles et des cartes en C ++, et pour mieux comprendre cet article, le lecteur aurait dû avoir une connaissance de base de C++.

Contenu de l'article:

• Classe et ses objets
• Création d'un ensemble ou d'une carte
• Bases itérateurs
• Accès à l'élément 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ées conteneurs. Une classe est une unité généralisée avec des membres de données, qui sont des variables et des fonctions membres qui sont liées. Lorsque les membres de données reçoivent des valeurs, un objet est formé. Cependant, un objet est formé dans un processus appelé, instanciation. Comme une classe peut conduire à des valeurs différentes pour les mêmes variables de 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 carte inutilisable. Lorsqu'un objet est instancié à partir de l'ensemble inutilisable ou de la carte inutilisable, l'objet devient la structure de données réelle. Avec les structures de données SET et MAP, le principal membre de données est une liste. Eh bien, l'ensemble et la carte forment un groupe de conteneurs appelés, commandés de conteneurs associatifs. L'ensemble non ordonné et la carte non ordonnée existent également, mais celles-ci ne sont malheureusement pas abordées dans cet article.

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

Instanciation d'un ensemble de sa classe SET créent un ensemble; Instanciation d'une carte à partir de sa classe de carte est de créer une carte. L'objet ainsi créé reçoit un nom du choix du programmeur.

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

#inclure
#inclure
Utilisation de Namespace Std;

Remarque la directive «#include», qui comprend la bibliothèque définie qui a la classe définie à partir de laquelle les structures de données définies seront instanciées.

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

#inclure
#inclure
Utilisation de Namespace Std;

Notez la directive «#include», qui comprend la bibliothèque de cartes qui contient la classe de carte à partir de laquelle les structures de données de cartes seront instanciées.

La syntaxe pour créer un ensemble vide est:

ensemble nom d'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 d'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);

Bases Iterator:

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 de membre begin ()

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

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

Remarque La façon dont Begin () a été utilisée avec SetObj et l'opérateur DOT. iter est l'objet itérateur retourné. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection. Tel qu'utilisé avec Iter, il renvoie le premier élément de l'ensemble; Le premier élément est 2 au lieu de 6 - voir l'explication ci-dessous.

L'exemple suivant illustre l'utilisation de la fonction début () pour la carte:

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

Remarque la façon dont Begin () a été utilisée avec MapObj et l'opérateur de points. iter est l'objet itérateur retourné. Notez également la façon dont il a été déclaré. «D'abord», comme utilisé ici, fait référence à la clé. «Second» fait référence à la valeur correspondant à la clé. Observez comment ils ont été utilisés avec Iter pour obtenir les composants de démarrage de la liste. Le premier élément est a, 10 au lieu de c, 30 - voir l'explication ci-dessous.

La fonction de 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, mentionné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:

constant constance setObj (6, 10, 2, 8, 4);
ensemble:: const_iterator iter = setObj.commencer();
couter << *iter << '\n';

Remarque La façon dont Begin () a été utilisée avec SetObj et l'opérateur DOT. Aucun «const» n'a été tapé juste après Begin (). Cependant, «const» a précédé la déclaration. Iter voici l'objet itérateur constant retourné, 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; Tel qu'utilisé avec Iter, il renvoie le premier élément de l'ensemble. Le premier élément est 2 au lieu de 6 - voir l'explication ci-dessous.

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

cartographie constante MapoBj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
carte:: const_iterator iter = mapobj.commencer();
couter << "" << (*iter).first <<',' << (*iter).second << "\n";

Remarque la façon dont Begin () a été utilisée avec MapObj et l'opérateur de points. Aucun «const» n'a été tapé juste après Begin (). Cependant, «const» a précédé la déclaration. Iter voici l'objet itérateur constant retourné, qui est différent de l'itérateur normal. Notez également la façon dont il a été déclaré. «D'abord», comme utilisé ici, fait référence à la clé; «Deuxième», 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 démarrage de la liste. Le premier élément est a, 10 au lieu de c, 30 - voir l'explication ci-dessous.

La fonction de membre fin ()

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

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

Remarque la façon dont fin () a été utilisée avec SetObj et l'opérateur de points. iter est l'objet itérateur retourné. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection; Tel qu'utilisé avec Iter, il renvoie le dernier élément + 1 de l'ensemble. Dans l'ordinateur de l'auteur, ce dernier élément + 1 est de 5, ce qui n'est pas sur la liste. Alors, attention à ne pas utiliser cet élément.

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

carte MapoBj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
carte:: iterator iter = mapobj.fin();
couter << "" << (*iter).first <<',' << (*iter).second << "\n";

Remarque la façon dont End () a été utilisée avec MapoBJ et l'opérateur de points. iter est l'objet itérateur retourné. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection; Tel qu'utilisé avec Iter, il renvoie le dernier élément + 1 de la carte. Dans l'ordinateur de l'auteur, ce dernier élément + 1 est , 0, qui n'est pas dans la liste. Alors, attention à ne pas utiliser cet élément.

La fonction de membre «end () const»

La fonction de 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 constante). Dans cette condition, la valeur de la liste, mentionné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:

constant constance setObj (6, 10, 2, 8, 4);
ensemble:: const_iterator iter = setObj.fin();
couter << *iter << '\n';

Remarque la façon dont fin () a été utilisée avec SetObj et l'opérateur de points. 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 retourné. Notez également la façon dont il a été déclaré. * est l'opérateur d'indirection; Tel qu'utilisé avec Iter, il renvoie le dernier élément + 1 de l'ensemble.

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

cartographie constante MapoBj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
carte:: const_iterator iter = mapobj.fin();
couter << "" << (*iter).first <<',' << (*iter).second << "\n";

Remarque la façon dont End () a été utilisée avec MapoBJ et l'opérateur de points. 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 soigneusement la façon dont il a été déclaré.

Accès à l'élément 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();
couter << *iter << '\n';
++iter;
couter << *iter << '\n';

La sortie est 2, puis suivie de 4 - voir l'explication ci-dessous. Pour pointer à 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 pour l'ensemble. Par exemple, «* iter = 9;» n'est pas possible.

carte

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

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

La sortie est:

20
55

L'opérateur de points n'a pas été utilisé ici. Au lieu de cela, c'est l'opérateur de carrés de 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 par ordre croissant. L'ordre croissant est l'ordre par défaut. Si l'ordre descendant est nécessaire, 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, suivi de «plus grand» dans les supports d'angle.

Les éléments peuvent être insérés dans une carte dans n'importe quel ordre. Cependant, une fois inséré, la carte réorganise ses éléments dans l'ordre croissant par clé (uniquement) tout en maintenant la relation entre chaque clé et sa valeur. L'ordre croissant est l'ordre par défaut; Si l'ordre descendant est nécessaire, 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, suivi de «plus grand» dans les supports d'angle.

Traverser un ensemble

La boucle ou la boucle pour l'itérateur peut être utilisée pour traverser un ensemble. L'exemple suivant utilise une boucle pour traverser un ensemble qui a été configuré dans l'ordre descendant:

ensemble > setObj (6, 10, 2, 8, 4);
pour (ensemble:: iterator iter = setObj.commencer(); iter != setObj.fin(); ++ iter)

couter << *iter << ";

La sortie est:

10 8 6 4 2

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

Traverser une carte

La boucle ou la boucle pour l'itérateur peut être utilisée pour traverser une carte. L'exemple suivant utilise une boucle pour traverser une carte qui a été configurée dans l'ordre descendant:

carte > mapoBj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
pour (carte:: iterator iter = mapobj.commencer(); iter != mapobj.fin(); ++ iter)

couter << "" << (*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. «Premièrement», 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. Définir l'exemple:

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

La sortie est 5.

Exemple de carte:

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

La sortie est 5.

La fonction insert ()

ensemble

le jeu ne permet pas de double. Ainsi, tout double inséré est rejeté silencieusement. Avec l'ensemble, l'argument de la fonction insert () est la valeur à insérer. La valeur est installée dans une position, dans laquelle l'ordre dans l'ensemble reste ascendant ou descendant. Exemple:

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

couter << *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 ne permet pas de double par clé. Ainsi, tout double inséré est rejeté silencieusement. Avec la carte, l'argument de la fonction insert () est la paire de touches / valeur en accolades. L'élément est installé dans une position par clé, dans laquelle l'ordre dans la carte reste ascendant ou descendant. 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(); iter != mapobj.fin(); ++ iter)
couter << "" << (*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 renvoie vrai si la liste est vide, et fausse si autrement. Définir l'exemple:

ensemble setObj (6, 10, 2, 8, 4);
bool ret = setObj.vide();
couter << 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.vide();
couter << ret << '\n';

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

La fonction effacer ()

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);
couter << "new size: " << setObj.size() << '\n';
couter << "next value: " << *itr << '\n';
itr = setObj.Effacer (ITR);
couter << "new size: " << setObj.size() << '\n';
couter << "next value: " << *itr << '\n';

La sortie est:

Nouvelle taille: 4
Valeur suivante: 20
Nouvelle taille: 3
Valeur suivante: 30

La fonction effacer () prend un itérateur qui pointe 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);
couter << "new size: " << mapObj.size() << '\n';
couter << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
ITR = MapoBj.Effacer (ITR);
couter << "new size: " << mapObj.size() << '\n';
couter << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

La sortie est:

Nouvelle taille: 4
Paire de valeur suivante: b, 20
Nouvelle taille: 3
Paire de valeur suivante: C, 30

La fonction effacer () prend un itérateur qui pointe 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.

La fonction claire ()

La fonction claire () supprime tous les éléments de la liste. Définir l'exemple:

ensemble setObj (6, 10, 2, 8, 4);
setobj.clair();
couter << setObj.size() << '\n';

La sortie est 0.

Exemple de carte:

carte MapoBj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapobj.clair();
couter << 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 par le 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 de clés / valeur, stocké par ordre croissant des clés par défaut, ou dans l'ordre descendant des clés par le choix du programmeur. Les clés sont également uniques, et il peut y avoir des valeurs dupliquées. Le principal membre de données de l'une ou l'autre des structures est la liste. L'une ou l'autre structure a des fonctions membres, dont certaines sont couramment utilisées.