Conteneurs de séquence - vector

Conteneurs de séquence

La bibliothèque C++ standard contient trois véritables conteneurs de séquence : vector, list et deque. Les conteneurs stack, queue et priority_queue sont plutôt des descripteurs de conteneur.

vector

Pour utiliser un conteneur vector, vous devez inclure le fichier en-tête <vector> au début du programme et travailler dans l’espace de noms std. Ce conteneur se comporte comme un tableau avec une efficacité et une sécurité optimales. Il est capable de faire évoluer sa taille si nécessaire. Comme pour un tableau l’accès aléatoire aux éléments est optimisé, mais si les insertions et suppressions d’éléments sont nombreuses, il sera préférable d’utiliser un conteneur list (voir section suivante). En effet, ce type d’opération impose le déplacement de tous les éléments suivants du conteneur avec toutes les opérations de gestion de la mémoire associées !

Pour commencer, examinons la déclaration du conteneur vector pour comprendre comment il est utilisé. Faute de place, nous ne reproduisons pas ici la déclaration de l’ensemble des fonctions membres que vous découvrirez dans les exemples des codes 8.1 (création et redimensionnement des conteneurs vector), 8.2 (accès aux éléments d’un vector via l’opérateur surchargé [ ]), 8.3 (accès aux éléments d’un vector via les itérateurs), 8.4 (ajout et suppression d’éléments dans un vector), et 8.5 (opérations sur des vector).

1 : template <class T, class A = allocator<T>> class vector  
2 : {  
3 : public:  
4 :  // types  
5 :  typedef typename A::size_type  size_type;  
6 :  
7 :  // constructeurs  
8 :  explicit vector(const A& = A());  
9 :  explicit vector(size_type n, const T& val = T(),   
10:                 const A& = A());  
11: vector(const vector& v);  
12:  
13: }

À la ligne 5, apparaissent deux nouveaux mots clés : typedef et typename.

Le premier correspond à un mécanisme de création d’alias fourni par le C++ pour simplifier la lecture d’un programme : vous remplacez dans le code un type complexe par le nom choisi. Par exemple :

typedef unsigned short int mot;  
mot x, y;       //déclaration de 2 entiers courts non signés

mot devient strictement équivalent à unsigned int. La syntaxe des types tableau est un peu différente :

typedef int tab[10];  
tab mon_tableau;   //déclaration d’un tableau de 10 entiers

Le deuxième mot clé, typename, est utilisé pour signaler au compilateur qu’un identificateur inconnu dans un modèle est un type. Voici la syntaxe de ce mot clé :

//déclaration d’une classe A  
class A  
{  
public:  
/*on définit le type entierNS dans la classe A :  
    typedef unsigned int entierNS;  //entierNS=unsigned int  
};  

//Déclaration d’un modèle  
template <class T>  
class mon_modele  
{  
   typename T::entierNS i;  // mon_modele suppose que le  
              // type générique T définit un type entierNS  
};  

mon_modele<A> ma_classe; // A peut servir à instancier une  
            //classe à partir du modèle de classe mon_modele

La ligne 5 peut donc être interprétée comme suit : « size_type est équivalent au type size_type défini dans la classe A ».
Les trois constructeurs des lignes 9, 10 et 11 permettent de créer :

//un vector d’entiers de 100 éléments :  
vector<int> v_entiers(100);  
//un vector initialisé à partir d’un autre :  
vector<int> v_entiers;

Code 8.1 création et redimensionnement des conteneurs vector

#include <iostream>  
#include <vector>  
using namespace std;  

typedef vector<int>  v_entiers;  
//v_entiers désigne le type vecteur d’entiers  

//Prototype de la fonction d’affichage du conteneur :  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v);  

//Définition de la fonction d’affichage du conteneur :  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v)  
{  
//max_size renvoie le nombre d’éléments du plus gros  
// vector possible  
  cout << "max_size() = " << v.max_size();  
//size() renvoie le nombre d’éléments du conteneur  
  cout << "tsize() = " << v.size();  
//empty est un booléen égal à 1 (vrai) si le vecteur  
// est vide  
  //si v.empty est vrai on affiche "vide" sinon "non vide"  
  cout << "t" << (v.empty()? "vide": "non vide");  
/*capacity() renvoie le nombre total d’éléments pouvant être stockés dans la mémoire réservée*/  
  cout << "tCapacité = " << v.capacity();  
  cout << "nn";  
}  

