STL containers
**************

.. include:: ../BoutonGoogleTrad.rst


Ce chapitre présente les principaux conteneurs de données disponibles en C++. Ils remplacent avantageusement les tableaux hérités du langage C.

**À partir de maintenant, vous devez les utiliser dans tous nos exercices. Les tableaux sont désormais INTERDITS.**

Jusqu'à présent, nous avons développé nous-mêmes les fonctionnalités nécessaires à la classe :cpp:`V10` dans les chapitres précédents.
La bibliothèque standard fournit des conteneurs qui prennent déjà en charge une grande partie de ce travail.
Ainsi maintenant vous pourrez/devrez simplement écrire :

.. code-block::

    using V10 = std::array<int, 10>;
    V10 v;
    cout << v.size();
    cout << v[3];


Ainsi les conteneurs ont été conçus pour offrir de bonnes performances tout en améliorant la sûreté et la lisibilité du code.
Leur conception, leur standardisation et leurs nombreuses années d’utilisation permettent aujourd’hui de s’appuyer sur des composants robustes et largement éprouvés.
Nous étudions dans la suite :

	* Les :cppterm:`array`  : container de taille fixe, accès aux éléments en *O(1)*, taille en mémoire optimale
	* Les :cppterm:`vector` : dimension dynamique, accès aux éléments en *O(1)*
	* Les :cppterm:`map`    : association par clé–valeur ordonnée et  accès aux éléments en *O(log n))*

La présentation est synthétique et convient à des étudiants de master expérimentés.

Array
=====


Rôle
----

Un `std::array <https://en.cppreference.com/w/cpp/container/array>`_ contient un nombre fixe d'éléments de même type.
 
Pourquoi utiliser un :cpp:`std::array` plutôt qu'un tableau :cpp:`int T[10]` ?

	* Les arrays sont des objets, ils peuvent donc être passés par copie ou par référence.
	* La fonction membre :cpp:`at(i)` permet de vérifier la validité de l'indice avant d'accéder au i-ème élément.
	* Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche...

Pour instancier un :cpp:`array`, vous devez :

	* Ecrire une directive :cpp:`#include <array>` en début de programme
	* En l'absence de : :cpp:`using namespace std`, vous devez écrire :cpp:`std::array`


Présentation rapide
-------------------

.. csv-table:: Opérations sur les arrays
    :header: "Type", "Exemple", Remarque
    :widths: 10, 10, 20
    :delim: |

    Initialisation | :cpp:`array<int, 3> a = {1, 2, 3};` |
    Initialisation | :cpp:`array<int, 3> a {1, 2, 3`     |
    Initialisation | :cpp:`array<int, 3> a({1, 2, 3});`  |
    Initialisation | :cpp:`array<int, 3> a = {};` | Avec initialisation des valeurs : les numériques sont mis à zéro !
    Initialisation | :cpp:`array<int, 3> a;` | Sans initialisation
    Méthode | :cpp:`a.fill(value)` | Initialise tous les éléments à la valeur donnée
    Méthode | :cpp:`a.at(i)`   | Retourne une référence vers le i-ème élément AVEC bound-checking
    Méthode | :cpp:`a[i]`      | Retourne une référence vers le i-ème élément SANS bound-checking
    Méthode | :cpp:`a.size()`  | Retourne le nombre d'éléments
    Méthode | :cpp:`a.swap(b)` | Permute les éléments des deux arrays


Quizzz
======

.. quiz:: Arrayaa
	:title: Array
		

	*	:quiz:`{"type":"TF","answer":"F"}` La fonction *length* retourne le nombre d'éléments.
	*	:quiz:`{"type":"TF","answer":"F"}` La syntaxe :cpp:`at(i)` ou :cpp:`[i]` sont identiques en tout point.
	*	:quiz:`{"type":"TF","answer":"T"}` La syntaxe : :cpp:`array<int, 3> a {1, 2, 3};` est valide.
	*	:quiz:`{"type":"TF","answer":"T"}` Il est possible d'instancier un array sans initialiser ses valeurs.
	*	:quiz:`{"type":"FB","answer":"fill"}`  Quel est le nom de la fonction initialisant l'ensemble des éléments à une valeur donnée.


