Ce petit document se veut une introduction simplifiée au conteneur standard le plus commun et le plus simple: le vecteur standard (classe std::vector, rendue visible par le fichier d'en-tête <vector>).
Pour accompagner cette introduction sur les vecteurs standard, vous trouverez aussi ici une brève introduction aux itérateurs et aux algorithmes standard. Encore une fois, il y a lieu de creuser plus loin que ce petit document pour bien comprendre l'impact et le potentiel de ces puissants outils.
Imaginons un programme très simple ayant pour rôle de lire des entiers puis de les afficher à la console (note : pour que l'exemple demeure simple, nous ferons abstraction des possibles erreurs de lecture au clavier). Dans la mesure où le nombre d'entiers à lire est connu au préalable, ce problème se résout bien à l'aide d'un tableau :
#include <iostream>
int main() {
using namespace std;
const int N = 10;
int tab[N];
for (int i = 0; i < N; i++)
cin >> tab[i];
for (auto n : tab)
cout << n << ' ';
}Si le nombre d'éléments à lire n'est pas connu au préalable, alors la situation se complique: on peut allouer un tableau aussi gros que possible (ce qui signifie probablement gaspiller des ressources) ou mettre en place une mécanique prenant manuellement en charge la croissance du tableau au besoin. Ce genre de code (un tableau dynamique) est instructif à rédiger mais, on s'en doute, il s'agit de code suffisamment utile pour être intégré aux bibliothèques standard: la classe std::vector est, à toutes fins pratiques, un tel tableau dynamique.
On peut reprendre le programme ci-dessus tel quel avec un vecteur :
#include <iostream>
#include <vector>
int main() {
using namespace std;
const int N = 10;
// constructeur paramétrique (N est le nombre d'éléments à initialiser par défaut)
vector<int> v(N);
for (int i = 0; i < N; i++)
cin >> v[i];
for (auto n : v)
cout << n << ' ';
}Il est aussi possible de rédiger le même programme sans réserver d'espace a priori, en laissant le vecteur croître au besoin. Puisque le vecteur croît au besoin, on peut y insérer une quantité arbitrairement grande de données :
#include <iostream>
#include <vector>
int main() {
using namespace std;
vector<int> v;
// lit jusqu'à ce qu'une erreur se produise (pour la simuler, entrer CTRL+D ou CTRL+Z)
for (int n; cin >> n; )
v.push_back(n); // insère à la fin; croît au besoin
for (vector<int>::size_type i = 0; i < v.size(); ++i)
cout << v[i] << ' ';
// ...ou encore...
for (auto n : v)
cout << n << ' ';
}Un vecteur standard, conmme tous les conteneurs standard, peut être parcouru du début à la fin de la séquence d'éléments qui s'y logent. Une séquence dans un conteneur est définie par une paire d'itérateurs – un itérateur est une abstraction du concept de séquence.
Pour comprendre ce qu'est un itérateur, reprenons l'exemple du tableau un peu plus haut. Nous avions :
#include <iostream>
int main() {
using namespace std;
const int N = 10;
int tab[N];
for (int i = 0; i < N; i++)
cin >> tab[i];
for (int i = 0; i < N; i++)
cout << tab[i] << ' ';
}Sachant qu'un tableau n'est qu'un pointeur sur son premier élément, et sachant que le i-ème élément d'un tableau tab peut s'écrire de manière équivalente sous la forme tab[i] ou sous la forme *(tab+i), il est clair (en y pensant bien) qu'on pourrait écrire le même algorithme sous la forme suivante :
#include <iostream>
int main() {
using namespace std;
const int N = 10;
int tab[N];
for (int *p = tab + 0; p != tab + N; ++p)
cin >> *p;
for (int *p = tab + 0; p != tab + N; ++p)
cout << *p << ' ';
}Le « + 0 » dans tab + 0 tient au fait que tab est un pointeur const sur un pointé non-const alors que tab + i est un pointeur non-const sur un pointeur non-const : ainsi, tab et tab + 0 ne sont pas du même type, ce qui posera problème sur les compilateurs les plus stricts lors de la comparaison avec tab + N.
Quelques trucs à remarquer :
Dans un vecteur standard, comme dans tous les conteneurs standard, le début de la séquence est un itérateur retourné par la méthode begin() et la fin de la séquence est un itérateur retourné par la méthode end() :
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
using namespace std;
vector<int> v;
for (int n; cin >> n; )
v.push_back(n);
for (auto it = begin(v); it != end(v); ++it)
cout << *it << ' ';
}Remarquez le type de l'itérateur : c'est un itérateur dans un vecteur de int. On pourrait utiliser un vecteur de std::string pour du code semblable avec très peu de changements:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main() {
using namespace std;
vector<string> v;
for (string s; cin >> s; )
v.push_back(s);
for (auto it = begin(v); it != end(v); ++it)
cout << *it << ' ';
}De même, parce que le code des conteneurs est très homogène, on pourrait remplacer un vecteur par une liste :
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
int main() {
using namespace std;
list<string> v;
for (string s; cin >> s; )
v.push_back(s);
for (auto it = begin(v); it != end(v); ++it)
cout << *it << ' ';
}Depuis C++ 11, les répétitives for sur des intervalles permettent de parcourir toute séquence déterminée par un intervalle à demi ouvert (début inclus, fin exclue) sur le même mode. Ainsi, on peut simplement écrire :
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
int main() {
using namespace std;
list<int> lst = { 2,3,5,7,11 };
vector<string> v = { "J'aime ", "mon ", "prof" };
float tab[] = { -1.5f, 0.0f, 1.5f };
for (auto & i : lst)
cout << i << ' ';
cout << endl;
for (auto & s : v)
cout << s << ' ';
cout << endl;
for (auto & f : tab)
cout << f << ' ';
cout << endl;
}Tel qu'indiqué précédemment, la fin d'une séquence est le premier élément juste après le dernier élément valide de la séquence, ce qui signifie qu'il s'agit d'une bonne valeur de test pour plusieurs opérations. Par exemple, si nous désirons savoir si la chaîne "Patate" est dans un conteneur, nous pourrions procéder ainsi :
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main() {
using namespace std;
vector<string> v;
for (string s; cin >> s; )
v.push_back(s);
const string MOT_RECHERCHE = "Patate";
vector<string> resultat = end(v);
for (auto it = begin(v); it != end(v); ++it)
if (*it == MOT_RECHERCHE) {
resultat = it;
break;
}
if (it != end(v))
cout << "Le mot " << MOT_RECHERCHE << " est dans la séquence" << endl;
}Évidemment, il existe des algorithmes standard qui couvrent plusieurs cas comme celui de la recherche dans une séquence. Dans le cas qui nous intéresse, il existe un algorithme std::find() dans la bibliothèque <algorithm> :
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main() {
using namespace std;
vector<string> v;
for (string s; cin >> s; )
v.push_back(s);
const string MOT_RECHERCHE = "Patate";
if (find(begin(v), end(v), MOT_RECHERCHE) != end(v))
cout << "Le mot " << MOT_RECHERCHE << " est dans la séquence" << endl;
}Un itérateur permet aussi un certain nombre d'opérations, comme la suppression de l'élément auquel il réfère :
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main() {
using namespace std;
vector<string> v;
for (string s; cin >> s; )
v.push_back(s);
const string MOT_RECHERCHE = "Patate";
if (auto it = find(begin(v), end(v), MOT_RECHERCHE); it != end(v)) {
cout << "Le mot " << MOT_RECHERCHE << " est dans la séquence" << endl;
v.erase(it); // bye bye Patate!
}
}On peut tester un conteneur pour savoir s'il est vide (méthode empty()), accéder directement à son premier élément (méthode front()) ou à son dernier élément (méthode back()), le vider (méthode clear()) et ainsi de suite.
Comment fonctionne std::vector à l'interne, une série de textes par Sergei Danielian en 2015 :
