Explorez tous les cours et tutoriels associés au tag #Structures de données.
La recherche est une technique fondamentale utilisée pour retrouver des éléments dans une collection ou une séquence ; dans ce cours, nous découvrirons plusieurs fonctions de la bibliothèque STL permettant d’effectuer ces recherches, comme find, adjacent_find, count, mismatch, equal, is_permutation et search.
Les séquences permettent de stocker des éléments, mais il est parfois nécessaire de vérifier si tous ou certains éléments satisfont un prédicat ou d’appliquer une fonction à chacun d’eux ; ce cours présente plusieurs fonctions déjà définies dans la bibliothèque STL pour accomplir ces tâches.
Le tri est un algorithme fondamental qui consiste à organiser des données dans un ordre particulier, soit croissant, soit décroissant.
La STL propose divers algorithmes pouvant être appliqués à n’importe quel conteneur via des itérateurs, ce qui permet d’utiliser directement ses fonctions intégrées sans avoir à définir soi-même des algorithmes complexes.
La classe map, définie dans l’en-tête et également appelée dictionnaire ou tableau associatif, est un conteneur stockant des paires clé-valeur avec des clés uniques, triées par ordre croissant.
La classe set, définie dans l’en-tête , est un conteneur où chaque élément, appelé clé, est unique et trié par ordre croissant, sans doublons.
Une file d'attente prioritaire est une extension de la file d'attente dans laquelle chaque élément possède une priorité. Les éléments sont retirés non pas dans l'ordre d'insertion, mais selon leur niveau de priorité : l'élément de plus haute priorité est toujours retiré en premier.
La classe queue, définie dans , est un adaptateur de conteneur conçu pour l'insertion à une extrémité et la suppression à l'autre. Elle suit le principe FIFO (First In, First Out) : le premier élément inséré est le premier à être retiré.
La classe stack, définie dans , est un adaptateur conçu pour trois opérations : push (empiler), pop (dépiler) et top (sommet). Elle suit le principe LIFO (Last In, First Out) : le dernier élément inséré est le premier retiré.
La classe array, définie dans l'en-tête , est une collection d'éléments du même type stockés dans des emplacements de mémoire contigus. C'est un conteneur de séquence à taille fixe : le nombre d'éléments est déterminé à la compilation et ne peut pas changer à l'exécution.
La classe list, définie dans l'en-tête , est un conteneur de séquence implémenté comme une liste doublement chaînée. Chaque nœud possède une section de données et deux pointeurs : un vers le nœud précédent et un vers le nœud suivant.
Une deque (double ended queue — file à deux bouts) est un conteneur de séquence qui permet l'expansion et la contraction aux deux extrémités. Définie dans l'en-tête , elle est similaire à vector mais avec des insertions et suppressions efficaces en tête et en queue.