//Fonction principale  
void main()  
{  
  cout << "On définit le vecteur d’entiers v_ent1 sans élémentn";  
  cout << "Voici les valeurs renvoyées par les fonctions membres: ;" << endl;  
  v_entiers  v_ent1;  
  AfficherVector(v_ent1);  

  cout << "On définit le vecteur d’entiers v_ent2 n";  
  cout << "avec 3 éléments (v_ent2(3)), les valeurs deviennent:" << "n";  
  v_entiers  v_ent2(3);  
  AfficherVector(v_ent2);  

  cout<<"On augmente la taille de v_ent2 à 5n";  
  cout << "Puis on ajoute la valeur 100 en finn";  
  v_ent2.resize(5, 100);  
  cout << "v_ent2 après resize(5, 100): n";  
  AfficherVector(v_ent2);  

  cout << "On réserve de la mémoire pour 10 élémentsn";  
  v_ent2.reserve(10);  
  cout << "v_ent2 après reserve(10):n";  
  AfficherVector(v_ent2);  

}

Voici le résultat de l’exécution du programme précédent :

On définit le vecteur d’entiers v_ent1 sans élément  
Voici les valeurs renvoyées par les fonctions membres:  
max_size()=1073741823  size()=0  vide  Capacité=0  

On définit le vecteur d’entiers v_ent2  
avec 3 éléments (v_ent2(3)), les valeurs deviennent:  
max_size()=1073741823 size()=3  non vide  Capacité=3  

On augmente la taille de v_ent2 à 5  
Puis on ajoute la valeur 100 en fin  
v_ent2 après resize(5, 100):   
max_size()=1073741823 size()=5  non vide  Capacité=6  

On réserve de la mémoire pour 10 éléments  
v_ent2 après reserve(10):  
max_size()=1073741823 size()=5  non vide  Capacité=10

La fonction d’affichage AfficherVector() est définie comme modèle pour être capable de traiter tout type de conteneur.

Selon le compilateur utilisé, la valeur renvoyée par capacity() pourra varier. Vous constatez que le compilateur réserve la mémoire juste suffisante pour stocker exactement le nombre d’éléments déclarés dans les deux premiers tests. Dans le troisième test, il réserve de la place pour 6 alors qu’on a demandé une taille de 5 et, dans le dernier, la mémoire est bien réservée mais la taille reste à 5.

Dans l’exemple qui suit, la fonction AfficherVector() est modifiée pour accéder aux éléments via l’opérateur d’index [].

Code 8.2 accès aux éléments d’un vector via l’opérateur surchargé [ ]

#include <iostream>  
#include <vector> // définition du modèle de classe vector  
#include <stdexcept> // pour l’exception out_of_rangeusing namespace std;  

typedef vector<int>  v_entiers;  

//prototype de la fonction AfficherVector  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v);  

// Définition de la fonction AfficherVector  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v)  
{  
  // On parcourt le vecteur via l’opérateur []  
  cout << "nVoici les éléments:n";  
  for (vector<int>::size_type i=0; i < v.size(); ++i)  
    cout << v[i] << ", ";   

  //on affiche la valeur du premier élément :  
  cout << "nValeur de front() = " << v.front();  
  //on affiche la valeur du dernier élément :  
  cout << "tValeur de back() = " << v.back();  

  cout << "nn";  
}  

int main()  
{  
  cout << "On crée le vecteur d’entiers v_ent(3)";  
  cout << " avec 3 éléments" << "n";  
  v_entiers  v_ent(3);  

  cout << "On affecte une valeur à chaque élément via l’opérateur []" << endl;  
  for (vector<int>::size_type i = 0; i < v_ent.size(); ++i)  
    v_ent[i] = i*i ;   

  cout << "On tente d'affecter une valeur à un élément";  
  cout << " via la fonction at()" << endl;  
  try  
  {   
    v_ent.at((v_entiers::size_type)4) = 50;   
    // Erreur, hors de l’intervalle admis !   
  }   
  // accès hors de l’intervalle admis?   
  catch(out_of_range)   
  {   
  //si oui, on affiche le message :  
    cout << "Index hors de l’intervalle admis" << endl;  
  }  
  AfficherVector(v_ent);  

// Augmente de 5 la taille de v_ent et ajoute 100 à la fin  
  v_ent.resize(5, 100);  
  cout << "On resize(5, 100) notre vecteur v_entn";  
  cout << "On essaie maintenant d'accéder au 4ième élément toujours";  
  cout << " via la fonction at()" << endl;  
  try  
  {   
    v_ent.at((v_entiers::size_type)4) = 50; //OK   
  }   
    cout << "Index hors de l’intervalle admis" << endl;  
  }  
  AfficherVector(v_ent);  
}

