STL utilities

To translate this course in your native langage:

In Chrome: right-click anywhere on the page and select “Translate to…”
Or use this language selector:

Les mots colorés en anglais représentent des mots-clés de la norme du langage C++. Ils sont conservés à l’identique lors de l’utilisation d’une traduction automatique avec Google Translate. Exemple : l’héritage (inheritance) est un principe fondamental de C++.

Algorithmes

La STL adopte une approche différente de la programmation orientée objet classique. Par exemple, en programmation orientée objet, l’usage voudrait que, pour trier un conteneur, on implémente une fonction membre que l’on utilise ainsi : T.sort(). Cependant, les différents conteneurs de la STL (vector, list, deque, etc.) ne faisant pas partie d’une même hiérarchie de classes, cela implique de recoder cette fonction sort() pour chaque conteneur, ce qui n’est pas très abile.

La STL a donc choisi une autre approche, plutôt que les fonctions membres, elle utilise des fonctions templates appelées algorithmes. L’idée ici est de coder une seule fonction sort() acceptant des itérateurs comme paramètres et pouvant ainsi s’appliquer à plusieurs containers.

Voici donc la syntaxe que vous allez rencontrer :

sort(T.begin(), T.end());

En résumé :

STL = Conteneurs + Itérateurs + Algorithmes

Pour présenter rapidement les différents algorithmes de la STL, on peut les regrouper par thématique :

Principaux algorithmes de la STL
Catégorie	Fonctions	Package
Parcours	for_each, count, find, search…	<algorithm>
Transformation	copy, move, fill, generate, replace, transform…	<algorithm>
Organisation	reverse, rotate, shuffle…	<algorithm>
Liste triée	sort, lower_bound, binary_search…	<algorithm>
Ensembliste	merge, set_intersection, set_difference…	<algorithm>
Calcul	accumulate, iota, inner_product…	<numeric>

Avertissement

Comme ces algorithmes ne sont pas des fonctions membres, ils n’apparaissent pas dans la documentation des containers ! Pour trouver toute information, il faudra donc parcourir la page des STL algorithms.

Nous avons choisi de les introduire à travers différents exercices.

Exercice 1 : premiers traitements

Créez un fichier nommé Utils_basic.cpp

Recopiez ce code comme point de départ :
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
using namespace std;

template <typename Container>
void print(const Container& c,string t="")
{
    for (const auto& x : c) cout << x << " " << t << endl;
}

int main()
{
    vector<int> v = { 1, 3, 5, 7, 9, 4, 3, 3, 3, 3, 9, 5, 9};
    vector<int> z = { 1, 3, 5 };
}
Analysez la fonction print() : comment peut-elle fonctionner sur tout type de container ?

Comptez le nombre d’apparitions du chiffre 9 dans le vector v : int count(first, last, value)

Affichez la plus petite valeur du vector v : iterator min_element(first,last)

Calculez la somme des éléments de v : T accumulate(first,last,T initvalue)

Dans le vector v, recherchez la valeur 4 et remplacez la par 8 : iterator find(first, last, value)

Vérifiez si les 3 premiers éléments de v sont identiques à ceux de z : bool equal(first1,last1,first2)

Une fois terminé, uploadez votre fichier sur votre espace partagé

Exercice 2 : transformations

Créez un fichier nommé Utils_transform.cpp

Ajoutez les fonctions documentées ci-après pour obtenir les sorties suivantes :

fill(first,last,value) : affecte la valeur value à chaque élément de l’intervalle [first, last).

fill_n(first,n,value) : affecte la valeur value aux n éléments à partir de la position first.

iota(first,last,startvalue) : remplit l’intervalle [first, last) avec des valeurs croissantes en commençant par startvalue.

rotate(first,middle,last) : effectue une rotation à gauche des éléments de sorte que l’élément middle devienne le premier.

reverse(first,last) : inverse l’ordre des éléments dans l’intervalle [first, last).

Uploadez le fichier sur votre espace partagé

Exercice 3 : données triées

Créez un fichier nommé Utils_sorted.cpp

Appliquez les algorithmes présentées sur les exemples fournis.
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>

using namespace std;
template <typename Container>
void print(const Container& c,string t="") { for (const auto& x : c) cout << x << " "; cout << t << "\n"; }

