{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Sequence containers in C++ STL" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "La standard template library (STL) met en oeuvre certaines des structures de données vues dans ce chapitre sous forme de classes C++ génériques. \n", "\n", "Un résumé des classes et méthodes disponibles se trouve à http://www.cplusplus.com/reference/stl/ \n", "\n", "| Classe | Description |\n", "| :--- | :--- |\n", "| [`std::array`](http://www.cplusplus.com/reference/array/array/)
| tableau de taille fixe de `N` éléments de type `T` |\n", "| [`std::vector`](http://www.cplusplus.com/reference/vector/vector/) | tableau de taille et capacité variables |\n", "| [`std::list`](http://www.cplusplus.com/reference/list/list/) | liste doublement chainée |\n", "| [`std::forward_list`](http://www.cplusplus.com/reference/forward_list/forward_list/) | liste simplement chainée |\n", "| [`std::deque`](http://www.cplusplus.com/reference/deque/deque/) | double-ended queue, mise en oeuvre avec un tableau redimensionable de tableaux de capacité fixe |\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## `std::array`\n", "\n", "Disponible depuis C++11, elle fournit un interface semblable aux autres conteneurs pour des tableaux pour lesquels on aurait précédemment utilisé des tableaux de type C. \n", "\n", "\n", "| Méthode | Description |\n", "| :----- | :--- |\n", "| `size()`
`max_size()` | retournent `N` |\n", "| `empty()` | retourne `N == 0` |\n", "| `operator[i]`| **référence** à l'élément d'indice `i` |\n", "| `at(i)` | idem, mais lève une exception si `i` n'est pas un indice valable |\n", "| `front()` | **référence** à l'élément en tête :`[0]` |\n", "| `back()` | **référence** à l'élément en queue: `[N-1]` |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "| Méthode | Description |\n", "| :----- | :--- |\n", "| `==`
`!=` | opérateurs d'(in)égalité |\n", "| `<` , `<=`
`>`, `>=` | opérateurs de comparaison lexicographique |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Elle fournit aussi un interface par itérateurs\n", "\n", "| Méthode | Description |\n", "| :----- | :--- |\n", "| `begin()` → `end()` | itère par indice croissant |\n", "| `cbegin()` → `cend()` | idem, mais seulement en lecture |\n", "| `rbegin()` → `rend()` | itère par indice décroissant |\n", "| `crbegin()` → `crend()` | idem, mais seulement en lecture |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Les itérateurs de `std::array` stockent l'adresse en mémoire de l'élément courant. Ce sont des [random access iterators](http://www.cplusplus.com/reference/iterator/RandomAccessIterator/). \n", "\n", "| Expression | Propriété |\n", "| :----- | :--- |\n", "| `X a;`
`X b(a);`
`b = a;` | Constructible par défaut et par copie, assignable et destructible |\n", "| `a == b;`
`a != b;` | Comparable (itère sur le même élément) |\n", "| `*a;`
`a->m;` | Déréférençable à droite |\n", "| `*a = t;` | Déréférençable à gauche (mutable) |\n", "| `++a;`
`a++;`
`*a++;` | Incrémentable: passe à l'élément suivant |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "| Expression | Propriété |\n", "| :----- | :--- |\n", "| `--a;`
`a--;`
`*a--;` | Décrémentable: passe à l'élément précédent |\n", "| `a < b;`
`a <= b`
`a > b`
`a >= b` | Comparable: devant ou derrière dans la séquence? |\n", "| `a + n;`
`n + a;`
`a - n;`
`a - b` | Décalable: passe `n` éléments plus loin |\n", "| `a += n;`
`a -= n` | Décalable et assignable |\n", "| `a[n]` | Décalable et déréférençable |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## `std::vector` \n", "\n", "Tableau de taille et capacité variables, il offre tout ce que `std::array` est capable d'offrir, mais y ajoute les méthodes d'insertion et de suppression d'éléments\n", "\n", "| Méthode | Description |\n", "| :----- | :--- |\n", "| `push_back(t)`
`pop_back()` | insère ou supprime un élément en queue |\n", "| `insert(pos,...)` | insère un (ou +) élément *devant* `pos` |\n", "| `erase(pos)`
`erase(first,last)` | supprime un ou plusieurs éléments | \n", "| `emplace_back(...)`
`emplace(pos,...)` | comme `push_back` et `insert` mais l'objet est construit en place |\n", "| `clear()` | supprime tous les éléments |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Il y ajoute aussi des méthodes de gestion des taille et capacité\n", "\n", "| Méthode | Description |\n", "| :----- | :--- |\n", "| `size()` | nombre d'éléments stockés |\n", "| `empty()` | retourne `size() == 0` |\n", "| `capacity()` | nombres d'éléments stockables dans la mémoire allouée |\n", "| `max_size()` | capacité maximale selon les limites du système |\n", "| `resize(s,...)` | change la taille, en construisant ou détruisant des éléments |\n", "| `reserve(s)` | augmente si nécessaire la capacité. ne change pas la taille | \n", "| `shrink_to_fit() `| diminue si nécessaire la capacité pour qu'elle égale la taille |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "L'insertion / suppression en queue est efficace. $\\Theta(1)$ en moyenne.\n", "\n", "L'insertion / suppression en autre position est chère $\\Theta(n-pos)$ puisqu'il faut déplacer vers la droite / gauche tous les éléments à partir de `pos`. \n", "\n", "La réallocation est chère - $\\Theta(n)$ - mais suffisamment rare pour ne pas impacter les insertions en moyenne. Mais c'est le facteur dominant si l'on évalue le pire des cas. \n", "\n", "L'allocation de mémoire et la construction des éléments, la destruction des éléments et la désallocation de la mémoire sont effectués séparément. Les éléments d'indices `[size(),capacity()[` sont alloués mais pas construits. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Les itérateurs fournis sont les mêmes que pour `std::array`. \n", "\n", "Il y a néanmoins une différence majeure. Ils peuvent être **invalidés**\n", "\n", "Un `std::vector::iterator` connait \n", "\n", "* l'addresse en mémoire de l'éléments qu'il itère\n", "* mais pas la structure de donnée du vecteur\n", "\n", "Toute opération qui change la capacité et réalloue donc la mémoire utilisée invalide tous les itérateurs. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## `std::list` \n", "\n", "met en oeuvre une liste doublement chainée. Elle n'offre donc pas \n", "\n", "| Expression | Description |\n", "| :----- | :--- |\n", "| `operator[i]`
`at(i)` | les opérations d'accès indexé |\n", "| `a+n; n+a;`
`a-n; a-b` | les propriétés de décalage pour ses itérateurs |\n", "| `a `a>b; a>=b` | les opérateurs de comparaisons pour ses itérateurs |\n", "\n", "Elle utilise par contre un attribut taille, ce qui lui permet d'offrir les mêmes possibilités de gestion de la taille que `std::vector`, mais la notion de capacité n'a pas ici lieu d'être." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Par contre, elle permet d'insérer et supprimer en tête, en queue ou en position quelconque connue en temps constant. \n", "\n", "| Méthode | Description |\n", "| :----- | :--- |\n", "| `push_back(t)`
`pop_back()` | insère ou supprime un élément en queue |\n", "| `push_front(t)`
`pop_front()` | insère ou supprime un élément en tête |\n", "| `insert(pos,...)` | insère des éléments *devant* l'itérateur `pos` |\n", "| `erase(pos)`
`erase(first,last)` | supprime des éléments et retourne un itérateur vers l'élément suivant le dernier supprimé | \n", "| `emplace(pos,...)`
`emplace_front()`
`emplace_back()` | comme `push_back`, `push_front()` et `insert` mais l'objet est construit en place |\n", "| `clear()` | supprime tous les éléments |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Elle offre par ailleurs des méthodes spécifiques aux listes \n", "\n", "| Méthode | Description |\n", "| :----- | :--- |\n", "| `splice(...)` | opération d'épissure |\n", "| `sort()` | tri stable en place en $\\Theta(n \\log n)$ |\n", "| `merge(...)` | opération de fusion du tri fusion | \n", "| `remove(...)`
`remove_if(...)`
`unique()` | suppression d'éléments selon divers critères |\n", "| `reverse()` | inversion tête à queue de la liste |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Les itérateurs fournis sont des [itérateurs bi-directionnels](http://www.cplusplus.com/reference/iterator/BidirectionalIterator/), qui ne fournissent donc aucune opération de décalage ou de comparaison autre que l'égalité. \n", "\n", "Un `std::list::iterator` stocke un pointeur vers le maillon de l'élément qu'il itère, mais ne connait pas l'objet `list` auquel l'élément appartient. \n", "\n", "Il reste valide tant que l'élément est dans la liste, mais \n", "\n", "* sa position dans la liste peut varier (après `list::sort()` par exemple)\n", "* il peut même itérer une autre liste après `splice` ou `merge`. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## `std::forward_list` \n", "\n", "disponible depuis C++11, elle met en oeuvre une liste simplement chainée. Par rapport à `std::list`, on perd \n", "\n", "| Expression | Description |\n", "| :----- | :--- |\n", "| `push_back(t)`
`pop_back()`
`back()` | les opérations en queue |\n", "| `rbegin()`
`rend()`
... | les itérateurs inversés |\n", "| `--a;`
`a--;`
`*a--;` | la décrémentation des itérateurs | \n", "| `size()` | la taille, qui n'est pas stockée |" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Par ailleurs, pour insérer, déplacer ou supprimer un élément, il est indispensable de connaitre l'élément précédent, qui n'est pas disponible depuis l'élément courant. Toute cette partie de l'API est donc modifiée pour que le paramètre à fournir soit l'élément précédent. \n", "\n", "| Expression | Description |\n", "| :----- | :--- |\n", "| `insert_after(it,t)`
`emplace_after(it,...)` | insertion après un élément |\n", "| `erase_after(it)`| suppression de l'élément suivant |\n", "| `splice_after(it,...)` | épissure derrière un élément | \n", "| `before_begin()` | itérateur *avant* l'élément de tête | " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Les itérateurs fournis sont des [itérateurs forward](http://www.cplusplus.com/reference/iterator/ForwardIterator/), qui ne fournissent donc aucune opération de décalage ou de comparaison autre que l'égalité, ni de décrémentation.\n", "\n", "Un `std::forward_list::iterator` stocke un pointeur vers le maillon de l'élément qu'il itère, mais ne connait pas l'objet `forward_list` auquel l'élément appartient, comme précédemment. \n", "\n", "Le fait que les opérations importantes prennent en paramètre un itérateur sur l'élément précédent a effet marqué sur la manière d'utiliser ceux-ci. Comparons le code de deux fonctions qui suppriment des éléments d'une `list` et d'une `forward_list`" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "#include \n", "#include \n", "#include \n", "#include " ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [], "source": [ "template < typename T > \n", "void supprimer(std::list& L, T val) \n", "{\n", " for(auto it = L.begin(); it != L.end();)\n", " {\n", " if(*it == val) it = L.erase(it);\n", " else ++it;\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "template < typename T >\n", "void supprimer(std::forward_list& L, T val)\n", "{\n", " auto prec = L.before_begin();\n", " for(auto it = next(prec); it != L.end();)\n", " {\n", " if(*it == val) L.erase_after(prec);\n", " else ++prec;\n", " it = next(prec);\n", " }\n", "}" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "Notons que la même fonction s'écrit ainsi pour les `std::vector`. Elle est efficace si `T::operator=(T&&)` est efficace." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "slideshow": { "slide_type": "-" } }, "outputs": [], "source": [ "template < typename T >\n", "void supprimer(std::vector& V, T val)\n", "{\n", " auto i_write = V.begin();\n", " for( auto i_read = V.begin(); i_read != V.end(); ++i_read )\n", " {\n", " if(*i_read != val) {\n", " *i_write = std::move(*i_read);\n", " ++i_write;\n", " }\n", " }\n", " V.erase(i_write,V.end());\n", "}" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Test de correction des fonction ci-dessus." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "template \n", "void display(I first, I last) {\n", " while(first != last) {\n", " std::cout << *first << \" \";\n", " ++first;\n", " }\n", " std::cout << std::endl; \n", "}" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 1 2 3 2 1 0 0 1 2 \n", "1 2 3 2 1 1 2 \n" ] } ], "source": [ "std::vector V { 0, 1, 2, 3, 2, 1, 0, 0, 1, 2 } ;\n", "std::list L(V.begin(),V.end());\n", "std::forward_list F(V.begin(),V.end());\n", "\n", "display(F.begin(),F.end()); supprimer(F,0); display(F.begin(),F.end()); " ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 1 2 3 2 1 0 0 1 2 \n", "1 2 3 2 1 1 2 \n" ] } ], "source": [ "display(L.begin(),L.end()); supprimer(L,0); display(L.begin(),L.end()); " ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 1 2 3 2 1 0 0 1 2 \n", "1 2 3 2 1 1 2 \n" ] } ], "source": [ "display(V.begin(),V.end()); supprimer(V,0); display(V.begin(),V.end()); " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## `std::deque` \n", "\n", "met en oeuvre une queue à deux bouts. Il fournit essentiellement les mêmes fonctionalités que `std::vector`, mais y ajoute \n", "\n", "| Méthode | Description |\n", "| :----- | :--- |\n", "| `push_front(t)`
`emplace_front(...)` | insère un élément en tête |\n", "| `pop_front()` | supprime un élément en tête |\n", "\n", "Par ailleurs, il n'a pas de méthode `capacity()`. Par rapport à `std::vector` \n", "\n", "* l'accès aux données est un peu plus lent\n", "* les opérations en tête sont $\\Theta(1)$ en moyenne, ce qui est nettement mieux\n", "* les opérations de réallocation sont plus légères" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Itérateurs\n", "\n", "Par ailleurs, vous lirez avec intérêt http://www.cplusplus.com/reference/iterator/ , qui compare les différents types d'itérateurs du C++. \n", "\n", "Cette librairie inclut aussi un certain nombre de fonctions utiles quand on travaille avec ces itérateurs\n", "\n", "* `begin`, `end`\n", "* `prev`, `next`\n", "* `advance`\n", "* `distance` \n", "\n", "Nous ne traitons pas dans ce cours des `input` et `output iterators`, tels que `front_inserter`, `back_inserter` ou `inserter` par exemple. Libre à vous d'en lire la documentation" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "\n", "\n", "\n", " \n", "\n", "
\n", " \n", " \n", "

\n", " ASD1 Notebooks on GitHub.io\n", "

\n", "

\n", "© Olivier Cuisenaire, 2018

\n", "
" ] }, { "cell_type": "raw", "metadata": {}, "source": [ "" ] } ], "metadata": { "celltoolbar": "Slideshow", "kernelspec": { "display_name": "C++14", "language": "C++14", "name": "xeus-cling-cpp14" }, "language_info": { "codemirror_mode": "text/x-c++src", "file_extension": ".cpp", "mimetype": "text/x-c++src", "name": "c++", "version": "-std=c++14" } }, "nbformat": 4, "nbformat_minor": 2 }