La bibliotheque standard C++ : Les conteneurs et algorithmes

class: middle
layout: true
---
class: center, middle, inverse

# La bibliothèque standard C++

## Les conteneurs et algorithmes

.right-column[
.footnote[Par **Loïc Hamot**]
]

---
.left-column[
  ## Histoire de la stdlib
  ### Histoire de la STL
]
.right-column[
1. L'architecture de la bibliothèque STL créée en grande partie par Alexander Stepanov. 
2. En 1979, premières idées de programmation générique.
3. Bibliothèque Ada, disponible dès 1987, dédiée aux calculs utilisant des listes.
4. Recherche au Laboratoire AT&T de Bell, puis au Centre de Recherche Hewlett-Packard.
5. Stepanov présenta ses idées lors d'une conférence du comité ANSI/ISO C++, en novembre 1993. 
6. Approuvée définitivement par le comité ANSI/ISO C++ en juillet 1994. 
]
---
.left-column[
## Histoire de la stdlib
### Histoire de la STL
### stdlib ou STL ?
]
.right-column[
#### Etait dans la STL:

- Les algorithmes
- Les conteneurs

#### La bibliothèque standard
- La bibliothèque standard à été construite autour de la STL.
- Aujourd'hui la STL n'existe plus dans la norme C++. 
- Bien que certaines bibliothèques standard conservent la dénomination STL (STL Port), il est préférable de parler de bibliothèque standard, ou stdlib.
]
---
class: center, middle, inverse
##Le concept d’itérateur
---
.left-column[
##Le concept d’itérateur
### C'est quoi un itérateur?
]
.right-column[
- Il permet de parcourir un conteneur.
- Ils sont généralement utilisés par paires : Un pour parcourir, un qui indique la fin.
- L'itérateur de fin est en fait un itérateur *"past the end"*. Il se situe juste après le dernier élément.
- Il permet l’interaction des algorithmes et des conteneurs.
- Il permet l'application de n’importe quel algorithme à n’importe quel conteneur.
- Il évite donc d’écrire C * A algorithmes
- Quand l'itérateur de début est égale à celui de fin, c'est que le range est vide.

```C++
while(iter != iter_end) {
 std::cout << *iter;
 ++iter;
}
```
]
---
.left-column[
##Le concept d’itérateur
### C'est quoi un itérateur?
### Les catégories d'itérateurs
]
.right-column[
<table style="font-size: 0.75em;">
<tr><th>category</th><th>properties</th><th>valid expressions</th></tr>
<tr><td rowspan="2">all categories</td><td>copy-constructible, copy-assignable and destructible</td><td><code>X b(a); b = a;</code></td></tr>
<tr><td>Can be incremented</td><td><code>++a, a++</code></td></tr>
<tr><td rowspan="2">Input</td><td>Supports equality/inequality comparisons</td><td><code>a == b; a != b;</code></td></tr>
<tr><td>Can be dereferenced as an rvalue</td><td><code>*a; a->m;</code></td></tr>
<tr><td>Output</td><td>Can be dereferenced as an lvalue (only for mutable iterator types)</td><td><code>*a=t; *a++=t;</code></td></tr>
<tr><td rowspan="2">Forward (+I+O)</td><td>default-constructible</td><td><code>X a; X();</code></td></tr>
<tr><td>Multi-pass: neither dereferencing nor incrementing affects dereferenceability</td><td><code>{ b=a; *a++; *b; }</code> </td></tr>
<tr><td>Bidirectional (+F)</td><td>Can be decremented</td><td><code>--a; a--; *a--;</code></td></tr>
<tr><td rowspan="4">Random Access (+B)</td><td>Supports arithmetic operators <tt>+</tt> and <tt>-</tt></td><td><code>a + n; n + a; a - n; a - b;</code></td></tr>
<tr><td>Supports inequality comparisons (<tt><</tt>, <tt>></tt>, <tt><=</tt> and <tt>>=</tt>) between iterators</td><td><code>a < b; a > b; a <= b; a >= b;</code></td></tr>
<tr><td>Supports compound assignment operations <tt>+=</tt> and <tt>-=</tt></td><td><code>a += n a -= n</code></td></tr>
<tr><td>Supports offset dereference operator (<tt>[]</tt>)</td><td><code>a[n]</code></td></tr>
</table>
]
---
class: center, middle, inverse
##Le concept de conteneur
---
.left-column[
##Le concept de conteneur
]
.right-column[
- Ils peuvent contenir des éléments copiables ou *movables*
- La plupart ont une politique d'allocation
- Ils ne peuvent contenir des éléments constants
- Les algorithmes travaillent avec des itérateurs et non des conteneurs.
- Du point de vue des algorithmes, tout ce qui peut fournir un itérateur de début et de fin est un conteneur.
- Dans le C++98, on utilisait la méthode membre begin et end pour avoir les itérateurs.

```C++
for(auto iter = c.begin(), iter_end = c.end(); 
 iter != iter_end; 
 ++iter)
 std::cout << *iter;
```
]
---
.left-column[
##Le concept de conteneur
#### Avec C++11
]
.right-column[
- C++11 ajoute std::begin et std::end pour obtenir les itérateurs de début et de fin.

```C++
for(auto iter = begin(c), iter_end = end(c); 
 iter != iter_end; 
 ++iter)
 std::cout << *iter;
```
- C++11 ajoute "range-based for loop" qui utilise std::begin et std::end.

```C++
for(auto value: container)
 std::cout << *iter;
```
- Donc, depuis C++11, un conteneur C++ doit implémenter std::begin et std::end.
]
---
.left-column[
##Le concept de conteneur
#### Avec C++11
###Les catégorie de conteneurs
]
.right-column[
||
|---|---
|Container|Structure de donnée qui permet l’accès aux éléments par un itérateur
|Reversible|Utilise des itérateurs bidirectionnels
|AllocatorAware (C++11)|Utilise une politique l'allocation (std::allocator)
|Sequence|Stock les éléments dans l'ordre d'insertion
|Contiguous (C++17)|Ces éléments sont contigus en mémoire
|Associative|Associe une clé aux valeurs
|UnorderedAssociative (C++11)|Associe une clé aux valeurs, mais ne trie pas les élément
]
---
class: center, middle, inverse
##Quelques conteneurs
---
.left-column[
##Quelques conteneurs
###array
]
.right-column[
- Accès par index
- Taille fixe, défini à la compilation
- Éléments contigus en mémoire
- Random-access iterator
- Insertion/suppression impossible
- Allocation très rapide
- Très proche des tableaux statiques C, mais permet des vérifications à l’exécution.
- Permet des vérifications d'index à la compilation (std::get<X>)

```C++
#include <array>
#include <cassert>
int main() {
 std::array<int, 4> tab = {0, 1, 2, 3};
 assert(tab[1] == 1);
 assert(std::get<1>(tab) == 1);
}
```
]
---
.left-column[
##Quelques conteneurs
###array
###vector
]
.right-column[
- Conserve l'ordre d'insertion
- Accès par index
- Taille dynamique
- Utilise un **std::allocator**
- Éléments contigus en mémoire
- Random-access iterator
- Parfait pour insertion/suppression en fin
- C'est le conteneur par défaut

```C++
#include <vector>
#include <cassert>
int main() {
 std::vector<int> tab = {0, 1, 2, 3};
 tab.push_back(4);
 assert(tab[4] == 4);
 tab.pop_back();
 assert(tab.size() == 4);
}
```
]
---
.left-column[
##Quelques conteneurs
###array
###vector
###list
]
.right-column[
- Conserve l'ordre d'insertion
- Taille dynamique
- C'est une liste doublement chaînée. 
 - **std::forward_list** est simplement chaînée.
- Utilise un **std::allocator**
- Itérateur bidirectionnel 
 - forward pour **std::forward_list**
- Parfait pour insertion/suppression aléatoire
- Accès par index impossible

```C++
#include <list>
#include <iostream>
int main() {
 std::list<int> tab = {0, 2, 99, 3, 4};
 auto iter = std::begin(tab);
 ++iter; ++iter;
 tab.erase(iter);
 --iter;
 tab.insert(iter, 1);
 for(int i: tab)
 std::cout << i;
}
```
Va afficher:
>01234
]
---
.left-column[
##Quelques conteneurs
###array
###vector
###list
###unordered_set
]
.right-column[
- Implémente les concepts : **Container**, **AllocatorAwareContainer**, **UnorderedAssociativeContainer**
- Utilise généralement une table de hachage
- Permet de rechercher par valeur avec une complexité constante
- Insertions/suppressions aléatoires ont une complexité constante
- Idéal pour
 - Conteneur sans doublon
 - Test d'existence rapide
- La version **std::multiset** autorise les doublons
- La version **std::set** permet de trier les éléments.

```C++
#include <unordered_set>
#include <cassert>
int main() {
 std::unordered_set<int> set = {0, 1, 2, 3, 4};
 set.insert(18);
 assert(set.count(18) == 1);
 set.insert(18);
 assert(set.count(18) == 1);
}
```
]
---
.left-column[
##Quelques conteneurs
###array
###vector
###list
###unordered_set
###unordered_map
]
.right-column[
- Implémente les concepts : **Container**, **AllocatorAware**, **UnorderedAssociative**
- Utilise généralement une table de hachage
- Une clé est associée à chaque élément
- Rechercher par clé avec une complexité constante
- Insertion/suppression aléatoire avec complexité constante
- La version **(unordered_)multimap** autorise les doublons de clés
- La version **map** permet de trier les éléments par la clé.
- Usage : Conteneur associatif sans doublon de clé

```C++
#include <unordered_map>
#include <string>
#include <cassert>
int main() {
 std::unordered_map<std::string, int> colors = {
 {"Rouge", 0xFF0000}, 
 {"Vert", 0x00FF00}, 
 {"Bleu", 0x0000FF}};
 colors.emplace("Violet", 0xFF00FF);
 assert(colors["Violet"] == 0xFF00FF);
}
```
]
---
.left-column[
##Quelques conteneurs
###array
###vector
###list
###unordered_set
###unordered_map
###Adaptateurs
]
.right-column[
####std::stack
- Permet de limiter l'interface d'un conteneur de manière à ne pouvoir l'utiliser que comme une pile (LIFO)

```C++
#include <stack>
#include <vector>
#include <cassert>
int main() {
 std::stack<int, std::vector<int>> myStack;
 myStack.push(1);
 myStack.push(2);
 assert(myStack.top() == 2);
 myStack.pop();
 assert(myStack.top() == 1);
}
```
####std::queue
- Permet de limiter l'interface d'un conteneur de manière à ne pouvoir l'utiliser que comme une queue (FIFO)
]
---
.left-column[
##Quelques conteneurs
###array
###vector
###list
###unordered_set
###unordered_map
###Adaptateurs
###Conseils
]
.right-column[
- N'utilisez jamais un itérateur qui a été invalidé!
- L’opérateur [] ne vérifie pas l'index.
- Le comparateur (pour les **set**) doit être inférieur **strict**.
- N'utilisez pas de tableau **C**
- Ne stockez pas d'objets polymorphiques dans les conteneurs (ou utilisez des pointeurs(intelligents) )
- Un élément d'un conteneur doit être copiable ou *movable*
- Préférez les méthodes basées sur des *range* pour traiter des *range*. (ex: insert)
- Utilisez **std::vector** par défaut. 
 - Sinon, utilisez le conteneur approprié.
- Construisez les conteneurs avec la syntax **()** pour la taille et la syntax **{}** pour une liste d'élément.
- Évitez d'écrire inutilement du code non générique (**std::begin**, **c.empty()**)
- Utilisez **std::vector::data** (et **std::string::c_str** et **std::array::data**) pour passer des données à une API C.
- Pour un simple parcours : *"range-based for loop"*
- Utilisez **emplace** pour simplifier l'écriture
- Utilisez la méthode **shrink_to_fit** pour libérer la mémoire des **std::vector**
- En matière de performance, ne faites pas confiance à votre intuition : Mesurez.
]
---
class: center, middle, inverse
##Quelques algorithmes
---
.left-column[
##Quelques algorithmes
###std::fill
]
.right-column[
Rempli un range avec une valeur donnée.

```C++
#include <algorithm>
#include <vector>
#include <iostream>
int main(){
 std::vector<int> v
 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 std::fill(v.begin(), v.end(), -1);
 for (auto elem : v)
 std::cout << elem << " ";
}
```
Va afficher:

>-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
]
---
.left-column[
##Quelques algorithmes
###std::fill
###std::copy
]
.right-column[
Copie un range vers un autre.

```C++
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
 std::vector<int> in = 
 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 std::vector<int> out;
 std::copy(in.begin(), in.end(), 
 std::back_inserter(out));
 for(int i: out)
 std::cout << i;
}
```
Va afficher:
> 0123456789
]
---
.left-column[
##Quelques algorithmes
###std::fill
###std::copy
###std::find(_if)
]
.right-column[
- std::find : Trouve un élément qui a une valeur donnée, et retourne un itérateur sur celle-ci, ou un itérateur *"past-the-end"*
- std::find_if : Idem mais recherche avec un prédicat plutôt qu'une valeur
- std::find_if_not : Idem mais recherche une valeur pour laquelle le prédicat est faux

```C++
#include <iostream>
#include <algorithm>
#include <vector>
int main(){
 std::vector<int> v{0, 1, 2, 3, 4};
 auto iter = 
 std::find(std::begin(v), std::end(v), 3);
 if (iter != std::end(v))
 std::cout << "v contains: 3\n";
 else
 std::cout << "v does not contain: 3\n";
}
```
Va afficher:
>v contains: 3
]
---
.left-column[
##Quelques algorithmes
###std::fill
###std::copy
###std::find(_if)
###std::count(_if)
]
.right-column[
- std::count : Compte les éléments qui sont égaux à une valeur donnée
- std::count_if : Compte les éléments qui correspondent à un prédicat donné

```C++
#include <algorithm>
#include <iostream>
#include <vector>
int main(){
 std::vector<int> v = 
 { 1, 2, 3, 4, 4, 3, 7, 8, 9, 10 };
 int num_items1 = 
 std::count_if(v.begin(), v.end(), 
 [](int i) {return i % 3 == 0;});
 std::cout << "number divisible by three: " 
 << num_items1 << '\n';
}
```
Va afficher:
>number divisible by three: 3
]
---
.left-column[
##Quelques algorithmes
###std::fill
###std::copy
###std::find(_if)
###std::count(_if)
###std::transform
]
.right-column[
- Applique une transformation à chaque élément d'un range, et les insère dans un autre range.
- Une version prend deux range en entrée.
- Le range de sortie peut être un range d'entrée

```C++
#include <algorithm>
#include <iostream>
#include <vector>
int main(){
 std::vector<int> a{ 1, 2, 3, 4, 5, 6, 7, 8, 9};
 std::vector<int> b{ 1, 2, 3, 4, 5, 6, 7, 8, 9};
 std::vector<int> c;
 std::transform(std::begin(a), std::end(a),
 std::begin(b),
 std::back_inserter(c),
 [](int i, int j){return i * j;});
 for(int i: c)
 std::cout <1 4 9 16 25 36 49 64 81 
]
---
.left-column[
##Quelques algorithmes
###std::fill
###std::copy
###std::find(_if)
###std::count(_if)
###std::transform
###std::accumulate
]
.right-column[
- Calcule la somme de la valeur donnée avec tout les éléments dans le range.
- Une seconde version peut utiliser un autre opérateur que plus.

```C++
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
int main() {
 std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};
 int sum = std::accumulate(v.begin(), v.end(), 0);
 int prod = std::accumulate(
 v.begin(), v.end(), 1, 
 [](int a, int b){return a * b;});
 std::string s = std::accumulate(
 std::begin(v), std::end(v), std::string{}, 
 [](std::string const& a, int b) {
 return a + std::to_string(b);
 });
 std::cout 
 << "sum: " << sum //sum: 45
 << "\nproduct: " << prod //product: 362880
 << "\nstr: " << s << '\n'; //str: 123456789
}
```
]
---
.left-column[
##Quelques algorithmes
###std::fill
###std::copy
###std::find(_if)
###std::count(_if)
###std::transform
###std::accumulate
###std::sort
]
.right-column[
- Trie les éléments du range dans l'ordre croissant
- Les éléments sont comparés en utilisant l'opérateur **<**
- On peut aussi passer un comparateur personnalisé

```C++
#include <algorithm>
#include <array>
#include <iostream>
int main(){
 std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; 
 std::sort(s.begin(), s.end()); // sort using the default operator<
 for (int a : s)
 std::cout << a << " ";
 std::cout << '\n';
 std::sort(s.begin(), s.end(), [](int a, int b) {return b < a;});
 for (int a : s)
 std::cout << a << " ";
}
```
Va afficher:
>0 1 2 3 4 5 6 7 8 9 
>9 8 7 6 5 4 3 2 1 0 
]
---
.left-column[
##Quelques algorithmes
###std::fill std::copy std::find(_if) std::count(_if) std::transform std::accumulate std::sort
###std::remove(_if)
]
.right-column[
- Place les éléments correspondant à la valeur ou au prédicat à la fin.
- Retourne un itérateur *"past-the-end"* du nouveau range. (Formé des éléments que l'on garde)
- Souvent utilisé avec **erase** pour réduire le conteneur.

```C++
#include <algorithm>
#include <string>
#include <iostream>
#include <cctype>
int main(){
 std::string s1 = "Text with some spaces";
 s1.erase(
 std::remove(std::begin(s1),std::end(s1), ' '), 
 std::end(s1));
 std::string s2 = 
 "Text\n with\tsome \t whitespaces\n\n";
 s2.erase(
 std::remove_if(std::begin(s2), std::end(s2),
 [](char x){return std::isspace(x);}),
 s2.end());
 std::cout << s1 << '\n' << s2 << '\n';
}
```
Va afficher:

>Textwithsomespaces

>Textwithsomewhitespaces
]
---
.left-column[
##Quelques algorithmes
###std::fill std::copy std::find(_if) std::count(_if) std::transform std::accumulate std::sort std::remove(_if)
###Conseils
]
.right-column[
- N'oubliez pas que l'itérateur de fin (**std::end**) pointe juste après le dernier élément.
- Les prédicats doivent être des fonctions pures
- Préférez utiliser des algorithmes plutôt que des boucles écrites à la main.
- Utilisez l'idiom erase-remove pour supprimer des éléments d'un conteneur
- Utilisez l’algorithme de recherche approprié
- Utilisez l'algorithme de tri approprié
- Préférez les foncteurs aux fonctions pour passer en argument d'un algorithme
]
---
.left-column[
##Références
]
.right-column[
###[www.cppreference.com](http://www.cppreference.com)
###[www.cplusplus.com](http://www.cplusplus.com)
###*Le language C++*
##### De Bjarne Stroustrup
###*C++ Coding Standard*
####101 Rules, Guidelines, and Best Practices
##### De Herb Sutter, Andrei Alexandrescu
]
---
class: center, middle, inverse
##Merci 
### et utilisez des algorithmes!!