int main()
{
    vector<int> v = { 1, 3, 5, 9, 11  };
    vector<int> w = { 0, 1 , 2, 7, 8, 13 };
    const int N = 1000000;
    vector<int> z(N);
}
Fusionnez le contenu de v et w dans un nouveau vector x en gardant les doublons : merge(first1,last1,first2,last2,back_inserter(first3))

Vérifiez si le nouveau vector x est bien trié : bool is_sorted(first,last)

Affichez le nombre d’éléments du nouveau vector x : size()

Fusionnez le contenu de v et w dans un nouveau vector x sans doublons : set_union(start1,end1,start2,end2,back_inserter(out1))

Remplissez une nouvelle liste y avec les éléments communs à v et w sans doublons : set_intersection(start1,end1,start2,end2,back_inserter(out1))

Initialisez les valeurs de la liste z de 1 à 1 000 000 : iota(start,end,val)

Recherchez la position de la valeur N/2 dans z. Affichez la pour vérification : iterator lower_bound(first,last,val)

Uploadez le fichier sur l’espace partagé

Avertissement

Si l’on prend l’exemple de la fusion de deux vectors triés, l’algorithme merge écrit le résultat dans un conteneur de destination. Avec un itérateur classique, ce conteneur doit donc disposer à l’avance d’un nombre suffisant d’éléments pour recevoir le résultat, ce qui peut être contraignant. Il est cependant possible d’effectuer la fusion directement dans un vector vide en utilisant back_inserter(vector_destination). Les éléments sont alors ajoutés automatiquement à la fin du vector.

Générateurs de nombres alétoires

Introduction

Vous êtes sans doute familier avec le langage C et sa célèbre fonction rand(), cependant la STL a choisi de mettre à disposition des développeurs toute une panoplie de générateurs de nombres aléatoires. Pourquoi une telle offre ? Tout simplement, pour répondre à différents besoins techniques. Par défaut, ils fournissent tous des nombres entiers positifs. A titre indicatif, voici quelques exemples :

Générateur	Vitesse	Qualité / Usage typique
mt19937	Rapide	Le plus utilisé. Bon compromis entre qualité et performance.
minstd_rand	Très rapide	Basique, faible qualité
ranlux24	Lent	Très bon aléatoire, utile pour la physique, les statistiques…
random_device	Très lent	Générateur entropique

Pour la petite histoire : un générateur entropique utilise une source physique présente dans votre processeur, censée fournir une information réellement aléatoire, comme le bruit électronique ou thermique capté par un composant adapté.

Exemple

#include <iostream>
#include <random>

int main()
{
        std::mt19937 gen;

        for (int i = 0; i < 3; ++i)  std::cout << gen() << " ";
}

>>> 3499211612 581869302 3890346734

Loi de probabilité

A titre indicatif, on peut utiliser différentes lois de probabilité :

Uniforme discrète : chaque entier dans l’intervalle a la même probabilité d’apparaître

Uniforme continue : même principe pour les réels

Normale (gaussienne) : définie à partir d’une moyenne et d’un écart type

#include <iostream>
#include <random>
using namespace std;

int main()
{
        mt19937 gen;

        uniform_int_distribution<int> unifInt(10, 30);
        for (int i = 0; i < 10; ++i)   cout << unifInt(gen) << " ";

        normal_distribution<double> normale(20.0, 3.0);                  // mean 20, std 3
        for (int i = 0; i < 10; ++i)   cout << normale(gen) << " ";
}

>> 12 29 27 12 30 29 14 23 16
>> 15.9701 20.6107 18.0698 22.8348 22.6076 20.9631 24.3167 20.0531 16.3851 18.2595

Exercice

Créez un fichier nommé Utils_shuffle.cpp

Créez un vecteur contenant les nombres de 1 à 20

Examinez la déclaration de la fonction shuffle() ci-dessous :

Utilisez là pour mélanger les valeurs dans ce tableau

Ne spécifiez pas les paramètres template de cette function, le C++ les déduira de manière à partir des arguments passés à la fonction

Affichez le résultat

Uploadez le fichier sur l’espace partagé

Functor

