Logo de SAASF

I - 5. Algorithmes et structures de données en C++

Si vous regardez des "Memes" de programmation de temps à autre, vous pourriez en voir un passer : "Learning programmation / Learning data structures and algorithms". En effet, cette section est souvent désignée par les développeurs comme une des parties les plus ennuyantes de leur apprentissage du développement.
Contenu

A. Les structures de données en C++

Il est difficile de stocker des données... sans moyen de stocker des données ¯\_(ツ)_/¯. Pour cela, que ce soit dans n'importe quel langage de programmation, il existe un moyen de faire ça facilement : les structures de données.

a. Qu'est ce qu'une structure de données ?

Une structure de données est une liste de normes, permettant de correctement structurer et stocker des données. Ces normes régissent en général la façon d'accéder (ou de ne pas accéder) aux données stockées, la façon permettant d'en rajouter, l'optimisation bas-niveau du code...

Il existe pas mal de structures célèbres, comme, en vrac :

  • Le tableau dynamique, très modulable mais assez lent
  • Le tableau statique, très rapide mais peu modulable
  • Le dictionnaire, très pratique mais assez lent
  • L'arbre binaire/pas binaire, accés spécial des données, sous forme de noeuds itératifs
  • D'autres sombres structures...
Pour des raisons de clareté et d'efficacité, nous n'allons parler que des structures existantes en C++.

La structure la plus bas-niveau en informatique est le tableau statique. Il s'agit d'un ensemble de données, qui comporte toujours le même nombre de données, défini à la création du tableau. Chaque donnée est accessible via un indice (ou index en anglais), représentant la position de la donnée, EN SACHANT QUE LA PREMIÈRE DONNÉES EST ACCESSIBLE PAR 0 ET PAS 1. En général (si le langage utilisé est bien optimisé), les données sont disposées dans la mémoire les unes à côtés des autres. Il a l'avantage d'être extrêmement rapide, puis ce que l'on peut savoir précisément où se trouve la donnée avec un simple calcul. Cependant, on ne peut pas lui rajouter de nouvelles données, mais seulement modifier celles déjà présentes.

Une autre structure très importante en informatique est le tableau dynamique. Il s'agit d'un ensemble de données, avec un nombre de données stockés variable dans le temps. On peut donc rajouter et enlever des données, ou bien modifier celles déjà présentes. On peut aussi avoir des informations générales sur le tableau, comme le nombre de données ou certaines informations sur les valeurs stockées. On peut aussi y appliquer des algorithmes, que nous verrons plus tard. Il existe plusieurs formes de tableaux dynamiques : pile (ou stack en anglais), file (ou queue en anglais), liste (ou list en anglais)...

Une autre structure très pratique dans plein de cas est le dictionnaire (ou tableau associatif, en terme plus précis). C'est une structure similaire au tableau dynamique, sauf que l'indice d'accés à une donnée peut être n'importe quoi, et pas juste sa position dans le tableau. Par exemple, l'indice peut être un texte, comme un pseudonyme, pour contenir une certaine donnée accessible via un pseudonyme. Dans ce genre de cas (assez récurents, disons le), cette structure est extrêmement efficace. Cependant, la consulter autrement que via cette indice est compliqué, ce qui peut la rendre assez peu intuitive dans certains cas.

Nous pouvons présenter plein d'autres structures de données, mais ça ne serait pas très intéressant d'en présenter des milliards, pour en présenter des milliards. Nous allons donc juste généraliser ce terme. Pour rappel, une structure de données est un moyen de stocker des données. Il s'agit donc de plusieurs façon de faire, comme l'accés (via la position de la donnée, son indice...), la façon de modifier (ou de ne pas modifier) la structure, et les actions réalisables avec la structure en entier. Il est aussi important de comprendre pourquoi la structure marche comme ça, pour savoir quand et comment l'utiliser. En tout cas, si cela vous intéresse, vous trouverez ici une liste de structures de données, plus ou moins différentes que les structures très basiques que nous avons vu plus tôt. Vous pouvez même créer les votres si besoins, en définissant vos propres règles.