Vector
======

Rôle
----


Un `std::vector <https://en.cppreference.com/w/cpp/container/vector>`_ représente une liste de **taille dynamique** d'éléments de même type.


Pourquoi utiliser un :cpp:`std::vector` :

	* Classe modèle pouvant s'adapter à tout type.
	* Les vectors sont des objets, ils peuvent donc être passés par copie ou par référence.
	* Pas de limite de taille.
	* Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche...	 
	* La fonction membre :cpp:`at(i)` permet de vérifier la validité de l'indice avant d'accéder au i-ème élément
	* Gestion automatisée de la mémoire : allocation, libération.

	
	

Présentation rapide
-------------------

Pour instancier un objet vector, vous devez :

	* Mettre une directive :cpp:`#include <vector>`   en début de programme
	* En l'absence de : :cpp:`using namespace std`, vous devez écrire :cpp:`std::array`


.. csv-table:: Opérations sur les vectors
        :header: "Type", "Exemple", ""
        :widths: 10, 10, 20
        :delim: |

		Initialisation | :cpp:`vector<int> L;`               | Vector vide ; pas d'éléments dans la liste
		Initialisation | :cpp:`vector<int> L = {};`          | Idem
		Initialisation | :cpp:`vector<int> L = {1,2,3,4};`   |
		Initialisation | :cpp:`vector<int> L( {1,2,3,4} );`  |
		Initialisation | :cpp:`vector<int> L( );`            | Confusion => Déclaration d'une fonction retournant un vector
		Initialisation | :cpp:`vector<int> v1(10);`          | Taille fixée à 10 éléments + INITIALISATION à zéro
		Initialisation | :cpp:`vector<int> v1(10,5);`        | Taille fixée à 10 éléments initialisés à la valeur 5
		Initialisation | :cpp:`vector<int> v2(v1);`          | Initialisation par copie
		Méthode,	| :cpp:`L.fill(value)`    | Initialise tous les éléments à la valeur donnée
		Méthode,	| :cpp:`L.at(i)`          |  Retourne une référence vers le i-ème élément AVEC bound-checking
		Méthode,	| :cpp:`L[i]`             | Retourne une référence vers le i-ème élément SANS bound-checking
		Méthode,	| :cpp:`L.size()`         | Retourne le nombre d'éléments
		Méthode,    | :cpp:`L.empty()`        | Indique si la liste est vide
		Méthode,	| :cpp:`L.clear()`        | Retire et détruit tous les éléments de la liste
		Méthode,	| :cpp:`L.resize(n)`      | Force le nombre d'éléments à *n*
		Méthode,	| :cpp:`L.push_back(v)`   |  Insère une copie de l'élément *v* en fin de liste en **O(1)**
		Méthode,    | :cpp:`L.pop_back()`     |   Retire et détruit le dernier élément de la liste en **O(1)**
		Méthode, 	| :cpp:`L.back()`         | Retourne une référence vers le dernier élément de la liste
		Méthode,    | :cpp:`L.erase(iter)`    | Supprime l'élément désigné par l'itérateur *iter*
		Méthode,	| :cpp:`L.insert(iter,v)` | Insère une copie de l'élément *v* à la position désignée par l'itérateur *iter*

		
	

 
.. warning:: Tous les éléments dans une liste de type *vector* sont de même type. Ainsi, si vous stockez un *double* dans une liste de type *vector<int>*, alors il sera implicitement converti en entier.

La fonction :cpp:`resize(n)` fixe le nombre d'éléments :

	* Si :cpp:`n < size()` alors les derniers éléments sont détruits.
	* Si :cpp:`n = size()` aucun effet.
	* Si :cpp:`n > size()` il y a création de nouveaux éléments par appel au constructeur par défaut.



