La plupart des programmes informatiques doivent, à un moment donné ou à un autre, conserver un nombre arbitraire de données en mémoire, généralement pour y accéder ultérieurement et leur appliquer des traitements spécifiques. En général, les structures de données utilisées sont toujours manipulées par des algorithmes classiques, que l'on retrouve donc souvent, si ce n'est plusieurs fois, dans chaque programme. Ces structures de données sont communément appelées des conteneurs en raison de leur capacité à contenir d'autres objets.
Afin d'éviter aux programmeurs de réinventer systématiquement la roue et de reprogrammer les structures de données et leurs algorithmes associés les plus classiques, la bibliothèque standard définit un certain nombre de classes template pour les conteneurs les plus courants. Ces classes sont paramétrées par le type des données des conteneurs et peuvent donc être utilisées virtuellement pour toutes les situations qui se présentent.
Les conteneurs de la bibliothèque standard ne sont pas définis par les algorithmes qu'ils utilisent, mais plutôt par l'interface qui peut être utilisée par les programmes clients. La bibliothèque standard impose également des contraintes de performances sur ces interfaces en termes de complexité. En réalité, ces contraintes sont tout simplement les plus fortes qui soient, ce qui garantit aux programmes qui les utilisent qu'ils auront les meilleures performances possibles.
La bibliothèque classifie les conteneurs en deux grandes catégories selon leurs fonctionnalités : les séquences et les conteneurs associatifs. Une séquence est un conteneur capable de stocker ses éléments de manière séquentielle, les uns à la suite des autres. Les éléments sont donc parfaitement identifiés par leur position dans la séquence, et leur ordre relatif est donc important. Les conteneurs associatifs, en revanche, manipulent leurs données au moyen de valeurs qui les identifient indirectement. Ces identifiants sont appelées des clefs par analogie avec la terminologie utilisée dans les bases de données. L'ordre relatif des éléments dans le conteneur est laissé dans ce cas à la libre discrétion de ce dernier et leur recherche se fait donc, généralement, par l'intermédiaire de leurs clefs.
La bibliothèque fournit plusieurs conteneurs de chaque type. Chacun a ses avantages et ses inconvénients. Comme il n'existe pas de structure de données parfaite qui permette d'obtenir les meilleures performances sur l'ensemble des opérations réalisables, l'utilisateur des conteneurs de la bibliothèque standard devra effectuer son choix en fonction de l'utilisation qu'il désire en faire. Par exemple, certains conteneurs sont plus adaptés à la recherche d'éléments mais sont relativement coûteux pour les opérations d'insertion ou de suppression, alors que pour d'autres conteneurs, c'est exactement l'inverse. Le choix des conteneurs à utiliser sera donc déterminant quant aux performances finales des programmes.
Au niveau de leurs interfaces, tous les conteneurs de la bibliothèque standard présentent des similitudes. Cet état de fait n'est pas dû au hasard, mais bel et bien à la volonté de simplifier la vie des programmeurs en évitant de définir une multitude de méthodes ayant la même signification pour chaque conteneur. Cependant, malgré cette volonté d'uniformisation, il existe des différences entre les différents types de conteneurs (séquences ou conteneurs associatifs). Ces différences proviennent essentiellement de la présence d'une clef dans ces derniers, qui permet de manipuler les objets contenus plus facilement.
Quelle que soit leur nature, les conteneurs fournissent un certain nombre de services de base que le programmeur peut utiliser. Ces services comprennent la définition des itérateurs, de quelques types complémentaires, des opérateurs et de fonctions standards. Les sections suivantes vous présentent ces fonctionnalités générales. Toutefois, les descriptions données ici ne seront pas détaillées outre mesure car elles seront reprises en détail dans la description de chaque conteneur.
Pour commencer, il va de soi que tous les conteneurs de la bibliothèque
standard disposent d'itérateurs. Comme on l'a vu dans la Section 13.4, les itérateurs
constituent une abstraction de la notion de pointeur pour les tableaux. Ils permettent donc de parcourir
tous les éléments d'un conteneur séquentiellement à l'aide de l'opérateur de déréférencement
* et de l'opérateur d'incrémentation ++.
Les conteneurs définissent donc tous un type iterator et un type const_iterator, qui sont les types des itérateurs sur les éléments du conteneur. Le type d'itérateur const_iterator est défini pour accéder aux éléments d'un conteneur en les considérant comme des constantes. Ainsi, si le type des éléments stockés dans le conteneur est T, le déréférencement d'un const_iterator renverra un objet de type const T.
Les conteneurs définissent également les types de données difference_type et size_type que l'on peut utiliser pour effectuer des calculs d'arithmétique des pointeurs avec leurs itérateurs. Le type difference_type se distingue du type size_type par le fait qu'il peut contenir toute valeur issue de la différence entre deux itérateurs, et accepte donc les valeurs négatives. Le type size_type quant à lui est utilisé plus spécialement pour compter un nombre d'éléments, et ne peut prendre que des valeurs positives.
Afin de permettre l'initialisation de leurs itérateurs,
les conteneurs fournissent deux méthodes begin et end, qui
renvoient respectivement un itérateur référençant le premier élément du conteneur et la valeur de fin
de l'itérateur, lorsqu'il a passé le dernier élément du conteneur. Ainsi, le parcours d'un conteneur
se fait typiquement de la manière suivante :
// Obtient un itérateur sur le premier élément :
Conteneur::iterateur i = instance.begin();
// Boucle sur toutes les valeurs de l'itérateur
// jusqu'à la dernière :
while (i != instance.end())
{
// Travaille sur l'élément référencé par i :
f(*i);
// Passe à l'élément suivant :
++i;
}Note : Pour des raisons de performances et de portabilité, la bibliothèque standard ne fournit absolument aucun support du multithreading sur ses structures de données. En fait, la gestion du multithreading est laissée à la discrétion de chaque implémentation. Généralement, seul le code généré par le compilateur est sûr vis-à-vis des threads (en particulier, les opérateurs d'allocation mémoire
newetnew[], ainsi que les opérateursdeleteetdelete[]peuvent être appelés simultanément par plusieurs threads pour des objets différents). Il n'en est pas de même pour les implémentations des conteneurs et des algorithmes de la bibliothèque standard.Par conséquent, si vous voulez accéder à un conteneur à partir de plusieurs threads, vous devez prendre en charge vous-même la gestion des sections critiques afin de vous assurer que ce conteneur sera toujours dans un état cohérent. En fait, il est recommandé de le faire même si l'implémentation de la bibliothèque standard se protège elle-même contre les accès concurrents à partir de plusieurs threads, afin de rendre vos programmes portables vers d'autres environnements.
Les itérateurs utilisés par les conteneurs sont tous au moins du type ForwardIterator. En pratique, cela signifie que l'on peut parcourir les itérateurs du premier au dernier élément, séquentiellement. Cependant, la plupart des conteneurs disposent d'itérateurs au moins bidirectionnels, et peuvent donc être parcourus dans les deux sens. Les conteneurs qui disposent de ces propriétés sont appelés des conteneurs réversibles.
Les conteneurs réversibles disposent, en plus des itérateurs
directs, d'itérateurs inverses. Ces itérateurs sont repectivement de type reverse_iterator et
const_reverse_iterator. Leur initialisation peut être réalisée à l'aide de la fonction
rbegin, et leur valeur de fin peut être récupérée à l'aide de la fonction
rend.
Outre les types d'itérateurs, les conteneurs définissent également des types spécifiques aux données qu'ils contiennent. Ces types de données permettent de manipuler les données des conteneurs de manière générique, sans avoir de connaissance précises sur la nature réelle des objets qu'ils stockent. Ils sont donc couramment utilisés par les algorithmes de la bibliothèque standard.
Le type réellement utilisé pour stocker les objets dans un conteneur n'est pas toujours le type template utilisé pour instancier ce conteneur. En effet, certains conteneurs associatifs stockent les clefs des objets avec la valeur des objets eux-mêmes. Ils utilisent pour cela la classe pair, qui permet de stocker, comme on l'a vu en Section 14.2.2, des couples de valeurs. Le type des données stockées par ces conteneurs est donc plus complexe que le simple type template par lequel ils sont paramétrés.
Afin de permettre l'uniformisation des algorithmes travaillant sur ces types de données, les conteneurs définissent tous le type value_type dans leur classe template. C'est en particulier ce type qu'il faut utiliser lors des insertions d'éléments dans les conteneurs. Bien entendu, pour la plupart des conteneurs, et pour toutes les séquences, le type value_type est effectivement le même type que le type template par lequel les conteneurs sont paramétrés.
Les conteneurs définissent également d'autres types permettant de manipuler les données qu'ils stockent. En particulier, le type reference est le type des références sur les données, et le type const_reference est le type des références constantes sur les données. Ces types sont utilisés par les méthodes des conteneurs qui permettent d'accéder à leurs données.
Toutes les classes template des conteneurs de la bibliothèque standard utilisent la notion d'allocateur pour réaliser les opérations de manipulation de la mémoire qu'elles doivent effectuer lors du stockage de leurs éléments ou lors de l'application d'algorithmes spécifiques au conteneur. Le type des allocateurs peut être spécifié dans la liste des paramètres template des conteneurs, en marge du type des données contenues. Les constructeurs des conteneurs prennent tous un paramètre de ce type, qui sera l'allocateur mémoire utilisé pour ce conteneur. Ainsi, il est possible de spécifier un allocateur spécifique pour chaque conteneur, qui peut être particulièrement optimisé pour le type des données gérées par ce conteneur.
Toutefois, le paramètre template spécifiant la classe de l'allocateur mémoire à utiliser dispose d'une valeur par défaut, qui représente l'allocateur standard de la bibliothèque allocator<T>. Il n'est donc pas nécessaire de spécifier cet allocateur lors de l'instanciation d'un conteneur. Cela rend plus simple l'utilisation de la bibliothèque standard C++ pour ceux qui ne désirent pas développer eux-même un allocateur mémoire. Par exemple, la déclaration template du conteneur list est la suivante :
template <class T, class Allocator = allocator<T> >Il est donc possible d'instancier une liste d'entiers simplement en ne spécifiant que le type des objets contenus, en l'occurrence, des entiers :
typedef list<int> liste_entier;
De même, le paramètre des constructeurs permettant de spécifier l'allocateur à utiliser pour les conteneurs dispose systématiquement d'une valeur par défaut, qui est l'instance vide du type d'allocateur spécifié dans la liste des paramètres template. Par exemple, la déclaration du constructeur le plus simple de la classe list est la suivante :
template <class T, class Allocator> list<T, Allocator>::list(const Allocator & = Allocator());Il est donc parfaitement légal de déclarer une liste d'entier simplement de la manière suivante :
liste_entier li;
Note : Il est peut-être bon de rappeler que toutes les instances d'un allocateur accèdent à la même mémoire. Ainsi, il n'est pas nécessaire, en général, de préciser l'instance de l'allocateur dans le constructeur des conteneurs. En effet, le paramètre par défaut fourni par la bibliothèque standard n'est qu'une instance parmi d'autres qui permet d'accéder à la mémoire gérée par la classe de l'allocateur fournie dans la liste des paramètres template.
Si vous désirez spécifier une classe d'allocateur différente de celle de l'allocateur standard, vous devrez faire en sorte que cette classe implémente toutes les méthodes des allocateurs de la bibliothèque standard. La notion d'allocateur a été détaillée dans la Section 13.6.
Les conteneurs disposent d'opérateurs de comparaison permettant d'établir des relations d'équivalence ou des relations d'ordre entre eux.
Les conteneurs peuvent tous être comparés directement avec
les opérateurs == et !=. La relation d'égalité entre deux
conteneurs est définie par le respect des deux propriétés suivantes :
les deux conteneurs doivent avoir la même taille ;
leurs éléments doivent être identiques deux à deux.
Si le type des objets contenus dispose des opérateurs d'infériorité et de supériorités strictes, les mêmes opérateurs seront également définis pour le conteneur. Ces opérateurs utilisent l'ordre lexicographique pour déterminer le classement entre deux conteneurs. Autrement dit, l'opérateur d'infériorité compare les éléments des deux conteneurs un à un, et fixe son verdict dès la première différence constatée. Si un conteneur est un sous-ensemble du deuxième, le conteneur le plus petit est celui qui est inclus dans l'autre.
Note : Remarquez que la définition des opérateurs de comparaison d'infériorité et de supériorité existe quel que soit le type des données que le conteneur peut stocker. Cependant, comme les conteneurs sont définis sous la forme de classes template, ces méthodes ne sont instanciées que si elles sont effectivement utilisées dans les programmes. Ainsi, il est possible d'utiliser les conteneurs même sur des types de données pour lesquels les opérateurs d'infériorité et de supériorité ne sont pas définis. Cependant, cette utilisation provoquera une erreur de compilation, car le compilateur cherchera à instancier les opérateurs à ce moment.
Enfin, les conteneurs disposent de méthodes générales permettant
d'obtenir des informations sur leurs propriétés. En particulier, le nombre d'éléments qu'ils contiennent
peut être déterminé grâce à la méthode size. La méthode empty
permet de déterminer si un conteneur est vide ou non. La taille maximale que peut prendre un conteneur
est indiquée quant à elle par la méthode max_size. Pour finir, tous les conteneurs
disposent d'une méthode swap, qui prend en paramètre un autre conteneur du même
type et qui réalise l'échange des données des deux conteneurs. On utilisera de préférence cette méthode
à toute autre technique d'échange car seules les références sur les structures de données des conteneurs
sont échangées avec cette fonction, ce qui garantit une complexité indépendante de la taille
des conteneurs.
| Précédent | Sommaire | Suivant |
| Personnalisation des mécanismes de localisation | Niveau supérieur | Les séquences |