Vecteur (structure de données)

En informatique, un tableau dynamique, ou table dynamique ou vecteur désigne un conteneur d'éléments ordonnés et accessibles par des indices, dont la taille est dynamique : elle est mise à jour automatiquement lors d'ajouts ou de suppressions d'éléments. On retrouve les vecteurs dans de nombreux langages de programmation, notamment le C++ et le Java. Ils sont alors inclus dans des bibliothèques et l'utilisateur n'a pas besoin de les implémenter.

En langage objet, la classe vecteur est généralement polymorphe, c'est-à-dire qu'il est possible de l'utiliser avec n'importe quel type d'objet.

Exemple

Exemple de manipulation d'un vecteur en C++:

#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.

Avantages et inconvénients

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 ;
• 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.

Utilisation

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.

Primitives

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é).

Exemple d'implémentation

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); }

Ajouter et supprimer

La méthode « ajouter » empile un entier de la façon suivante : il suffit d'augmenter le nombre de données, ce qui va agrandir le vecteur. Il suffit ensuite d'écrire à ce nouvel emplacement. Une autre méthode similaire peut dépiler un entier, en réduisant le nombre d'octets qui seront réalloués, ce qui permet de libérer (détruire) le dernier élément du vecteur.

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

void supprimer(){ n--; reallouer(); }

Lire et modifier

Pour lire et modifier une valeur à partir d'un index, il suffit d'utiliser la syntaxe classique des pointeurs. Dans cet exemple l'index doit être compris entre 0 et le nombre de données moins un (comme dans un tableau classique en C++). Pour éviter les erreurs de dépassement, une fonction sec(int index) vérifie que l'index est de bonne taille.

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; }

Positionnement

Il est possible de créer les méthodes début() et fin() qui retournent l'index du premier et de l'élément suivant le dernier afin de créer des boucles for facilement pour afficher le vecteur. La fonction fin() peut être utilisée pour connaître la taille du vecteur. En général les termes begin et end sont plus utilisés. Il existe des variantes pour obtenir le dernier élément afin de créer des boucles dans le sens inverse.

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; }

Échanger deux éléments

Cette méthode est simple à mettre en œuvre; elle est souvent appelée swap en anglais. Pour ne pas perdre de donnés, une variable tampon (appelée c dans ce cas) est nécessaire.

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

Voir aussi

• Structure de données
• Liste
• Analyse amortie

Bibliographie

• 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).