Quel container STL utiliser pour un FIFO?

Puisqu'il y a une myriade de réponses, vous pourriez être confus, mais pour résumer:

utiliser un std::queue . La raison en est simple: c'est une structure FIFO. Vous voulez FIFO, vous utilisez un std::queue .

il fait votre intention claire à quelqu'un d'autre, et même vous-même. Un std::list ou std::deque ne fonctionne pas. Une liste pouvez insérer et supprimer n'importe où, ce qui n'est pas ce qu'une structure FIFO est censée faire, et une deque peut ajouter et supprimer de chaque extrémité, ce qui est également quelque chose QU'une structure FIFO 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 règle empirique importante: le bon code d'abord, la performance en dernier.

la raison en est simple: les gens qui luttent pour les performances avant la propreté et l'élégance finissent presque toujours en dernier. Leur code devient une bouillie de bouillie, parce qu'ils ont abandonné tout ce qui est bon pour ne rien en tirer.

en écrivant un bon code, lisible d'abord, la plupart d'entre vous les problèmes de performance se résoudront eux-mêmes. Et si plus tard vous constatez que votre performance fait défaut, il est maintenant facile d'ajouter un profileur à votre code propre et agréable, et de trouver où est le problème.

que tout dit, std::queue n'est qu'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é.

alors, quel contenant sous-jacent devez-vous utiliser? Nous savons que std::list et std::deque fournissent toutes deux les fonctions nécessaires ( push_back() , pop_front() , et front() ), alors comment décider?

d'abord, comprendre que l'attribution (et désallouer) la mémoire n'est pas une chose rapide à faire, généralement, parce qu'il s'agit d'aller à L'OS et lui demander de faire quelque chose. Un list doit allouer de la mémoire à chaque fois que quelque chose est ajouté, et le désallouer quand il disparaît.

A deque , d'autre part, allaite en morceaux. Il attribuera moins souvent qu'un list . Pensez-y comme une liste, mais chaque morceau de la mémoire peut contenir plusieurs nœuds. (Bien sûr, je suggère que vous vraiment savoir comment elle fonctionne .)

donc, avec cela seul un deque devrait mieux fonctionner, parce qu'il ne traite pas avec la mémoire aussi souvent. Mélangée au fait que vous manipulez des données de taille constante, elle n'aura probablement pas à se répartir après le premier passage à travers les données, alors qu'une liste sera constamment allouer et désallouer.

une deuxième chose à comprendre est cache performance . Aller sortir en RAM est lent, donc quand le CPU en a vraiment besoin, il tire le meilleur parti de ce temps en récupérant un morceau de mémoire avec lui, dans la cache. Parce qu'un deque s'allonge en morceaux de mémoire, il est probable que l'accès à un élément dans ce conteneur fera que le CPU ramènera aussi le reste du conteneur. Maintenant, tout autre accès au deque sera rapide, parce que les données sont dans le cache.

ce n'est pas une liste, où les données sont attribuées un à un temps. Cela signifie que les données pourraient être réparties partout dans la mémoire, et les performances de cache seront mauvaises.

Donc, considérant que, une deque devrait être un meilleur choix. C'est pourquoi c'est le conteneur par défaut lorsqu'on utilise un queue . Cela dit, ce n'est encore qu'une (très) supposition: vous devrez profiler ce code, en utilisant un deque dans un test et list dans l'autre pour vraiment savoir avec certitude.

But rappelez-vous: obtenez le code de travail avec une interface propre, puis se soucier de la performance.

John craint que l'emballage d'un list ou d'un deque entraîne une diminution de la performance. Une fois de plus, lui et moi pouvons le dire avec certitude sans le profiler nous-mêmes, mais il y a des chances que le compilateur alignera les appels que le queue fait. C'est-à-dire , quand vous dites queue.push() , il va vraiment dire queue.container.push_back() , sautant complètement l'appel de fonction.

encore une fois, ce n'est qu'une supposition éclairée, mais l'utilisation d'un queue ne dégradera pas la performance, par rapport à l'utilisation du conteneur brut sous-jacent. Comme je l'ai déjà dit, utilisez le queue , parce qu'il est propre, facile à utiliser, et sûr, et si elle devient vraiment un profil de problème et de test.