Remédiation en C++
—
C++: Gérer les tableaux avec la classe vector

De très nombreux algorithmes nécessitent de traiter des séries de données, plutôt que de simples variables isolées. C’est d’autant plus vrai en ingénierie mathématique où une très grande majorité des problèmes sont posés sous forme linéarisée, sous forme de matrices et de vecteurs.

Il est donc indispensable d’avoir une façon de gérer les tableaux dans un langage de programmation. Le C gérait les tableaux d’une façon très efficace mais très peu pratique. Le C++ les gère un peu mieux, mais ce n’est franchement pas l’idéal. Il existe des bibliothèques C++ qui s’en occupent bien mieux.

Pour autant, quand on n’a besoin que de tableaux 1D (“vecteurs”), la manière C++ convient tout à fait, et on peut déjà faire un peu de tableaux 2D (“matrices”).

La classe std::vector

En C++, les tableaux à une dimension – c’est-à-dire un seul indice pour désigner la position dans le tableau – peuvent être représentés par des variables de type std::vector. Pour être rigoureux, je devrais dire des «instances de la classe std::vector», mais ça c’est vu plus tard en cours.

Les std::vector ne sont pas inclus d’office, il faut les importer depuis la bibliothèque qui s’appelle … vector.

#include <vector>

Cette bibliothèque fait partie de la STL, la Standard Template Library. La STL est une collection de bibliothèque dans laquelle on retrouve plein de manières de stocker les données : les tableaux de taille variable (std::vector), les tableaux de taille fixe (std::array), les tables de hachages (std::map), etc. Ces containers permettent de stocker n’importe quel type de données.

Ces bibliothèques étant bien faites, elles incluent tout un tas de fonctions usuelles pour manipuler ces containers. On va en voir certaines pour les std::vector.

Les tableaux dynamiques

Les std::vector sont utilisés pour représenter les tableaux 1D dont on ne connait pas la taille au moment de l’écriture du code, et/ou qui peuvent aussi changer de taille au cours de l’exécution du programme.

Par exemple, on peut demander à l’utilisateur ou lire dans un fichier une liste de noms. Le programme stocke les noms dans un std::vector, et le tableau verra sa taille augmenter au fur et à mesure des saisies de l’utilisateur, ou de la lecture du fichier.

Le fait de pouvoir changer la taille du tableau au moment de l’exécution fait qu’on parle de tableaux dynamiques, en opposition aux tableaux statiques qui auront toujours la même à chaque exécution, et ne pouvant pas changer de taille.

La classe std::vector se charge de gérer pour vous la zone de mémoire où sont stockées les données. Pour autant, il faut savoir qu’un tableau qui change trop souvent de taille amène souvent à de mauvaises performances.

Déclarer les std::vector

Pour déclarer un std::vector, il faut obligatoirement préciser le type de données qui sera stocké. Tous les éléments du vecteur doivent avoir le même type et ce type ne peut pas changer pendant l’existence du vecteur.

Voici trois exemples de déclaration de vecteur:

#include<vector>
// ...

std::vector<int>         v1; // v1 est un vecteur d'entiers
std::vector<float>       v2; // v2 est un vecteur de réels simple précision
std::vector<std::string> v3; // v3 est un vecteur de chaines de caractères

Initialiser les std::vector

En même temps que la déclaration, on peut déterminer la taille du vecteur, et aussi donner la même valeur initiale à tous les éléments du tableau.

#include<vector>

std::vector<int>         v4(20);         // v4 est un tableau de 20 entiers, non intialisés
std::vector<std::string> v5(10,"untel"); // v5 est un tableau de 10 chaines de caractères
                                         // qui valent toutes "untel"

Pour initialiser des petits tableaux, on peut donner directement des valeurs qui sont mises entre accolades:

#include<vector>

std::vector<double> v6 = {1., -2., 5.4, 1.e10}; // v6 est un tableau de 4 réels initialisés

Accéder à un élément d’un std::vector

