Utiliser un vecteur standard

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

Programme avec tableau
#include <iostream>
int main() {
   using namespace std;
   const int MAX = 10;
   int tab[MAX];
   for (int i = 0; i < MAX; i++)
      cin >> tab[i];
   for (int i = 0; i < MAX; i++)
      cout << tab[i] << ' ';
}

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 :

Programme avec vecteur simulant un tableau
#include <iostream>
#include <vector>
int main() {
   using namespace std;
   const int MAX = 10;
   // constructeur paramétrique (MAX est la taille à réserver)
   vector<int> v(MAX);
   for (int i = 0; i < MAX; i++)
      cin >> v[i];
   for (int i = 0; i < MAX; i++)
      cout << v[i] << ' ';
}

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 :

Programme avec vecteur croissant (v.00)
#include <iostream>
#include <vector>
int main() {
   using namespace std;
   const int MAX = 10;
   // constructeur par défaut (vecteur vide)
   vector<int> v;
   for (int i = 0; i < MAX; i++) {
      int n;
      cin >> n;
      v.push_back(n); // insère à la fin; croît au besoin
   }
   // v.size() retourne le nombre d'éléments de v (de type
   // vector<int>::size_type qui peut ne pas être int)
   for (vector<int>::size_type i = 0; i < v.size(); i++)
      cout << v[i] << ' ';
}

Puisque le vecteur croît au besoin, on peut y insérer une quantité arbitrairement grande de données :

Programme avec vecteur croissant (v.01)
#include <iostream>
#include <vector>
int main() {
   using namespace std;
   const int MAX = 10;
   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] << ' ';
}

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 :

Programme avec tableau (rappel)
#include <iostream>
int main() {
   using namespace std;
   const int MAX = 10;
   int tab[MAX];
   for (int i = 0; i < MAX; i++)
      cin >> tab[i];
   for (int i = 0; i < MAX; 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 :

Programme avec tableau (avec itérateur)
#include <iostream>
int main() {
   using namespace std;
   const int MAX = 10;
   int tab[MAX];
   for (int *p = tab + 0; p != tab + MAX; ++p)
      cin >> *p;
   for (int *p = tab + 0; p != tab + MAX; ++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+MAX.

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() :

Programme avec vecteur (avec itérateur), v.00
#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:

Programme avec vecteur (avec itérateur), v.01
#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 :

Programme avec liste (avec itérateur)
#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 :

Programme avec liste (avec itérateur)
#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 :

Recherche (manuelle) dans un conteneur
#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 = tt;
   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> :

Recherche (standard) dans un conteneur
#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 :

Suppression d'un élément dans une séquence
#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";
   auo it = find(begin(v), end(v), MOT_RECHERCHE);
   if (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.

Lectures complémentaires

Comment fonctionne std::vector à l'interne, une série de textes par Sergei Danielian en 2015 :


Valid XHTML 1.0 Transitional

CSS Valide !