Voici le résultat de l’exécution de ce programme :

On crée le vecteur d’entiers v_ent(3) avec 3 éléments  
On affecte une valeur à chaque élément via l’opérateur []  
On tente d’affecter une valeur à un élément via la fonction at()  
Index hors de l’intervalle admis  

Voici les éléments:  
0, 1, 4,  
Valeur de front()=0  Valeur de back()=4  

On resize(5, 100) notre vecteur v_ent  
On essaie maintenant d’accéder au 4e élément toujours via la fonction at()  

Voici les éléments:  
0, 1, 4, 100, 50,  
Valeur de front()=0  Valeur de back()=50

L’association bloc try/catch et détection de l’exception out_of_range permet de détecter toute tentative d’accès hors de la zone de mémoire réservée pour le vecteur (voir section « Gestion des erreurs et exceptions » en annexe).

Dans l’exemple qui suit, la fonction AfficherVector() est encore modifiée pour accéder aux éléments via un itérateur.

Un itérateurxe "itérateur" n’est rien d’autre qu’un objet permettant d’accéder à tous les objets d’un conteneur donné, souvent séquentiellement, selon une interface standardisée. La dénomination d’itérateur provient donc du fait que les itérateurs permettent d’itérer sur les objets d’un conteneur, c’est-à-dire d’en parcourir le contenu en passant par tous ses objets. Chaque conteneur utilise la classe d’itérateurs la plus appropriée selon sa nature.
Les itérateurs ne sont pas des pointeurs, mais ils sont implémentés pour avoir le même comportement. Ils peuvent donc être incrémentés, décrémentés, et vous pouvez leur appliquer l’indirection.

Un itérateur reverse_iterator permet de parcourir les éléments d’un conteneur à l’envers et un const_iteratorxe "const_iterator ou un const_reverse_iterator interdit toute modification de l’élément sur lequel il pointe.
Enfin, deux itérateurs sont égaux s’ils pointent sur le même élément dans le même vecteur.

Code 8.3 : accès aux éléments d’un vector via les itérateurs

#include <iostream>  
#include <vector>  
using namespace std;  

typedef vector<int>  v_entiers;  

template<class T, class A>  
void AfficherVector(const vector<T, A>& v);  

int main()  
{  
  cout << "On définit un vecteur d’entiers de 3 élémentsn";  
  v_entiers  v_ent(3);  

  cout << "On affecte une valeur à chaque élément de v_ent";  
  cout << " via un itérateur" << endl;  
  int i = 0;  
  v_entiers::iterator itor ;  
  for (itor = v_ent.begin(); itor != v_ent.end(); ++itor)  

itor = i * i++;
  cout << "Voici sa valeur: " << *++itor << endl;  
  AfficherVector(v_ent);  
}  

//Définition de la fonction AfficherVector  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v)  
{  
  // On parcourt le vecteur via un itérateur  
  cout << "nEléments affichés via un itérateur:n";  
  for (typename vector<T, A>::const_iterator itor = v.begin();  
             itor != v.end(); ++itor)  
    cout << *itor << ", ";  
  cout << "n";  
  // On parcourt le vecteur via un itérateur inverse  
  cout << "nEléments affichés via un itérateur inverse:n";  
  for (typename vector<T, A>::const_reverse_iterator r_itor = v.rbegin();  
              r_itor < v.rend(); ++r_itor)  
    cout << *r_itor << ", ";  
  cout << "nn";  
}

L’exécution de ce programme donne le résultat suivant :

On définit un vecteur d’entiers de 3 éléments  
On affecte une valeur à chaque élément de v_ent via un itérateur  
Voici sa valeur: -572662307  

Eléments affichés via un itérateur:  
0, 1, 4,  

Eléments affichés via un itérateur inverse:  
4, 1, 0,

À savoir

L’emploi du mot clé type name dans les deux dernières boucles for signale au compilateur que le type décrit juste derrière est un véritable type et non un modèle. En l’absence de ce mot clé, le compilateur émet un message d’erreur itor was not declared in this scope (itor n’est pas déclaré dans cette portée).

L’ajout et la suppression d’éléments dans un vector sont des opérations plus complexes dans la mesure où elles impliquent le déplacement de tous les éléments situés entre l’élément modifié et la fin du conteneur. S’il s’agit d’une insertion et que la capacité du vecteur est égale à sa taille, un nouveau bloc de mémoire doit aussi être réservé pour accueillir le nouvel élément. Notez qu’un vector utilise toujours un bloc de mémoire continu pour stocker ses éléments.