Pour lire et écrire dans un std::vector, on peut utiliser l’opérateur [].

En C++, les indices commencent à 0. Un tableau de taille N a des indices allant de 0 à N-1.

std::vector<unsigned int> v7(20,0u); // v7 est un tableau de 20 entiers non signés (positifs), initialisés à 0

// acces en lecture
std::cout << v7[0] << " " << v7[1] <<std::endl;
unsigned int k = v7[2];
// acces en ecriture
v7[10] = 5u;
v7[6]  = 10u;

unsigned int k2 = v7.at(2);
v7.at(10) = 2u;
v7.at(-1) = 0u; // Le programme plantera quand meme, mais il y aura un message qui donnera la cause

Des méthodes utiles (1)

size()

La méthode size() retourne la taille d’un vecteur. Cette méthode est notamment très utile dans les boucles qui parcourent un tableau jusqu’à la fin:

std::vector<int> tab = {5,6,7,8,1,2,3,4}; 
for (unsigned int i = 0u; i < tab.size(); i++)
  std::cout << tab[i] << " ";
std::cout << std::endl;

// Ce code affiche toutes les valeurs du tableau:
// 5 6 7 8 1 2 3 4
// A chaque passage dans la boucle, i augmente de 1 (entre 0 et tab.size() qui vaut 7)
// tab[i] fait alors reférence aux elements du tableau, les uns apres les autres

using uint = unsigned int;

Des méthodes utiles (2)

resize()

resize(taille) ou resize(taille,valeur) permet de changer la taille d’un vecteur

• Si taille est plus grand que la taille actuelle du vecteur, le vecteur sera agrandi, et si précisé, les nouveaux éléments vaudront valeur.
• Si taille est plus petit, ce sont les éléments à la fin du vecteur qui seront supprimés.
• Les éléments au début du vecteur sont conservés.

std::vector<std::string> noms = {"Alice","Bob","Gertrude"};
noms.resize(5,"Toto"); // Le vecteur contient maintenant "Alice""Bob""Gertrude""Toto""Toto"
noms.resize(2);        // Le vecteur contient maintenant "Alice""Bob"

Des méthodes utiles (3)

empty()

empty() retourne un booléen qui dit si le tableau est vide (true) ou contient des éléments (false).

std::vector<int> v;
std::cout << v.empty() << std::endl; // Affiche 1, car le vecteur n'a pas ete initialise avec une taille
v = {1,2,3};
std::cout << v.empty() << std::endl; // Affiche 0, car v.size() != 0 

Opérateur ==

On peut comparer des vecteurs deux à deux. L’égalité entre deux vecteurs est vraie si ils ont la même taille, et que chaque élément de l’un est égal à l’élément correspondant dans l’autre.

On ne peut malheureusement pas directement utiliser les opérateurs habituels +, -, *, %, etc pour faire des opérations sur les vecteurs. On verra plus tard dans le cours sur les fonctions comment résoudre ce problème.

Des méthodes utiles (4)

push_back, pop_back

push_back(valeur) permet de placer une valeur supplémentaire à la fin du tableau. La taille du tableau augmente de 1. pop_back() permet de supprimer la dernière valeur du tableau. La taille du tableau diminue de 1.

front, back

On peut accéder aux premières et dernières valeurs du tableau avec front() et back(), respectivement.

std::vector<int> v = {12,-56,7,24};
v.push_back(13);            // v vaut maintenant {12,-56,7,24,13}
v.pop_back(); v.pop_back(); // v vaut maintenant {12,-56,7}
int a = v.front();          // a vaut 12
int b = v.back();           // b vaut 7

Exemple de programme utilisant un vecteur.

Passons à un cas pratique.

On va classer une liste de noms entrés par l’utilisateur dans l’ordre alphabétique, et afficher le resultat à l’écran une fois la liste terminée.

Commençons par nous occuper de la saisie des noms. On dira que l’utilisateur aura fini de rentrer les noms quand il entrera “0”.

#include<iostream> // pour std::cout, std::cin, std::endl

