17.2. Les séquences

Les séquences sont des conteneurs qui ont principalement pour but de stocker des objets afin de les traiter dans un ordre bien défini. Du fait de l'absence de clef permettant d'identifier les objets qu'elles contiennent, elles ne disposent d'aucune fonction de recherche des objets. Les séquences disposent donc généralement que des méthodes permettant de réaliser l'insertion et la suppression d'éléments, ainsi que le parcours des éléments dans l'ordre qu'elles utilisent pour les classer.

17.2.1. Fonctionnalités communes

Il existe un grand nombre de classes template de séquences dans la librairie standard qui permettent de couvrir la majorité des besoins des programmeurs. Ces classes sont relativement variées tant dans leurs implémentations que dans leurs interfaces. Cependant, un certain nombre de fonctionnalités communes sont gérées par la plupart des séquences. Ce sont ces fonctionnalités que cette section se propose de vous décrire. Les fonctionnalités spécifiques à chaque classe de séquence seront détaillées séparément dans la Section 17.2.2.1.

Les exemples fournis dans cette section se baseront sur le conteneur list, qui est le type de séquence le plus simple de la librairie standard. Cependant, ils sont parfaitement utilisables avec les autres types de séquences de la librairie standard, avec des niveaux de performances éventuellement différents en fonction des séquences choisies bien entendu.

17.2.1.1. Construction et initialisation

La construction et l'initialisation d'une séquence peuvent se faire de multiples manières. Les séquences disposent en effet de plusieurs constructeurs et de deux surcharges de la méthode assign qui permet de leur affecter un certain nombre d'éléments. Le constructeur le plus simple ne prend aucun paramètre, hormis un allocateur standard à utiliser pour la gestion de la séquence, et permet de construire une séquence vide. Le deuxième constructeur prend en paramètre le nombre d'éléments initial de la séquence et la valeur de ces éléments. Ce constructeur permet donc de créer une séquence contenant déjà un certain nombre de copies d'un objet donné. Enfin, le troisième constructeur prend deux itérateurs sur une autre séquence d'objets qui devront être copiés dans la séquence en cours de construction. Ce constructeur peut être utilisé pour initialiser une séquence à partir d'une autre séquence ou d'un sous-ensemble de séquence.

Les surcharges de la méthode assign se comportent un peu comme les deux derniers constructeurs, à ceci près qu'elles ne prennent pas d'allocateur en paramètre. La première méthode permet donc de réinitialiser la liste et de la remplir avec un certain nombre de copies d'un objet donné, et la deuxième permet de réinitialiser la liste et de la remplir avec une séquence d'objets définie par deux itérateurs.

Bien entendu, il existe également un constructeur et un opérateur de copie capables d'initialiser une séquence à partir d'une autre séquence du même type. Ainsi, il n'est pas nécessaire d'utiliser les constructeurs vus précédemment ni les méthodes assign pour initialiser une séquence à partir d'une autre séquence de même type.

17.2.1.2. Ajout et suppression d'éléments

L'insertion de nouveaux éléments dans une séquence se fait normalement à l'aide de l'une des surcharges de la méthode insert. Bien entendu, il existe d'autres méthodes spécifiques à chaque conteneur de type séquence et qui leur sont plus appropriées, mais ces méthodes ne seront décrites que dans les sections consacrées à ces conteneurs. Les différentes versions de la méthode insert sont récapitulées ci-dessous :

De manière similaire, il existe deux surcharges de la méthode erase qui permettent de spécifier de différentes manières les éléments qui doivent être supprimés d'une séquence. La première méthode prend en paramètre un itérateur sur l'élément à supprimer, et la deuxième un couple d'itérateurs donnant l'intervalle des éléments de la séquence qui doivent être supprimés. Ces deux méthodes retournent un itérateur sur l'élément suivant le dernier élément supprimé ou l'itérateur de fin de séquence s'il n'existe pas de tel élément. Par exemple, la suppression de tous les éléments d'une liste peut être réalisée de la manière suivante :