Les algorithmes de la STL sont très puissants et robustes. Les utiliser, c’est ainsi éviter de reprogrammer la roue. Mais, nos besoins sont souvent un peu différents des algorithmes proposés ce qui nous empêche de les utiliser directement. Cependant, on peut fournir à ces algorithmes des fonctions lambda ou des functor pour ajuster leur comportement. Nous allons montrer comment exploiter cette souplesse pour adapter les algorithmes de la STL à des besoins très variés.

Un functor (ou fonction objet) n’est rien d’autre qu’une classe/struct qui surcharge l’opérateur (). Autrement dit, il est alors possible d’utiliser un objet comme s’il s’agissait d’une fonction. L’intérêt ? Une fonction classique ne conserve pas d’état interne, tandis qu’un foncteur peut stocker des informations supplémentaires dans ses champs, ce qui permet d’associer des données persistantes au comportement. Cette approche est donc très pratique dans certains cas, mais dans la pratique, les foncteurs deviennent plus rares, éclipsés par les expressions lambda que nous découvrirons juste après.

Point sur la syntaxe

Lorsque vous redéfinissez l’operateur +, vous écrivez par exemple : T operator+(const T&a,const T& b). L’opérateur associé à l’appel de function s’intitule : operator(), ainsi, pour le redéfinir, il faudra écrire :

struct stepGenerator
{
        int _val   = 0;
        int _step  = 2;

        stepGenerator(int start, int step)  { _val = start; _step = step; }

        int operator()()      //  definition of operator ()
        {
            int v = _val;
            _val+=_step;
            return v;
        }

        int operator()(int dec)  // operator() with 1 argument
        {
            int v = _val;
            _val+=_step;
            return v+dec;
        }
};

Exemple

Utilisons l’algorithme generate de la STL pour remplir les valeurs d’un verctor. Dans cet exemple, le foncteur est utile car il nous permet de conserver le dernier nombre généré.

#include <iostream>
#include <vector>
#include <algorithm>

    using namespace std;

    template <typename Container>
    void print(const Container& c,string t="") { for (const auto& x : c) cout << x << t << endl; }

int main()
{
    stepGenerator gen(0,2);
    cout << gen()   << endl;    // 0
    cout << gen()   << endl;    // 2
    cout << gen()   << endl;    // 4
    cout << gen()   << endl;    // 6

    vector<int> v(10);
    stepGenerator gen2(1,2);    // odd number generator

    generate(v.begin(),v.end(),gen2);
    print(v," ");
}

    >> 1 3 5 7 9 11 13 15 17 19

Le foncteur offre aussi l’avantage de la réutilisabilité, contrairement à une expression lambda qui est temporaire, il peut être instancié et employé à différents endroits du programme.

Lambda

Syntaxe

Une lambda expression ou lamda est une syntaxe introduite à partir de C++11 qui permet de définir une fonction anonyme (une fonction sans nom) que l’on peut écrire directement dans le code, souvent pour la passer en argument.

Syntaxe d’une lambda : [captures] (parameters) -> returnType { … }

Avec :

captures : indique comment la lambda accède aux variables environnantes.

parameters : comme une fonction classique.

returnType : type de retour de la lambda expression - optionnel

{ } : instructions à exécuter.

Voici un exemple simple :

auto square = [](int x) { return x * x; };

cout << square(5);              // 25

Ici, la variable square correspond à une lambda qui reçoit une valeur et retourne son carré.

Les captures

Les paramètres de capture déterminent comment une expression lambda accède aux variables locales au moment :

[ ] : rien n’est capturé.

[x] : capture la variable x par valeur (read-only).

[&x] : capture la variable x par référence.

[=] : capture toutes les variables visibles par valeur.

[&] : capture toutes les variables visibles par référence.

[=, &y] : capture par valeur par défaut, mais y par référence.

Exemples

Il est possible de reprendre l’exemple du stepGenerator, voici le code associé :

#include <iostream>
#include <vector>
#include <algorithm>

    using namespace std;

    template <typename Container>
    void print(const Container& c,string t="") { for (const auto& x : c) cout << x << " " << t; }

    int main()
    {
            int val   = 1;
            int step  = 2;

            vector<int> v(10);
            generate(v.begin(),v.end(), [&val,step] () { int v=val; val+=step; return v; } );
            print(v);
    }

    >> 1 3 5 7 9 11 13 15 17 19