int main() { // obligatoire

  std::cout << "Entrez une suite de noms. Entrez 0 pour finir la saisie." << std::endl;
  
  return 0;  
}

Exemple de programme utilisant un vecteur.

Au moins un nom doit être lu, et ensuite, on continue la saisie tant que ce nom est différent de “0”. Cette phrase précédente est quasiment la traduction de ce qu’on doit écrire : un while.

#include<iostream>

int main() {

  std::string nom;
  std::cout << "Entrez une suite de noms. Entrez 0 pour finir la saisie." << std::endl;
  std::cin >> nom;
  
  while(nom != "0") {
    std::cin >> nom;
  }
  
  return 0;  
}

Exemple de programme utilisant un vecteur.

Au fur et à mesure, les noms doivent être placés dans un vecteur. On initialise donc un vecteur vide, dont le type de données stockées est chaîne de caractères.

N’oubliez pas d’inclure la bibliothèque vector, sinon le compilateur ne saura pas ce que c’est !

#include<iostream>
#include<vector>

int main() {

  std::cout << "Entrez une suite de noms. Entrez 0 pour finir la saisie." << std::endl;
  
  std::string nom;
  std::cin >> nom;
  std::vector<std::string> noms;
  while(nom != "0") {
    // On lit nom suivant
    std::cin >> nom;
  }
  
  return 0;  
}

Exemple de programme utilisant un vecteur.

Maintenant réfléchissons un peu. On pourrait stocker les noms dans le tableau dans l’ordre où ils ont été saisis, et ensuite trier le tableau.

Mais autant faire un petit exercice d’algorithmique au passage. On va trier le tableau au fur et à mesure de son remplissage.

Supposons que trois noms ont été déjà rentrés et triés:

On veut ajouter un nom, donc avoir un tableau plus grand d’une case, pour l’instant avec une case vide à la fin.

Ce qu’on va faire, c’est qu’on va décaler tous les éléments du tableau jusqu’à libérer la bonne case où placer le nom. Supposons que le nom rentré est “Andrew”. “June” est après “Andrew” dans l’ordre alphabétique, donc on le décale. “Bob” est après “Andrew”, on le décale. “Alice” est avant “Andrew”, on laisse donc “Alice” à sa place, et il n’y a plus qu’à placer “Andrew” là où était “Bob”.

Exemple de programme utilisant un vecteur.

Implémentons cela.

À chaque passage dans la boucle while, on ajoute un élément au tableau. On peut le faire avec un resize(noms.size()+1), ou avec un push_back(nom). L’avantage du push_back est que si jamais le nom doit être classé après le dernier élément, au moins le travail sera déjà fait !

#include<iostream>
#include<vector>

int main() {

  std::cout << "Entrez une suite de noms. Entrez 0 pour finir la saisie." << std::endl;
  
  std::string nom;
  std::cin >> nom;
  std::vector<std::string> noms;
  while(nom != "0") {
    // On ajoute le dernier nom saisi à la fin du tableau
    noms.push_back(nom);
    // On lit le nom suivant
    std::cin >> nom;
  }
  
  return 0;  
}

Exemple de programme utilisant un vecteur.

Pour effectuer le décalage des noms, on peut utiliser soit un for soit un while. Si je suis le conseil que j’ai donné dans le tuto sur les boucles, il vaut mieux utiliser un while car on ne connait pas le nombre de décalage.

Pour classer les chaines de caratères par ordre alphabétique, c’est très simple. Il suffit d’utiliser les opérateurs de comparaison < > <= >= qui utilisent l’ordre alphabétique pour dire si une chaine est «plus grande» qu’une autre.

(Faites défiler pour voir tout le code)

#include<iostream>
#include<vector>

