STL utilities
*************


.. include:: ../BoutonGoogleTrad.rst

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 : :cpp:`T.sort()`.
Cependant, les différents conteneurs de la STL (:cpp:`vector`, :cpp:`list`, :cpp:`deque`, etc.) ne faisant pas partie d'une même hiérarchie de classes,
cela implique de recoder cette fonction :cpp:`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 :cpp:`algorithmes`.
L'idée ici est de coder une seule fonction :cpp:`sort()` acceptant des itérateurs comme paramètres et pouvant ainsi s'appliquer à plusieurs containers.

Voici donc la syntaxe que vous allez rencontrer :


.. code-block:: cpp

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

En résumé :

.. panels::

	:column: col-lg-10 p-2

        **STL = Conteneurs + Itérateurs + Algorithmes**

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


.. list-table:: Principaux algorithmes de la STL
    :widths: 20 60 20
    :header-rows: 1

    * * **Catégorie**
      * **Fonctions**
      * **Package**
    * * **Parcours**
      * :cpp:`for_each, count, find, search...`
      * :cpp:`<algorithm>`
    * * **Transformation**
      * :cpp:`copy, move, fill, generate, replace, transform...`
      * :cpp:`<algorithm>`
    * * **Organisation**
      * :cpp:`reverse, rotate, shuffle...`
      * :cpp:`<algorithm>`
    * * **Liste triée**
      * :cpp:`sort, lower_bound, binary_search...`
      * :cpp:`<algorithm>`
    * * **Ensembliste**
      * :cpp:`merge, set_intersection, set_difference...`
      * :cpp:`<algorithm>`
    * * **Calcul**
      * :cpp:`accumulate, iota, inner_product...`
      * :cpp:`<numeric>`


.. warning:: 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 <https://en.cppreference.com/w/cpp/algorithm>`_.

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


Exercice 1 : premiers traitements
---------------------------------

	* Créez un fichier nommé :cpp:`Utils_basic.cpp`

	* Recopiez ce code comme point de départ :


        .. code-block:: cpp

            #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 :cpp:`print()` : comment peut-elle fonctionner sur tout type de container ?


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

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

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

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

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

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



Exercice 2 : transformations
----------------------------

    * Créez un fichier nommé :cpp:`Utils_transform.cpp`

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

        .. image:: resultat1.png

    * :cpp:`fill(first,last,value)` : affecte la valeur :cpp:`value` à chaque élément de l’intervalle :cpp:`[first, last)`.
    * :cpp:`fill_n(first,n,value)` : affecte la valeur :cpp:`value` aux :cpp:`n` éléments à partir de la position :cpp:`first`.
    * :cpp:`iota(first,last,startvalue)` : remplit l’intervalle :cpp:`[first, last)` avec des valeurs croissantes en commençant par :cpp:`startvalue`.
    * :cpp:`rotate(first,middle,last)` : effectue une rotation à gauche des éléments de sorte que l’élément :cpp:`middle` devienne le premier.
    * :cpp:`reverse(first,last)` : inverse l’ordre des éléments dans l’intervalle :cpp:`[first, last)`.

    * Uploadez le fichier  sur votre espace partagé





Exercice 3 : données triées
---------------------------



	* Créez un fichier nommé :cpp:`Utils_sorted.cpp`

	* Appliquez les algorithmes présentées sur les exemples fournis.

        .. code-block:: cpp

            #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 :cpp:`v` et :cpp:`w` dans un nouveau :cpp:`vector x` en gardant les doublons : :cpp:`merge(first1,last1,first2,last2,back_inserter(first3))`
	* Vérifiez si le nouveau vector :cpp:`x` est bien trié : :cpp:`bool is_sorted(first,last)`
	* Affichez le nombre d'éléments du nouveau vector :cpp:`x` : :cpp:`size()`
	* Fusionnez le contenu de :cpp:`v` et :cpp:`w` dans un nouveau vector :cpp:`x` sans doublons : :cpp:`set_union(start1,end1,start2,end2,back_inserter(out1))`
	* Remplissez une nouvelle liste :cpp:`y` avec les éléments communs à :cpp:`v` et :cpp:`w` sans doublons : :cpp:`set_intersection(start1,end1,start2,end2,back_inserter(out1))`
	* Initialisez les valeurs de la liste :cpp:`z` de :cpp:`1` à :cpp:`1 000 000` : :cpp:`iota(start,end,val)`
	* Recherchez la position de la valeur :cpp:`N/2` dans :cpp:`z`. Affichez la pour vérification : :cpp:`iterator lower_bound(first,last,val)`

	* Uploadez le fichier  sur l'espace partagé

