OK, le vecteur est beaucoup plus pratique que le tableau pour stocker les 'int'
Mais que peut on lui confier à stocker ? avec quels avantages et inconvénients ?
PARTIE I : le vecteur est vide, on lui ajoute un élément
PARTIE II : le vecteur reçoit un deuxième élément
PARTIE III : le vecteur reçoit un troisième élément
PARTIE IV : l'insertion autre part qu'à la fin du tableau
PARTIE V : Tentative d'optimisation de l'utilisation du vecteur
PARTIE VI : Trop de copie ... on utilise des pointeurs... mais attention !
En conclusion : les bonnes pratiques et les interdits
Source / Exemple :
//Le vecteur est un sacré copieur
#include <iostream>
#include <vector>
using namespace std;
/*On prendra une classe simple class A dotée d'un int pour "voir" comment les choses se passent */
class A
{
private :
int i_;
public:
A(int i=0) : i_(i){cout << "Ctor : " << i_ << endl;}
// A(const A& a) : i_(a.i_){cout << "Ctor de copie : " << i_ << endl;} //a décommenter selon indication
void print(ostream& out) const{ out << i_;}
// ~A() {cout << "Dtor : " << i_ << endl;}
};
ostream& operator<<(ostream& out, const A& a) { a.print(out); return out;}
int main()
{
//**********************************************************************
//PARTIE I :le vecteur est vide, on lui ajoute un élément
//**********************************************************************
cout << "vector<A> v;" << endl;
vector<A> v; //vecteur vide, destiné à stocker des objets A
//ici, le vecteur est vide... la preuve :
cout << "vecteur vide ? " << boolalpha << v.empty() << endl;
A a1(1); //création d'un objet de type A
cout << "v.push_back(a1);" << endl;
v.push_back(a1);
//ici, le vecteur n'est plus vide... la preuve :
cout << "vecteur vide ? " << boolalpha << v.empty() << endl;
//on peut accéder à sa capacité de stockage : combien d'éléments sont stockables sans nouvelle réallocation ?
cout << "capacite du vecteur = " << v.capacity() << ", taille = " << v.size() << endl;
/*mais quel est l'objet qui a été stocké par le vector ?
NON, la réponse a1 est FAUSSE ! Je vous avais prévenu (dans le titre de l'article)
La bonne réponse est UNE COPIE DE a1 !
Comment s'en apercevoir ? en traçant l'exécution du Ctor de copie => décommentez le
On peut aussi chercher à écrire l'adresse mémoire du premier élément du vecteur : v[0]
cout << "@ de a1: &a1=" << &a1 << " et @ 1er element du vecteur &v[0]="<< &v[0] << endl;
cout << "le vecteur lui-meme est en " << &v << " (pile)" << endl;
/*on remarque ici que les adresses sont dans des plages différentes
a1 est alloué sur la pile et l'objet copié dans le vecteur est alloué sur le tas...
donc par de l'allocation dynamique...
ce qui est nécessaire pour faire évoluer dynamiquement sa taille (augmentation ou diminution)
//**********************************************************************
//PARTIE II : le vecteur reçoit un deuxième élément
//**********************************************************************
A a2(2); //création du deuxième objet de type A
cout << "v.push_back(a2);" << endl;
v.push_back(a2);
/* Cette fois ci, la question est : qu'à fait le vecteur ?
On sait qu'il a copié l'objet a2 est qu'il a ajouté la copie dans son conteneur
mais allez voir la trace laissée par notre Ctor de copie !
Pour mieux comprendre, allons voir l'adresse des deux éléments du vecteur
cout << " &v[0]="<< &v[0] << " et &v[1]="<< &v[1] << endl;
cout << "capacite du vecteur = " << v.capacity() << ", taille = " << v.size() << endl;
//le conteneur (mémoire allouée) du vecteur se trouvait un peu à l'étroit à l'ancienne place,
//il a donc déménagé dans un deux pièce... et copié chacun des éléments
// Je vous avais prévenu ... blabla
//**********************************************************************
//PARTIE III : le vecteur reçoit un troisième élément
//**********************************************************************
A a3(3);
cout << "v.push_back(a3);" << endl;
v.push_back(a3);
/* Cette fois ci, la question est qu'à fait le vecteur ?
On sait maintenant qu'il a alloué suffisamment de place pour stocker les 3 éléments
Mais il a anticipé les allocations futures et optimisé en allouant 4 objets... la preuve
cout << " &v[0]="<< &v[0] << ", &v[1]="<< &v[1] << " et &v[2]="<< &v[2] << endl;
cout << "capacite du vecteur = " << v.capacity() << ", taille = " << v.size() << endl;
/* Remarquons que ce comportement du vecteur n'est pas spécifié par les standards et que chaque
implémentation peut se comporter différemment : le vecteur de l'implémentation VC++ alloue le double de la taille courante
lors de chaque nouveau besoin
Pour vérifier cela, que les éléments ne sont pas copiés cette fois ci, ajoutons un autre élément
cout << "v.push_back(a4);" << endl;
v.push_back(A(4));
cout << " &v[0]="<< &v[0] << ", &v[1]="<< &v[1] << ", &v[2]="<< &v[2] << " et &v[3]="<< &v[3] << endl;
cout << "capacite du vecteur = " << v.capacity() << ", taille = " << v.size() << endl;
//on retire alors cet élément
cout << "pop_back de : " << v.back()<< " par v.pop_back();" << endl;
v.pop_back();
//remarque 1 : l'appel à pop_back() appelle le destructeur de l'objet chassé
//remarque 2 : le pop_back ne renvoie rien, il convient d'avoir récupéré l'objet par back() si besoin est
cout << "capacite du vecteur = " << v.capacity() << ", taille = " << v.size() << endl;
/*
Pourquoi ces réallocations ?
Car le vecteur est implémenté par un tableau en memoire dynamique ... et tous les éléments d'un tableau sont contigus
C'est d'ailleurs ce qui rend le tableau si efficace lors de l'accès aléatoire par l'opérateur []
L'élément 2 est alors récupéré directement par son adresse : adresse_début_tableau+2*sizeof(élément)
PARTIE IV : l'insertion autre part qu'à la fin du tableau
Il existe la possibilité d'insérer des éléments à la position de notre choix dans le tableau
La méthode 'insert' permet cela, à condition de lui fournir un itérateur initialisé sur l'élément
devant lequel on veut insérer notre nouvel élément.
Par exemple, pour initialiser un itérateur au début du vecteur :
vector<A>::iterator it = v.begin();
// Pour insérer un objet a4 :
A a4(4);
cout << "v.insert(v.begin(), a4);" << endl;
v.insert(v.begin(), a4);//ou à des emplacements différents : v.insert(v.begin()+1, a4);
//v.insert(it, a4);
cout << " &v[0]="<< &v[0] << ", &v[1]="<< &v[1] << ", &v[2]="<< &v[2] << ", &v[3]="<< &v[3] << " et &v[4]="<< &v[4] << endl;
/* Que fait le vecteur à votre avis ?
Comment ? il copie tout le monde ? tous les éléments suivant le point d'insertion ?
et ceci, même s'il a suffisamment de place dans sa capacité ?
PAS DU TOUT ! sur ce coup là, il optimise les appels au ctor de copie dans les déplacements mémoire
C'est pour montrer ceci que nous avons retiré l'ancien 4ème élément dans la partie précédente.
Mais au fait, comment les éléments sont ils déplacés ?
Comme nos Ctors de copies ne sont pas appelés, la copie est faite par bit-copy
//ici des exemples de parcours du vecteur fonctionnellement identiques
for (it=v.begin(); it!=v.end(); it++)//boucle avec itérateur
cout << *it << " "; //impression de l?élément via l'itérateur (déréférencé)
cout << endl;
for (int i =0; i<v.size(); i++)//boucle simple
cout << v[i] << " "; //impression de l?élément via l'opérateur []
cout << endl;
//ici une faible utilisation du vecteur, le parcours direct par un pointeur utilisateur
A * ptr = &v[0];
for (int ii=0; ii<4; ii++)
cout << *ptr++ << " " ;
cout << endl;
/*********************************************************************
PARTIE V : Tentative d'optimisation de l'utilisation du vecteur
Que de copies d'objet lorsque les insertions sont faites une par une !
Dans le cas de figure ou nous savons à peu près combien d'objets seront mis dans le vecteur,
l'idée est de TAILLER notre vecteur dès le début.
Pour faire cela, tournons nous vers les Constructeurs du vecteur, nous en voyons un qui SEMBLE
répondre à notre souhait
explicit vector(size_type n, const T& v = T(), const A& al = A());
Utilisons le pour vérifier son fonctionnement
cout << "vector<A> v2(5);" << endl;
vector<A> v2(5);
/*Qu'a t il fait ?
BRAVO : il a copié ! il a d'abord utilisé le Ctor par défaut de A pour créer un objet temporaire
il a ensuite utilisé cet objet temporaire comme source d'information pour la création par le Ctor de copie
des autres éléments (les vrais) v2[0], .... v2[4] et il a ensuite détruit l'objet temporaire.
On voit aussi que l'on peut choisir l'objet source de copie en codant ainsi :
cout << "vector<A> v3(5, A(10));\n";
vector<A> v3(5, A(10));
/*
Quand un vecteur est trop petit, peux t on suggérer nous même l'aggrandissement ?
OUI en utilisant la méthode resize()
cout << "avant resize : capacity=" << v3.capacity() << " et size=" << v3.size() << endl;
cout << "v3.resize(20);\n";
v3.resize(20);
cout << "apres resize : capacity=" << v3.capacity() << " et size=" << v3.size() << endl;
/*
On a pas mal de copies, mais par rapport à la construction d'un vecteur vide suivi de push_back
on gagne les réallocations mémoire et copies intermédiaires successives
Mais n'y a t il pas un moyen de tailler le vecteur SANS CREER TOUS CES OBJETS ?
La réponse est dans la méthode reserve()
vector<A> v4;
cout << "\nv4.reserve(20); \n";
v4.reserve(20);
cout << "apres reserve : capacity=" << v4.capacity() << " et size=" << v4.size() << endl;
//reserve est différent de resize dans la mesure ou il ne s'occupe que de la mémoire allouée
//et PAS des objets du vecteur : pas de création et donc pas de copie
/*************************************************************************
PARTIE VI : Trop de copie ... on utilise des pointeurs... mais attention !
Que de copies d'objet ! l'idée suivante est de ne confier au conteneur que des pointeurs
sur mes objets
On va donc créer un objet dynamiquement et l'ajouter au vecteur
{
A* pa=new A(1);
vector<A*> v5;
v5.push_back((A*)&v5);
v5.resize(2);//cette fois ci, le resize ne fait pas de copie d'objet
cout << "cap=" <<v5.capacity() << " et size=" << v5.size() << endl;
//ici, une boucle jusqu'a size-1 provoquerait un TRAP
for (int i =0; i<v5.size(); i++)//boucle simple
// cout << *v5[i] << " "; //A décommenter pour voir le trap
cout << endl;
//ici, lorsque le vecteur va être détruit, ne pas oublier de libérer l'objet par
delete pa; // car le destructeur de vector ne fera rien pour nos pointeurs
}
return 0;
}
/*
En conclusion :
La bonne pratique est d'anticiper la taille finale de l'objet vecteur dès sa construction
ou au moins par une opération de reserve faite avant la première insertion.
Ceci n'est pas toujours possible ... évidemment
Les interdits :
- si vous avez un objet lent à copier ou un objet non copiable (Ctor de copie privé)
il est impossible d'utiliser le vecteur
- De même, si votre objet ne possède pas de Ctor par défaut, l'utilisation du vecteur est handicappée
car les resize y font appel
- Pour éviter toutes les copies lourdes, on pourrait envisager de confier des pointeurs à notre vecteur
Mais alors il faut gérer nous même la synchronisation du conteneur, des pointeurs et des objets
En particulier, la création par new d'un objet et l'ajout du pointeur dans le vecteur nécessitera
l'appel à delete lors de la destruction du vecteur... car le vecteur appellera seulement le destructeur
de ce que nous lui avons confié... un pointeur. Le type pointeur n'étant pas une classe, aucun destructeur
n'est appelé automatiquement.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.