Quel container STL utiliser pour un FIFO?

quel container STL conviendrait le mieux à mes besoins? J'ai fondamentalement un conteneur de 10 éléments de large dans lequel je continuellement push_back nouveaux éléments tout en pop_front ing l'élément le plus ancien (environ un million de temps).

j'utilise actuellement un std::deque pour cette tâche, mais je me demandais si un std::list serait plus efficace puisque je n'aurais pas besoin de me réallouer (ou peut-être que je prends un std::deque pour un std::vector ?). Ou est-il encore plus efficace conteneur pour mon besoin?

P.S. Je n'ai pas besoin d'un accès aléatoire

71
demandé sur Gab Royer 2009-08-12 00:45:26

6 réponses

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.

161
répondu GManNickG 2017-03-28 20:07:24

Check out std::queue . Il enveloppe un type de conteneur sous-jacent, et le conteneur par défaut est std::deque .

26
répondu Mark Ransom 2018-08-02 20:53:24

là où la performance compte vraiment, consultez la Boost circular buffer library .

10
répondu Emile Cormier 2010-01-22 04:12:31

I continuellement push_back nouveaux éléments tandis que pop_front ing l'élément le plus ancien (environ un million de fois).

un million n'est vraiment pas un grand nombre dans l'informatique. Comme d'autres l'ont suggéré, utilisez une std::queue comme première solution. Dans le cas peu probable où il serait trop lent, identifiez le goulot d'étranglement à l'aide d'un profileur (ne pas deviner!) et ré-implémenter en utilisant un conteneur différent avec la même interface.

7
répondu phoenix 2017-05-09 03:34:35

pourquoi pas std::queue ? Tout ce qu'il a est push_back et pop_front .

5
répondu eduffy 2009-08-11 20:51:50

a queue est probablement une interface plus simple qu'une deque mais pour une si petite liste, la différence de performance est probablement négligeable.

idem pour list . Il suffit de choisir l'API que vous voulez.

3
répondu lavinio 2009-08-11 20:48:45