Quel conteneur STL dois-je utiliser pour un FIFO?

Quel conteneur STL répondrait le mieux à mes besoins? J'ai essentiellement un conteneur de 10 éléments de large dans lequel je continue de push_backcréer des éléments tout en pop_frontajoutant l'élément le plus ancien (environ un million de fois).

J'utilise actuellement un std::dequepour la tâche mais je me demandais si un std::listserait plus efficace car je n'aurais pas besoin de se réallouer (ou peut-être que je prends un std::dequepour un std::vector?). Ou existe-t-il un conteneur encore plus efficace pour mon besoin?

PS je n'ai pas besoin d'un accès aléatoire

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

Utilisez un std::queue. La raison en est simple: il s'agit d'une structure FIFO. Vous voulez FIFO, vous utilisez un fichier std::queue.

Cela rend votre intention claire à quiconque, et même à vous-même. A std::listou std::dequepas. Une liste peut insérer et supprimer n'importe où, ce qui n'est pas ce qu'une structure FIFO est censée faire, et une dequepeut ajouter et supprimer de l'une ou l'autre extrémité, ce qu'une structure FIFO ne peut pas faire.

C'est pourquoi vous devez utiliser un fichier queue.

Maintenant, vous avez posé des questions sur les performances. Tout d'abord, rappelez-vous toujours cette règle empirique importante: un bon code d'abord, les performances en dernier.

La raison en est simple: les personnes qui recherchent la performance avant la propreté et l'élégance finissent presque toujours en dernier. Leur code devient un tas de bouillie, car ils ont abandonné tout ce qui est bon pour ne rien en tirer.

En écrivant d'abord un bon code lisible, la plupart de vos problèmes de performances se résoudront d'eux-mêmes. Et si plus tard vous trouvez que vos performances font défaut, il est maintenant facile d'ajouter un profileur à votre code agréable et propre et de découvrir où se trouve le problème.

Cela dit, ce std::queuen'est qu'un adaptateur. Il fournit l'interface sûre, mais utilise un conteneur différent à l'intérieur. Vous pouvez choisir ce conteneur sous-jacent, ce qui permet une grande flexibilité.

Alors, quel conteneur sous-jacent devriez-vous utiliser? Nous savons que std::listet à la std::dequefois fournir les fonctions nécessaires ( push_back(), pop_front()et front()), alors comment nous décidons?

Tout d'abord, comprenez que l'allocation (et la désallocation) de la mémoire n'est pas une chose rapide à faire, en général, car cela implique d'aller au système d'exploitation et de lui demander de faire quelque chose. A listdoit allouer de la mémoire à chaque fois que quelque chose est ajouté, et la désallouer quand elle disparaît.

