Introduction aux algorithmes de la bibliothèque STL (programmation compétitive)

Un algorithme est une procédure de résolution d'une classe de problèmes. La STL contient une multitude d'algorithmes que vous pouvez utiliser dans vos programmes. Étant donné que de nombreuses personnes très intelligentes ont consacré beaucoup de temps à s'assurer que ces algorithmes sont corrects et efficaces, vous ne devriez généralement pas essayer, par exemple, d'écrire votre propre algorithme de tri.

STL fournit différents types d'algorithmes qui peuvent être implémentés sur n'importe quel conteneur à l'aide d'itérateurs. Ainsi, nous n'avons plus besoin de définir des algorithmes complexes, mais nous utilisons simplement les fonctions intégrées fournies par la bibliothèque d'algorithmes STL.

L'en-tête <algorithme> définit une collection de fonctions spécialement conçues pour être utilisées sur des collections

Une collection est une séquence d'objets accessible via des itérateurs ou des pointeurs, comme un tableau ou une instance de certains des conteneurs STL. Notez cependant que les algorithmes fonctionnent via des itérateurs directement sur les valeurs, n'affectant en aucune façon la structure de tout conteneur possible (cela n'affecte jamais la taille ou l'allocation de stockage du conteneur).

•  Algorithmes de tri
•  Algorithmes de recherche dichotomique
•  Algorithmes en lecture seule
•  Algorithmes de lecture-écriture
•  Algorithmes numériques
•  Minimum et maximum opérations.

Certains algorithmes, ceux que l'on appelle communément algorithmes parallèles, peuvent diviser un problème afin que des entités indépendantes puissent travailler simultanément sur différentes parties du problème. De nombreux algorithmes STL vous permettent de spécifier le parallélisme avec une politique d'exécution. Une politique d'exécution indique le parallélisme autorisé pour un algorithme.

Du point de vue de la STL, un algorithme peut être exécuté séquentiellement ou en parallèle. Un algorithme séquentiel ne peut avoir qu'une seule entité travaillant sur le problème à la fois ; un algorithme parallèle peut avoir de nombreuses entités travaillant de concert pour résoudre le problème.

De plus, les algorithmes parallèles peuvent être vectorisés ou non vectorisés. Les algorithmes vectorisés permettent aux entités d'effectuer des travaux dans un ordre non spécifié, permettant même à une seule entité de travailler simultanément sur plusieurs parties du problème. Par exemple, un algorithme qui nécessite une synchronisation entre les entités est généralement non vectorisable car la même entité peut tenter d'acquérir un verrou plusieurs fois, entraînant un blocage.

Trois politiques d'exécution existent dans l'en-tête <execution> :

•  std::execution::seq spécifie une exécution séquentielle (et non parallèle).
•  std::execution::par spécifie une exécution parallèle.
•  std::execution::par_unseq spécifie une exécution parallèle et vectorisée.

Pour les algorithmes qui prennent en charge une politique d'exécution, la valeur par défaut est seq, ce qui signifie que vous devez opter pour le parallélisme et les avantages de performances associés. Notez que la norme C++ ne précise pas la signification précise de ces politiques d'exécution car différentes plates-formes gèrent le parallélisme différemment. Lorsque vous fournissez une politique d'exécution non séquentielle, vous déclarez simplement que "cet algorithme peut être parallélisé en toute sécurité".