Optimisation vector ou list

J'ai vu dans un exemple de code de STL le code suivant censé etre plus rapide que la methode push_back :

Code:

---

1 2 3 4

vector<T> v; ... v.resize(v.size()+1); T& newElement = v.back();

---

En effet, il y a une copie en moins par rapport au code "habituel" :

Code:

---

1 2	T newElement; v.push_back(newElement);

---

Mais je ne connais pas assez bien la methode resize() pour dire que le 1er exemple est plus rapide que le 2nd.
Qu'en pensent les specialistes du forum ?

La principale différence c'est que push_back (si je ne me trompe pas) va doubler la mémoire allouée par le vector si il n'y a pas assez de mémoire déjà réservée.

Le premier exemple va augmenter le vector d'un seul élément.

Autrement dit, si ce code est appelé souvent, le premier exemple sera plus lent car réalocation intempestive, tandis que le second sera de moins en moins lent car de l'espace sera déjà alloué la plupart du temps (donc yaura uniquement de la copie).

A voir si tu as plus besoin d'espace que de vitesse.

Corrigez moi si je me trompe :)

C'est vrai que la fonction resize() pourrait rajouter des éléments en appelant juste le constructeur par défaut, sans utiliser le constructeur de copie comme le fait push_back().

Pourtant quand je regarde les implémentations de la STL dont j'ai accès (VC2005 et gcc 3.4.4) toutes les deux implémentent resize(newSize) en appelant resize(newSize, T()), perdant ainsi la possibilité d'optimisation.

Quelqu'un sait pourquoi ?

NB : par contre, normalement, pas de différence au niveau gestion de la mémoire entre resize(size() + 1) et push_back().

Citation:

---

Envoyé par Sylvain Togni

Pourtant quand je regarde les implémentations de la STL dont j'ai accès (VC2005 et gcc 3.4.4) toutes les deux implémentent resize(newSize) en appelant resize(newSize, T()), perdant ainsi la possibilité d'optimisation.

Quelqu'un sait pourquoi ?

---

Il n'y a normalement qu'un resize avec un argument par defaut.

Il y a aussi des cas ou la tendance est de penser que la norme surspecifie certains membres (par exemple en donnant une implementation possible -- c'est une occurence du probleme general absolument pas propre aux normes de prendre une implementation pour une specification), c'est en particulier vrai dans le cadre de la nouvelle norme mais c'aurait pu etre le cas (et ce l'est potentiellement si il y a une permission de remplacer les arguments par defaut par une surcharge; dans du code de bibliotheque, j'ai tendance a considerer les arguments par defaut comme etant des fausses bonnes idees, surtout a cause des problemes qu'ils posent quand on veut passer la fonction... la surdefinition est une raison de plus).

Salut,

La version 'push_back' me parait un peu plus sûre en cas de levée d'exception, mais peut-être que tu t'en fout ;)

MAT.

Je me demande s'il ne s'agissait pas de la difference entre:

Code:

---

1 2 3 4

T newElement; Initialize(newElement); v.push_back(newElement);

---

et

Code:

---

1 2 3 4

v.resize(v.size()+1); T& newElement = v.back(); Initialize(newElement);

---

Le gain est dans le cas ou copier l'objet apres l'appel a Initialize est plus couteux que celui de la copie d'un objet construit par defaut (c'est vraisemblablement le cas par exemple si Initialize introduit de l'allocation dynamique).