instance est une instance de la séquence Sequence.

Vous noterez que la suppression d'un élément dans une séquence rend invalide tous les itérateurs sur cet élément. Il est à la charge du programmeur de s'assurer qu'il n'utilisera plus les itérateurs ainsi invalidés. La librairie standard ne fournit aucun support pour le diagnostic de ce genre d'erreur.

Note : En réalité, l'insertion d'un élément peut également invalider des itérateurs existants pour certaines séquences. Les effets de bord des méthodes d'insertion et de suppression des séquences seront détaillés pour chacune d'elle dans les sections qui leur sont dédiées.

Il existe une méthode clear dont le rôle est de vider complètement un conteneur. On utilisera donc cette méthode dans la pratique, le code donné ci-dessous ne l'était qu'à titre d'exemple.

La complexité de toutes ces méthodes dépend directement du type de séquence sur lequel elles sont appliquées. Les avantages et les inconvénients de chaque séquence seront décrits dans la Section 17.2.2.

17.2.2. Les différents types de séquences

La librairie standard fournit trois classes fondamentales de séquence. Ces trois classes sont respectivement la classe list, la classe vector et la classe deque. Chacune de ces classes possède ses spécificités en fonction desquelles le choix du programmeur devra se faire. De plus, la librairie standard fournit également des classes adaptatrices permettant de construire des conteneurs équivalents, mais disposant d'une interface plus standard et plus habituelle aux notions couramment utilisées en informatique. Toutes ces classes sont décrites dans cette section, les adaptateurs étant abordés en dernière partie.

17.2.2.1. Les listes

La classe template list est certainement l'une des plus importantes car, comme son nom l'indique, elle implémente une structure de liste chaînée d'éléments, ce qui est sans doute l'une des structures les plus utilisées en informatique. Cette structure est particulièrement adaptée pour les algorithmes qui parcourent les données dans un ordre séquentiel.

Les propriétés fondamentales des listes sont les suivantes :

Les listes offrent donc la plus grande souplesse possible sur les opérations d'insertion et de suppression des éléments, en contrepartie de quoi les accès sont restreints à un accès séquentiel.

Comme l'insertion et la suppression des éléments en tête et en queue de liste peuvent se faire sans recherche, ce sont évidemment les opérations les plus courantes. Par conséquent, la classe template list propose des méthodes spécifiques permettant de manipuler les éléments qui se trouvent en ces positions. L'insertion d'un élément peut donc être réalisée respectivement en tête et en queue de liste avec les méthodes push_front et push_back. Inversement, la suppression des éléments situés en ces emplacements est réalisée avec les méthodes pop_front et pop_back. Toutes ces méthodes ne renvoient aucune valeur, aussi l'accès aux deux éléments situés en tête et en queue de liste peut-il être réalisé respectivement par l'intermédiaire des accesseurs front et back, qui renvoient tous deux une référence (éventuellement constante si la liste est elle-même constante) sur ces éléments.

Les listes disposent également de méthodes spécifiques qui permettent de leur appliquer des traitements qui leur sont propres. Ces méthodes sont décrites dans le tableau ci-dessous :

Tableau 17-1. Méthodes spécifiques aux listes

MéthodeFonction
remove(const T &)

Permet d'éliminer tous les éléments d'une liste dont la valeur est égale à la valeur passée en paramètre. L'ordre relatif des éléments qui ne sont pas supprimés est inchangé. La complexité de cette méthode est linéaire en fonction du nombre d'éléments de la liste.

remove_if(Predicat)

Permet d'éliminer tous les éléments d'une liste qui vérifient le prédicat unaire passé en paramètre. L'ordre relatif des éléments qui ne sont pas supprimés est inchangé. La complexité de cette méthode est linéaire en fonction du nombre d'éléments de la liste.