A deque, d'autre part, alloue par blocs. Il allouera moins souvent qu'un fichier list. Considérez-le comme une liste, mais chaque bloc de mémoire peut contenir plusieurs nœuds. (Bien sûr, je vous suggère d' apprendre vraiment comment cela fonctionne .)

Donc, avec cela seul, un dequedevrait mieux fonctionner, car il ne traite pas aussi souvent de la mémoire. Mélangé au fait que vous manipulez des données de taille constante, il ne sera probablement pas nécessaire d'allouer après le premier passage des données, alors qu'une liste sera constamment allouée et désallouée.

Une deuxième chose à comprendre est la performance du cache . La sortie vers la RAM est lente, donc lorsque le processeur en a vraiment besoin, il tire le meilleur parti de ce temps en ramenant une partie de la mémoire avec lui, dans le cache. Étant donné qu'une dequeallocation dans des blocs de mémoire, il est probable que l'accès à un élément de ce conteneur amènera le processeur à ramener également le reste du conteneur. Désormais, tout accès supplémentaire au dequesera rapide, car les données sont en cache.

Cela ne ressemble pas à une liste, où les données sont allouées une par une. Cela signifie que les données peuvent être réparties partout dans la mémoire et que les performances du cache seront mauvaises.

Donc, compte tenu de cela, un dequedevrait être un meilleur choix. C'est pourquoi il s'agit du conteneur par défaut lors de l'utilisation d'un fichier queue. Cela dit, ce n'est encore qu'une supposition (très) éclairée: vous devrez profiler ce code, en utilisant un dequedans un test et listdans l'autre pour vraiment le savoir avec certitude.

Mais rappelez-vous: faites fonctionner le code avec une interface propre, puis préoccupez-vous des performances.

John soulève la crainte que l'encapsulation d'un listou dequeentraîne une diminution des performances. Encore une fois, lui ni moi ne pouvons le dire avec certitude sans le profiler nous-mêmes, mais il y a de fortes chances que le compilateur intègre les appels qu'il queueeffectue. C'est-à-dire que lorsque vous dites queue.push(), cela va simplement dire queue.container.push_back(), sauter complètement l'appel de fonction.

Encore une fois, il ne s'agit que d'une supposition éclairée, mais l'utilisation de a queuene dégradera pas les performances par rapport à l'utilisation du conteneur sous-jacent brut. Comme je l'ai déjà dit, utilisez le queue, car il est propre, facile à utiliser et sûr, et s'il devient vraiment un profil de problème et un test.

Vérifiez std::queue. Il encapsule un type de conteneur sous-jacent et le conteneur par défaut est std::deque.

Là où les performances comptent vraiment, consultez la bibliothèque de tampons circulaires Boost .

J'ai continuellement de push_backnouveaux éléments en pop_frontingérant l'élément le plus ancien (environ un million de fois).

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

Pourquoi pas std::queue? Tout ce qu'il a, c'est push_backet pop_front.

Une file d'attente est probablement une interface plus simple qu'un deque mais pour une si petite liste, la différence de performances est probablement négligeable.

Il en va de même pour la liste . C'est juste un choix de l'API que vous voulez.

Utilisez a std::queue, mais soyez conscient des compromis de performance des deux Containerclasses standard .

Par défaut, std::queueest un adaptateur au-dessus de std::deque. En règle générale, cela donnera de bonnes performances lorsque vous avez un petit nombre de files d'attente contenant un grand nombre d'entrées, ce qui est sans doute le cas courant.

Cependant, ne soyez pas aveugle à l'implémentation de std :: deque . Plus précisément:

"... les deques ont généralement un coût mémoire minimal élevé; un deque contenant un seul élément doit allouer son tableau interne complet (par exemple, 8 fois la taille de l'objet sur libstdc ++ 64 bits; 16 fois la taille de l'objet ou 4096 octets, selon la valeur la plus grande , sur la libc ++ 64 bits). "

Pour résumer cela, en supposant qu'une entrée de file d'attente est quelque chose que vous voudriez mettre en file d'attente, c'est-à-dire, d'une taille raisonnablement petite, alors si vous avez 4 files d'attente, chacune contenant 30 000 entrées, l' std::dequeimplémentation sera l'option de choix. Inversement, si vous avez 30 000 files d'attente, chacune contenant 4 entrées, il est fort probable que l' std::listimplémentation sera optimale, car vous n'amortirez jamais les std::dequefrais généraux dans ce scénario.

Vous lirez beaucoup d'opinions sur la façon dont le cache est roi, comment Stroustrup déteste les listes liées, etc., et tout cela est vrai, sous certaines conditions. Ne l'acceptez pas sur une foi aveugle, car dans notre deuxième scénario, il est peu probable que l' std::dequeimplémentation par défaut fonctionne. Évaluez votre utilisation et mesurez.

Ce cas est suffisamment simple pour que vous puissiez simplement écrire le vôtre. Voici quelque chose qui fonctionne bien pour les situations de micro-contrôleur où l'utilisation de STL prend trop de place. C'est un bon moyen de transmettre les données et le signal du gestionnaire d'interruption à votre boucle principale.

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};