b. Les structure de données en C++

Comme dans tous les langages, le C++ utilise des structures de données. Cependant, une seule est considérée comme un type primaire en C++. C'est le tableau statique. Il permet de contenir un nombre donné de données, d'un certain type. Pour en définir une, il faut utiliser cette syntaxe, avec les crochets :

type nom_du_tableau[taille_du_tableau];
Par exemple :
#include <iostream>

using namespace std;

int main() {
        int tableau[5]; // Créer un tableau de nombre entier "int" contenant 5 éléments
        return 0;
}
Les valeurs par défaut dans un tableau comme ça sont en général aléatoires, si elles n'ont pas été modifiées après la création du tableau. Cependant, on peut y attribuer des valeurs à la création du tableau, comme ça :
#include <iostream>

using namespace std;

int main() {
        int tableau[5] = {1, 2, 3, 5, 7}; // Créer un tableau de nombre entier "int" contenant les éléments 1, 2, 3, 5 et 7
        return 0;
}
Pour accéder à un élément du tableau, il faut utiliser sur le tableau un opérateur assez spécial : l'opérateur d'indice, utilisant les crochets. Chaque élément du tableau s'obient par sa position dans le tableau. Une chose très importante, LE PREMIER ÉLÉMENT DE LA LISTE S'OBTIENT AVEC LE CHIFFRE "0", et donc, le dernier s'obtient avec le chiffre taille_du_tableau - 1. On peut l'utiliser de cette manière :
#include <iostream>

using namespace std;

int main() {
        int tableau[5] = {1, 2, 3, 5, 7}; // Créer un tableau de nombre entier "int" contenant les éléments 1, 2, 3, 5 et 7
        cout << tableau[0] << " " << tableau[3] << endl; // Affiche le premier et le 4ème élément du tableau, séparé par un espace
        return 0;
}
D'ailleurs, cette opérateur retourne une référence vers l'endroit où la donnée est stockée. On peut donc la modifier directement avec cet opérateur, comme ça :
#include <iostream>

using namespace std;

int main() {
        int tableau[5] = {1, 2, 3, 5, 7}; // Créer un tableau de nombre entier "int" contenant les éléments 1, 2, 3, 5 et 7
        tableau[1] = 25; // Met la valeur du deuxième élément du tableau à 25
        cout << tableau[0] << " " << tableau[3] << endl; // Affiche le premier et le 4ème élément du tableau, séparé par un espace
        return 0;
}
Si vous spécifier une références invalide (trop grand, négative...), des comportements inatendus peuvent apparaître et faire disfonctionner le programme. D'autres choses sont possibles avec ce tableaux, mais sans plus de connaissances en C++, nous ne pourrons les aborder pleinement. Nous y reviendrons donc dans les prochains cours.

Toutes les autres structures ne sont pas définies par défaut en C++. Il faudra donc utiliser du code avec "include", comme nous l'avons vu plus tôt. Le tableau dynamique est aussi présent en C++, sous le nom de "vector", que nous appellerons vecteur dans la suite du cours. Il utilise une mécanique que nous n'avons pas vu pour l'instant pour savoir quel type stocker : les templates. Voici comment définir un vecteur :

// Ligne à ajouter pour utiliser des vecteurs
#include <vector>
#include <iostream>

using namespace std;