Code 8.4 ajout et suppression d’éléments dans un vector

#include <iostream>  
#include <vector>  
using namespace std;  

typedef vector<int>  v_entiers;  
typedef vector<int>::iterator  iter_vEnt;  

template<class T, class A>  
void AfficherVector(const vector<T, A>& v);  

int main()  
{  
  cout << "On définit un vecteur d’entiers avec 5 élémentsn";  
  v_entiers  v_ent(5);  

  cout << "On affecte une valeur à chaque élément de v_ent";  
  cout << " via l'opérateur index []:n";  
  for (vector<int>::size_type i = 0; i < v_ent.size(); ++i)  
    v_ent[i] = 5 * i;  

  AfficherVector(v_ent);  

  cout << "On insère un élément avec insert(v_ent.begin()";  
  cout << " + 1, 50)nNotre conteneur devient:n";  
  iter_vEnt itor = v_ent.insert(v_ent.begin() + 1, 50);  
  AfficherVector(v_ent);  
  cout << "Voici l’élément courant : " << *itor << "nn";  

  cout << "On insère 5 éléments avec insert(v_ent.end(), 5, 30):n";  
  v_ent.insert(v_ent.end(), 5, 30);  
  AfficherVector(v_ent);  

  cout << "On supprime un élément dans VInt, on obtient:n";  
  v_ent.erase(v_ent.begin() + 3);  
  AfficherVector(v_ent);  

  cout << "On supprime 3 éléments dans VInt:n";  
  v_ent.erase(v_ent.begin() + 3, v_ent.begin() + 6);  
  AfficherVector(v_ent);  

  cout << "On insère plusieurs éléments à partir d’un autre vecteurn";  
  v_entiers  v_ent2(2, 0);  
  cout << "Voici le vecteur cible v_ent2:n";  
  AfficherVector(v_ent2);  

  cout << "v_ent2 après insertion depuis v_entn";  
  v_ent2.insert(v_ent2.begin() + 1, v_ent.begin() + 1, v_ent.begin() + 3);  
  AfficherVector(v_ent2);  

  cout << "On ajoute un élément à la fin de v_ent2";  
  cout << "avec push_back()n";  
  v_ent2.push_back(100);  
  AfficherVector(v_ent2);  

  cout << "On supprime un élément à partir de la fin";  
  cout << " de v_ent2 avec pop_back()n";  
  v_ent2.pop_back();  
  AfficherVector(v_ent2);  

  cout << "On supprime v_ent2n";  
  v_ent2.clear();  
  AfficherVector(v_ent2);  
}  

//Définition de AfficherVector  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v)  
{  
  cout << "Taille= " << v.size() << "tCapacité= " << v.capacity() << "n";  

  // On parcourt le vecteur via l’opérateur []  
  cout << "éléments:t";  
  for (typename vector<T, A>::size_type i = 0; i < v.size(); ++i)  
    cout << v[i] << ", ";  

  cout << "nn";  
}

Ce programme produit la sortie suivante :

On définit un vecteur d’entiers avec 5 éléments  
On affecte une valeur à chaque élément de v_ent via l’opérateur index []:  
Taille= 5  Capacité = 5  
éléments:  0, 5, 10, 15, 20,  

On insère un élément avec insert(v_ent.begin()+ 1, 50)  
Notre conteneur devient:  
Taille= 6  Capacité = 10  
éléments:  0, 50, 5, 10, 15, 20,  

Voici l’élément courant : 50  

On insère 5 éléments avec insert(v_ent.end(), 5, 30):  
Taille= 11  Capacité = 12  
éléments:  0, 50, 5, 10, 15, 20, 30, 30, 30, 30, 30,  

On supprime un élément dans VInt, on obtient:  
Taille= 10  Capacité = 12  
éléments:  0, 50, 5, 15, 20, 30, 30, 30, 30, 30,  

On supprime 3 éléments dans VInt:  
Taille= 7  Capacité = 12  
éléments:  0, 50, 5, 30, 30, 30, 30,  

On insère plusieurs éléments à partir d’un autre vecteur  
Voici le vecteur cible v_ent2:  
Taille= 2  Capacité = 2  
éléments:  0, 0,  

v_ent2 après insertion depuis v_ent  
Taille= 4  Capacité = 4  
éléments:  0, 50, 5, 0,  

On ajoute un élément à la fin de v_ent2 avec push_back()  
Taille= 5  Capacité = 8  
éléments:  0, 50, 5, 0, 100,  

