Implémentation de la carte en C++

Question

Je trouve que l'ensemble et la carte sont implémentés comme un arbre. set est un arbre de recherche binaire, map est un arbre de recherche binaire auto-équilibré, tel qu'un arbre rouge-noir? Je suis confus au sujet de la différence au sujet de la mise en œuvre. La différence je peux l'image sont les suivantes

1) élément dans la série a une seule valeur (n), l'élément de carte comporte deux valeurs. 2) set est utilisé pour stocker et récupérer des éléments par lui-même. map est utilisé pour stocker et récupérer des éléments via la clé.

Quoi d'autre sont importants?

Merci!

Answer 1

Les cartes et les ensembles ont un comportement presque identique et il est courant que l'implémentation utilise exactement la même technique sous-jacente.

La seule différence importante est la carte ne pas utiliser toute value_type pour comparer, juste la partie clé de celui-ci.

Answer 2

Habituellement, vous saurez tout de suite que vous avez besoin: si vous avez juste un bool pour l'argument « valeur » à la carte, vous voulez probablement un ensemble à la place.

Set est un concept mathématique discret qui, dans mon expérience, apparaît encore et encore dans la programmation. La classe stl set est un moyen relativement efficace de garder trace des ensembles où les opérations les plus courantes sont insert/remove/find.

Les cartes sont utilisées lorsque les objets ont une identité unique qui est petite par rapport à l'ensemble de leurs attributs. Par exemple, une page Web peut être définie comme une URL et un flux d'octets de contenu. Vous pourriez mettre ce flux d'octets dans un ensemble, mais le processus de recherche binaire serait extrêmement lent (puisque le contenu est beaucoup plus grand que l'URL) et vous ne seriez pas capable de rechercher une page Web si son contenu change. L'URL est l'identité de la page Web, c'est donc la clé de la carte.

Answer 3

Une carte est généralement mis en œuvre comme un ensemble < std :: paire <>>.

L'ensemble est utilisé lorsque vous souhaitez une liste ordonnée de rechercher rapidement un élément, au fond, tandis qu'une carte est utilisée lorsque vous souhaitez récupérer une valeur donnée sa clé. Dans les deux cas, la clé (pour la carte) ou la valeur (pour l'ensemble) doit être unique. Si vous souhaitez stocker plusieurs valeurs identiques, vous utiliserez multimap ou multiset.