int main() {
        vector<int> tableau; // Créer un vecteur de nombre entier "int" vide
        vector<int> tableau_2(5, 1); // Créer un autre vecteur de nombre entier "int" contenant 5 fois le nombre 1
        vector<int> tableau_3({1, 10, 100}); // Créer un autre vecteur de nombre entier "int" contenant 1, 10 et 100
        vector<int> copie(tableau_2); // Créer un autre vecteur, une copie de tableau 2
        return 0;
}
Voici quatres façons pratiques de définir des vecteurs. Le système de template est le système permettant de spécifier un type, entre "< >", pour pouvoir créer un vecteur de n'importe quel type. Appart ça, ils s'utilisent exactement comme le tableau statique (opérateur "[]"...). Il offre cependant plusieurs possibilités supplémentaires intéressantes. Par exemple, comme le tableau est dynamique, vous pouvez y ajouter un élément avec la méthode (concept vu au dernier cours) "push_back" :
// Rajoute 78 au tableau
tableau.push_back(78);
Vous pouvez aussi supprimer le dernier élement du tableau (avec l'indice le plus élevé) avec "pop_back" :
// Supprime le dernier élément du tableau
tableau.pop_back();
Vous pouvez aussi avoir la taille du tableau avec la méthode "size()" :
// Affiche la taille du tableau
cout << tableau.size() << endl;
Vous pouvez aussi vider le tableau avec la méthode "clear()" :
// Vide complétement le tableau
tableau.clear();
cout << tableau.size() << endl; // Affiche 0
Plein d'autres choses sont possibles avec ce type, mais ce serait trop long de tout présenter un par un. La documentation de ce type est disponible ici.

Avec ces structures là, nous avons fait une par conséquente du travail, mais plein d'autres structures sont possibles en C++. En fait, les autres structures sont justes des utilisations différentes des structures déjà vu, selon leur type. Par exemple, le type "map" documenté ici représente les tableaux associatifs, utilisables comme les tableaux dynamiques. Elle utilise un tempalte double pour pouvoir utiliser n'importe quel type en indice. Cependant, il n'y a ni "push_back()" ni "front_back()", tout se fait via l'opérateur "[]", avec entre "[]" l'indice d'une valeur et en retour la référence vers la valeur. Si l'indice n'est pas déjà dans le "map", il faut l'assigner via l'opérateur "=", comme ça :

// Ligne à ajouter pour utiliser des maps
#include <map>
#include <iostream>
#include <string>

using namespace std;

int main() {
        map<string, int> habitants; // Créer un map de nombre entier "int" accessible via des "string" vide
        habitants["france"] = 69000000; // Ajoute la valeur 69000000 accessible via "france"
        habitants["belgique"] = 12000000; // Ajoute la valeur 12000000 accessible via "belgique"
        cout << habitants["france"] << endl; // Affiche "69000000"
        return 0;
}
Plein d'autres structures sont possibles : queue (la file), list (la liste), string (la chaîne de caractère / texte)...

c. Utiliser proprement des structures de données en C++

Bien que les structures de données peuvent contenir des méthodes très utiles pour les utiliser facilement, il y a cependant quelques petits trucs à connaître autres que les méthodes. Un moyen efficace de parcourir les données dans un vecteur ou un tableau statique est la boucle for. L'idée est d'attribuer à la valeur défini pour la boucle toutes les valeurs, de 0 jusqu'à la dernière (taille_du_tableau - 1). Voici comment faire :

#include <iostream>
#include <vector>

using namespace std;

int main() {
        vector<int> tableau({1, 10, 100}); // Créer un vecteur de nombre entier "int" contenant 1, 10 et 100
        for(int i = 0;i < tableau.size();i++) {
                cout << tableau[i] << endl; // Affiche "1" puis "10" puis "100" sur différentes lignes
        }
        return 0;
}
La condition d'arrêt arrête la boucle quand "i" est égal à la taille du tableau, et donc la boucle s'exécutera quand "i" sera entre 0 et taille_du_tableau - 1 inclue, permettant de parcourir tout le tableau.

De plus, les structures peuvent contenir beaucoup de données, et devenir très lourdes. Il est donc conseillé d'en créer le moins possible, si il y a une chance que la structure devienne vraiment lourde. Par exemple, il est conseillé de les passer en tant que références constantes ou non dans les fonctions. Cependant, si la structure est constante, on ne pourra pas utiliser l'opérateur "[]". Pour pallier à ce problème, on peut utiliser la méthode "at(int indice)", qui fonctionne exactement comme l'opérateur "[]", mais pour les structures constantes. Cependant, elle ne permet pas de modifier la structure, parce qu'elle est constante. En général, les algorithmes (que nous verrons après) utilisent des références non-constantes pour traiter les structures.

Pour en finir, nous allons parler de quelque chose de très important avec les structures de données : les itérateurs. Les itérateurs permettent d'utiliser n'importe quel structure itérative (map, queue...) comme un vecteur. Pour cela, ils utilisent un système que nous n'avons pas encore vu : les pointeurs. Donc, nous allons seulement effleurer le concept, avec les façon d'utiliser les itérateurs sans avoir besoin d'utiliser les pointeurs. La meilleur façon de les utiliser sont les méthodes "begin()" et "end(). "begin()" représente l'itérateur du premier élément de la structure, et "end()" représente un élément vide, présent après le dernier éléments de la structure. Les itérateurs sont utilisables comme des nombres entiers positifs (pour des raisons que nous verrons lors du cours sur les pointeurs). Donc, "begin() + 3" représente l'itérateur du quatrième élément de la structure (pour rappel, on commence par 0) et "end() - 1" l'itérateur du dernier élement de la structure. Ce terme nous sera utile dans la suite du cours.

Contenu

B. Les algorithmes en C++

Utiliser les structures de données en C++ sans algorithmes, c'est comme utiliser une voiture sans moteur : completement inutile. Il faut quand même bien comprendre la notion d'algorithme dans le cas présent, pour mieux les utiliser et mieux les appréhender.

a. Qu'est ce qu'est un algorithme ?

Nous avons déjà parlé d'algorithmes sur SAASF, dans ce cours là. La définition d'algorithme que nous allons utiliser est une suite d'action permettant d'aboutir à une tâche. Cela est très proche des définitions de la programmation que nous avons établi au premier cours de C++.

Si vous devez traiter une grande quantité de données, un algorithme sera efficace si il permet de réaliser la tâche qu'il doit résoudre rapidement. Pour cela, il faut passer du temps pour l'optimiser. Cependant, pas tout le monde n'a que ça à faire, mais heuresement, il existe des algorithmes pré-définis et célèbres pour parvenir efficacement à la tâche nécessaire. Malheuresement, ils sont souvent fournis sous la forme de pseudo-code, ce qui est mieux que rien, mais vous demande de l'implémenter vous même (bien que, en soit, ce n'est pas une si mauvaise chose pour progresser en programmation, bien que pas tout le monde n'est le temps pour ça).

b. Les algorithmes pour les structures de données en C++

En C++, le problème de l'implémentation ne se pose pas vraiment, puis ce qu'il existe un moyen d'accéder à une grande quantité d'algorithmes, avec seulement un "include". En effet, il existe un morceau de code pour utiliser pleins d'algorithmes facilement, "algorithm" :

// Ligne à ajouter
#include <algorithm>

#include <iostream>

using namespace std;

int main() {
        int i = 0;
        return 0;
}
L'ajout du morceau de code pour "<algorithm>" donne accés à une aberrante quantité de choses. La documentation pour savoir comment l'utiliser se trouve ici. En général, ce code contient des fonctions avec des paramètres références, vues au dernier cours. Il est aussi très axé structures de données.

C'est ici que les itérateurs vus plus haut nous seront utile. En effet, la manipulation de structures de données est plus rapide via des itérateurs. Par exemple, il y a une fonction, dans "algorithm", permettant de trier une structure de donnée : sort. Étudions cette fonction d'un peu plus prés. Elle est sous la forme :

void sort(RandomIt first, RandomIt last, Compare comp);
Elle ne retourne donc rien. "first" et "last" représentent les itérateurs entre lesquelles le tri aura lieu (avec "first" inclu et "last" pas inclu). Leur type "RandomIt" ici est défini sous la forme d'un template par défaut, mais nous n'allons pas aller trop loin pour ne pas perdre tout le monde. Retenons juste qu'il s'agit d'un itérateur. "comp" représente la fonction de comparaison lors de la comparaison entre deux objets dans la structure de données. Son utilisation et compréhension précise nous demanderait plus de connaissance en programmation-orienté-objet, nous n'allons donc pas nous étaler dessus. Cependant, cette fonction a un argument par défaut équivalent à "<" (trier du plus petit au plus grand). Voici une application de "sort" :
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
        vector<int> tableau({10, 1, 100}); // Créer un vecteur de nombre entier "int" contenant 10, 1 et 100

        sort(tableau.begin(), tableau.end()); // Tri le vecteur

        for(int i = 0;i < tableau.size();i++) {
                cout << tableau[i] << endl; // Affiche "1" puis "10" puis "100" sur différentes lignes
        }
        return 0;
}
Les itérateurs étant, comme nous l'avons vu, une sorte de pointeur, alors on peut l'utiliser comme une référence vers la structure. Presque toutes les fonctions dans "algorithm" utilisent ce procédé.

