Vecteur (structure de données)

Exemple de manipulation d'un vecteur en C++[1] - [2]:

#include <vector>
#include <iostream>
int main()
{
   std::vector<int> v; // vector v manipulant des entiers(type int)
   v.push_back(1); // Empile l'entier 1
   v.push_back(2); // Empile l'entier 2
   v.pop_back(); // Dépile un élément
   v.insert(6, v.begin() + 1); // Insère 6 après le premier élément
   std::cout << v.capacity(); // Affiche 3, le nombre d'éléments
}

Le vecteur utilisé ici est l'objet vector (inclut avec la STL). Le vector est un modèle. On peut donc l'utiliser avec n'importe quel type. Par exemple, pour faire un vecteur de char, il faut écrire vector<char>.

L'allocation de mémoire d'un vecteur se fait généralement en doublant sa capacité lorsque sa taille (le nombre d’éléments) égale sa capacité (le nombre d'octets allouées). Pour voir évoluer sa capacité, le vector dispose des méthodes size() et capacity():

#include <vector>
#include <iostream>
int main()
{
   std::vector<int> v;
   for(int i = 0; i < 20; i++)
   {
      std::cout << "capacité = " << v.capacity() << " pour une taille de " << v.size() << '\n';
      v.push_back(1);
   }
}

Le graphique ci-dessous représentant la capacité en fonction de la taille permet de voir qu'avec le vector, la capacité augmente de 50% environ à chaque fois que la taille et la capacité sont égaux. Si ce nombre est trop faible, il y aura trop de ré-allocations. S'il est trop élevé, il prendra trop de mémoire. Dans les deux cas, cela pourra occasionner une perte des performances.

Le vecteur possède de nombreux avantages par rapport à un simple tableau, du fait de l'allocation mémoire dynamique principalement :

• Il n'est pas nécessaire de spécifier la taille du conteneur à sa création ;
• Dans la limite des ressources de la machine, il est possible d'ajouter autant d'éléments que souhaité au vecteur, sans modifier sa structure ;
• Inversement, lors du retrait d’éléments, il n'est pas nécessaire de rétrécir la taille du conteneur[3] ;
• Dans beaucoup d'implémentations, des instructions supplémentaires (pour trier ou rechercher un élément par exemple) permettent de gagner du temps.

Dans certains cas, les tableaux sont néanmoins plus simples à utiliser, en particulier lorsqu'il faut créer des matrices. En effet, il faut créer un vecteur de vecteurs. La conséquence est que l'on n'est pas assuré d'obtenir la même taille de colonnes. Pour y remédier, il faut créer des classes complexes manuellement. De plus, dans les langages ne disposant pas de pointeurs, le développeur devra se contenter des vecteurs proposés par défaut. Pour finir, la taille et la capacité d'un vecteur ne sont pas forcément égaux. De la mémoire peut donc être utilisée inutilement.

Le vecteur est surtout utilisé lorsque l'on ne connaît pas à l'avance le nombre de données qu'il va devoir contenir. Il est aussi utile pour ne pas redéfinir de tableau afin d'être réutilisé directement. Si l'on considère l'exemple du tri fusion, une fonction reçoit en argument deux tableaux de deux entiers chacun. Avec un tableau, la fonction devra créer un nouveau tableau, alors qu'avec deux vecteurs, il suffira juste de recopier les données du premier dans le second puis de supprimer le premier vecteur.

Une autre application est lorsque l'on veut copier facilement des données en les empilant. Avec un tableau classique, il faut utiliser un entier qui est incrémenté de 1 à chaque ajout. En C++ cela donne :

#include <vector>
int main()
{
//Empilement avec un tableau
int n = 0;
int tab[10];
tab[n++] = 2;
// Avec un vecteur
vector<int> vec;
vec.push_back(2);
}

Pour finir, le vecteur est généralement très polyvalent. Il est capable de servir de pile, de liste ou de file. Néanmoins, les conteneurs spécialisés sont plus optimisés pour ces tâches.

Un vecteur peut généralement recevoir les instructions suivantes :

• « insérer » pour insérer un élément avant l'endroit désigné ;
• « effacer » pour effacer un élément ;
• « empiler » permet d'ajouter un élément à la fin du vecteur ;
• « dépiler » permet de supprimer un élément à la fin du vecteur ;
• « taille » permet de connaître le nombre d'éléments du vecteur ;
• « lire » pour connaître la valeur de l'élément sélectionné ;
• « modifier » permet de régler la valeur de l'élément sélectionné ;
• « échanger » pour échanger deux éléments ;
• « max » pour connaître la valeur maximale du vecteur ;
• « min » pour connaître la valeur minimale du vecteur.

Ils peuvent aussi retourner des adresses ou des indices:

• « début » pour obtenir l'adresse du premier élément ;
• « fin » pour obtenir l'adresse de l'élément suivant le dernier (pour les boucles for) ;
• « recherche » pour obtenir l'adresse du premier élément correspondant.

De plus, certaines implémentations supportent d'autres fonctions pour trier le vecteur ou le formater par exemple. Il existe aussi des instructions conditionnelles qui permettent de raccourcir le code en enlevant une instruction if(l'instruction replace_if() avec le vector en C++, remplace un élément si un prédicat est vérifié).

