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.

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.

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

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.

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.

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

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

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.

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.

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.

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.