conteneurs STL associatifs. partie 6




c ++ débutants, Standard Template Library, conteneurs associatifs STL C ++, paire c ++, carte<> c ++Tous les types de conteneurs précédents (mentionnés ou discutés en détail: vecteur, liste, et) - une collection cohérente, dans lequel les éléments sont disposés séquentiellement l'un après l'autre, mais ils diffèrent entre un procédé pour accéder à des éléments.

Une autre grande catégorie de conteneurs sont dits conteneurs associatifs, qui sont, en fait, tables, recherche des valeurs qui ont fait pour certains clés.

Mais avant de détailler les conteneurs associatifs, attention à une classe de modèle (в составе STL) comment paire<>. C'est une conception assez simple. Chaque objet représente une paire connectée de champs premier et seconde. Dans les tableaux (en STL ou dans vos propres classes) Ces champs peuvent être la clé, et la valeur. Mais nous ne serons pas pressés - une classe de modèle paire<> et peut lui-même être intéressant quel que soit les conteneurs.

nous, par exemple, déterminer classe représentation 2D des points dans le plan pour une large classe de problèmes géométriques (файл Point.h):

point p(*ce); moyens, qui crée une nouvelle variable (objet) classe point, et a appelé son constructeur de copie. Prises pour initialiser la valeur de l'objet en cours *ce – comme indiqué par la aiguille ce. à savoir. une nouvelle variable point p établi, comme une copie de l'objet courant. Le reste de vous tous est d'être compris.

résultat:c ++ débutants, Standard Template Library, conteneurs associatifs STL C ++, paire<> c ++

maintenant, quand nous voyons, ce qu'est un modèle de classe paire<>, nous pouvons aller à la liste des, quels sont les conteneurs associatifs de base STL.

Contrairement à la discuté précédemment consécutif conteneurs, élément dans lequel l'emplacement est déterminé par sa position parmi les autres éléments, conteneurs associatifs sont stockés en tant que paire d'éléments (paire<>) <clé, sens>. Pour trouver les valeurs de l'élément que vous souhaitez rechercher sa clé, qui peut être une variété de types.

note: peut être considéré comme, dans tableau ou vecteur La recherche est un index de clé, qui a toujours entier sens. par analogie, table de type générique (hashtable) carte<>, à partir de laquelle nous commencerons le type associatif, peut être considéré comme, dans un tableau ou un vecteur (pour faciliter la compréhension ). Il peut être indexé par tout (mais toujours seul) type de clé aléatoire, type: Titre[ 'une’ ], payer или[ “Ivanov” ].

L'un des plus fréquemment utilisés conteneurs associatifs STL est carte<> - Table, des paires de tableaux <clé, sens>, dans lequel la recherche est effectuée sur un élément clé. La clé peut avoir tout type complexe, à condition que, qui existe pour ce type d'opération comparaison (moins Plus), ou une telle opération est réalisée par l'utilisateur et est spécifiée lors de la création d'une table. Pour illustrer une application simple carte<> Nous utilisons l'exemple déjà discuté plus tôt avec une base des étudiants de la Faculté de l'information:

résultat:c ++ débutants, Standard Template Library, conteneurs associatifs STL C ++, paire c ++, carte<> c ++Même un exemple superficiel (jusqu'à ce que nous sommes profondément dans les détails des conteneurs associatifs) Il vous permet de voir et d'en tirer quelques conclusions:

  • éléments, placé dans le tableau, Il n'est pas placé dans l'ordre de leur placement (comme avec vecteur ou liste), mais dans l'ordre de tri par valeur de la clé (FIO);

  • Voilà pourquoi pour le type de données, la clé doit être soit l'opération de comparaison, ou il doit être créé par l'utilisateur;

pour la recherche (par la clé) conteneurs associatifs non en utilisant une analyse séquentielle de tous les éléments, un des algorithmes très efficaces et sophistiqués, travaillé pendant des années (et même des décennies) существования STL . Habituellement, pour la mise en œuvre de carte<> Technique utilisée d'arbres rouge-noir ... mais les détails de ce ne sont pas fondamentales. Une conclusion importante de ce fait devrait être la, que la recherche de conteneurs associatifs est très rapide, et il est beaucoup mieux, que si vous avez essayé de le mettre en œuvre manuellement.

Bulletin de nouvelles leçons sur la programmation:

conteneurs STL associatifs. partie 6
Noter cet article

Sur huile

une expérience pratique sur le développement de logiciels 40 ans. société de logiciels internationale Global Teacher Logic. IBM Developer Works auteur permanent des publications. éditeur scientifique de l'ordinateur littérature maison d'édition "Symbole-Plus", Saint-Pétersbourg.

Laisser un commentaire

Votre adresse email ne sera pas publiée. les champs requis sont indiqués *