Containers ✱
************

.. include:: ../BoutonGoogleTrad.rst


Ce chapitre présente les principaux containers de données disponibles en C++.
Ils enterrent définitivement l'utilisation des tableaux du C.
**A partir de maintenant, vous devez les utiliser à chaque fois dans tous nos exercices.
Les tableaux du C sont INTERDITS.**
Nous rappelons qu'ils ont été conçus pour optimiser performance et sûreté.
Effectivement, des années de tests et développement permettent de garantir leur robustesse.

Nous étudions dans la suite :

	* Les **array** - container à taille fixe avec mémoire contiguë
	* Les **vector** - dimension dynamique, contiguïté)
	* Les **map** - association par clé–valeur ordonnée et opérations garanties en *O(log n))* amortie.

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 std::array plutôt qu'un tableau (int T[10]) :

	* Les arrays sont des objets, ils peuvent donc être passés par copie ou par référence.
	* La fonction membre *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 *array*, vous devez :

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

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

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

	 
		Initialisation, "array<int, 3> a = {1, 2, 3};", 
		Initialisation, "array<int, 3> a {1, 2, 3};", 
		Initialisation, "array<int, 3> a({1, 2, 3});", 
		Initialisation, "array<int, 3> a = {};", Avec initialisation des valeurs : les numériques sont mis à zéro !
		Initialisation, "array<int, 3> a;", Sans initialisation
		Méthode,		"a.fill(value)", Initialise tous les éléments à la valeur donnée
		Méthode,		"a.at(i)", Retourne une référence vers le i-ème élément AVEC bound-checking
		Méthode,		"a[i]", Retourne une référence vers le i-ème élément SANS bound-checking
		Méthode,		a.size(), Retourne le nombre d'éléments
		Méthode,		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 *at(i)* ou *[i]* sont identiques en tout point.
	*	:quiz:`{"type":"TF","answer":"T"}` La syntaxe : *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 *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 *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 *#include <vector>*  en début de programme
	* En l'absence de : *using namespace std*, vous devez écrire std::array


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

	* Si *n < size()* alors les derniers éléments sont détruits.
	* Si *n = size()* aucun effet.
	* Si *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 *resize()* et *reserve()* ainsi que *size()* et *capacity()*. Une clarification s'impose ! Un objet *vector* alloue une zone mémoire servant de buffer. La mécanique interne du *vector* fait en sorte que la taille de ce buffer soit supérieure au nombre d'éléments stockés. La méthode **reserve()** permet de fixer la taille de ce buffer et **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 *vector*.  	


Quizzz
======

.. quiz:: vectorrr
	:title: Vector
		

	*	:quiz:`{"type":"TF","answer":"F"}` La fonction *pop_back* insère un élément en fin.
	*	:quiz:`{"type":"TF","answer":"F"}` La syntaxe *at(i)* ou *[i]* sont identiques en tout point.
	*	:quiz:`{"type":"TF","answer":"T"}` La fonction *size* retourne le nombre d'éléments.
	*	:quiz:`{"type":"TF","answer":"F"}` La syntaxe : *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 (value) à une clé (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 *vector*, 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
		

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


Parcours
========

.. warning:: Les présentations ci-dessous sont valables pour un *array* comme pour un *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
		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 *for* retourne un objet dont :

   * La variable *first* correspond à la clé
   * La variable *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



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

.. note:: Un effort de simplification a été fait dans ce cours relativement aux syntaxes présentées pour les itérateurs. Cependant, lorsque vous trouverez des informations sur internet, certains auteurs pourront fournir un code beaucoup plus difficile à lire, il faut le savoir. 


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


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


La norme de la Standard Template Library (STL) n'impose aucune implémentation particulière. Elle se limite à spécifier les signatures des fonctions membres ainsi que, le cas échéant, les complexités algorithmiques de certaines fonctions : temps constant, logarithmique ou linéaire amorti. Par conséquent, les conteneurs définis par la STL peuvent, en interne, recourir à des mécanismes variés, par exemple l’utilisation d’entiers ou de pointeurs pour l’indexation des données.
Il convient également de rappeler que plusieurs implémentations de la STL coexistent :

	* libstdc++ :distribuée avec GCC et appréciée pour sa large compatibilité avec différentes architectures 
	* LLVM libc++ : associée à Clang, caractérisée par sa légèreté et sa conception modulaire 
	* Microsoft STL : intégrée à Visual Studio et optimisée pour les environnements Windows ;
	* Des implémentations internes ou adaptées : développées par certaines entreprises afin de répondre à des besoins spécifiques, notamment dans le domaine des consoles de jeu ou du développement embarqué.

Quelle que soit la structure de données ou l’implémentation retenue, la nécessité d’une abstraction pour l’accès et l’indexation des éléments s’est imposée : on parle des itérateurs **iterator**. Cependant, la syntaxe des itérateurs peut surprendre. On l'aime, on ne l'aime pas, mais dans tous les cas, il faut savoir les utiliser.


Les itérateurs remplacent ainsi les indices  :

   * begin() : retourne un itérateur positionné sur le premier élément.
   * end() : retourne un itérateur positionné a fin du container : un élément fictif placé après le dernier élément.
   * \*it : si *it* est un itérateur ; *\*it* est une référence vers l'élément désigné par cet itérateur.

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



.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 5> arr = {1, 2, 3, 4, 5};
		
		std::cout << *arr.begin() << std::endl;   // prints the first element
		*arr.begin() = 9;                         // modifies the first element
		for(int v : arr) std::cout << v << " ";   // prints the list
	}  
	
	>> 1
	>> 9 2 3 4 5

	
