Apprenez le développement informatique à votre rythme.
Les méthodes de recherche dichotomique supposent que la séquence est déjà triée et offrent des performances de complexité supérieures à celles de la recherche classique sur une séquence non triée.
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.
La programmation compétitive combine deux thèmes : la conception d'algorithmes et leur implémentation. L'objectif est d'inventer des algorithmes efficaces qui résolvent des problèmes de calcul bien définis, en combinant des méthodes connues et de nouvelles idées. Les solutions sont évaluées en les testant sur un ensemble de cas de test.