unique(Predicat)

Permet d'éliminer tous les éléments pour lesquels le prédicat binaire passé en paramètre est vérifié avec comme valeur l'élément courant et son prédécesseur. Cette méthode permet d'éliminer les doublons successifs dans une liste selon un critère défini par le prédicat. Par souci de simplicité, il existe une surcharge de cette méthode qui ne prend pas de paramètres, et qui utilise un simple test d'égalité pour éliminer les doublons. L'ordre relatif des éléments qui ne sont pas supprimés est inchangé, et le nombre d'applications du prédicat est exactement le nombre d'éléments de la liste moins un si la liste n'est pas vide.

splice(iterator position, list<T, Allocator> liste, iterator premier, iterateur dernier)

Injecte le contenu de la liste fournie en deuxième paramètre dans la liste courante à partir de la position fournie en premier paramètre. Les éléments injectés sont les éléments de la liste source identifiés par les itérateurs premier et dernier. Ils sont supprimés de la liste source à la volée. Cette méthode dispose de deux autres surcharges, l'une ne fournissant pas d'itérateur de dernier élément et qui insère uniquement le premier élément, et l'autre ne fournissant aucun itérateur pour référencer les éléments à injecter. Cette dernière surcharge ne prend donc en paramètre que la position à laquelle les éléments doivent être insérés et la liste source elle-même. Dans ce cas, la totalité de la liste source est insérée en cet emplacement. Généralement, la complexité des méthodes splice est proportionnelle au nombre d'éléments injectés, sauf dans le cas de la dernière surcharge, qui s'exécute avec une complexité constante.

sort(Predicat)

