cpp comment comparer aux cartes


Réponse 1:

Mathématiquement, une carte est un modèle qui prend une clé et répond avec une valeur. Un Set est un cas spécialisé de Map où la clé est identique à la valeur à laquelle elle correspond. Ce concept s'étend à l'implémentation C ++ de ces deux objets.

Quand std :: map est-il utile: considérez une base de données stockant des comptes d'utilisateurs, disons que ce sont des comptes netflix. La carte qui représente cette table d'utilisateurs de Netflix peut recevoir un ID utilisateur et renvoyer l'objet utilisateur correspondant à ce numéro d'identification. Nous pouvons ensuite utiliser l'ID pour récupérer le compte d'utilisateur dans le temps O (1) en hachant l'ID d'utilisateur unique sur le compte, et pour rechercher un compte, tout ce dont vous auriez besoin est l'ID afin de récupérer toutes ces données utilisateur.

Pouvons-nous faire cela avec std :: set? Comment pourrions-nous implémenter cet exemple précédent avec un ensemble? Nous pouvons insérer des comptes utilisateur dans notre std :: set, mais lorsque nous souhaitons rechercher un compte utilisateur, nous aurons besoin de l'intégralité du compte utilisateur afin d'effectuer une recherche sur notre enregistrement utilisateur. Attendez une minute, si nous avons déjà les informations du compte utilisateur, pourquoi aurions-nous besoin de les rechercher? Et si nous n'avons que le numéro d'identification de l'utilisateur, nous ne pouvons plus récupérer le compte en temps O (1), nous devons parcourir toute la table pour trouver le compte qui correspond et ce sera O (N).

Quand pouvez-vous utiliser std :: map ou quand vous voudrez peut-être utiliser std :: map pour les primitives? Considérons une structure destinée à stocker tous les nombres premiers sous une valeur arbitraire N.Si nous voulons simplement savoir si un nombre est membre de l'ensemble des nombres premiers, alors std :: set a du sens, nous pouvons simplement vouloir vérifier si un entier arbitraire la valeur 'k' existe dans notre ensemble et nous pouvons être indifférents à toute notion d'index ou de clé. Cependant, si nous nous intéressons à la séquence des nombres premiers, nous souhaitons peut-être un couple clé-valeur. Peut-être aimerions-nous modéliser la séquence p = {2, 3, 5, 7, 11,…} et nous aimerions savoir si p [j] = k pour certaines valeurs arbitraires de j & k. Dans ce dernier cas, nous pouvons vouloir considérer std :: map (bien que std :: vector puisse également être un bon choix).

Donc en bref:

  1. Une structure de données d'ensemble est un type spécialisé de structure de données de carte où clé == valeur, et les définitions C ++ STL reflètent ce concept
  2. std :: map que std :: set est généralement plus utile car std :: map fournit une recherche rapide par clé pour les valeurs agrégées (objets entiers plutôt que primitives).
  3. std :: set est souvent plus utile pour les primitives car le mappage d'une valeur primitive k-> k est plutôt arbitraire

Réponse 2:

Beaucoup de réponses n'abordent pas le changement d'implémentation de la carte et des conteneurs définis pour C ++ 17, même lorsque cela est pertinent, donc je couvrirai cela exclusivement.

Comment déplacer un nœud d'un conteneur à un autre?

Comment modifier la clé d'un nœud de carte?

Si vous avez placé des données mobiles mais non copiables dans une carte ou un ensemble, comment pouvez-vous les récupérer?

C ++ 17 répond à toutes ces questions par l'ajout d'une nouvelle structure de données opaque… le descripteur de nœud… et deux nouvelles fonctions membres pour chaque ensemble ou conteneur de carte qui fonctionnent avec des descripteurs de nœud… extrait, qui extrait un nœud d'une carte ou set dans un handle de nœud, et une nouvelle surcharge d'insertion, qui prend un nœud d'un handle de nœud et l'insère dans une carte ou un ensemble. Il existe également une nouvelle méthode pratique, la fusion, qui déplace tous les nœuds non dupliqués dans une carte ou ensemble dans une autre.

Poignée de nœud (C ++ 17)