.. note:: Certaines méthodes des vectors portent des noms similaires ce qui prête à confusion. On pense ici aux fonctions membres :cpp:`resize()` et :cpp:`reserve()` ainsi que :cpp:`size()` et :cpp:`capacity()`. Une clarification s'impose ! Un objet :cpp:`vector` alloue une zone mémoire servant de buffer. La mécanique interne du :cpp:`vector` fait en sorte que la taille de ce buffer soit supérieure au nombre d'éléments stockés. La méthode :cpp:`reserve()` permet de fixer la taille de ce buffer et :cpp:`capacity()` retourne sa taille. Par exemple, si vous savez que 10 000 000 d'éléments vont être stockés, alors, il peut être utile de fixer directement la taille du buffer à cette grandeur ce qui évite de multiples redimensionnements et permet de gagner en efficacité. Ainsi, ces deux fonctions permettent une optimisation fine des objets :cpp:`vector`.


Quizzz
======

.. quiz:: vectorrr
	:title: Vector
		

	*	:quiz:`{"type":"TF","answer":"F"}` La fonction :cpp:`pop_back()` insère un élément en fin.
	*	:quiz:`{"type":"TF","answer":"F"}` Les syntaxe :cpp:`at(i)` et :cpp:`[i]` sont identiques en tout point.
	*	:quiz:`{"type":"TF","answer":"T"}` La fonction :cpp:`size()` retourne le nombre d'éléments.
	*	:quiz:`{"type":"TF","answer":"F"}` La syntaxe : :cpp:`vector<int> v(10)` crée une liste et initialise ses éléments à la valeur 10.
	*	:quiz:`{"type":"FB","answer":"fill"}`   Quel est le nom de la fonction initialisant l'ensemble des éléments à une valeur donnée ?
	*	:quiz:`{"type":"FB","answer":"clear"}`  Quel est le nom de la fonction retirant tous les éléments ?
	*	:quiz:`{"type":"FB","answer":"empty"}`  Quel est le nom de la fonction indiquant si la liste est vide ?
	*	:quiz:`{"type":"FB","answer":"resize"}` Quel est le nom de la fonction permettant de fixer le nombre d'éléments dans la liste ?
	

Map
===

 

Un `std::map <https://en.cppreference.com/w/cpp/container/map>`_ représente un dictionnaire permettant d'associer une valeur (:cppterm:`value`) à une clé (:cppterm:`key`) pouvant être un entier comme un string !
	
.. note:: Si les dictionnaires sont si souples et si pratiques, pourquoi ne pas utiliser que des dictionnaires ? Oui cette question peut être posée ! En fait ils sont plus souples, mais chaque opération sur un dictionnaire est plus longue que sur un :cpp:`vector` : :cpp:`O(log n)` versus :cpp:`O(1)`. Il y a donc un surcoût à cette souplesse.

Présentation rapide
-------------------

.. csv-table:: Opérations sur les maps
        :header: "Type", "Exemple", ""
        :widths: 10, 10, 20
        :delim: |


		Initialisation | :cpp:`map<string,int> m = { {\"one\",1}, {\"two\",2} };`  |
		Affectation    | :cpp:`m[\"trois\"] = 3;`   | Associe la valeur 3 à la clé \"trois\"
		Opérateur[]    | :cpp:`cout << m[\"deux\"]` | Retourne la valeur associée à la clé \"deux\"
		Méthode        | :cpp:`m.count(key) > 0`    | Teste si la clé existe dans ce dictionnaire
		Méthode,       | :cpp:`m.erase(\"trois\")`  | Supprime la paire clé/valeur correspondant à la clé \"trois\"
		Méthode,       | :cpp:`m.size()`            | Nombre de paires clé/valeur dans le dictionnaire
		
	


Parcours
========

.. warning:: Les présentations ci-dessous sont valables pour un :cpp:`array` comme pour un :cpp:`vector`


En mode read-only
-----------------

