push_back d'un objet

D'après la définition de la fonction push_back, cette dernière fait une copie de l'objet et l'ajoute au conteneur:

Citation:

---

The content of this new element is initialized to a copy of x.

---

Donc, j'ai fait un petit exemple illustrant le problème:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include <iostream> #include <vector>   using namespace std;   class Foo { public: Foo() { cout << "Constructeur Foo()" << endl; }   Foo(const Foo& foo) { cout << "Constructeur par copie Foo(Foo& foo)" << endl; *this = foo; }   Foo& operator=(const Foo& foo) { cout << "Operateur de copie operator=(const Foo& foo)" << endl; return *this; } };   void addFoo(); void displayListFoo();   vector<Foo> listFoo;   int main( ) { addFoo(); displayListFoo(); addFoo(); displayListFoo(); addFoo(); displayListFoo();   return 0; }   void addFoo() { Foo foo; cout << "&foo: " << &foo << endl; listFoo.push_back(foo); Foo& rFoo = listFoo.back(); cout << "&rFoo: " << &rFoo << endl; cout << endl; }   void displayListFoo() { for (vector<Foo>::const_iterator itr = listFoo.begin(); itr != listFoo.end(); ++itr) { cout << "&*itr: " << &*itr << endl; } cout << endl; }

---

Et voici le résultat:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Constructeur Foo() &foo: 0012FE8F Constructeur par copie Foo(Foo& foo) Operateur de copie operator=(const Foo& foo) &rFoo: 003459B8   &*itr: 003459B8   Constructeur Foo() &foo: 0012FE8F Constructeur par copie Foo(Foo& foo) Operateur de copie operator=(const Foo& foo) Constructeur par copie Foo(Foo& foo) Operateur de copie operator=(const Foo& foo) &rFoo: 003459E9   &*itr: 003459E8 &*itr: 003459E9   Constructeur Foo() &foo: 0012FE8F Constructeur par copie Foo(Foo& foo) Operateur de copie operator=(const Foo& foo) Constructeur par copie Foo(Foo& foo) Operateur de copie operator=(const Foo& foo) Constructeur par copie Foo(Foo& foo) Operateur de copie operator=(const Foo& foo) &rFoo: 003459BA   &*itr: 003459B8 &*itr: 003459B9 &*itr: 003459BA

---

Normal que foo et rFoo n'aient pas la même adresse mémoire vu que la fonction effectue une copie.

Par contre, je ne comprends pas pourquoi à chaque fois que j'ajoute un nouvel élément à mon conteneur, alors tous les précédents sont égalément reconstruits.

Quelqu'un pourrait m'expliquer? Car ce problème que j'ai réussi à isoler fait planter mon application et je ne comprends pas pourquoi.

Concrètement, après avoir ajouter un élément dans mon vecteur, je garde une trace à l'aide d'un pointeur de l'élément ajouté (rFoo), mais vu que dans mon vecteur les éléments ont changé, alors je perds la concordance :?

Autre problème:

Si les objets sont lourds et que j'ajoute pas mal d'éléments dans mon conteneur, alors ça va faire autant de copies qu'il y a d'éléments, donc chaque ajout va devenir de plus en plus gourmand !!!

Par exemple, si j'ai 1000 éléments, alors j'aurais 1 + 2 + 3 + ... + 1000 copies !!!

Formellement, ajouter un élément à un vecteur invalide tout pointeur et tout itérateur sur un élément, pour peu qu'il n'y ait pas assez de place dans le vecteur. Si tu veux que ça ne soit pas le cas, utilise list, ou réserve assez de place avec la fonction réserve.

Citation:

---

Envoyé par Trunks

Par contre, je ne comprends pas pourquoi à chaque fois que j'ajoute un nouvel élément à mon conteneur, alors tous les précédents sont égalément reconstruits.

---

Il ne le fait pas à chaque ajout. Un vecteur a une size et une capacity, on a réserve de la place en plus pour permettre une croissance sans réallocation. Mais quand la size excède la capacity, il faut bien réallouer. Tracer la veleur de ces deux fonctions dans ton code devrait être instructif.

Citation:

---

Envoyé par Trunks

Si les objets sont lourds et que j'ajoute pas mal d'éléments dans mon conteneur, alors ça va faire autant de copies qu'il y a d'éléments, donc chaque ajout va devenir de plus en plus gourmand !!!

Par exemple, si j'ai 1000 éléments, alors j'aurais 1 + 2 + 3 + ... + 1000 copies !!!

---

Non, car comme je l'ai dit il ne réalloue pas à chaque fois. Et la stratégie de croissance est soigneusement choisie pour qu'il y ait peu de recopies. C'est d'ailleurs un problème que j'aime bien donner quand je parle de complexité algorithmique : Déterminer la complexité d'ajout 1 par 1 de N éléments dans un vecteur, quand on a choisi la stratégie de multiplier la capacité par K quand le vecteur est trop petit.

Je ne pensais pas avoir une réponse dans la nuit :D

D'accord, je comprends mieux, le problème est qu'un vecteur utilise des espaces contigüees. Donc, quand il n'y a plus assez de place, alors il recopie le tout dans un autre espace mémoire. C'est la raison qui explique pourquoi dans mon cas concrets, sur 36 éléments, seulement les 6 derniers n'avaient pas changé de place. Ca veut dire que la dernière migration avait été effectué 6 éléments avant.

Je vais donc utiliser une liste à la place.

Par contre les listes n'utilisent pas d'espaces contigües, du coup ce problème devrait disparaître !

Merci encore pour ton explication, tu es un chef :king:

Edit: Maintenant mon programme marche nickel ! A dire que j'ai passé la journée pour isoler le problème... tout ça résolu en changeant le type du conteneur :)

Citation:

---

Envoyé par JolyLoic

Il ne le fait pas à chaque ajout. Un vecteur a une size et une capacity, on a réserve de la place en plus pour permettre une croissance sans réallocation. Mais quand la size excède la capacity, il faut bien réallouer.

---

J'avais pas lu la suite:

Code:

---

This effectively increases the vector size by one, which causes a reallocation of the internal allocated storage if the vector size was equal to the vector capacity before the call. Reallocations invalidate all previously obtained iterators, references and pointers.

---

Ou plutôt, quand j'ai créé mon programme, je n'y avait pas pensé, d'où le plantage bien en règle :mouarf:

A noter que il y'a une méthode reserve() qui te permet de réserver suffisamment de mémoire pour garantir que ton vector ne sera pas déplacer (et donc tes objets reconstruits). Néanmoins ça implique d'avoir un ordre d'idée de la taille finale de ton vecteur..

Dans ton cas la liste doit être la meilleure solution ^^.

Citation:

---

Envoyé par Goten

A noter que il y'a une méthode reserve() qui te permet de réserver suffisamment de mémoire pour garantir que ton vector ne sera pas déplacer (et donc tes objets reconstruits). Néanmoins ça implique d'avoir un ordre d'idée de la taille finale de ton vecteur..

Dans ton cas la liste doit être la meilleure solution ^^.

---

J'opte pour le plus générique, que ça marche quelque soit les conditions, donc j'opte pour la liste :)