On supprime un élément à partir de la fin de v_ent2 avec pop_back()  
Taille= 4  Capacité = 8  
éléments:  0, 50, 5, 0,  

On supprime v_ent2  
Taille= 0  Capacité = 8  
éléments: 

La bibliothèque standard fournit des opérateurs surchargés pour comparer les vector. Le code 8.5 présente diverses comparaisons de vecteurs.

Code 8.5 opérations sur des vector

#include <iostream>  
#include <vector>  
using namespace std;  

typedef vector<int>      v_entiers;  

//prototype de la fonction d’affichage  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v);  
//Prototype de la fonction de comparaison  
template<class T, class A>  
void ComparerVectors(const vector<T, A>& v1, const vector<T, A>& v2);  

int main()  
{  
cout << "On définit un vecteur d’entiers avec 5 élémentsn";  
  v_entiers  v_ent1(5);  

cout<<"On affecte une valeur à chaque élément via []n";  
  for (vector<int>::size_type i = 0; i < v_ent1.size(); ++i)  {  
    v_ent1[i] = i * i;  
  }  
  AfficherVector(v_ent1);  

cout << "On définit v_ent2 en recopiant les éléments ";  
cout << "de v_ent1 nVoici v_ent2:" << endl;  
  v_entiers v_ent2 = v_ent1;  
  AfficherVector(v_ent2);  

  cout << "On compare v_ent et v_ent2" << endl;  
  ComparerVectors(v_ent1, v_ent2);  

  cout << "On ajoute un élément à la fin de v_ent2n";  
  v_ent2.push_back(100);  
  AfficherVector(v_ent2);  

  cout << "On compare v_ent et v_ent2 de nouveau" << endl;  
  ComparerVectors(v_ent1, v_ent2);  

  cout << "On échange v_ent et v_ent2 avec swap()" << endl;  
  v_ent1.swap(v_ent2);  
  cout << "v_ent1 devient:n";  
  AfficherVector(v_ent1);  
  cout << "v_ent2:n";  
  AfficherVector(v_ent2);  
  cout << "Dernière comparaison:" << endl;  
  ComparerVectors(v_ent1, v_ent2);  
}  

//Définition de la fonction d’affichage  
template<class T, class A>  
void AfficherVector(const vector<T, A>& v)  
{  
  cout << "Taille= " << v.size() << "tCapacité = " << v.capacity() << "n";  

  // On affiche les éléments du vecteur  
  cout << "éléments:t";  
  for (typename vector<T,A>::size_type i = 0; i < v.size(); ++i)  
    cout << v[i] << ", ";  
  cout << "nn";  
}  

//Définition de la fonction de comparaison  
template<class T, class A>  
void ComparerVectors(const vector<T, A>& v1, const vector<T, A>& v2)  
{  
  if (v1 == v2)    {  
    cout << "v1 == v2";  
  }  
  else if (v1 < v2)  
  {  
    cout << "v1 < v2";  
  }  
  else  
  {  
    cout << "v1 > v2";  
  }  
  cout << "nn";  
}

Voici le résultat de l’exécution de ce programme :

On définit un vecteur d’entiers avec 5 éléments  
On affecte une valeur à chaque élément via []  
Taille= 5  Capacité = 5  
éléments:  0, 1, 4, 9, 16,  

On définit v_ent2 en recopiant les éléments de v_ent1  
Voici v_ent2:  
Taille= 5  Capacité = 5  
éléments:  0, 1, 4, 9, 16,  

On compare v_ent et v_ent2  
v1 == v2  

On ajoute un élément à la fin de v_ent2  
Taille= 6  Capacité = 10  
éléments:  0, 1, 4, 9, 16, 100,  

On compare v_ent et v_ent2 de nouveau  
v1 < v2  

On échange v_ent et v_ent2 avec swap()  
v_ent1 devient:  
Taille= 6  Capacité = 10  
éléments:  0, 1, 4, 9, 16, 100,  

v_ent2:  
Taille= 5  Capacité = 5  
éléments:  0, 1, 4, 9, 16,  

Dernière comparaison:  
v1 > v2

Comme pour AfficherVector(), la fonction de comparaison ComparerVectors() est définie comme modèle pour l’utiliser quel que soit le contenu du vector.
L’importante consommation de ressources inhérente aux opérations d’insertion et de suppression est le principal inconvénient d’un conteneur vector. Si vous envisagez d’effectuer fréquemment ce type d’opération, choisissez plutôt un conteneur list.

Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)