.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 3> a = {1, 2, 3};
		for (int v : a)  std::cout << v << " ";
		for (int v : a)  v = 4;   // warning: v is a local copy - no update of a
		for (int v : a)  std::cout << v << " ";
	}
	
	>> 1 2 3
	>> 1 2 3

	
En mode read-write
------------------

.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 3> a = {1, 2, 3};
		for (int v  : a)  std::cout << v << " ";
		for (int &v : a)  v = 4;   // this time v is a reference
		for (int v  : a)  std::cout << v << " ";
	}
	
	>> 1 2 3
	>> 4 4 4


.. warning:: Un *vector* ne peut gérer le retrait ou l'ajout d'élément durant un parcours. 

Map
---

Pour les dictionnaires, il y a une légère différence car la boucle :cpp:`for` retourne un objet dont :

   * La variable :cpp:`first` correspond à la clé
   * La variable :cpp:`second` correspond à la valeur


.. code-block:: cpp

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

	int main() 
	{
		map<string,int> myMap = {{"one",1}, {"two",2}, {"three",3}};

		for (auto pair : myMap) 
			cout << pair.first << " => " << pair.second << endl;
	}

	>> one => 1
	>> three => 3
	>> two => 2



Rule of Zero
============

Pour gérer des données, il est recommandé d’utiliser les conteneurs de la STL. Plusieurs raisons justifient ce choix :

    * Les opérations de copie sont déjà implémentées.
    * Le conteneur :cpp:`vector` adapte dynamiquement sa taille en fonction des besoins.
    * La libération de la mémoire est gérée automatiquement.

Il ne faut pas sous-estimer la complexité de la gestion des ressources mémoire.
Prenons l’exemple de deux objets :cpp:`M1` et :cpp:`M2` de type :cpp:`Matrix` :

.. code-block::

	M1 = M2;	// copy a matrix object into an existing matrix object

Cette opération, qui paraît simple, soulève en réalité plusieurs difficultés :

    * Rien ne garantit que les deux matrices possèdent les mêmes dimensions.
    * Il faut penser à libérer correctement les données précédemment contenues dans :cpp:`M1`.
    * Il ne faut pas simplement faire pointer :cpp:`M1` vers les données de :cpp:`M2`. Dans ce cas, la destruction de :cpp:`M2` pourrait rendre les données de :cpp:`M1` invalides.
    * Pour copier les données de :cpp:`M2` vers :cpp:`M1`, la bibliothèque standard utilise des fonctions de transfert mémoire par bloc pour optimiser les performances.
    * Il existe des cas particuliers, comme par exemple celui où :cpp:`M1` est une référence vers :cpp:`M2`. On doit gérer un :cpp:`self-assignment`.

L’utilisation des conteneurs de la STL constitue donc un choix **sûr**, **efficace** et **robuste**.
Les principaux cas complexes liés à la gestion de la mémoire, à la copie et à la destruction des objets ont déjà été pris en charge et optimisés par la bibliothèque standard.
Il est donc préférable de s’appuyer sur ces mécanismes plutôt que de les réimplémenter soi-même.
Cette idée est notamment exprimée dans les *C++ Core Guidelines* à travers la règle :cppterm:`RC-0`, également appelée **Rule of Zero**.
`Cette règle <https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rc-zero>`_ peut être résumée ainsi :

.. panels::

	:column: col-lg-10 p-2

	Règle :cppterm:`RC-0` : Si vous pouvez éviter de gérer des ressources ou des situations complexes, faites-le et laissez les containers de la STL s’en charger.


En conclusion de ce chapitre :

.. panels::

	:column: col-lg-10 p-2


		Tous les containers de vos exercices et projets seront choisis parmis les containers de la STL : :cpp:`vector`, :cpp:`array`...



Les itérateurs
==============

Dans ce cours, la syntaxe des itérateurs a été volontairement simplifiée pour en faciliter la lecture. Vous verrez cependant, en consultant d’autres sources, que certains exemples sur Internet peuvent sembler plus complexes — c’est normal. 

