C++ deque vs vecteur et C++ carte vs

Peut quelques un s'il vous plaît dites-moi quelle est la différence entre le vecteur vs deque. Je sais que la mise en œuvre de vector en C++, mais pas deque. Aussi les interfaces de la carte et le jeu semble similaire à moi. Quelle est la différence entre les deux et quand les utiliser.

OriginalL'auteur brett | 2010-09-13

  1. 47

    std::vector: Une dynamique de la classe array. L'allocation mémoire interne permet de s'assurer qu'il crée toujours un tableau. Utile lorsque la taille des données est connu et est connu pour ne pas changer trop souvent. Il est également bon si vous voulez avoir accès aléatoire à des éléments.

    std::deque: Un double-clos de la file d'attente qui peut agir comme un pile ou file d'attente. Bon pour quand vous n'êtes pas sûr au sujet du nombre d'éléments et lorsque l'accès aux données-élément sont toujours en série. Ils sont rapides lorsque des éléments sont ajoutés ou supprimés à partir de l'avant et de fin, mais pas lorsqu'ils sont ajoutés/retirés du milieu.

    std::list: Une double liste chaînée qui peut être utilisé pour créer une "liste" des données. L'avantage d'une liste, c'est que les éléments peuvent être insérés ou supprimés à partir de toute partie de la liste sans affecter un itérateur qui pointe vers un membre de la liste (et est encore un membre de la liste après la suppression). Utile quand vous savez que les éléments seront supprimés très souvent à partir de toute partie de la liste.

    std::map: Un dictionnaire des cartes a 'clé' pour une 'valeur'. Utile pour des applications comme des "tableaux" dont les index ne sont pas un entier. Fondamentalement, peut être utilisé pour créer une carte-liste de nom d'un élément, comme une carte qui stocke le nom à l'widget relation.

    std::set: Une liste de "unique" valeurs de données. Par exemple, si vous insérez 1, 2, 2, 1, 3, la liste seulement les éléments 1, 2, 3. Notez que les éléments de cette liste sont toujours commandés. En interne, ils sont généralement mis en œuvre comme des arbres binaires (comme la carte).

    +1 : Vous pouvez mentionner que d'un set est vraiment un map avec la valeur de la clé. Vous pouvez également mentionner multimap et multiset pour completeless.
    Merci pour la mention à ajouter que les détails sur set. J'ai ajouté la partie. Je suis ignorant multimap et multiset parce que l'OP a été de plus en plus dans des vecteurs, deque, la carte et le jeu. Je l'ai mis dans la liste pour s'assurer qu'il sait à ce sujet au cas où c'était ce qu'il veut. Aussi, je n'ai aucune expérience dans l'utilisation de multiset.
    Un ensemble n'est pas nécessairement une carte. Un ensemble seulement des besoins de stockage pour les clés et une carte pour l'allocation de stockage de la clé et la valeur. Donc, on pourrait dire qu'un jeu est vraiment une carte sans valeurs.

    OriginalL'auteur Vite Falcon

  2. 5

    Voir ici pour plus de détails:

    Ce sont la complexité des garanties de la norme des containers?

    vecteur Vs deque

    Un deque est le même que pour un vecteur, mais avec l'ajout des points suivants:

    • C'est un "avant insertion de la séquence"

    Cela signifie que deque est le même que pour un vecteur, mais fournit les informations supplémentaires suivantes garantit:

    • push_front() O(1)
    • pop_front() O(1)

    set Vs carte

    Une carte est une "Paire Conteneur Associatif" tout est un "Simple Conteneur Associatif"

    Cela signifie qu'ils sont exactement la même. La différence est que la carte est titulaire des paires d'objets (Clé/Valeur) plutôt que de juste valeur.

    deque également déménage éléments en moins de situations que vector, ce qui pourrait être important de ne pas en raison de la complexité temporelle, mais parce que vous avez des références.
    Aussi, une deque et vecteur ne sont pas les mêmes en ce qui concerne la gestion de la mémoire. Un vecteur est garantie d'être contiguës en mémoire (comme un C tableau), mais d'un deque ne l'est pas.

    OriginalL'auteur Martin York

  3. 1

    Une carte est ce qui est souvent désigné comme un tableau associatif sont généralement mis en oeuvre à l'aide d'un arbre binaire (par exemple). Une deque est un double clos de la file d'attente, une certaine incarnation d'une liste chaînée.

    Qui n'est pas à dire que les implémentations réelles des conteneurs de la bibliothèque utilise ces concepts - la containr bibliothèque va juste vous donner quelques garanties sur la façon dont vous pouvez accéder au conteneur et à quel (amorti) des coûts.

    Je vous suggère de prendre un coup d'oeil à une référence qui va aller dans le détail de ce que ces garanties sont. Scott Meyers livre "Effective STL: 50 Moyens Spécifiques pour Améliorer Votre Utilisation de la Bibliothèque de modèles Standard" devrait parler un peu de ceux-ci, si je me souviens bien. En dehors de cela, la norme C++ est évidemment un bon choix.

    Ce que je veux vraiment dire, c'est: conteneurs sont décrits par leurs propriétés, non pas par l'implémentation sous-jacente.

    OriginalL'auteur Jim Brissom

  4. 1

    ensemble: détient des valeurs uniques. Mis 'a' en deux fois, le jeu a un "a".
    carte: les cartes des clés à des valeurs, par exemple, 'nom' => 'fred', 'age' => 40. Vous pouvez consulter 'nom' et vous obtiendrez "fred".

    file d'attente, comme un vecteur, mais vous ne pouvez ajouter/supprimer à la fin. Pas insère dans le milieu. http://en.wikipedia.org/wiki/Deque

    edit: ma file d'attente description est manquant, voir les commentaires ci-dessous pour les corrections

    Je dirais "deque, comme un vecteur, mais vous pouvez ajouter/supprimer des DEUX extrémités (plutôt que de simplement le dos)".
    La bibliothèque standard deque prend en charge les insertions dans le milieu, avec la même complexité linéaire prévue par la norme du vecteur. D'autres implémentations ne pourrait pas puisque ce n'est pas l'âme "double fin de la file d'attente".
    Mais une deque pas comme un vecteur dans consécutives éléments sont pas la garantie d'être contigus en mémoire. Si vous appuyez assez d'éléments sur une extrémité d'un deque qu'il s'exécute hors de son espace de stockage interne, il va allouer un nouveau bloc de stockage et le cloue à une extrémité ou à l'autre. Si vous appuyez assez d'éléments sur la fin d'un vecteur qu'il est à court de capacité, le vecteur a pour allouer un nouveau bloc assez grand pour contenir tout, tout copier sur elle, et la libération de l'ancien stockage. Beaucoup plus lent que d'une deque, et la taille de bloc devient de plus en plus gros.
    Je n'ai jamais pensé à un deque comme ça. Je suis maintenant plus susceptibles de les utiliser, merci Drew & Mike!

    OriginalL'auteur Graham Perks