Les champs du functeur sont remplacés par deux variables locales val et step. Certe, cette approche permet d’écrire rapidement le code attendu, le problème est que la qualité du code chute.

Predicate

En C++, un predicate est simplement une fonction (un functeur ou une lambda) qui retourne un booléen. L’injection d’un predicate à l’intérieur des algorithmes de la STL permet de faire du code sur mesure. Prenons un exemple où l’on veut copier depuis un vector tous les nombres impairs.

Le prédicat écrit comme une fonction donne :

bool isOdd(int x) {  return x % 2 != 0; }

Il reste ensuite à utiliser l’algorithme copy_if :

#include <iostream>
#include <vector>
#include <algorithm>

    using namespace std;

    template <typename Container>
    void print(const Container& c,string t="") { for (const auto& x : c) cout << x << " "; }

    bool isOdd(int x) {  return x % 2 != 0; }

    int main()
    {

            vector<int> v = { 4, 5, 7, 8 ,2, 12, 7, 9, 17 };
            vector<int> r;
            copy_if(v.begin(),v.end(), back_inserter(r), isOdd);
            print(r);
    }
    >> 5 7 7 9 17

Il est aussi possible d’utiliser la version avec une lambda :

copy_if(v.begin(), v.end(), back_inserter(r), [](int x) { return x % 2 != 0; });

Travail à rendre sur l’espace partagé

Exercice 1

Créez un fichier nommé Utils_lambda.cpp
A partir de l’exemple ci-dessous, effectuez les actions demandées en utilisant la STL et les lambdas.
Uploadez le fichier sur votre espace partagé

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
template <typename Container>
void print(const Container& c,string t="") { for (const auto& x : c) cout << x << " "; }

int main()
{
        vector<int> v = { 4, 5, 7, 5, 3, 8, 6, 4, 9, 5, 10};
        vector<int> w = {1, 2, 3, 4, 5, 6, 7, 8, 9};
}

En C++, les algorithmes de la STL comme remove_if() ne suppriment pas réellement des éléments d’un conteneur. Ils déplacent simplement les éléments conservés vers le début et retournent un itérateur marquant la nouvelle fin. Il faut ensuite appeler erase() pour raccourcir le vector et supprimer les éléments à effacer.

Opération	Description
transform(first1, last1, out1, UnaryFnt)	Créez un vector contenant les carrés de v
replace_if(first1, last1, UnaryPredicate p, val)	Dans le vector v remplacez tous les multiples de 5 par la valeur 0
iter remove_if(first1, last1, predicate) + erase(first1,last1)	Retirez les multiples de 3 du vector v
it partition(first1,last1, predicate)	Partitionnez le vector w avec les nombres impairs à gauche et les pairs à droite
count_if(first1,last1, predicate)	Dans w, comptez la quantité de nombres pairs
bool all_of(first1,last1,predicate)	Vérifiez si tous les éléments du vector w sont inférieurs à 100
bool any_of(first1,last1,predicate)	Détectez si au moins un élément de w est supérieur à 5

Exercice 2

Créez un fichier nommé Utils_functor.cpp
On dispose de trois listes de températures :
vector<int> jour1 = { 12, 18, 25, 7, 30, 21, 15, 28 };
vector<int> jour2 = { 10, 14, 17, 22, 24, 19, 16, 20 };
vector<int> jour3 = { 8, 11, 15, 18, 21, 26, 29, 23 };
Comptez le nombre de températures inférieures à 12° sur l’ensemble des trois listes, pour cela :

Vous devez parcourir chaque liste avec une boucle for

Utilisez un functor sans paramètre

Le functor doit conserver dans un attribut le nombre de températures correspondant au critère

Testez votre functor

Modifiez ensuite votre functor afin que la température limite puisse être passée en paramètre

Comptez et affichez le total de températures inférieures à 15°

Comptez et affichez le total de températures inférieures à 20°

Uploadez le fichier sur votre espace partagé

Avertissement

IA or not IA, that is the question. Ces exercices sont au programme de l’examen.