Il est facile de créer son propre vecteur avec des pointeurs. Voici un exemple en C++ où le vecteur manipule des entiers. La classe vecteur non présentée ici en intégralité est constituée de deux champs : un pointeur p sur des entiers, qui pointe sur le début du bloc de mémoire qui a été alloué, et un entier n qui enregistre le nombre de données contenues dans le vecteur. Dans cet exemple, la mémoire est allouée de nouveau à chaque suppression ou ajout. Seules les méthodes de cette classe vont être exposées.

Il n'est pas obligatoire de créer une classe pour créer son propre vecteur. Il est par contre nécessaire d'avoir accès à des pointeurs ou des références. D'autres langages, comme le C ou le Pascal peuvent donc convenir.

Le constructeur qui est exécuté quand le vecteur sera créé initialise le pointeur sur une adresse, et met le nombre de données à 0. Le destructeur qui est exécuté quand le vecteur est détruit libère le bloc mémoire qui est alloué au vecteur pour éviter des fuites de mémoire. Le constructeur alloue seulement un octet de mémoire afin d'avoir un bloc mémoire de référence que le pointeur p peut adresser. Ce bloc pourra ensuite être agrandi avec la méthode « réallouer » pour contenir plus de nombres. Il faut également ajouter une ligne afin d'utiliser stdlib.h, qui donne accès à realloc(), malloc(), et free()(non présente ici).

vecteur(){ n = 0; p = malloc(1); }
~vecteur(){ free(p); }

La méthode « réallouer » se charge d'allouer le nombre d'octets nécessaires au vecteur pour contenir ses données avec la fonction realloc() qui agrandit ou réduit le bloc mémoire alloué. La taille d'un entier étant fixe, il est possible de déclarer une constante taille_int pour ne pas avoir à écrire sizeof(int).

void reallouer(){ p = (int *) realloc(p, sizeof(int) * n); }

void ajouter(int var)
{
n++;
reallouer();
*(p + n - 1) = var;
}
void supprimer(){ n--; reallouer(); }

int sec(int i){ return (i>=n) * (n-1) + ((i>-1)&&(i<n)) * i; }
int lire(int index){ return *(p + sec(index)); }
void modifier(int var, int index){ *(p + sec(index)) = var; }

int debut(){ return 0; }
int fin(){ return n; }
void afficher()
{
for(int i = debut(); i < fin(); i++)
std::cout << lire(i) << endl;
}
void afficher_taille(){ std::cout << fin() << endl; }

void echanger(int i1, int i2)
{
int c = lire(i1);
modifier(lire(i2), i1);
modifier(c, i2);
}

• Structure de données
• Liste
• Analyse amortie

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition] (chap. 17.4, « Tables dynamiques », p. 406-414).