Discussion :

[camboui]

Je cherche l'équivalent de la méthode reserve() de std::vector mais pour deque (et queue). Je ne la trouve pas...
Merci.

[ZaaN]

dans quel but ?

gagner du temps d'execution en allouant dès le debut de la memoire ?

pour la gestion de la memoire (system embarqué) ?

[camboui]

Oui, c'est l'évidence même...

J'use et abuse de la méthode reserve() de std::vector quand je connais à l'avance le nombre d'éléments à traiter ou quand je peux en faire une estimation assez précise. Ça évite une fragmentation inutile de la mémoire (sans compter les allocations/désallocations avec les copies d'objets que cela implique, etc).

Je m'étonne de ne pas trouver d'équivalent dans std::queue et std::deque.

Une telle méthode existe-elle ?

[coyotte507]

pour les vecteurs la méthode reserve() est utile car la mémoire n'est pas fragmentée, c'est un bloc qu'il faudrait réallouer entièrement à chaque changement de taille.

Pour ta queue, les différents objets n'ont pas besoin d'être côte à côte et faire une nouvelle allocation avant ou après ne change vraiment pas grand chose car il faudra faire autant d'allocations, car une allocation = un objet. (pour les vecteurs une allocation = tous les objets)

[koala01]

Salut,

Si reserve a un intéret dans le cadre des vector, c'est parce qu'ils sont basés sur un tableau C style ( ex: int mbr[10], int ptr*= new int[10]), meme si c'est transparent pour l'utilisateur, ce qui fait que les différents éléments sont placés dans des espaces contigus de la mémoire.

Cela permet donc de dire, dés le départ "je prévois d'avoir (n) éléments dans mon tableau", et d'éviter le problème de la réallocation de la mémoire tant que l'on n'a pas atteind le (n-1)eme élément.

Par contre la deque fnoctionne plutot sur le principe d'une "structure dynamique", ou, si tu préfères, d'une structure dans laquelle chaque élément dispose d'un pointeur vers l'élément précédent/suivant.

L'espace mémoire utilisé par les différents éléments ne doit donc pas etre contigu, vu qu'il est alloué "au premier endroit où on trouve un espace suffisant pour faire tenir l'élément"

Simplement, afin de permettre un ajout en temps constant à la fin de la liste (en évitant de devoir reparcourrir l'ensemble des élément), la deque maintient également un pointeur sur le dernier élément qu'elle contient

Il n'y a donc aucune raison de vouloir réserver de l'espace pour les différents éléments qu'elle contient, et, c'est la raison pour laquelle la méthode reserve n'existe purement et simplement pas

[JolyLoic]

Par contre la deque fnoctionne plutot sur le principe d'une "structure dynamique", ou, si tu préfères, d'une structure dans laquelle chaque élément dispose d'un pointeur vers l'élément précédent/suivant.

Ne confondrais-tu pas avec std::list ?

Je vois plus un deque comme une liste de tableaux de taille fixe.

[camboui]

OK, merci pour vos réponses.
C'est l'implémentation de std::queue qui me parait lourde. Je pense qu'elle aurait pu être plus simple et basée sur std::vector au lieu de std::deque.

Vu la simplicité de mes besoins (std::queue<unsigned>), j'en ferai une implémentation moi-même si nécessaire.

Merci encore.

[Laurent Gomila]

Tu veux un std::queue basé sur un std::vector ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

std::queue<T, std::vector<T> >

Mais std::vector sera moins efficace, car une file nécessite des opérations en début de séquence, ce qui entraîne une recopie de tout le tableau dans le cas d'un std::vector.

[Alp]

La solution donnée par Laurent est ce que tu désires, seulement comme il l'a dit cela sera très lourd, donc à n'utiliser que si tu n'as pas besoin de rapidité.

[r0d]

Sinon, je me demande: si tu connais à l'avance la taille de ton conteneur (enfin, le nombre d'éléments qu'il va contenir), et que les problèmes de performances semblent si contraignantes, pourquoi ne pas utiliser un simple vector alloué une bonne fois pour toute, et puis tu le parcours avec un itérateur que tu garde en mémoire quelque part pour ne pas avoir à re-parcourir ton tableau à chaque fois?

[camboui]

Tu veux un std::queue basé sur un std::vector ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

std::queue<T, std::vector<T> >

Non, je veux une (autre) queue basée sur un std::vector, puisque std::queue me semble trop lourde pour mes besoins.

Mais std::vector sera moins efficace, car une file nécessite des opérations en début de séquence, ce qui entraîne une recopie de tout le tableau dans le cas d'un std::vector.

En effet, une recopie sera nécessaire de temps en temps, mais uniquement lorsqu'il faudra réalouer de l'espace mémoire.
Deux indices sur std::vector, en plus de std::vector lui-même, sont suffisants pour faire une queue: un pour le début de la queue et un pour la fin, l'indice de fin pouvant être inférieur à celui de début (std::vector pouvant être vu comme une liste circulaire, l'élément d'indice 0 étant le suivant de celui d'indice N-1, s'il y a N éléments).