Les itérateurs sont apparus dans les années 2000 avec une syntaxe reposant sur deux fonctions, :cpp:`begin()` et :cpp:`end()`.
Depuis C++20, a fait son apparition la notion de :cpp:`range/view`, similaire aux ranges de Python.
Cependant, pour rester concis, nous nous limiterons aux itérateurs :cpp:`begin/end`.


Présentation
------------

Les présentations ci-dessous sont valables pour un :cpp:`array` comme pour un :cpp:`vector`.


La STL introduit le concept d’itérateur, qui généralise et unifie les mécanismes d’accès aux éléments : 
l’indice pour les tableaux et le pointeur pour les listes chaînées.
Chaque container fournit ainsi ses propres itérateurs (~une sorte d'index) permettant d'accéder à ses éléments.
La convention de la STL impose à un itérateur d'assurer les opérations suivantes :

		* Se copier/assigner, se comparer : :cpp:`==, !=, <, >, <=, >=`
		* Passer à l'élément suivant/précédent : :cpp:`++it, --it`
		* Avancer/reculer de :cpp:`n` : :cpp:`it + n, it - n, it += n, it -= n`
		* Accéder en O(1) à l’élément :  :cpp:`\*it`




Itérateurs begin/end
--------------------

Chaque container fournit deux fonctions spécifiques :

   * :cpp:`begin()` : retourne un itérateur positionné sur le premier élément.
   * :cpp:`end()` : retourne un itérateur positionné a la fin du container : **un élément fictif placé après le dernier élément**.
   


.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 5> arr = {1, 2, 3, 4, 7};
		
		std::cout << *arr.begin() << std::endl;    // prints the first element
	 
		std::cout << *(arr.end()-1) << std::endl;  // prints the last element 
	}  
	
	>> 1
	>> 7

	
Les itérateurs :cpp:`begin/end` permettent un accès en lecture/écriture. Pour un accès en mode read-only, le langage fournit des const iterator :cpp:`cbegin()` et :cpp:`cend()` !

.. warning:: On n'utilise plus la valeur 0 ou le paramètre :cpp:`size()` pour parcourir une liste à partir de maintenant !

A noter qu'il n'y a pas de :cpp:`#include` particulier à effectuer en début de programme. L'insertion d'un :cpp:`#include <vector>` est suffisante pour pouvoir utiliser les itérateurs venant d'un :cpp:`vector`.


Généricité
----------


La généricité des containers opèrent à travers l'utilisation des templates.

Ainsi, si on vous demandait d'écrire une fonction qui recopie les valeurs d'un container vers un autre,
vous pourriez coder la fonction suivante :
 
.. code-block:: cpp

	template <typename InputIt, typename OutputIt>
	OutputIt my_copy(InputIt first, InputIt last, OutputIt dest) 
	{
		while (first != last) 
		{
			*dest = *first;   // copy in O(1)
			++first;          // go forward in the source
			++dest;           // go forward in the destination
		}
		return dest;
	}

Grâce au mécanisme des templates et des itérateurs, même si les containers sont de type différent,
du moment qu'ils fournissent des itérateurs, la méthode fonctionne.




	
Le mot-clef auto
----------------


Le type des itérateurs est assez long à écrire : :cpp:`array<T, N>::iterator`.
Ainsi, on préfère utiliser le mot-clef :cpp:`auto` qui laisse au langage le soin de déduire automatiquement le type :

.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 5> arr = {1, 2, 3, 4, 5};
		auto it = arr.begin();   // iterator pointing to the first element
	}

   
Arithmétique des itérateurs
---------------------------

L'expression :

    * :cpp:`begin()+1` désigne l'élément placé après le premier élément
    * :cpp:`begin()+2` désigne le suivant du suivant !
    * :cpp:`L.end() - L.begin()` correspond aux nombres d'éléments dans :cpp:`L`

Voici quelques exemples :


