Editions ENI Livres | Vidéos | e-Formations
Listes en C++ (conteneurs)
Principes des conteneurs
Les librairies 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.
1. Trois catégories de conteneurs
Les conteneurs sont essentiellement répartis en trois catégories :
a. 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.
b. 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é....
Conteneurs séquentiels
1. La classe array
Cette classe donne des méthodes pour la gestion d’un tableau à taille fixe. Pour l’utiliser, il faut inclure la librairie <array> :
#include <array>
a. Template, constructeurs, destructeurs
Le template est le suivant :
template < class T, size_t N > class array;
La classe array ne fournit ni constructeur ni destructeur mais des méthodes pour l’utilisation d’un tableau statique. Le type et le nombre des éléments sont déterminés à la déclaration dans le template :
array<int 1> tab ; // un tableau de 10 int
array<double, 50> d ; // un tableau de 50 double
b. Accès éléments, itérateurs
operator[ ] : opérateur crochet pour l’accès immédiat à chaque élément selon son indice, comme pour tous les tableaux classiques. L’accès n’est pas contrôlé et il y a possibilité de débordement si l’indice est hors tableau.
array<int,10> a;
for (int i = 0; i < 10; i++) {
a[i] = i ;
cout << a[i] << ' '; // 0 1 2 3 4 5 6 7 8 9
}
cout << endl;
at() : méthode pour un accès contrôlé à un élément du tableau selon son indice donné en paramètre. En cas de débordement, il est possible de récupérer une erreur de type exception.
array<int,10> a;
for (int i = 0; i < 10; i++) {
a.at(i) = i ;
cout << a.at(i) << ' '; // 0 1 2 3 4 5 6 7 8 9
}
cout << endl;
back() : retourne une référence sur le dernier.
front() : retourne une référence sur le premier élément :
array<int,5> a = {1,2,3,4,5};
cout << "front : " << a.front() << endl; // 1
cout << "back : " << a.back() << endl; // 5
a.back() += 50;
a.front()+= 50 ;
for ( int& i : a )
cout << i << ' ';...Conteneurs séquentiels spécialisés
Les conteneurs séquentiels spécialisés implémentent pile (stack), file (queue) et file de priorité en s’appuyant sur les conteneurs vector, deque et list.
1. La classe stack
Il s’agit d’une pile « LIFO », dernier entré premier sorti (last in first out), sur le modèle de la pile d’assiettes pour la plonge. Les assiettes sont empilées au sommet de la pile au fur et à mesure et celui qui fait la vaisselle prend tour à tour les assiettes au sommet de la pile. Les fonctions principales sont pile vide ou pas, empiler, dépiler, lire le sommet. Le nombre des méthodes est réduit par rapport à un conteneur vector, deque et list.
Une pile est implémentée avec un conteneur vector, deque ou list. Par défaut c’est un conteneur deque.
Pour l’utiliser, il faut inclure la librairie <stack> :
#include <stack>
a. Templates, constructeurs
stack<type élément, type conteneur> : le template de la pile spécifie le type des éléments et éventuellement en second le type de conteneur compatible voulu pour son implémentation (vector, list, deque). Par défaut, lorsqu’il n’est pas précisé, c’est un conteneur deque :
template <class T, class Container = deque<T> > class stack;
Il y a deux constructeurs :
stack() : constructeur par défaut qui initialise une pile vide.
stack(conteneur en copie) : constructeur qui remplit une pile en prenant en copie un autre conteneur (ne fonctionne pas pour une portion).
stack<int> p1; // pile vide
// pile initialisée en copie d'un deque
deque<int> dq(3, 100); // 3 éléments à 100
stack<int> p2(dq); // p2 copie dq
// pile vide de int spécifiant l'utilisation d'un vecteur de int
stack<int, vector<int> > p3;
// pile de int spécifiant l'utilisation d'un vecteur de int
// la pile est initialisée en copie d'un vecteur de int
vector<int> v = { 1, 2, 3, 4 };
stack<int, vector<int> > p4(v);
cout <<...Conteneurs associatifs
Comme nous l’avons déjà indiqué, dans un conteneur associatif chaque élément est doublé d’une clé qui sert pour son identification et son insertion à une place qui répond à l’ordre souhaité dans le conteneur. La valeur de chaque élément est accédée en utilisant les opérateurs crochets autour de la clé de l’élément, comme s’il s’agissait d’un tableau :
leMap[cléElément] = valeur ;
Notre objectif ici est de présenter la map, le multimap, le set et le multiset. Tous sont ordonnés. 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. Il existe des versions non ordonnées mais nous ne les abordons pas ici.
1. La classe map
Clés et valeurs peuvent prendre différents types. L’association clé-valeur est une paire générique constituée à partir de la structure pair définie dans l’espace de noms standard (namespace std) :
template <class T1, class T2> struct pair
{
T1 first ;
T2 second ;
};
Cette structure est redéfinie ensuite en value_type de la façon suivante :
typedef pair<const Key, T> value_type;
Key désigne le type de la clé, c’est une constante quel que soit son type. Le second paramètre du template donne le type de la valeur.
Comme pour tous les conteneurs l’inclusion de la bibliothèque concernée <map> est nécessaire pour l’utilisation de map :
#include <map>
a. Templates, constructeurs
Le template du map précise le type pour la clé, le type de valeur des éléments, la fonction de comparaison des éléments ou une fonction et un type d’allocateur mémoire.
template < class Key, // type clé
class T, ...Conteneurs « presque conteneurs »
1. La classe string
a. Template
Le traitement des chaînes de caractères s’appuie à la racine sur le template basic_string défini ainsi :
template <
class charT,
class traits = char_traits<charT>,
class Alloc = allocator<charT>
> class basic_string;
Le premier paramètre p1 indique le type de caractère : char, wchar_t, char16_t (C++11), char32_t (C++11).
Le second paramètre p2 spécifie des propriétés pour les caractères et prend par défaut la valeur char_trait<charT> selon le type de caractère donné en p1.
Le troisième paramètre p3 spécifie un allocateur avec par défaut allocator<charT> selon le type donné en p1.
À partir de ce template sont définis les différents types de chaînes de caractères :
string :
typedef basic_string<char> string; // 8 bits
wstring :
typedef basic_string<wchar_t> wstring; // 16 bits
u16string :
typedef basic_string<char16_t> u16string; // 16 bits
u32string :
typedef basic_string<char32_t> u32string; // 32 bits
Pour ce qui est des méthodes ce sont les mêmes quel que soit le type des caractères. Nous allons les tester en utilisant la classe string.
Quel que soit le type de chaîne voulu il faut inclure la bibliothèque <string> :
#include <string>
b. Constructeurs
Les possibilités de constructeurs sont les suivantes :
Chaîne vide, 0 caractère :
string s0;
Chaîne initialisée avec la répétition d’un caractère :
string s1(10, 'w'); // wwwwwwwwww
Copie de chaîne donnée en paramètre :
string s3("une chaine");
string s4(s3);
Copie d’une section de chaîne :
p1 : la chaîne, p2 : le nombre de caractères à prendre, p3 : la position de départ :
string s5(s3, 8, 3);
p1 : la chaîne, p2 : le nombre de caractères depuis le début :
string s6("tata...