std::deque ou std::list

Question

J'utilise push_front() y push_back() seulement. Ainsi, je n'ai pas d'autres frais à supporter pour l'utilisation de ce service. insert() ou remove() .

Je sais que les deux conteneurs offrent O(1) la complexité de chacune de ces fonctions, deque ayant un temps constant amorti par rapport aux list ayant un temps constant.

Mais je veux savoir quel temps est inférieur à l'autre, si tant est qu'il y en ait un.

Answer 1

Je ne sais pas comment répondre à votre question. Vous semblez vouloir que nous écrivions un programme de référence que vous pourriez facilement écrire vous-même. Au lieu de cela, je me contenterai d'énoncer ceci :

• Avec un list chaque élément que vous poussez entraîne une allocation de mémoire.
• Avec un deque de grands blocs sont alloués en une seule fois.

Étant donné que l'allocation de la mémoire est normalement lente, je m'attendrais à ce que la fonction deque pour surpasser la liste.

Si vous poussez ou éjectez de nombreux éléments à la fois, cela sera particulièrement vrai, car la localité de la mémoire cache entre en jeu.

Bien sûr, vous pouvez écrire un allocateur sur la liste pour utiliser un pool de mémoire. Vous obtiendriez alors de meilleures performances.

Alors, avec ces hypothèses à l'esprit, partez et mesure et si vous voulez discuter des résultats, c'est le moment de poser une question.

Answer 2

Lorsqu'il s'agit de performances, c'est une mauvaise idée de "deviner" (ou de demander sur Internet, ce qui est légèrement mieux que de deviner, mais seulement un peu), et il est toujours préférable de mesurer les deux options - dans ce cas, il suffit de faire une boucle, et de pousser_back ou push_front suffisamment de choses pour que cela soit réaliste [vous pouvez rendre cela plus réaliste et exécuter la plupart de ce que votre code fait, et le faire dans une boucle suffisamment de fois pour que cela dure assez longtemps pour mesurer le temps - c'est souvent plus réaliste que d'ajouter un milliard de valeurs à un fichier de type list / deque et de constater que "lorsqu'il faut échanger, cela devient très lent"].