Un handle de nœud a plusieurs propriétés. Il possède un nœud extrait exactement de la même manière qu'un std :: unique_ptr et est donc également déplaçable mais non copiable. Si un descripteur de nœud possède un nœud lorsqu'il est détruit, le nœud est détruit et désalloué… ce qui signifie qu'il doit également avoir une copie de l'allocateur utilisé dans son conteneur pour effectuer la désallocation. Cela signifie que les allocateurs utilisés dans deux conteneurs doivent comparer égaux (l'opérateur == renvoie true) pour qu'un nœud soit déplacé d'un conteneur à l'autre. Tous les allocateurs par défaut se comparent égaux, donc ce n'est généralement pas un problème.

Alors qu'un nœud appartient à un handle de nœud nh, il peut être utilisé d'une manière qui n'est pas possible tant qu'il se trouve dans une carte ou un ensemble. Par exemple, un nœud de carte extrait peut avoir sa clé modifiée en affectant à nh.key () et avoir une valeur mappée non copiable déplacée à l'aide de std :: move (nh.mapped ()). Un nœud d'ensemble extrait peut avoir une valeur non copiable déplacée à l'aide de std :: move (nh.value ()).


Réponse 3:

Actuellement, C ++ propose 8 standards

conteneurs associatifs

dans cet espace:

  • std :: set
  • std :: multiset
  • std :: unordered_set
  • std :: unordered_multiset
  • std :: carte
  • std :: multimap
  • std :: unordered_map
  • std :: unordered_multimap

Vous remarquerez peut-être qu'il y a 3 axes de variation ici:

  • ensemble vs carte.
  • ordonné vs non ordonné.
  • clé unique vs clé multiple.

Vous avez posé des questions sur le jeu et la carte; cependant, il vaut la peine de savoir comment choisir parmi les 8 combinaisons.

ensemble vs carte

Un ensemble contient un ensemble de clés. Vous pouvez insérer et supprimer des clés de l'ensemble, tester si la clé est présente dans l'ensemble et parcourir l'ensemble de toutes les clés. Une fois qu'une clé est insérée dans l'ensemble, la clé est immuable. Vous ne pouvez pas modifier une clé une fois qu'elle est insérée. Vous devez plutôt la supprimer et insérer la nouvelle clé si vous souhaitez modifier une clé existante.

Une carte associe une valeur à chaque clé. Les valeurs peuvent être un type distinct de la clé elle-même. Normalement, les valeurs sont également modifiables. Je peux rechercher une valeur par sa clé et changer la valeur une fois que je l'ai trouvée.

Vous souhaitez utiliser set lorsque vous ne vous souciez que de l'ensemble de clés dont vous disposez. Vous souhaitez utiliser la carte lorsque vous souhaitez suivre un groupe de valeurs auxquelles des clés sont associées.

Par exemple, supposons que je veuille garder une trace de toutes les personnes participant à une réunion. Un ensemble pourrait être suffisant pour cela. Chaque participant est membre de l'ensemble, et je peux parcourir tous les membres de l'ensemble pour générer une liste de participants.

Supposons que ma réunion soit prise en charge et que je souhaite suivre les préférences de repas de toutes les personnes participant à ma réunion. Maintenant, je veux une carte des participants aux préférences de repas. La clé dans ce cas est le participant et la valeur est la préférence de repas. Vous pouvez modifier les préférences de repas de chaque participant sans modifier le participant lui-même. (C'est moins gênant comme ça…)

ordonné vs non ordonné

Les conteneurs associatifs sans

désordonné

dans l'offre de nom

O (\ lg n)

temps d'accès. Ils nécessitent des clés

Comparable

et

Strict faible ordonné.

Ils sont généralement construits à partir d'arbres de recherche binaires équilibrés. Si vous itérez sur tous les éléments, vous visiterez les clés dans un ordre non décroissant. (Ou ordre non croissant, si vous utilisez des itérateurs inversés.)

Les conteneurs associatifs dont le nom n'est pas ordonné offrent un temps d'accès O (1) amorti, à condition que vous puissiez construire une fonction de hachage O (1) pour votre clé. Familièrement, ceux-ci sont connus sous le nom de tables de hachage. Vous avez besoin d'une fonction de hachage efficace pour que les conteneurs non ordonnés fonctionnent efficacement. Si vous parcourez tous les éléments, vous visiterez les clés dans un ordre arbitraire.

Quand devriez-vous utiliser avec ou sans commande? Cela dépend de plusieurs choses:

  • Avez-vous besoin de visiter souvent toutes les clés dans un ordre déterministe? Si tel est le cas, un conteneur commandé peut être un choix raisonnable.
  • La comparaison est-elle plus rapide ou plus lente que le hachage? Si c'est beaucoup plus rapide, la commande pourrait être meilleure. Si c'est beaucoup plus lent, sans ordre pourrait être plus rapide.
  • Connaissez-vous la taille totale approximative du conteneur à l'avance? Le redimensionnement d'un conteneur non commandé peut être coûteux, tandis que l'insertion dans un conteneur commandé n'a pas tendance à avoir des fluctuations de performances féroces.
  • Quelle empreinte mémoire pouvez-vous tolérer? Les conteneurs non commandés ont tendance à échanger la taille contre la vitesse.

Si vous écrivez votre code avec soin, vous pouvez essayer de basculer entre les conteneurs ordonnés et non ordonnés pour comparer les meilleurs résultats pour votre charge de travail particulière.

Une application que j'ai écrite a abouti à un mélange intéressant de conteneurs commandés et non commandés basé sur un tel benchmarking. J'ai été un peu surpris de savoir quels conteneurs ont gagné où et comment cela a changé lorsque j'ai changé les propriétés des clés. En particulier, le passage de std :: string à une table de chaînes indexée par des entiers a sensiblement modifié le coût des fonctions de hachage.

clé unique vs clé multiple

Les conteneurs associatifs sans multi dans le nom n'autorisent qu'une seule instance de chaque clé dans le conteneur. Autrement dit, chaque clé doit être unique. Cela fournit une sémantique similaire à un tableau 1-D, où chaque index contient un élément. L'insertion d'une clé qui existe déjà dans le conteneur est une erreur logique.

Les conteneurs associatifs avec multi dans le nom autorisent plusieurs instances de chaque clé. Vous pouvez insérer chaque clé autant de fois que vous le souhaitez. Les clés répétées sont conservées dans l'ordre d'insertion.

Remarque: Ceci est important même pour les multisets car les critères de comparaison distinguent l'équivalent de l'égal. Deux clés sont équivalentes si aucune ne se compare moins que l'autre; cependant, la fonction de comparaison n'est pas obligée de prendre en compte tous les champs de l'objet clé.

Lequel devriez-vous choisir? Cela dépend vraiment du problème que vous essayez de résoudre. Pour l'anecdote, j'ai rarement eu besoin de multisets ou de multimaps.

Si vous avez besoin de garder une trace de toutes les instances de «clé» que vous voyez, que certaines d'entre elles se comparent comme égales ou non, alors un multiset ou une multi-carte est le bon choix. Sinon, vous voudrez probablement les ensembles ou les cartes non multi.

Une utilisation intéressante de std :: multiset ou std :: multimap est en tant que file d'attente prioritaire. Utilisez la priorité comme clé. L'élément renvoyé par begin () est votre élément de priorité la plus élevée. La liste des éléments est conservée dans un ordre trié, de sorte que, étant donné un itérateur qui pointe vers un élément, vous pouvez rapidement déterminer ce qui se trouve juste avant et juste après. En particulier, si la priorité est en fait représentée par le temps, c'est-à-dire que cette file d'attente prioritaire est en fait une file d'attente d'événements ordonnés dans le temps, vous pouvez déterminer à peu de frais les événements planifiés à proximité d'une certaine heure.

Cependant, cela ne fonctionne qu'avec le multiset ordonné et le multimap ordonné.

std :: priority_queue

peut être un meilleur choix si vous n'avez besoin que d'un accès rapide à l'élément de priorité la plus élevée et que vous ne bénéficiez pas de la nature entièrement triée d'un multiset ou d'une multi-carte. (Voir

std :: priority_queue

pour plus de détails.)


Réponse 4:

Eh bien, je peux répondre à cela.

Plans

Les cartes nécessitent des clés. Pour chaque clé, vous avez un certain type de valeur (s).

Désormais, une clé peut être n'importe quoi, un entier, une chaîne ou même un objet (fourni avec une fonctionnalité de comparaison supplémentaire). Ainsi peuvent être les valeurs.

Regarde ça:

carte M; // clé entière - valeur entièreM [3] = 2;carte S; // clé de chaîne - valeur entièreS ["ahar"] = 26;

C'est fascinant.

Supposons que vous souhaitiez enregistrer les anniversaires de vos amis. Vous venez de déclarer une carte et enregistrez leurs noms et dates de naissance simplement en effectuant une tâche simple. C'est comme un dictionnaire en Python.

Ensembles

Ce n'est pas le cas pour les décors. Les ensembles n'ont pas besoin d'appariement (clé, valeur). Ils contiennent juste n'importe quel type de valeurs (bien sûr avec des fonctions de comparaison ou une surcharge d'opérateur si nécessaire) que vous voulez qu'ils contiennent. Par exemple:

ensemble S;S.insert (13);ensemble T;S.insert ("ahar");ensemble X;S.insert (votreObjet);

Du point de vue de la performance, ils présentent des similitudes. La recherche, l'insertion, l'effacement, etc. sont dans l'ordre

O (connexion)

dans les deux (merci à

Arbre noir rouge

, la chose dont vous aviez peur dans votre cours sur la structure des données: P). Mais en raison des différences d'implémentation et d'utilisation, il peut y avoir certains frais généraux.

Remarque supplémentaire:

Si vous faites une observation, vous constaterez que du point de vue structurel de base, les ensembles et les cartes sont différents. La question que vous avez posée peut donc être un peu plus intéressante si vous la pensez d'une manière où vous pouvez utiliser des ensembles comme alternative aux cartes et vice versa.

Cela peut nous conduire à une question intéressante: quelle est la différence entre set > et carte ? C'est une question assez valable car dans ce scénario, vous pouvez penser au premier élément de la paire dans l'ensemble équivalent à la clé dans la carte!

Par exemple:

carte M;M.insert ({"motta", 13});ensemble > S;S.insert ({"motta", 13});

Vous pouvez voir que l'ensemble écrit ci-dessus peut être une alternative potentielle à la carte.

Alors sont-ils équivalents? Et bien non.

Premièrement, la carte ne peut pas contenir un entier différent pour la même clé que nous l'avons déclaré ci-dessus. Mais ensemble peut.

Alors,

M.insert ({"ahar", 13)};S.insert ({"ahar", 13});M.insert ({"ahar", 26});S.insert ({"ahar", 26});

rend la taille de l'ensemble égale à 2 mais pour la carte, c'est 1.

Deuxièmement, vous devez déjà savoir que ces conteneurs C ++ utilisent des itérateurs qui sont utilisés pour pointer des éléments dans ces conteneurs. Pour le penser simplement, les itérateurs sont ce dont vous avez besoin pour accéder aux données de ces conteneurs.

Maintenant, regardez ceci:

ensemble > S;S.insert ({"ahar", 26});auto it = S.begin (); // c'est maintenant un itérateur pour ("ahar", 26)

Pour une raison quelconque, vous avez l'intention de changer la valeur de la paire correspondante itérée par elle de 26 à 13. Vous essayez ceci:

it-> seconde = 13;

Euh… non. Tu ne peux pas faire ça.

La raison est un peu compliquée. En termes simples, les itérateurs pour l'ensemble C ++ sont comme des itérateurs constants. Vous ne pouvez donc pas simplement modifier la valeur de données correspondante sur place. Vous devez l'effacer de l'ensemble, puis ajouter votre nouvelle valeur, comme ceci:

S.erase (it);paire p = {"ahar", 13};S.insert (p);

: |

Dans le cas des cartes, ceci est tout à fait valable:

carte M;M.insert ({"motta", 13});auto it = M.begin ();it-> seconde = 26;

J'espère que tout est bien. : P

Merci d'avoir lu.


Réponse 5:

Une carte est une structure de données utilisée pour rechercher des valeurs par clés, tandis qu'un ensemble n'est qu'une collection de valeurs.

En termes de mise en œuvre, ils ne sont généralement pas mis en œuvre différemment et les deux utilisent généralement des arbres rouge-noir sous le capot pour obtenir une complexité temporelle logarithmique pour la plupart des opérations. Une différence, selon les implémentations, est qu'un ensemble serait un arbre d'éléments rouge-noir tandis qu'une carte serait un arbre rouge-noir d'éléments de tuple (clé, valeur) triés en fonction du premier élément (la clé) dans le tuple.


Réponse 6:

Une carte mappe un objet à un autre. Un ensemble est un ensemble ordonné d'objets. Une carte est souvent utilisée pour accéder aux objets par un index de telle manière que objectMap [i] contienne l'objet avec l'index i. Un ensemble peut être utilisé pour stocker des objets, avec l'avantage supplémentaire qu'un ensemble identifie si un objet y est déjà contenu et ne stocke qu'une seule entité des objets. Cependant, vous ne pouvez accéder aux objets d'un ensemble qu'en effectuant une itération dessus ou en obtenant le premier ou le dernier élément de l'ensemble.


Réponse 7:

std :: map est un tableau ordonné associatif. Cela signifie qu'il stocke paires et par la clé, vous pouvez obtenir la valeur. Vous pouvez également parcourir le paires et l'itération suivra un bon ordre des clés.

std :: set est une collection de valeurs, uniquement. Encore une fois, vous pouvez itérer dessus et encore une fois l'itération suivra un bon ordre des valeurs. Mais il n'y a pas d'association comme ci-dessus, vous ne pouvez poser que des questions telles que "cette valeur est-elle dans l'ensemble?" Et pour cela, vous devez déjà avoir la valeur en question.