c. Les autres algorithmes en C++

Les structure de données, c'est bien, mais il y a aussi d'autres algorithmes de disponibles directement en C++. Par exemple, plein d'algorithmes mathématiques sont disponible via l'include du code "cmath". La documentation de "cmath" est présente ici. Pour citer quelques exemples en vrac : l'exposant d'un nombre avec pow(double nombre, double exposant), le cosinus d'un nombre avec cos(double nombre) en radians, l'inverse de la tangent hyperbolique avec atanh(double nombre)... Avec ça, vous pourrez utiliser les mathématiques plus facilement en C++.

Un autre algorithme très pratique est disponible via l'include de "random". Il permet la génération de nombres aléatoires. En informatique, un nombre aléatoire est obtenu grâce à une fonction mathématique si complexe que le prochain nombre de cette fonction est trop compliqué pour être prévisible. Pour cela, la fonction utilise une graine, permettant la génération des nombres aléatoires. Si vous utilisez une même graîne dans deux mêmes fonctions différentes utilisées de la même manière, leurs résultats seront exactement les mêmes. Voici comment générer des nombres aléatoires en C++ :

#include <iostream>
#include <random>

using namespace std;

int main() {
        // Création des choses nécessaires
        random_device moteur;
        mt19937 generateur(moteur());
        uniform_int_distribution distributeur(1, 6);

        for (int n = 0; n != 10; ++n) {
                // Affiche 10 nombres aléatoires
                cout << distributeur(generateur) << endl;
        }
        return 0;
}
On commence par créer un "moteur de génération aléatoire", de type "random_device" nommé "moteur". Il nous permettra d'utiliser le reste des fonctions aléatoires nécessaires. En suite, on crée un "générateur de nombres aléatoires", de type "mt19937" nommé "generateur" et prenant notre moteur "moteur" en tant que moteur de génération. Le générateur utilise l'algorithme Mersenne Twitser pour générer les nombres. Finalement, on crée le "distributeur de nobmre aléatoires uniformes" de nombre, de type "uniform_int_distribution" nommé "distributeur", permettant d'obtenir des nombres aléatoires contenus entre 1 et 6 inclus. L'obtension des nombres aléatoires ce fait via l'appel de "distributeur" avec en paramètre le générateur de nombre. En effet, bien qu'il s'agisse d'une variable, on peut l'utiliser comme une fonction (nous verrons comment et pourquoi dans des prochains cours). Cet appel retournera un nombre aléatoire entre 1 et 6 inclus. Plein d'autres utilisations sont possible avec les nombres aléatoires, documentées ici.

Je vous ai montré ici deux exemples d'include offrant des algorithmes simples à utiliser, mais des includes comme ça, il y en a plein d'autres. Sur le site d'où je tire toutes les documentations, vous trouverez une liste d'includes juste ici. À partir de là, votre mission est de s'entraîner à lire une documentation, pour utiliser de mieux en mieux les programmes mis à disposition par le C++ primaire. Cependant, des bases d'anglais sont nécessaires pour bien comprendre le tout (sinon, il y a toujorus Google Traduction ou Reverso pour vous aider).

C'est sur cela que nous terminons cette partie très théorique du C++, et même, l'ensemble de cours très théoriques nécessaire pour comprendre le C++. À partir de là, vous devriez déjà être capable de faire des petits programmes, selon vos envies. Cependant, vous ne restez qu'un débutant en C++ pour l'instant. Les parties avancées du C++ seront abordées dans les prochains chapitres de cours.