Discussion :

[Legro]

Bonjour,

J'ai besoin d'utiliser un conteneur et je m'interroge au niveau de la rapidité de traitement. Lequel serait le meilleur ?

A la base j'hésitais entre stack et queue en ayant l'impression que stack serait plus rapide.

Mais après réflexion je me demande si les deux ne sont pas en fait tout aussi lents puisqu'ils ne sont que des adaptateurs et non pas en eux mêmes des conteneurs.
Et alors tant qu'a faire autant utiliser un vector...

Je précise que le seul paramètre qui me préoccupe est la rapidité de traitement et qu'un LIFO ou FIFO ou autre forme d'accès m'est (dans ce cas) indifférent.

Merci.

[Bousk]

Salut,

vector devrait toujours être le container par défaut.
Cela dit il faudrait au moins décrire ce traitement pour savoir lequel serait mieux ou comment le faire mieux.

[dalfab]

stack<> est par défaut implémenté au dessus de vector<>, alors que queue<> est au dessus de deque<>.
Celui qui ira le plus vite, c'est celui qui correspond à ton besoin. Et si tu as besoin d'une queue<>, utiliser une queue<> ou un deque<> sera aussi optimum, et il faudra vraisemblablement éviter le vector<> dans ce cas.

[koala01]

Salut,

Si la seule chose qui t'intéresse, c'est la rapidité d'accès aux éléments, sans ajouts, sans retraits, alors, la question ne se pose pas: il te faut un tableau.

Cela pourrait cependant impliquer une certaine baisse (et même une baisse certaine dans le pire des cas) des performances au moment de remplir ta collection. Il vaut donc mieux en être conscient

De même, la recherche peut, dans le meilleur des cas, se faire en O(log(N) ), si les éléments sont correctement tirés, mais pourrait s'étendre à du O(N) dans le cas contraire, et l'unicité des éléments n'est absolument pas garantie.

Si tu passe ton temps à ajouter / retirer des éléments (sans commencer à les chercher), la liste sera sans doute pour toi.

Si tu passes d'avantage de temps à chercher un élément particulier parmi "tant d'autres", le tableau trié est l'idéal, mais, à défaut de pouvoir garantir le tri, les structures basées sur les arbres binaires seront tes amies.

Pile et file (stack et queue) posent de très sérieux problèmes en terme d'accès aux éléments, ce qui justifie d'ailleurs leur nom:

• dans une pile, tu ne peux pas accéder à un élément avant d'avoir retiré tous les éléments qui ont été ajoutés après celui auquel tu veux accéder
• dans une pile, tu ne peux accéder à un élément qu'après avoir retiré ceux qui ont été ajouté avant celui auquel tu veux accéder.

LIFO et FIFO ne sont donc pas que des concepts! Ce sont bel et bien des notions qui viennent avec des notions dont il faut tenir compte. Il est particulièrement rare de se trouver dans une situation dans laquelle l'ordre dans lequel tu accèdes à tes données n'a absolument aucune importance

[Legro]

Merci à tous de votre participation,

En fait mon besoin est le suivant : ayant un programme avec un certain nombre de fonctions qui peuvent se renvoyer les une aux autres, il y a une forme de désordre qui s'installe, des appels nombreux et incontrolés. Qui plus est, je crains de que l'application ne tombe un jour dans une boucle infinie. Je cherche donc à neutraliser cette liberté qu'ont les fonctions à s'appeler, et à créer à la place une "liste d'attente". De telle sorte qu'une fonction lorsqu'elle devrait en appeler une autre, inscrive au lieu de cela sa demande dans la liste d'attente, et le programme 'main' se chargera plus tard de faire les appels.
Notons que l'ordre de traitement des données n'a pas d'importance, pour peu qu'elles soient toutes bien traitées.
La vitesse de traitement, elle par contre, est cruciale.
Je cherche donc quel est le meilleur moyen de créer cette liste, sachant que je vais devoir très souvant y ajouter et en retirer des éléments (et que même lorsque je suis en train d'en retirer, d'autres vont s'y ajouter) , mais que l'ordre n'a aucune importance.

[koala01]

Oui, donc, tu vas passer ton temps à ajouter et à supprimer des éléments...

A priori, les tableaux ne sont donc pas pour toi

Par contre, pile, file, liste et éventuellement std;;deque s’avéreront sans doute intéressante. Pile, file et liste proposent l'ajout et la suppression en temps constant, alors que deque ne fourni cela que pour les éléments qui se trouve "en fin de collection".

J'aurais même tendance à dire que la file (d'attente) serait sans doute l'idéal étant donné:

• que l'on ajoute les éléments d'un coté
• que l'on retire les éléments de l'autre
• que l'ordre des éléments est maintenu (FIFO)

parce que,tu m'excuseras,mais, quand tu dis

Notons que l'ordre de traitement des données n'a pas d'importance, pour peu qu'elles soient toutes bien traitées.

hé ben, j'ai le plus grand mal à te croire

Je peux en effet me tromper, mais, généralement, l'ordre d'exécution de différentes fonctions va grandement influer sur le résultat final et il est même possible d'envisager des circonstances où un ordre d'exécution erroné peut carrément empêcher certaines actions d'être entreprises.

Le seul cas où l'ordre pourrait effectivement n'avoir aucune importance, serait que chaque fonction appelée travaille sur des données strictement différentes et sans aucun lien entre elles. C'est envisageable, mais relativement rare

Ceci étant dit, je crois que tu fais fausse route en voulant placer tes fonctions en file d'attente.

A mon sens, cela ne résoudra rien, du moins, pour le problème que tu essaye de gérer: si A fait appel à B, que B fait appel à C et que C fait appel à A, tu auras beau mettre tes fonctions en file d'attente, C finira toujours par faire appel à A, quoi qu'il arrive, et la boucle sera bouclée.

Tu aurais intérêt réfléchir à ton problème comme à un cas de récursivité; c'est à dire, en définissant le cas de base: qu'est ce qui pourra faire, dans ma boucle A, B, C, que la "fonction suivante" ne sera pas appelée, et que la boucle s'arrête Ensuite, il faudra tout faire pour "tendre" vers ce cas particulier.

Maintenant, si chaque fonction ne doit jamais être appelée plus d'une (ou de X ) fois (mais est-ce le cas ) tu peux envisager d'avoir un "élément extérieur" qui pourrait s'occuper de "garder une trace" des différentes fonctions qui ont été appelées.

Pour chaque fonction à laquelle tu ferait appel, tu commencerais par vérifier si la fonction a déjà été appelée (aussi souvent qu'elle le pouvait) ou non, et tu n'y ferais appel que... si ce n'est pas le cas.

Seulement, une telle vérification "prendra du temps"... Peut-être pas "énormément", mais sans doute assez pour ressentir une baisse de performances

Au final, si j'étais toi, j’achèterais sans doute une grande nappe en papier, et je commencerais à tracer le diagramme d'appel des fonctions dessus: si A appelle B, je tracerais une flèche partant de A allant jusqu'à B.

Une fois que j'aurais ce diagramme, je regarderais où se situent les éventuelles boucles, et je verrais comment je peux faire pour les supprimer

[Bousk]

Des tableaux utilisés intelligemment peuvent faire l'affaire.
Si tu reserve ton vector avec une taille suffisante, sans être abusive, push dessus depuis plusieurs threads (avec un lock bien sûr), et swap son contenu dans un autre sur le thread qui va faire les opérations, ca te fait une FIFO efficace et un cache-miss limité puisque tableau et tu évites l'inconvénient de retirer un élément en tête, ce qui est le plus gros piège et l'opération la plus lente du vector imo.