Listes en C++ (conteneurs)

Auteur

Frédéric Drouillon

N'hésitez pas à donner vos avis par rapport à ce tutoriel : Commentez

- Titre : Listes en C++ (conteneurs)

- Auteur : Frédéric Drouillon

- Parution : 11 décembre 2014

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2014 Frédéric Drouillon. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Principes des conteneurs

- I-A. Trois catégories de conteneurs

- I-A-1. Conteneurs séquentiels

- I-A-2. Conteneurs associatifs

- I-A-3. Les « presque conteneurs »

- I-B. Récapitulation des bibliothèques conteneurs

- I-C. Opérations sur les conteneurs

- I-C-1. Templates, constructeurs, destructeurs

- I-C-2. Accès aux éléments

- I-C-3. Itérateurs

- I-C-4. Pointeurs

- I-C-5. Affectation

- I-C-6. Opérations de liste, pile et file

- I-C-7. Gestion des tailles et capacités

- I-C-8. Fonctions de comparaison

- II. Conclusion

- III. Remerciements

I - Principes des conteneurs

Les bibliothèques standard du C++ (STL, contenues dans l'espace de noms std) implémentent différentes sortes de listes, à savoir des ensembles d'objets appelés des conteneurs (container en anglais). Leur utilisation permet d'éviter de les programmer soi-même comme c'est nécessaire en C, d'autant que les implémentations proposées sont génériques, optimisées et sécurisées. Toutefois dans certains cas, probablement pour des raisons d'optimisation bien spécifiques, il peut rester avantageux de créer soi-même un conteneur. Une documentation de qualité est accessible sur le site http:// www.cplusplus.com. C'est une documentation de grande qualité, extrêmement complète et pratique d'utilisation rédigée entièrement en anglais.

L'objectif de ce chapitre et d'exposer les principes de base des différents conteneurs du C++ afin de démarrer avec eux. En particulier nous nous attachons à présenter : ce qui les différencie, comment déclarer un conteneur, les différents constructeurs, l'ajout et la suppression d'éléments, l'accès aux éléments, le parcours des listes.

I-A - Trois catégories de conteneurs

Les conteneurs sont essentiellement répartis en trois catégories.

I-A-1 - Conteneurs séquentiels

Ce sont les tableaux et les listes chaînées mis en place sur le modèle du conteneur vector. Les trois principaux sont vector, list et deque. À partir de ces trois-là, des adaptations sont fournies pour les piles, les files et les files de priorité avec respectivement stack, queue et priority_queue.

I-A-2 - Conteneurs associatifs

Les conteneurs associatifs sont caractérisés par un accès aux éléments à partir de clés. Ils gèrent ainsi des paires clé-valeur dans lesquelles la clé d'accès à un élément n'est pas nécessairement un nombre entier. Il y a le map (ordonné ou non), le multimap (ordonné ou non), le set (ordonné ou non), le multiset (ordonné ou non). Le map est un tableau associatif sans répétition de clé. Le multimap autorise la répétition d'une même clé. Le set est un map dans lequel clés et valeurs sont uniques et confondues. Le multiset est un set qui autorise plusieurs éléments identiques. Dans cet ouvrage nous présentons le map, le multimap, le set et le multiset et nous ne traitons pas les versions non ordonnées qui leur correspondent.

I-A-3 - Les « presque conteneurs »

Il reste d'autres types d'ensembles d'éléments que l'on peut aussi rattacher aux conteneurs. En particulier nous trouvons les valarray (type de tableaux de nombres avec fonctions optimisés pour le calcul), les string (chaînes de caractères), et les bitset (tableaux de bits sur le principe C qui utilise les opérateurs bit à bit). Mais ces types n'implémentent pas la totalité des propriétés et méthodes d'un conteneur standard complet. Pour cette raison Bjarne Stroustrup, créateur du C++, les désigne comme des « presque conteneurs ».

I-B - Récapitulation des bibliothèques conteneurs

Conteneurs séquentiels : tableaux et listes chaînées

<array> : un array est un tableau statique non dynamique (taille fixe) de n éléments de type T à une dimension. Le type et le nombre d'éléments sont spécifiés dans le template :

array<T, n> a;

<vector> : un vector est un tableau dynamique (taille modulable) de T à une dimension.

vector<T> v;

<list> : une list est une liste de T doublement chaînée.

list<T> l;

<deque> : un deque est une file à double accès de T.

deque<T> d ;

<stack> : une stack est une pile de T basée sur vector, list ou deque, deque par défaut.

stack<T> p ;

<queue> : une queue est une file de T basée sur vector liste ou deque, deque par défaut.

queue<T> f ;

Conteneurs associatifs : arbres binaires, arbres binaires de recherche

Dans un conteneur associatif, chaque élément est référencé par une clé, ce qui constitue un couple clé-valeur. La clé sert à identifier l'élément et à le positionner dans l'ordre du conteneur, ou selon toutes sortes de tris, mais elle ne correspond pas nécessairement à sa position physique dans le conteneur. Ce n'est pas un indice comme dans un tableau ordinaire. En effet le plus souvent les conteneurs associatifs sont implémentés sous la forme d'arbres binaires et d'arbres binaires de recherche (éventuellement en utilisant des tableaux).

Trois critères distinguent entre eux les types de conteneurs associatifs :

- il peut y avoir ou non plusieurs fois la même clé dans le conteneur ;

- il peut y avoir ou non plusieurs fois la même valeur dans le conteneur ;

- le conteneur peut être ordonné ou non.

Ainsi nous avons :

<map> ordonné, clé unique. Un map est un tableau associatif ordonné de T avec une clé unique pour chaque élément. Deux éléments ne peuvent pas partager la même clé, mais il peut y avoir plusieurs fois la même valeur avec des clés différentes.

map<T> m ;

<unordered_map> non ordonné, clé unique. C'est un map non ordonné. La clé est unique pour chaque élément. Deux éléments ne peuvent pas partager la même clé, mais il peut y avoir plusieurs fois la même valeur avec des clés différentes.

unordered_map<T> m ;

<multimap> ordonné, possibles répétitions de clés. Un multimap est un tableau associatif ordonné de T dans lequel nous pouvons avoir plusieurs éléments avec la même clé.

multimap<T> m ;

<unordered_multimap> non ordonné, possibles répétitions de clés. Un unordered multimap est un tableau associatif non ordonné de T dans lequel plusieurs éléments peuvent partager la même clé.

unordered_multimap<T> m ;

<set> ordonné, clé et valeur uniques. Le set est un conteneur ordonné de T dans lequel la valeur de chaque élément est unique ainsi que sa clé. Il n'y a pas de valeur dupliquée et la valeur de l'élément lui sert aussi de clé d'accès.

set<T> s ;

<unordered_set> non ordonné, clé et valeur uniques. Le set non ordonné est un conteneur non ordonné de T dans lequel la valeur de chaque élément est unique ainsi que sa clé. Il n'y a pas de valeur dupliquée et la valeur de l'élément lui sert aussi de clé d'accès.

unordered_set<T> us ;

<multiset> ordonné, possibles répétitions d'éléments. Le multiset est un set ordonné qui accepte de contenir plusieurs éléments identiques (même clé même valeur).

multiset<T> mt ;

<unordered_multiset> non ordonné, possibles répétitions d'éléments. Le multiset non ordonné est un set non ordonné qui accepte de contenir plusieurs éléments identiques (même clé, même valeur).

unordered_multiset<T> um ;

Presque conteneurs

<bitset> : le bitset correspond à un tableau de booléens implémenté soit sous forme de tableau de bits sur un unsigned long soit sous forme de chaîne de caractères (tableau de char).

bitset<T> b ;

<valarray> : tableau à une dimension de valeurs numériques de type T et implémentation optimisée pour le calcul.

valarray<T> v ;

<string> : cette bibliothèque regroupe des classes affectées aux traitements de chaînes de caractères dans différents formats. Nous trouvons :

- la classe string qui traite les chaînes en 8 bits (char) ;

- la classe wstring qui traite les chaînes en 16 bits avec le wchar_t comme type de caractère.

Et depuis la version 11 de C++ sont ajoutées :

- la classe u16string qui traite les chaînes en 16 bits avec le char16_t comme type de caractère ;

- la classe u32string qui traite les chaînes en 16 bits avec le char32_t comme type de caractère.

Autres

Aux bibliothèques de conteneurs s'ajoutent d'autres bibliothèques notamment :

<functional> : une bibliothèque de fonctions-objets utiles par exemple pour les files de priorités ;

<iterator> : une bibliothèque pour les itérateurs ;

<algorithm> : une bibliothèque d'algorithmes (fonctions de tris, de recherche, etc.) avec également <cstdlib> pour les fonctions bsearch(), qsort().

I-C - Opérations sur les conteneurs

Au départ Bjarn Stroustrup explique qu'il y a deux critères dans la conception des conteneurs de la bibliothèque standard (STL) :

- ils doivent être génériques ;

- ils doivent tendre vers une interface commune afin que dans l'idéal, l'utilisateur puisse écrire du code qui serait indépendant du type de conteneur utilisé. Mais cet idéal ne peut être atteint que partiellement. Chaque type de conteneur propose un ensemble standard d'opérations de base qui comprend :

- constructeurs,

- accès aux éléments,

- itérateurs (ce sont des pointeurs sur les éléments d'un conteneur),

- affectation,

- opérations de liste (insertion et suppression),

- opérations de pile et file,

- gestion des tailles et capacités,

- fonctions de comparaisons (surcharge des opérateurs ==, !=, <),

- opérations associatives (uniquement pour les conteneurs associatifs).

I-C-1 - Templates, constructeurs, destructeurs

Templates

Tous les conteneurs sont génériques et le type des éléments est défini à la déclaration d'un conteneur par le template. Mais, selon le conteneur, le template peut servir à d'autres paramétrages.

Pour un array le nombre des éléments.

- Pour les conteneurs séquentiels vector, list, deque, stact et queue le type d'allocateur.

- Pour une file de priorité priority_queue le type de conteneur utilisé et une fonction de comparaison.

- Pour un map et un multimap le type de clé, le type des éléments, une fonction de comparaison, un allocateur.

- Pour un set et un multiset le type des éléments, une fonction de comparaison et unallocateur. Il n'y a pas de clé parce que la clé est l'élément lui-même.

Tous les templates proposent des valeurs par défaut sauf pour les types d'élément et de clé.

Constructeurs

Les constructeurs proposés sont en général les suivants :

conteneur() : conteneur vide ;

conteneur(n) : n éléments avec la valeur par défaut. Ne fonctionne pas pour les conteneurs associatifs ;

conteneur(n,x) : n éléments avec la valeur x. Ne fonctionne pas pour les conteneurs associatifs ;

conteneur(premier, dernier) : crée et initialise un conteneur à partir d'une liste dont est fourni un itérateur qui pointe sur le premier et le dernier élément ;

conteneur(x) : constructeur de copie. Crée un nouveau conteneur à partir du conteneur x.

Destructeur

Le destructeur est équivalent à delete, il désalloue l'objet courant comme pour tous les objets :

~conteneur() : détruit le conteneur et tous ses éléments.

I-C-2 - Accès aux éléments

Les méthodes d'accès aux éléments sont en général les suivantes :

front() : retourne une référence sur le premier élément du conteneur (intéresse aussi la gestion d'une file) ;

back() : retourne une référence sur le dernier élément du conteneur (intéresse aussi la gestion d'une pile) ;

data() uniquement pour vector : retourne un pointeur sur le premier élément du tableau interne au conteneur ;

[ ] : indiçage comme pour tous les tableaux classiques, avec un accès non contrôlé (possibilité de débordement). Ne fonctionne pas avec une liste ;

at(i) : indiçage avec accès contrôlé (possibilité de récupérer une erreur en cas de débordement). Ne fonctionne pas avec une liste.

I-C-3 - Itérateurs

Les itérateurs sont des pointeurs qui pointent sur des éléments des conteneurs et dédiés à son parcours. Il y a quatre types d'itérateurs : iterator, reverse_iterator, const_iterator, const_reverse_iterator :

iterator : donne accès en écriture et lecture à l'élément pointé et sous-tend un parcours du conteneur du début vers la fin ;

reverse_iterator : donne accès en écriture et lecture à l'élément pointé, mais sous-tend un parcours du conteneur de la fin vers le début ;

const_iterator : donne accès en lecture seule à l'élément pointé et sous-tend un parcours du début vers la fin du conteneur ;

const_reverse_iterator : donne accès en lecture seule à l'élément pointé et sous-tend un parcours de la fin vers le début du conteneur ;

Des itérateurs sont retournés par les méthodes suivantes présentes dans tous les conteneurs.

begin() : retourne un itérateur iterator qui pointe sur le premier élément ;

end() : retourne un itérateur iterator qui pointe sur l'élément suivant le dernier (balise de fin) ;

rbegin() : retourne un itérateur reverse_iterator qui pointe sur le premier élément de la séquence inverse (le dernier) ;

rend() : retourne un itérateur reverse_iterator qui pointe sur l'élément suivant le dernier dans l'ordre inverse (balise de fin) ;

cbegin() : retourne un itérateur const_iterator qui pointe sur le premier élément. L'élément pointé n'est alors accessible qu'en lecture et non en écriture. Il ne peut être modifié ;

cend() : retourne un itérateur const_iterator qui pointe sur ce qui suit le dernier élément. L'élément pointé n'est alors accessible qu'en lecture et non en écriture. Il ne peut être modifié ;

crbegin() : retourne un itérateur const_reverse_iterator qui pointe sur le premier élément de la séquence inverse (le dernier). L'élément pointé n'est accessible qu'en lecture et ne peut pas être modifié ;

crend() : retourne un itérateur const_reverse_iterator qui pointe sur le dernier de la séquence inverse (le premier). L'élément pointé n'est accessible qu'en lecture et ne peut pas être modifié.

I-C-4 - Pointeurs

Les pointeurs ordinaires (type*) ainsi que les références (type&) sont utilisables, mais les types suivants sont redéfinis par les conteneurs :

pointer : pointeur du type d'un élément du conteneur ;

const_pointer : pointeur constant interdisant la modification de l'élément pointé du type d'un élément du conteneur ;

reference : référence du type d'un élément du conteneur ;

const_reference : référence du type d'un élément du conteneur interdisant la modification de l'élément référé.

I-C-5 - Affectation

Il est en général possible d'affecter des éléments à un conteneur en utilisant les méthodes suivantes :

operator=(x) : surcharge de l'affectation pour la copie de conteneurs ;

assign(n,x) : affecte n copies d'un élément x à un conteneur. La taille du conteneur est allouée ou réallouée en conséquence ;

assign(premier, dernier) : affecte à un conteneur une liste d'éléments dont est fourni un itérateur qui pointe sur le premier et le dernier élément.

I-C-6 - Opérations de liste, pile et file

Les principales opérations de liste consistent à insérer ou supprimer des éléments. Ces opérations sont implémentées avec les méthodes suivantes :

insert(p, x) : ajoute un élément x avant l'élément désigné par l'itérateur p ;

insert(p, n, x) : ajoute n copies de x avant l'élément désigné par l'itérateur p ;

insert(p, premier, dernier) : ajoute avant l'élément désigné par l'itérateur p les éléments d'une liste compris entre l'itérateur premier et l'itérateur dernier ;

erase(p) : supprime l'élément pointé par l'itérateur p ;

erase(premier, dernier) : efface les éléments pointés depuis l'itérateur premier à l'itérateur dernier ;

clear() : efface tous les éléments d'un conteneur. Équivalent à c.erase(c.begin(), c.end()) ;

push_back(x) : ajoute l'élément x à la fin ;

pop_back() : supprime le dernier élément ;

push_front(x) : ajoute l'élément x au début (nouveau premier) ;

pop_front() : supprime le premier élément.

I-C-7 - Gestion des tailles et capacités

Il s'agit d'obtenir le nombre d'éléments d'un conteneur, éventuellement sa taille en mémoire. Il y a également possibilité de redimensionner un conteneur et d'échanger le contenu de deux conteneurs de même type d'éléments. Ce sont les méthodes suivantes :

size() : retourne le nombre d'éléments du conteneur ;

resize( nb ), resize( nb , val) : uniquement pour vector, list et dequeue. Redimensionne un conteneur avec nb éléments. Si le conteneur existe avec une taille plus petite, les éléments conservés restent inchangés et les éléments supprimés sont perdus. Avec une taille plus grande, les éléments ajoutés sont initialisés avec une valeur par défaut ou avec une valeur spécifiée en val. Si la taille d'un vector est modifiée, la totalité de ses éléments peut être déplacée en mémoire. Il est donc déconseillé de conserver des pointeurs sur des éléments de vector dont la taille peut être modifiée. Pour un vecteur resize, augmente de la moitié la capacité totale du conteneur et l'ajuste si la taille demandée est supérieure ;

capacity() : uniquement pour vector. Retourne le nombre courant d'emplacements mémoire réservés. C'est-à-dire le total de mémoire allouée en nombre d'éléments pour le conteneur. Attention, à ne pas confondre avec le nombre des éléments effectivement contenus retourné par size() ;

empty() : retourne true si le conteneur est vide, false sinon ;

max_size() : donne le nombre maximum d'éléments qu'il serait possible de stocker dans le conteneur (dépend de la RAM) ;

reserve( nb ) : uniquement pour vector. Réserve de l'espace pour un total de nb éléments. Pas d'initialisation et déclenche un length_error si > max_size(). Il n'est possible que d'augmenter la taille du vecteur. La diminution de la taille réservée n'est pas possible ;

shrink_to_fit() : uniquement pour vector, deque. Rétrécit la capacité du vecteur au plus près du nombre d'éléments qu'il contient ;

swap( n ) : le conteneur appelant copie le conteneur n. Si sa taille est différente elle est ajustée sur celle de n ;

get_allocator() : obtient une copie de l'allocateur du conteneur. La fonction d'un allocateur est d'offrir des méthodes standard pour allouer et désallouer de la mémoire. Mais l'utilisation d'un allocateur est nécessaire uniquement pour une gestion plus pointue et avancée de la mémoire. Les allocateurs implémentés par défaut pour les conteneurs sont suffisants.

I-C-8 - Fonctions de comparaison

Les opérateurs de comparaison ==, !=, <, <=, >, >= sont surchargés de façon à pouvoir comparer entre eux des conteneurs :

== : donne true si le contenu de deux conteneurs est identique, false sinon ;

!= : donne true si le contenu de deux conteneurs est différent, false sinon ;

a < b : donne true si le conteneur a se situe avant le conteneur b d'un point de vue lexicographique ;

a <= b : donne true si le conteneur a se situe avant le conteneur b d'un point de vue lexicographique ou est égal au conteneur b ;

a > b : donne true si le conteneur a se situe après le conteneur b d'un point de vue lexicographique ;

a >= b : donne true si le conteneur a se situe après le conteneur b d'un point de vue lexicographique ou est égal au conteneur b.

II - Conclusion

Ce tutoriel est extrait du livre Du C au C++ - De la programmation procédurale à l'objet de Frédéric Drouillon.

Commandez Du C au C++ - De la programmation procédurale à l'objet sur Amazon

III - Remerciements

Je tiens sincèrement à remercier Vincent VIALE pour la mise au gabarit et Claude LELOUP pour la relecture orthographique.