Sequence containers in C++ STL¶

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.

Un résumé des classes et méthodes disponibles se trouve à http://www.cplusplus.com/reference/stl/

Classe	Description
`std::array<T,N>`	tableau de taille fixe de `N` éléments de type `T`
`std::vector<T>`	tableau de taille et capacité variables
`std::list<T>`	liste doublement chainée
`std::forward_list<T>`	liste simplement chainée
`std::deque<T,N>`	double-ended queue, mise en oeuvre avec un tableau redimensionable de tableaux de capacité fixe

`std::array<T,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.

Méthode	Description
`size()` `max_size()`	retournent `N`
`empty()`	retourne `N == 0`
`operator[i]`	référence à l'élément d'indice `i`
`at(i)`	idem, mais lève une exception si `i` n'est pas un indice valable
`front()`	référence à l'élément en tête :`[0]`
`back()`	référence à l'élément en queue: `[N-1]`

Méthode	Description
`==` `!=`	opérateurs d'(in)égalité
`<` , `<=` `>`, `>=`	opérateurs de comparaison lexicographique

Elle fournit aussi un interface par itérateurs

Méthode	Description
`begin()` → `end()`	itère par indice croissant
`cbegin()` → `cend()`	idem, mais seulement en lecture
`rbegin()` → `rend()`	itère par indice décroissant
`crbegin()` → `crend()`	idem, mais seulement en lecture

Les itérateurs de std::array<T,N> stockent l'adresse en mémoire de l'élément courant. Ce sont des random access iterators.

Expression	Propriété
`X a;` `X b(a);` `b = a;`	Constructible par défaut et par copie, assignable et destructible
`a == b;` `a != b;`	Comparable (itère sur le même élément)
`*a;` `a->m;`	Déréférençable à droite
`*a = t;`	Déréférençable à gauche (mutable)
`++a;` `a++;` `*a++;`	Incrémentable: passe à l'élément suivant

Expression	Propriété
`--a;` `a--;` `*a--;`	Décrémentable: passe à l'élément précédent
`a < b;` `a <= b` `a > b` `a >= b`	Comparable: devant ou derrière dans la séquence?
`a + n;` `n + a;` `a - n;` `a - b`	Décalable: passe `n` éléments plus loin
`a += n;` `a -= n`	Décalable et assignable
`a[n]`	Décalable et déréférençable

`std::vector<T>`¶

Tableau de taille et capacité variables, il offre tout ce que std::array<T,N> est capable d'offrir, mais y ajoute les méthodes d'insertion et de suppression d'éléments

Méthode	Description
`push_back(t)` `pop_back()`	insère ou supprime un élément en queue
`insert(pos,...)`	insère un (ou +) élément devant `pos`
`erase(pos)` `erase(first,last)`	supprime un ou plusieurs éléments
`emplace_back(...)` `emplace(pos,...)`	comme `push_back` et `insert` mais l'objet est construit en place
`clear()`	supprime tous les éléments

Il y ajoute aussi des méthodes de gestion des taille et capacité

Méthode	Description
`size()`	nombre d'éléments stockés
`empty()`	retourne `size() == 0`
`capacity()`	nombres d'éléments stockables dans la mémoire allouée
`max_size()`	capacité maximale selon les limites du système
`resize(s,...)`	change la taille, en construisant ou détruisant des éléments
`reserve(s)`	augmente si nécessaire la capacité. ne change pas la taille
`shrink_to_fit()`	diminue si nécessaire la capacité pour qu'elle égale la taille

L'insertion / suppression en queue est efficace. $\Theta(1)$ en moyenne.

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.

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.

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.

Les itérateurs fournis sont les mêmes que pour std::array<T,N>.

Il y a néanmoins une différence majeure. Ils peuvent être invalidés

Un std::vector<T>::iterator connait

l'addresse en mémoire de l'éléments qu'il itère
mais pas la structure de donnée du vecteur

Toute opération qui change la capacité et réalloue donc la mémoire utilisée invalide tous les itérateurs.

`std::list<T>`¶

met en oeuvre une liste doublement chainée. Elle n'offre donc pas

Expression	Description
`operator[i]` `at(i)`	les opérations d'accès indexé
`a+n; n+a;` `a-n; a-b`	les propriétés de décalage pour ses itérateurs
`a<b; a<=b;` `a>b; a>=b`	les opérateurs de comparaisons pour ses itérateurs

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<T>, mais la notion de capacité n'a pas ici lieu d'être.

Par contre, elle permet d'insérer et supprimer en tête, en queue ou en position quelconque connue en temps constant.

Méthode	Description
`push_back(t)` `pop_back()`	insère ou supprime un élément en queue
`push_front(t)` `pop_front()`	insère ou supprime un élément en tête
`insert(pos,...)`	insère des éléments devant l'itérateur `pos`
`erase(pos)` `erase(first,last)`	supprime des éléments et retourne un itérateur vers l'élément suivant le dernier supprimé
`emplace(pos,...)` `emplace_front()` `emplace_back()`	comme `push_back`, `push_front()` et `insert` mais l'objet est construit en place
`clear()`	supprime tous les éléments

Elle offre par ailleurs des méthodes spécifiques aux listes

Méthode	Description
`splice(...)`	opération d'épissure
`sort()`	tri stable en place en $\Theta(n \log n)$
`merge(...)`	opération de fusion du tri fusion
`remove(...)` `remove_if(...)` `unique()`	suppression d'éléments selon divers critères
`reverse()`	inversion tête à queue de la liste

Les itérateurs fournis sont des itérateurs bi-directionnels, qui ne fournissent donc aucune opération de décalage ou de comparaison autre que l'égalité.

Un std::list<T>::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.

Il reste valide tant que l'élément est dans la liste, mais

sa position dans la liste peut varier (après list<T>::sort() par exemple)
il peut même itérer une autre liste après splice ou merge.

`std::forward_list<T>`¶

disponible depuis C++11, elle met en oeuvre une liste simplement chainée. Par rapport à std::list<T>, on perd

Expression	Description
`push_back(t)` `pop_back()` `back()`	les opérations en queue
`rbegin()` `rend()` ...	les itérateurs inversés
`--a;` `a--;` `*a--;`	la décrémentation des itérateurs
`size()`	la taille, qui n'est pas stockée

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.

Expression	Description
`insert_after(it,t)` `emplace_after(it,...)`	insertion après un élément
`erase_after(it)`	suppression de l'élément suivant
`splice_after(it,...)`	épissure derrière un élément
`before_begin()`	itérateur avant l'élément de tête

Les itérateurs fournis sont des itérateurs forward, qui ne fournissent donc aucune opération de décalage ou de comparaison autre que l'égalité, ni de décrémentation.

Un std::forward_list<T>::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.

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

In [2]:

template < typename T > 
void supprimer(std::list<T>& L, T val) 
{
  for(auto it = L.begin(); it != L.end();)
  {
    if(*it == val) it = L.erase(it);
    else ++it;
  }
}

In [3]:

template < typename T >
void supprimer(std::forward_list<T>& L, T val)
{
  auto prec = L.before_begin();
  for(auto it = next(prec); it != L.end();)
  {
    if(*it == val) L.erase_after(prec);
    else ++prec;
    it = next(prec);
  }
}

Notons que la même fonction s'écrit ainsi pour les std::vector<T>. Elle est efficace si T::operator=(T&&) est efficace.

In [4]:

template < typename T >
void supprimer(std::vector<T>& V, T val)
{
  auto i_write = V.begin();
  for( auto i_read = V.begin(); i_read != V.end(); ++i_read )
  {
    if(*i_read != val) {
      *i_write = std::move(*i_read);
      ++i_write;
    }
  }
  V.erase(i_write,V.end());
}

`std::deque<T>`¶

met en oeuvre une queue à deux bouts. Il fournit essentiellement les mêmes fonctionalités que std::vector<T>, mais y ajoute

Méthode	Description
`push_front(t)` `emplace_front(...)`	insère un élément en tête
`pop_front()`	supprime un élément en tête

Par ailleurs, il n'a pas de méthode capacity(). Par rapport à std::vector<T>

l'accès aux données est un peu plus lent
les opérations en tête sont $\Theta(1)$ en moyenne, ce qui est nettement mieux
les opérations de réallocation sont plus légères

Itérateurs¶

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++.

Cette librairie inclut aussi un certain nombre de fonctions utiles quand on travaille avec ces itérateurs

begin, end
prev, next
advance
distance

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

ASD1 Notebooks on GitHub.io

Sequence containers in C++ STL¶

std::array<T,N>¶

std::vector<T>¶

std::list<T>¶