int main() {

  std::cout << "Entrez une suite de noms. Entrez 0 pour finir la saisie." << std::endl;
  
  std::string nom;
  std::cin >> nom;
  std::vector<std::string> noms;
  while(nom != "0") {
    // On ajoute le dernier nom saisi a la fin du tableau
    noms.push_back(nom);
    // On decale les noms jusqu'a un nom qui precede:
    
    // L'indice nous dira ou placer le nom.
    // On l'initialise avec le dernier indice du tableau: taille-1
    int index = noms.size()-1;
    
    while (noms[index-1] > nom) // tant que le nom situe avant dans le tableau
                                // est apres dans l'ordre alphabetique
    {
      noms[index] = noms[index-1]; // On ecrase les valeurs suivantes
      index--;                     // N'oubliez pas de faire évoluer index !
    }
    // On lit le nom suivant
    std::cin >> nom;
    
  }
  
  return 0;  
}

Exemple de programme utilisant un vecteur.

À la sortie du while, index désigne la case où placer le nom. Si vous ne comprenez pas pourquoi, faites l’exercice sur une feuille à côté. Faites des cases qui contiennent les valeurs des différentes variables, et faites tourner “à la main” l’algorithme, instruction après instruction, en mettant à jour les variables.

(Faites défiler pour voir tout le code)

#include<iostream>
#include<vector>

int main() {

  std::cout << "Entrez une suite de noms. Entrez 0 pour finir la saisie." << std::endl;
  
  std::string nom;
  std::cin >> nom;
  std::vector<std::string> noms;
  while(nom != "0") {
    // On ajoute le dernier nom saisi a la fin du tableau
    noms.push_back(nom);
    // On decale les noms jusqu'a un nom qui precede:
    
    // L'indice nous dira ou placer le nom.
    // On l'initialise avec le dernier indice du tableau: taille-1
    int index = noms.size()-1;
    
    while (noms[index-1] > nom) // tant que le nom situe avant dans le tableau
                                // est apres dans l'ordre alphabetique
    {
      noms[index] = noms[index-1]; // On ecrase les valeurs suivantes
      index--;                     // N'oubliez pas de faire évoluer index !
    }
    // On place le nom au bon endroit
    noms[index] = nom;
    // On lit le nom suivant 
    std::cin >> nom;
  }
  
  return 0;  
}

Exemple de programme utilisant un vecteur.

Finissons le programme en affichant la liste des noms: (Faites défiler pour voir tout le code)

#include<iostream>
#include<vector>

int main() {

  std::cout << "Entrez une suite de noms. Entrez 0 pour finir la saisie." << std::endl;
  
  std::string nom;
  std::vector<std::string> noms;
  while(nom != "0") {
    // On ajoute le dernier nom saisi a la fin du tableau
    noms.push_back(nom);
    // On decale les noms jusqu'a un nom qui precede:
    
    // L'indice nous dira ou placer le nom.
    // On l'initialise avec le dernier indice du tableau: taille-1
    int index = noms.size()-1;
    
    while (noms[index-1] > nom) // tant que le nom situe avant dans le tableau
                                // est apres dans l'ordre alphabetique
    {
      noms[index] = noms[index-1]; // On ecrase les valeurs suivantes
      index--;                     // N'oubliez pas de faire évoluer index !
    }
    // On place le nom au bon endroit
    noms[index] = nom;
    
    // On lit le nom suivant 
    std::cin >> nom;
  }
  
  // Affichage des resultats
  std::cout << std::endl;
  for(unsigned int i=0; i<noms.size(); i++)
    std::cout << noms[i] << std::endl;
  
  return 0;  
}

Exemple de programme utilisant un vecteur.

Testons le programme:

QCM

std::vector<int> vec(10,2);

QCM

std::vector<int> vec(10,2);

QCM

std::vector<int> vec = {1,2,3,4,5,6};
int prod = 1;
for (unsigned int i=0; i<vec.size(); i++) {
  prod *= vec[i];
  std::cout << prod << " ";
}
std::cout << std::endl;

QCM

std::vector<int> vec = {1,2,3,4,5,6};
int prod = 1;
for (unsigned int i=0; i<vec.size(); i++) {
  prod *= vec[i];
  std::cout << prod << " ";
}
std::cout << std::endl;