.. code-block:: cpp

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

	int main()
	{
		vector<int> L = {2,3,4,5,6};    // 2 3 4 5 6
		
		L.erase(L.begin()+2);         // Removes the element at index 2 (the 3rd one, which is 4)
		                              // L becomes [2, 3, 5, 6]
		
		L.insert(L.begin()+3, 8);     // Inserts 8 *before* the element at index 3 (the 4th one, which is 6)
		                              // L becomes [2, 3, 5, 8, 6]

		cout << L.end() - L.begin();  // returns the number of elements !!!
	}

 




Travail à rendre sur l'espace partagé
=====================================


 
Exercice 1 : relevés de température
-----------------------------------

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

* On stocke une série de mesures expérimentales dans un :cpp:`vector<double>` :

    .. code-block:: cpp

        vector<double> values = {  12.5, 8.2, 15.7, 9.1, 18.4, 7.8, 11.3, 21.6, 14.2, 10.0  };

* Réalisez les opérations suivantes :

    * Affichez toutes les valeurs à l'aide d'une boucle for moderne.
    * Ajoutez les valeurs 13.7 et 16.1 à la fin du vecteur.
    * Affichez le nombre de valeurs contenues dans le vecteur.
    * À l'aide d'un itérateur, faites une boucle qui recherche la première valeur strictement supérieure à 18.0.
    * Affichez cette valeur ainsi que sa position dans le vecteur - vous ne devez pas utiliser un parcours avec indice.
    * Insérez la valeur 20.0 juste avant cette valeur.
    * Supprimez la troisième valeur du vecteur en utilisant la fonction :cpp:`erase()`.
    * Multipliez toutes les valeurs par 2 en utilisant un parcours par référence.
    * Affichez le vecteur final.


* Contraintes :

    * Aucun tableau C ne doit être utilisé.
    * Pour les étapes nécessitant une position dans le conteneur, utilisez :cpp:`begin()` et :cpp:`end()`.
    * Utilisez le mot-clef :cpp:`auto` pour déclarer les itérateurs.
    * N'utilisez pas directement un indice pour les opérations d'insertion ou de suppression.




* Vérification - Le vecteur final est :

    * 25 16.4 18.2 40 36.8 15.6 22.6 43.2 28.4 20 27.4 32.2


* Déposez votre fichier dans l'espace partagé.


Exercice 2 : analyse des résultats d'étudiants
----------------------------------------------


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

    * Utilisez la structure suivante pour représenter les notes de plusieurs étudiants :

        .. code-block:: cpp

            map<string, vector<double>> students =
            {
                {"Alice", {12.0, 15.0, 14.0}},
                {"Bob",   {8.0,  11.0, 10.0}},
                {"Chloe", {17.0, 16.0, 18.0}},
                {"David", {10.0, 13.0, 12.0}}
            };

    * Réalisez les opérations suivantes :

        * Affichez le nom de chaque étudiant ainsi que toutes ses notes.
        * Ajoutez la note 16.0 à Alice.
        * Ajoutez une nouvelle étudiante : :cpp:`Emma -> {14.0, 13.0, 15.0}`

    * Vérifiez si *Paul* est présent dans le dictionnaire.
    * Pour chaque étudiant, calculez sa moyenne - une fonction serait bienvenue.
    * Affichez les résultats sous la forme suivante :

        .. code-block:: text

            Alice : 14.25
            Bob   : 9.67
            ...

    * Recherchez l'étudiant possédant la meilleure moyenne.
    * Affichez son nom ainsi que sa moyenne.
    * Supprimez de la *map* tous les étudiants dont la moyenne est strictement inférieure à 10.

        * Vous ne pouvez pas faire un parcours standard type :cpp:`for(each)` car des suppressions ont lieu durant le parcours
        * Préférez un itérateur courant qui avance tant qu'il reste des éléments à parcourir

    * Affichez le contenu final du dictionnaire.

    * Déposez votre fichier dans l'espace partagé.


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