Pour une application à un seul thread, vous pouvez souvent utiliser n'importe quel type de file simplement en traitant l'élément suivant comme il arrive, mais il existe de nombreuses applications où ce n'est pas le cas (mise en file d'attente des données pour la sortie, par exemple).
Sans le besoin de verrouiller la file d'attente (pas d'autres threads à s'inquiéter) un tampon circulaire simple va être difficile à battre pour les performances. Si, pour une raison ou une autre, la file d'attente doit augmenter après la création, c'est un peu plus difficile, mais vous ne devriez pas avoir du mal à trouver une implémentation de file d'attente circulaire (ou à créer la vôtre). Si l'insertion ou l'extraction est effectuée dans un gestionnaire de signal (ou une routine de service d'interruption), vous devrez peut-être protéger les index de position de lecture et/ou écriture, mais si vous connaissez bien votre cible, vous pourrez déterminer le cas (en cas de doute protéger, cependant). La protection consiste soit à bloquer temporairement les signaux ou les interruptions qui pourraient mettre des choses dans votre file d'attente. (Vous auriez vraiment besoin de bloquer cela si vous deviez redimensionner la file d'attente)
Si tout ce que vous mettez dans la file d'attente doit être alloué dynamiquement de toute façon, alors vous pouvez simplement virer sur un pointeur et tourner la chose dans un noeud de liste. Une liste liée individuellement où le maître de liste contient un pointeur sur la tête et le dernier nœud est suffisant. Extrait de la tête et insérer à la queue. Protéger les insertions et les extractions des conditions de course est à peu près indépendant et il suffit de s'inquiéter des choses quand la liste est très faible. Si vous avez vraiment une seule application threadée, vous n'avez pas à vous inquiéter du tout.
Je n'ai pas de benchmarks réels et je ne peux faire aucune suggestion sur les implémentations de bibliothèques, mais les deux méthodes sont O (1) pour l'insertion et l'extraction. Le premier cache plus de mémoire cache (et pager mémoire) à moins que la taille de votre file d'attente ne soit plus grande que nécessaire. La seconde méthode est moins favorable au cache, car chaque membre de la file d'attente peut se trouver dans une zone différente de la RAM.
Espérons que cela vous aide à évaluer ou à créer votre propre file d'attente.
Cela dépend vraiment de la façon dont vous avez l'intention d'utiliser les files d'attente. Sont-ils des FIFO, des Dqueues, des files d'attente de priorité, ou est-ce que l'ordre n'importe quoi? Y a-t-il plusieurs threads? Contention pour mettre les choses dans les files d'attente et/ou les sortir? – nategoose
@nategoose: Je m'intéresse surtout aux FIFO, fonctionnant sur un seul thread. Je n'ai pas compris ce que vous entendiez par "Contention pour mettre les choses dans les files d'attente et/ou les sortir?" – korbes
Contention est juste un problème lorsqu'une file d'attente doit être utilisée par plusieurs threads. Si de nombreux threads peuvent placer des objets dans une file d'attente et en sortir, alors toute implémentation simple nécessitera un mutex d'un type que chaque thread devra acquérir avant d'insérer ou d'extraire de la file d'attente. Il existe plusieurs façons d'implémenter des files d'attente plus complexes qui, bien que se produisant plus mal sous des applications à un seul thread, fonctionneraient généralement mieux pour plusieurs threads. – nategoose