.. warning:: 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 :cpp:`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 :cpp:`langage C` et sa célèbre fonction :cpp:`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 :

.. list-table::
   :header-rows: 1
   :widths: 20 20 60

   * - **Générateur**
     - **Vitesse**
     - **Qualité / Usage typique**
   * - :cpp:`mt19937`
     - Rapide
     - Le plus utilisé. Bon compromis entre qualité et performance.
   * - :cpp:`minstd_rand`
     - Très rapide
     - Basique, faible qualité
   * - :cpp:`ranlux24`
     - Lent
     - Très bon aléatoire, utile pour la physique, les statistiques...
   * - :cpp:`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
-------


.. code-block:: cpp

	#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



.. code-block:: cpp

	#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é :cpp:`Utils_shuffle.cpp`

    * Créez un vecteur contenant les nombres de :cpp:`1` à :cpp:`20`

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

        * .. image:: doc.png

        * 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 :cpp:`lambda` ou des :cpp:`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 :cppterm:`functor` (ou fonction objet) n’est rien d’autre qu’une classe/struct qui surcharge l’opérateur :cpp:`()`. 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 : :cpp:`T operator+(const T&a,const T& b)`.
L'opérateur associé à l'appel de function s'intitule : :cpp:`operator()`, ainsi, pour le redéfinir, il faudra écrire :

.. code-block:: cpp

	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 :cpp:`generate` de la STL pour remplir les valeurs d'un :cpp:`verctor`.
Dans cet exemple, le foncteur est utile car il nous permet de conserver le dernier nombre généré.

.. code-block:: cpp

    #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 :cppterm:`lambda expression` ou :cppterm:`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.


.. panels::

	:column: col-lg-10 p-2
	
	**Syntaxe d'une lambda** :  :cpp:`[captures] (parameters) -> returnType { ... }`

Avec :

	* :cpp:`captures`  : indique comment la lambda accède aux variables environnantes.
	* :cpp:`parameters` : comme une fonction classique.
	* :cpp:`returnType` : type de retour de la lambda expression - **optionnel**
	* :cpp:`{ }`        : instructions à exécuter.
	
Voici un exemple simple :

.. code-block:: cpp

	auto square = [](int x) { return x * x; };
	
	cout << square(5); 		// 25


Ici, la variable :cpp:`square` correspond à une :cpp:`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 :

	* :cpp:`[ ]`     : rien n’est capturé.
	* :cpp:`[x]`     : capture la variable :cpp:`x` par valeur (read-only).
	* :cpp:`[&x]`    : capture la variable :cpp:`x` par référence.
	* :cpp:`[=]`     : capture toutes les variables visibles par valeur.
	* :cpp:`[&]`     : capture toutes les variables visibles par référence.
	* :cpp:`[=, &y]` : capture par valeur par défaut, mais :cpp:`y` par référence.
	
	
Exemples
--------

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

	
.. code-block:: cpp

    #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 :cpp:`val` et :cpp:`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 :cppterm:`predicate` est simplement une fonction (un functeur ou une lambda) qui retourne un booléen.
L'injection d'un :cppterm:`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 :cpp:`vector` tous les nombres impairs.

Le prédicat écrit comme une fonction donne :

.. code-block:: cpp

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

Il reste ensuite à utiliser l'algorithme :cpp:`copy_if` :



.. code-block:: cpp

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

.. code-block:: cpp

	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é :cpp:`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é



	.. code-block:: cpp

		#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 :cpp:`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 :cpp:`erase()` pour raccourcir le :cpp:`vector` et supprimer les éléments à effacer.


.. list-table:: 
	:header-rows: 1
	:widths: 25 75
	:align: left
	:class: wrap

	* - 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é :cpp:`Utils_functor.cpp`

    * On dispose de trois listes de températures :

        .. code-block:: cpp

            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 :cpp:`for`
        * Utilisez un :cpp:`functor` sans paramètre
        * Le :cpp:`functor` doit conserver dans un attribut le nombre de températures correspondant au critère

    * Testez votre :cpp:`functor`

    * Modifiez ensuite votre :cpp:`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é

.. warning:: :cppterm:`IA or not IA, that is the question.` Ces exercices sont au programme de l'examen.