Trie les éléments de la liste dans l'ordre défini par le prédicat binaire de comparaison passé en paramètre. Encore une fois, il existe une surcharge de cette méthode qui ne prend pas de paramètre et qui utilise l'opérateur d'infériorité pour comparer les éléments de la liste entre eux. L'ordre relatif des éléments équivalents (c'est-à-dire des éléments pour lesquels le prédicat de comparaison n'a pas pu statuer d'ordre bien défini) est inchangé à l'issue de l'opération de tri. On indique souvent cette propriété en disant que cette méthode est stable. La méthode sort s'applique avec une complexité égale à N×ln(N), où N est le nombre d'éléments de la liste.

merge(list<T, Allocator>, Predicate)

Injecte les éléments de la liste fournie en premier paramètre dans la liste courante en conservant l'ordre défini par le prédicat binaire fourni en deuxième paramètre. Cette méthode suppose que la liste sur laquelle elle s'applique et la liste fournie en paramètre sont déjà triées selon ce prédicat, et garantit que la liste résultante sera toujours triée. La liste fournie en argument est vidée à l'issue de l'opération. Il existe également une surcharge de cette méthode qui ne prend pas de second paramètre et qui utilise l'opérateur d'infériorité pour comparer les éléments des deux listes. La complexité de cette méthode est proportionnelle à la somme des tailles des deux listes ainsi fusionnées.

reverse

Inverse l'ordre des éléments de la liste. Cette méthode s'exécute avec une complexité linéaire en fonction du nombre d'éléments de la liste.

17.2.2.2. Les vecteurs

La classe template vector de la librairie standard fournit une structure de données dont la sémantique est proche de celle des tableaux de données classiques du langage C/C++. L'accès aux données de manière aléatoire est donc réalisable en un coût constant, mais l'insertion et la suppression des éléments dans un vecteur ont des conséquences nettement plus lourdes que dans le cas des listes.

Les propriétés des vecteurs sont les suivantes :

Note : Notez bien que les vecteurs peuvent effectuer une réallocation même lorsque l'insertion se fait en dernière position. Dans ce cas, le coût de l'insertion est bien entendu très élevé. Toutefois, l'algorithme de réallocation utilisé est suffisament évolué pour garantir que ce coût est constant en moyenne (donc de complexité constante). Autrement dit, les réallocations ne se font que très rarement.

Tout comme la classe list, la classe template vector dispose de méthodes front et back qui permettent d'accéder respectivement au premier et au dernier élément des vecteurs. Cependant, contrairement aux listes, seule les méthodes push_back et pop_back sont définies, car les vecteurs ne permettent pas d'insérer et de supprimer leurs premiers éléments de manière rapide.

En revanche, comme nous l'avons déjà dit, les vecteurs ont la même sémantique que les tableaux et permettent donc un accès rapide à tous leurs éléments. La classe vector définit donc une méthode at qui prend en paramètre l'indice d'un élément dans le vecteur et qui renvoie une référence, éventuellement constante si le vecteur l'est lui-même, sur cet élément. Si l'indice fourni en paramètre référence un élément situé en dehors du vecteur, la méthode at lance une exception out_of_range. De même, il est possible d'appliquer l'opérateur [] utilisé habituellement pour accéder aux éléments des tableaux. Cet opérateur se comporte exactement comme la méthode at, et est donc susceptible de lancer une exception out_of_range.

Par ailleurs, la librairie standard définit une spécialisation de la classe template vector pour le type bool. Cette spécialisation a essentiellement pour but de réduire la consommation mémoire des vecteurs de booléens, en codant ceux-ci à raison d'un bit par booléen seulement. Les références des éléments des vecteurs de booléens ne sont donc pas réellement des booléens, mais plutôt une classe spéciale qui simule ces booléens tout en manipulant les bits réellement stockés dans ces vecteurs. Ce mécanisme est donc complètement transparent pour l'utilisateur, et les vecteurs de booléens se manipulent exactement comme les vecteurs classiques.

17.2.2.3. Les deques

Pour ceux à qui les listes et les vecteurs ne conviennent pas, la librairie standard fournit un conteneur plus évolué qui offre un autre compromis entre la rapidité d'accès aux éléments et la souplesse dans les opérations d'ajout ou de suppression. Il s'agit de la classe template deque, qui implémente une forme de tampon circulaire dynamique.

Les propriétés des deques sont les suivantes :

Comme vous pouvez le constater, les deques sont donc extrêmement bien adaptés aux opérations d'insertion et de suppression en première et en dernière position, tout en fournissant un accès rapide à leurs éléments. En revanche, les itérateurs existants sont systématiquement invalidés, quel que soit le type d'opération effectuée, hormis la suppression en tête et en fin de deque.

Comme elle permet un accès rapide à tous ses éléments, la classe template deque dispose de toutes les méthodes d'insertion et de suppression d'éléments des listes et des vecteurs. Outre les méthodes push_front, pop_front, push_back, pop_back et les accesseurs front et back, la classe deque définit donc la méthode at, ainsi que l'opérateur d'accès aux éléments de tableaux []. L'utilisation de ces méthodes est strictement identique à celle des méthodes homonymes des classes list et vector et ne devrait donc pas poser de problème particulier.

17.2.2.4. Les adaptateurs de séquences

Les classes des séquences de base list, vector et deque sont supposées satisfaire à la plupart des besoins courants des programmeurs. Cependant, la librairie standard fournit des adaptateurs pour transformer ces classes en d'autres structures de données plus classiques. Ces adaptateurs permettent de construire des piles, des files et des files de priorité.

17.2.2.4.1. Les piles

Les piles sont des structures de données qui se comportent, comme leur nom l'indique, comme un empilement d'objets. Elles ne permettent donc d'accéder qu'aux éléments situés en haut de la pile, et la récupération des éléments se fait dans l'ordre inverse de leur empilement. En raison de cette propriété, on les appelle également couramment LIFO, acronyme de l'anglais « Last In First Out » (dernier entré, premier sorti).

La classe adaptatrice définie par la librairie standard C++ pour implémenter les piles est la classe template stack. Cette classe utilise deux paramètres template : le type des données lui-même et le type d'une classe de séquence implémentant au moins les méthodes back, push_back et pop_back. Il est donc parfaitement possible d'utiliser les listes, deques et vecteurs pour implémenter une pile à l'aide de cet adaptateur. Par défaut, la classe stack utilise une deque, et il n'est donc généralement pas nécessaire de spécifier le type du conteneur à utiliser pour réaliser la pile.

L'interface des piles se réduit au strict minimum, puisqu'elles ne permettent de manipuler que leur sommet. La méthode push permet d'empiler un élément sur la pile, et la méthode pop de l'en retirer. Ces deux méthodes ne renvoient rien, l'accès à l'élément situé au sommet de la pile se fait donc par l'intermédiaire de la méthode top.

17.2.2.4.2. Les files

Les files sont des structures de données similaires aux piles, à la différence près que les éléments sont mis les uns à la suite des autres au lieu d'être empilés. Leur comportement est donc celui d'une file d'attente où tout le monde serait honnête (c'est-à-dire que personne ne doublerait les autres). Les derniers entrés sont donc ceux qui sortent également en dernier, d'où leur dénomination de FIFO (de l'anglais « First In First Out »).

