Utiliser plusieurs push_back d'affilé: quelle est la meilleur solution?

Salut,
dansle cadre d'un projet, je dois parser un gros fichier, puis de stocker des elemets un par un dans un vector!
mais là, u probleme se pose: quelle est la meilleur solution pour faire cela

• Compter le nombre d'elements, et faire un seul vector::resize au debut!
• oubien lire le fichier directment, et a chque nouveau element, on fait un vector::push_back

seulement, pour la deuxieme solution, je ne sais pas si beaucoup reallocations font faire baisser les performances, a moins que la classe vector soit asser intelligente pour prevoir un peu plus d'espace a chaque reallocation(je ne suis pas sur qu'elle le fait)

Bonjour,

A mon avis, ce n'est pas une mauvaise idée de réserver de la mémoire pour le vector dès que le nombre d'éléments est connu, pas avec resize, mais avec reserve.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#include <vector> int main(){   size_t size = 10000000;   std::vector<int> vi;   #ifdef WITH_RESERVE vi.reserve(size); #endif   for(size_t i = 0; i < size; ++i){   vi.push_back(i);   }   }

---

Résultat :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

> g++ bench.vec.cc -o bench > time ./bench.exe   real 0m0.584s user 0m0.374s sys 0m0.218s > > g++ bench.vec.cc -o bench -DWITH_RESERVE > time ./bench.exe   real 0m0.390s user 0m0.281s sys 0m0.093s

---

Ici, le code est fait un peu à la va-vite, mais on peut quand même observer une accélération de l'éxécution.

Si on augmente le nombre d'éléments stockés, la différence de performance est encore plus visible.

voila ce que je vais faire:
je vais d'abord faire avec la methode des push_back sans reserve, et apres que je sois sur que tout va bien, j'implementerai un reserve!

faut quand même un assez grand nombre d'élément pour que ça devienne critique.

Ton std::vector n'alloue pas élément par élément, mais par tranche. Par exemple si tu fais 3 push_backs, il n'aura pas alloué 3 éléments mais 10. Si tu fais 5 push_backs de plus, il va en réallouer 20. etc..

Salut,

Effectivement, du point de vue des performances, il est préférable de pouvoir avoir une taille la plus correcte possible à faire réserver pour un vecteur.

Cependant, si tu parle de parser un fichier, peut être le but est-il d'utiliser les éléments que tu as récupérés en vue de les réutiliser dans l'ordre dans lequel tu les as stockés (voire, dans l'ordre inverse de leur stockage) , mais, en tout cas, dans une optique d'utilisation plutôt séquentielle :question:

Si tel est le cas, peut-être aurais tu avantage à envisager un autre conteneur que le vector, telle que la pile (std::stack), la file (std::queue) ou la liste (std::list), selon les besoins réels :question:

L'avantage de ces conteneurs est que l'ajout d'éléments aux extrémités se fait en temps constant, alors qu'il me semble dommage - surtout si le fichier à lire est particulièrement gros - de commencer par... le lire une fois pour compter le nombre d'éléments que tu vas devoir prévoir pour ton tableau et de le lire une seconde fois... pour insérer les éléments dans le tableau :P:aie:

L'inconvénient de ces conteneurs étant... qu'ils sont particulièrement bien adaptés à un accès séquentiel aux éléments, mais qu'ils sont en revanche très peu adaptés à un accès aléatoire aux éléments.

Si ça t'oblige à faire deux passes qui font exactement la même chose c'est pas une bonne idée...
Utilise push_back. Peut-être passe à un conteneur plus approprié à ce que tu veux faire.

push_back est de complexité amortie O(1). Même sans reserve. Plutôt que de faire 2 passes, je te conseille de l'utiliser directement.

ok, merci pour toutes ;)