Depuis il y a une multitude de réponses, vous pourriez être confus, mais pour résumer:
Utiliser un std::queue. La raison pour cela est simple: il s'agit d'une FIFO de la structure. Vous souhaitez FIFO, vous utilisez un std::queue.
Il rend votre intention claire pour quelqu'un d'autre, et vous-même. Un std::list ou std::deque ne le sont pas. Une liste pouvez insérer et supprimer n'importe où, ce qui n'est pas une FIFO structure est supposé faire, et un deque pouvez ajouter et supprimer à partir de chaque extrémité, qui est aussi quelque chose d'une FIFO de la structure ne peut pas faire.
C'est pourquoi vous devez utiliser un queue.
Maintenant, vous avez demandé à propos de la performance. Tout d'abord, rappelez-vous toujours cette importante règle de base: le code de Bonne tout d'abord, la performance de la dernière.
La raison pour cela est simple: les personnes qui se battent pour la performance avant de propreté et d'élégance presque toujours finir dernier. Leur code devient un retraité de la bouillie, parce qu'ils ont abandonné tout ce qui est bon pour vraiment rien en sortir.
Par la rédaction d'un bon, un code lisible tout d'abord, la plupart d'entre vous des problèmes de performance permettra de résoudre eux-mêmes. Et si plus tard vous trouvez que votre performance est insuffisante, il est maintenant facile d'ajouter un profiler à votre belle, propre code, et de trouver où est le problème.
Que tout est dit, std::queue est uniquement un adaptateur. Il fournit l'interface sûre, mais utilise un autre conteneur à l'intérieur. Vous pouvez choisir ce conteneur sous-jacent, ce qui permet une bonne flexibilité.
Donc, ce qui sous-jacent conteneur devriez-vous utiliser? Nous savons qu' std::list et std::deque à la fois fournir les fonctions nécessaires (push_back(), pop_front(), et front()), alors comment pouvons-nous décider?
Tout d'abord, comprendre que l'affectation de (et la désallocation de la mémoire n'est pas une chose rapide à faire, en général, parce qu'il implique d'aller à l'OS et lui demandant de faire quelque chose. Un list a pour allouer de la mémoire à chaque fois que quelque chose est ajouté, et de libérer quand il s'en va.
Un deque, d'autre part, il attribue en morceaux. Il va allouer moins souvent que d'un list. Pensez-y comme une liste, mais chaque nœud peut avoir plusieurs nœuds. (Bien sûr, j'avais asuggest que vous vraiment savoir comment elle fonctionne.)
Donc, avec ce seul un deque devrait mieux fonctionner, car il n'a pas affaire à de la mémoire comme souvent. Mélangé avec le fait que vous êtes la manipulation de données de taille constante, il ne sera probablement pas avoir à attribuer après le premier passage dans les données, tandis qu'une liste sera constamment l'allocation et la désallocation.
Une deuxième chose à comprendre est que les performances du cache. Sortir de la RAM est lent, de sorte que lorsque le CPU doit vraiment, il fait le meilleur de ce moment en prenant une partie de la mémoire de retour avec elle, dans le cache. Parce qu'un deque alloue de la mémoire de morceaux, il est probable que l'accès à un élément dans ce conteneur sera la cause de la CPU pour ramener le reste du conteneur ainsi. Maintenant tout accès ultérieur à l' deque sera rapide, car les données sont dans le cache.
C'est à l'inverse une liste, où les données sont affectées à la fois. Cela signifie que les données peuvent être réparties sur tout le place dans la mémoire et les performances du cache sera mauvaise.
Donc, considérant que, une deque devrait être un meilleur choix. C'est pourquoi il est le conteneur par défaut lors de l'utilisation d'un queue. Que tout est dit, ce n'est encore qu'une supposition: vous devrez le profil de ce code, à l'aide d'un deque dans un test et list dans les autres pour savoir vraiment pour certains.
Mais rappelez-vous: obtenir le code de travail avec une interface propre, alors vous soucier de la performance.
John soulève l'inquiétude que l'enveloppant d'un list ou deque entraînera une baisse de la performance. Une fois de plus, il ni ce que je peux dire pour certains sans profilage de nous-mêmes, mais les chances sont que le compilateur inline les appels que l' queue rend. C'est, quand vous dites queue.push(), il va vraiment juste dire queue.container.push_back(), en ignorant l'appel de fonction complètement.
Encore une fois, ce n'est qu'une supposition, mais à l'aide d'un queue ne dégrade pas les performances par rapport à l'utilisation du conteneur sous-jacent raw. Comme je l'ai dit avant, l'utilisation de l' queue, parce que c'est propre, facile à utiliser et sûr, et si il devient vraiment un problème de profil et de test.