Les files sont implémentées par la classe template queue. Cette classe utilise comme paramètre template le type des éléments stockés ainsi que le type d'un conteneur de type séquence pour lequel les méthodes front, back, push_back et pop_front sont implémentées. En pratique, il est possible d'utiliser les listes et les deques, la classe queue utilisant d'ailleurs ce type de séquence par défaut comme conteneur sous-jacent.

Les méthodes fournies par les files sont les méthodes front et back, qui permettent d'accéder respectivement au premier et au dernier élément de la file d'attente, ainsi que les méthodes push et pop, qui permettent respectivement d'ajouter un élément à la fin de la file et de supprimer l'élément qui se trouve en tête de file.

17.2.2.4.3. Les files de priorités

Enfin, la librairie standard fournit un adaptateur permettant d'implémenter les files de priorités. Les files de priorités ressemblent aux files classiques, mais ne fonctionnent pas de la même manière. En effet, contrairement aux files normales, l'élément qui se trouve en première position n'est pas toujours le premier élément qui a été placé dans la file, mais celui qui dispose de la plus grande valeur. C'est cette propriété qui a donné son nom aux files de priorités, car la priorité d'un élément est ici donnée par sa valeur. Bien entendu, la librairie standard permet à l'utilisateur de définir son propre opérateur de comparaison, afin de lui laisser spécifier l'ordre qu'il veut utiliser pour définir la priorité des éléments.

La classe template fournie par la librairie standard pour faciliter l'implémentation des files de priorité est la classe priority_queue. Cette classe prend trois paramètres template : le type des éléments stockés, le type d'un conteneur de type séquence permettant un accès direct à ses éléments et implémentant les méthodes front, push_back et pop_back, et le type d'un prédicat binaire à utiliser pour la comparaison des priorités des éléments. On peut donc implémenter une file de priorité à partir d'un vecteur ou d'une deque, sachant que, par défaut, la classe priority_queue utilise un vecteur. Le prédicat de comparaison utilisé par défaut est le foncteur less<T>, qui effectue une comparaison à l'aide de l'opérateur d'infériorité des éléments stockés dans la file.

Comme les files de priorités se réorganisent à chaque fois qu'un nouvel élément est ajouté en fin de file, et que cet élément ne se retrouve par conséquent pas forcément en dernière position s'il est de priorité élevée, accéder au dernier élément des files de priorité n'a pas de sens. Il n'existe donc qu'une seule méthode permettant d'accéder à l'élément le plus important de la pile : la méthode top. En revanche, les files de priorité implémentent effectivement les méthodes push et pop, qui permettent respectivement d'ajouter un élément dans la file de priorité et de supprimer l'élément le plus important de cette file.