tableau vs vecteur vs liste

Question

Je suis le maintien d'une longueur fixe de table de 10 entrées. Chaque élément est une structure de 4 champs. Il y aura insérer, mettre à jour et supprimer des opérations, indiquée par la position numérique. Je me demande quelle est la meilleure structure de données à utiliser pour l'entretien de ce tableau d'information:

1. tableau - insérer/supprimer prend un temps linéaire en raison du déplacement; mise à jour constante de temps, pas d'espace est utilisé pour les pointeurs; l'accès à un élément à l'aide de [] est plus rapide.

2. vecteur stl - insérer/supprimer prend un temps linéaire en raison du déplacement; mise à jour constante de temps, pas d'espace est utilisé pour les pointeurs; l'accès à un élément est plus lent qu'un tableau c'est un appel à l'opérateur[] et une liste liée .

3. liste stl - insérer et supprimer des prend le temps linéaire, car vous avez besoin d'accéder à une position spécifique avant l'application de l'insérer/supprimer; espace supplémentaire est nécessaire pour les pointeurs; l'accès à un élément est plus lent qu'un tableau, puisque c'est une liste liée linéaire de la traversée.

Pour l'instant, mon choix est d'utiliser un tableau. Est-il justifiable? Ou ai-je raté quelque chose?

Ce qui est plus rapide: parcours d'une liste, puis de l'insertion d'un nœud ou d'évolution des éléments dans un tableau afin de produire une position vide l'insertion de l'article dans cette position?

Quelle est la meilleure façon de mesurer cette performance? Puis-je afficher l'horodatage avant et après les opérations?

Answer 1

L'utilisation de la STL vector. Il fournit également une interface riche comme list et supprime la douleur de la gestion de la mémoire que les piles de besoin.

Vous devez essayer très dur pour exposer la performance coût de la operator[] - il obtient habituellement incorporé.

Je n'ai pas de numéro à vous donner, mais je me souviens de la lecture de l'analyse de performance qui décrit comment vector<int> a été plus rapide que list<int> même pour les insertions et les suppressions (en vertu d'une certaine taille bien sûr). La vérité de la question est que ces processeurs que nous utilisons sont très rapide et si votre vector en L2 cache, puis ça va aller très très vite. Les listes d'autre part, ont à gérer des tas d'objets qui vont tuer votre L2.

Answer 2

L'optimisation prématurée est la racine de tout Mal.

D'après votre message, je dirais qu'il n'y a aucune raison de faire de votre structure de données une structure basée sur la performance. Choisissez ce qui vous convient le mieux et recommencez à le changer si et seulement si les tests de performance montrent que c'est un problème.

Answer 3

Il est vraiment la peine d'investir un certain temps à comprendre les différences fondamentales entre les listes et les vecteurs. La différence la plus importante entre les deux est le mode de stockage des éléments et d'en garder une trace.

- Listes -

La liste contient des éléments qui ont l'adresse d'un précédent et suivant de l'élément stockée en eux. Cela signifie que vous pouvez INSÉRER ou SUPPRIMER un élément n'importe où dans la liste avec la constante de vitesse O(1), indépendamment de la taille de la liste. Vous aussi splice (insérer une autre liste) dans la liste existante de n'importe où avec la constante de vitesse ainsi. La raison en est que la liste ne doit changer les deux pointeurs (précédent et suivant) pour l'élément, nous sommes de l'insérer dans la liste.

Les listes ne sont pas bien si vous avez besoin d'un accès aléatoire. Donc, si l'un des plans d'accès n-ième élément de la liste a à la traversée de la liste un par un - O(n) vitesse de

- Les vecteurs -

Vecteur contient les éléments dans l'ordre, tout comme un tableau. C'est très pratique pour un accès aléatoire. D'accès à la "nième" élément dans un vecteur est un simple pointeur de calcul (O(1) de la vitesse). Ajout d'éléments à un vecteur, toutefois, est différente. Si l'on veut ajouter un élément au milieu d'un vecteur - tous les éléments qui viennent après cet élément devra être ré alloué vers le bas pour faire de la place pour la nouvelle entrée. La vitesse dépendra de la taille de vecteur et sur la position de l'élément nouveau. Le pire scénario est d'insérer un élément à la position 2 dans un vecteur, le meilleur est l'ajout d'un nouvel élément. Donc - insert fonctionne avec la vitesse de O(n), où "n" est le nombre d'éléments qui doivent être déplacés - pas nécessairement de la taille d'un vecteur.

Il existe d'autres différences qui impliquent des exigences de la mémoire, etc., mais la compréhension de ces principes de base de la façon dont les listes et les vecteurs effectivement le travail est vraiment la peine de dépenser un peu de temps sur.

Comme toujours ... "l'optimisation Prématurée est la racine de tout mal" donc d'abord considérer ce qui est plus pratique et faire fonctionner les choses exactement comme vous le souhaitez, puis de les optimiser. Pour 10 entrées que vous mentionnez - il n'a vraiment pas d'importance ce que vous utilisez, vous ne serez jamais en mesure de voir toute sorte de différence de performances quelle que soit la méthode que vous utilisez.

Answer 4

Préférez un std::vector-dessus et tableau. Certains avantages de vecteur sont:

• Ils allouer de la mémoire à partir de l'espace libre lors de l'augmentation de la taille.
• Ils ne sont PAS un pointeur dans le déguisement.
• Ils peuvent augmenter/diminuer la taille au moment de l'exécution.
• Ils peuvent faire le contrôle de la portée à l'aide à().
• Un vecteur sait de sa taille, de sorte que vous ne pas avoir à compter les éléments.

La raison la plus convaincante pour l'utilisation d'un vecteur, c'est qu'il vous permet de vous libérer de la mémoire explicite de gestion, et il n'a pas de fuite de mémoire. Un vecteur conserve la trace de la mémoire qu'il utilise pour stocker ses éléments. Lorsqu'un vecteur a besoin de plus de mémoire pour les éléments, il alloue de plus, lorsqu'un vecteur est hors de portée, il libère cette mémoire. Par conséquent, l'utilisateur n'a pas besoin d'être concerné par l'allocation et la désallocation de la mémoire pour les éléments du vecteur.

Answer 5

Vous êtes à faire des hypothèses, vous ne devriez pas faire, comme "l'accès à un élément est plus lent qu'un tableau c'est un appel à l'opérateur[]." Je peux comprendre la logique derrière elle, mais vous ni moi ne peut savoir jusqu'à ce que nous profil.

Si vous le faites, vous trouverez il n'y a pas de frais généraux à tous, lorsque les optimisations sont activés. Le compilateur inlines les appels de fonction. Il y est une différence dans les performances de la mémoire. Un tableau est alloué de manière statique, tandis qu'un vecteur alloue de manière dynamique. Une liste alloue par nœud, ce qui peut accélérateur de cache si vous ne faites pas attention.

Certaines solutions sont à avoir l' vector allouer sur la pile, et de disposer d'un pool d'allocation pour un list, de sorte que les nœuds peuvent tenir dans le cache.

Alors plutôt que de vous inquiéter de la non prise en charge des réclamations, vous devez vous soucier de faire votre conception aussi propre que possible. Donc, ce qui fait plus de sens? Un tableau, d'un vecteur ou d'une liste? Je ne sais pas ce que vous essayez de faire, donc je ne peux pas vous répondre.

Le "défaut" conteneur a tendance à être un vector. Parfois, un tableau est parfaitement acceptable.