Liste dynamique
Nous allons présenter l’utilisation des listes dynamiques (vector). Plusieurs syntaxes existent, nous nous concentrons cependant sur les syntaxes les plus intuitives.
Création
La STL fournit la classe vector pour gérer les listes de taille dynamique. Elle offre deux avantages majeurs :
Cette classe est une classe template, elle peut donc se spécialiser pour tout type d’éléments. On peut ainsi construire une liste d’entiers comme une liste de string.
Contrairement aux tableaux, nous n’avons plus à nous préocupper de la taille maximale. En effet, la taille d’objet vector grandit au fur et à mesure que l’on insère des éléments.
Pour instancier un objet vector, vous devez :
Mettre une directive #include <vector>
En l’absence de : using namespace std, vous devez écrire std::vector
Préciser le type d’éléments stockés en écrivant vector<int> par exemple.
Voici différentes syntaxes avec ou sans initialisation :
vector<int> L;
vector<int> L( );
vector<int> L( {1,2,3,4} );
vector<int> L = {1,2,3,4};
Note
Une fois l’objet créé, vous ne devez plus écrire <int> pour appeler ses méthodes.
Avertissement
Tous les éléments dans une liste de type vector sont de même type. Ainsi, si vous stockez un double dans une liste de type vector<int>, alors il sera implicitement converti en entier.
Boucle foreach
Syntaxe du parcours des éléments d’un vector : for ( type nom_variable : obj_vector )
Voici un exemple :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {1,2,3,4};
for ( int v : L ) cout << v << endl;
}
>> 1
>> 2
>> 3
>> 4
Avertissement
Un vector ne peut gérer le retrait ou l’ajout d’élément durant une boucle foreach.
Avertissement
Dans la syntaxe : for ( int v : L ), la variable v correspond itérativement à une copie de chaque élément de la liste. Ainsi, dans ce contexte, modifiez la variable v ne modifie pas la valeur associée dans la liste.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {1,2,3,4};
for ( int v : L ) v = 1;
for ( int v : L ) cout << v << endl;
}
>> 1
>> 2
>> 3
>> 4
Si vous voulez modifier les valeurs contenues dans la liste, utilisez une référence sur les éléments de la liste :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {1,2,3,4};
for ( int & v : L ) v = 1; // <<< référence de l'élément courant dans la liste
for ( int v : L ) cout << v << endl;
}
>> 1
>> 1
>> 1
>> 1
Gestion de la taille
Plusieurs fonctions sont disponibles pour gérer la taille d’une liste :
size() : indique le nombre d’éléments stockés dans la liste
empty() : indique si la liste est vide
clear() : vide la liste
resize(n) : fixe la taille de la liste à n éléments.
Note
la fonction resize(n), lorsque n est inférieur au nombre d’éléments dans la liste actuelle, réduit la taille de la liste.
Avertissement
la fonction resize(n) lorsque n est plus grand que la taille actuelle de la liste a pour objectif d’étendre la liste. Pour cela, de nouveaux éléments sont créés pour remplir les nouveaux emplacements. Ainsi, le constructeur par défaut sera appelé pour les instancier (à partir du C++11). S’il s’agit d’un vecteur de valeurs numériques, alors les valeurs instanciées automatiquement sont par défaut initialisés à la valeur 0 !!!
Voici un exemple :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {1,2};
cout << "size : " << L.size() << endl;
L.resize(4);
cout << "size : " << L.size() << endl;
for(int v : L ) cout << v << endl;
cout << " Empty ? " << L.empty() << endl;
L.clear();
cout << "size : " << L.size() << endl;
cout << " Empty ? " << L.empty() << endl;
}
>> size : 2
>> size : 4
>> 1 2 0 0
>> Empty ? 0
>> size : 0
>> Empty ? 1
Lecture / Ecriture
La classe vector redéfinit l’opérateur [] pour accéder aux éléments de la liste. Vous pouvez donc utiliser cet objet comme un tableau :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {10,11,12};
for (int i = 0 ; i < L.size() ; i++) cout << L[i] << endl;
for (int i = 0 ; i < L.size() ; i++) L[i] = i;
for (int i = 0 ; i < L.size() ; i++) cout << L[i] << endl;
}
>> 10 11 12
>> 0 1 2
Insertion / Suppression
Plusieurs fonctions sont fournies pour insérer/supprimer/récupérer des éléments dans la liste :
push_back(v) : insère l’élément v en fin de liste.
pop_back() : retire le dernier élément de la liste.
back() : retourne le dernier élément sans le retirer.
Voici un exemple :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {2,3,4};
cout << "Last element : " << L.back() << " Size : " << L.size() << endl;
L.pop_back();
cout << "Last element : " << L.back() << " Size : " << L.size() << endl;
L.push_back(6);
for (int i = 0 ; i < L.size() ; i++) cout << L[i] << endl;
}
>> Last element : 4 Size : 3
>> Last element : 3 Size : 2
>> 2 3 6
Note
Les vector sont construits comme des tableaux en mémoire. Ainsi, ajouter ou retirer un élément en fin de tableau est une opération rapide et efficace. Les insertions ou retrait en fin sont ainsi à privilégier.
Manipulations avancées
La STL a voulu généraliser de la notion d’indice d’un tableau à l’ensemble de ses structures de données. Ainsi sont nés les itérateurs. Dans cette logique, il ne faudrait plus écrire :
for (int i = 0 ; i < L.size() ; i++) cout << L[i] << endl;
Mais, cette version plus moderne :
for (vector<int>::iterator it = L.begin() ; it != L.end() ; it++) cout << *it << endl;
Quelques conseils pour comprendre cette syntaxe :
L.begin() est une méthode retournant un objet itérateur désignant le premier élément.
L.end() est une méthode retournant un objet itérateur désignant la fin de la liste, une sorte d’élément fictif positionné après le dernier élément.
On n’utilise plus le signe < mais l’opérateur != pour vérifier que nous n’avons pas atteint la fin de la liste.
L’opérateur ++ ne s’applique pas à un entier, mais sur l’itérateur nommé it. L’opérateur ++ a donc été surchargé pour passer à l’élément suivant.
L’opérateur * a été surchargé pour accéder au contenu désigné par l’itérateur it. Même si cette syntaxe ressemble à celle des pointeurs, l’itérateur ne correspond pas forcément à un pointeur.
Afin d’alléger cette syntaxe assez lourde, certains développeurs utilisent le mot clef auto qui détermine automatiquement le type d’une variable :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {2,3,4};
for (auto it = L.begin() ; it != L.end() ; it++)
cout << *it << endl;
}
Vous pouvez évidemment continuer à utiliser la syntaxe vue précédemment à base de boucles for. Nous allons cependant conserver les deux fonctions begin() et end() car elles sont nécessaires pour les opérations de manipulation suivantes :
erase(it) : supprime l’élément désigné par l’itérateur it.
insert(it,v) : insére l’élément v à la position désignée par l’itérateur it.
Mais pourquoi ne pas utiliser un indice entier pour ces opérations ? Rassurez vous, heureusement pour vous, les itérateurs supportent l’opérateur d’addition. Ainsi la syntaxe L.begin()+4 designe le 5-ième élément de la liste L. Voici un exemple :
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> L = {2,3,4};
for (int v : L) cout << v << endl;
L.erase(L.begin()+1);
for (int v : L) cout << v << endl;
L.insert(L.begin()+1,8);
for (int v : L) cout << v << endl;
}
>> 2 3 4
>> 2 4 // L.erase(L.begin()+1);
>> 2 8 4 // L.insert(L.begin()+1,8);