.. note:: Un itérateur permet un accès en lecture/écriture. Pour un accès en mode read-only, le langage fournit des const iterator ainsi que les méthodes  *cbegin()* et *cend()*.


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


Le type des itérateurs est assez long à écrire : *array<T, N>::iterator*.
Ainsi, on préfère utiliser le mot-clef **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 *begin()+1* désigne un itérateur associé à l'élément suivant.
Voici quelques exemples :


.. code-block:: cpp

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

	int main()
	{
		vector<int> L = {2,3,4};
		for (int v : L) cout << v << endl;
		
		L.erase(L.begin()+1);   // removes the 2nd element
		for (int v : L) cout << v << endl;
		
		L.insert(L.begin()+1, 8); // inserts 8 at the 2nd position
		for (int v : L) cout << v << endl;
	}
	>> 2 3 4
	>> 2 4          // L.erase(L.begin()+1);
	>> 2 8 4        // L.insert(L.begin()+1,8);

 

.. raw:: html

   <style>
   .wy-table-responsive table.wrap td,
   .wy-table-responsive table.wrap th { white-space: normal !important; word-break: break-word; overflow-wrap: anywhere; }
   .wy-table-responsive table.wrap code { white-space: pre-wrap; }
   </style>  




Travail à rendre sur Github Classroom
=====================================


Exercice 1
----------

	* Créez un fichier nommé *6_STL_basic.cpp*

	* A partir de l'exemple ci-dessous, effectuez les actions demandées.
	
	* Uploadez le fichier  sur votre github

.. code-block:: cpp

	#include <iostream>
	#include <vector>
	#include <algorithm> 
	#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, 7, 9, 4, 3, 3, 3, 3, 9, 5, 9};
		vector<int> t = { 9, 4, 3 };
		vector<int> z = { 1, 3, 5 };
	}

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

	* - Opération
	  - Description
	* - *int count(first, last, value)*
	  - Comptez le nombre d'apparitions du chiffre 9 dans le vector
	* - *iterator min_element(first,last)*
	  - Affichez la plus petite valeur du vector
	* - *T accumulate(first,last,T initvalue)*
	  - Calculez la somme des éléments de *v*
	* - *iterator find(first, last, value)* 
	  - Recherchez la valeur 4 et remplacez la par 8 - *find* returns an iterator
	* - *bool equal(first1,last1,first2)*
	  - Vérifiez si les 3 premiers éléments de *v* sont identiques à ceux de *z*
 

Exercice 2
----------

	* Créez un fichier nommé *6_STL_arrangement.cpp*

	* A partir de l'exemple ci-dessous, ajoutez les fonctions documentées ci-dessous pour obtenir la sortie suivante :
	
		.. image:: resultat1.png
	

	* Uploadez le fichier  sur votre github



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

   * - Opération
     - Description
   * - *fill(first,last,value)*
     - Assigne la valeur *value* à chaque élément de l’intervalle *[first, last)*.
   * - *fill_n(first,n,value)*
     - Assigne 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*.
   * - *shuffle(first,last,rng)*
     - Réorganise aléatoirement les éléments dans l’intervalle *[first, last)* en utilisant le générateur de nombres aléatoires *rng*.
   * - *rotate(first,middle,last)*
     - Effectue une rotation à gauche des éléments dans l’intervalle *[first, last)*, de sorte que l’élément pointé par *middle* devienne le premier de la séquence.
   * - *reverse(first,last)*
     - Inverse l’ordre des éléments dans l’intervalle *[first, last)*.



Exercice 3
----------

Nous allons présenter plusieurs algorithmes de la STL fonctionnant uniquement sur des listes triées.


	.. warning:: Si l'on prend l'exemple de la fusion de deux vectors triés, l'algorithme merge a pour objectif de construire un nouveau vector résultat. Dans ce genre de cas, la STL souhaite que l'on initialise la taille du vector cible à sa taille finale, ceci AVANT l'appel du merge, ce qui est contraignant. Cependant, il est possible d'effectuer la fusion vers vector vide en utilisant la syntaxe *back_inserter(vector_destination)*.


	* Créez un fichier nommé *6_STL_sorted.cpp*

	* A partir de l'exemple ci-dessous, effectuez les actions demandées.
	
	* Uploadez le fichier  sur votre github


.. 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);
	}
 

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

	* - Opération
	  - Description
	* - *merge(first1,last1,first2,last2,back_inserter(first3))*
	  - Fusionnez le contenu des deux vectors dans un nouveau vector, les doublons seront préservés
	* - *bool is_sorted(first,last)*
	  - Vérifiez si le nouveau vector est bien trié
	* - *size()*
	  - Affichez le nombre d'éléments du nouveau vector
	* - *set_union(start1,end1,start2,end2,back_inserter(out1))*
	  - Créez un  vector qui correspond à l'union ensembliste  de *v* et *w*
	* - *set_intersection(start1,end1,start2,end2,back_inserter(out1))*
	  - Créez un  vector qui correspond à l'intersection ensembliste de *v* et *w*
	* - *iota(start,end,val)*
	  - Initialisez les valeurs de la liste *z* de 1 à 1000000
	* - *iterator lower_bound(first,last,val)*
	  - Grâce à une boucle, recherchez la position des valeurs 1 à N dans le vector. A votre avis, quelle est la complexité de l'algorithme de recherche ?