Algorithmes STL

lower_bound et upper_bound sont des fonctions de recherche binaires intégrées.

lower_bound - une fonction qui, en temps logarithmique, trouve le plus petit élément dans un tableau trié qui est supérieur ou égal à la valeur donnée k.
Il prend les bornes du tableau et la valeur de k comme arguments.
Renvoie un itérateur à l'élément trouvé, ou à la fin (non incluse) du tableau si aucun élément de ce type n'existe.
Vous pouvez en savoir plus dans la documentation.

upper_bound - une fonction qui, en temps logarithmique dans un tableau trié, trouve le plus petit élément strictement supérieur à la valeur donnée k.
Il prend les bornes du tableau et la valeur de k comme arguments.
Renvoie un itérateur à l'élément trouvé, ou à la fin (non incluse) du tableau si aucun élément de ce type n'existe.
Vous pouvez en savoir plus dans la documentation.

Il convient de préciser que l'utilisation de ces fonctions sur un ensemble ou un multiensemble ne fonctionne pas en temps logarithmique en raison du manque d'itérateurs dans les collections à accès aléatoire ci-dessus.
Cependant, ces collections ont des méthodes intégrées correspondantes (c'est-à-dire que vous devez les utiliser "à travers un point").

Exemples :
  vecteur a = { 0, 1, 3, 5, 7 } ; vector::iterator it ; it = borne_inférieure(a.begin(), a.end(), 4); // *il == 5 it = borne_inférieure(a.begin(), a.end(), 5); // *il == 5 it = borne_inférieure(a.begin(), a.end(), 8); // it == a.end() it = upper_bound(a.begin(), a.end(), 4); // *il == 5 it = upper_bound(a.begin(), a.end(), 5); // *il == 7 it = upper_bound(a.begin(), a.end(), -1); // *il == 0 // en soustrayant les itérateurs, vous pouvez obtenir l'index de l'élément trouvé int ind = borne_inférieure(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // besoin d'utiliser des méthodes au lieu de fonctions pour les collections set et similaires set s{ 1, 3, 5 } ; set::iterator sit; sit = s.lower_bound(3); // *assis == 3 sit = s.upper_bound(3); // *assis == 5  

unique - une fonction qui comprime toutes les séquences d'éléments consécutifs identiques en une seule en temps linéaire.
En argument, on lui passe les limites du tableau, à l'intérieur desquelles il faut appliquer la compression.
Un itérateur est renvoyé à la nouvelle fin (non inclusive) du tableau. Vous devez être prudent avec les éléments après la nouvelle fin mais avant l'ancien, car ils auront une valeur indéfinie.
Vous pouvez en savoir plus dans la documentation.

Si vous utilisez cette fonction sur un vecteur, il est pratique de redimensionner en utilisant le résultat renvoyé (plus d'informations ci-dessous).

Exemples :
  vecteur une = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 } ; unique(a.begin(), a.end()); // un = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // utiliser la fonction unique est pratique à faire // tableau auxiliaire pour la compression des coordonnées un = { 235, 10, 41, 10, 41, 41, 235, 500, 500 } ; sort(a.begin(), a.end()); // un = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // un = [10, 41, 235, 500]  

merge - une fonction qui fusionne deux tableaux triés, à savoir, en temps linéaire, elle obtient un tableau trié, qui se compose des éléments du premier et du deuxième tableau.
Il prend 5 arguments : deux bornes pour chaque tableau et la borne gauche de la destination (où les éléments du tableau résultant seront placés).
Plus de détails peuvent être trouvés dans la documentation.

Exemples: // les tableaux source doivent être triés vecteur a = { 1, 3, 5, 7 } ; vecteur b = { 2, 4, 6 } ; // besoin que la destination soit assez grande vecteur c(7); fusionner(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // les éléments peuvent être répétés un = {1, 2, 4, 4} ; b = { 2, 3, 3, 3, 4, 4 } ; c.resize(10); fusionner(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Cette fonction est très utile dans le cadre du tri par fusion.

nth_element est une fonction qui vous permet de trouver le nième élément d'un tableau dans un ordre trié en temps linéaire.
La fonction prend l'extrémité gauche du tableau, un itérateur à la position dont la valeur dans l'ordre trié doit être trouvée, et l'extrémité droite du tableau.
Après avoir appliqué la fonction, la valeur requise sera située à l'endroit indiqué par l'itérateur, tandis que les valeurs restantes acquerront un ordre chaotique, mais à gauche du nième, il n'y aura pas plus de valeurs qu'elle, et à droite pas moins. Autrement dit, il faut comprendre que cette fonction détruit l'ordre d'origine des éléments.
Vous pouvez en savoir plus dans la documentation (https://www.cplusplus.com/reference/algorithm/nth_element/).

Exemple: vecteur a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 } ; // recherche l'élément à l'index 4 // attention à l'ordre des arguments nth_element(a.begin(), a.begin() + 4, a.end()); // un = [#, #, #, #, 4, $, $, $, $, $] // où # <= 4 et 4 <= $  

Une permutation de longueur n est une collection ordonnée sans répétitions des nombres 1, 2, ..., n. Par exemple, [3, 1, 2] et [5, 4, 3, 2, 1] sont des permutations, mais [1, 2, 1, 3] et [1, 2, 4] ne le sont pas.

Si la tâche est réduite au fait qu'il est nécessaire d'itérer sur toutes les permutations de longueur n, vous pouvez utiliser un mécanisme pratique en C ++, appelé "next_permutation".

Vous pouvez en savoir plus à ce sujet dans la documentation, mais le fait est que cette fonction modifie le tableau passé à la permutation ultérieure dans l'ordre lexicographique (qui est généralement clair et son nom).

Pour utiliser next_permutation, vous devez inclure la bibliothèque d'algorithmes (c'est-à-dire écrire #include <algorithm> au début du programme)

Exemples: vecteur arr ; arr = { 1, 2, 3 } ; // le tableau est [1, 2, 3] next_permutation(arr.begin(), arr.end()); // passe le tableau entier à la fonction // le tableau est maintenant [1, 3, 2] arr = { 2, 3, 1 } ; // le tableau est [2, 3, 1] next_permutation(arr.begin(), arr.end()); // passe le tableau entier à la fonction // le tableau est maintenant [3, 1, 2] next_permutation(arr.begin() + 1, arr.begin() + 3); // il est possible d'appliquer une fonction à une partie d'un tableau, mais en pratique c'est rarement nécessaire // le tableau est maintenant [3, 2, 1]
Dans ce cas, la fonction a une valeur de retour booléenne qui est vraie si la permutation suivante a été générée et fausse s'il n'y en a pas eu de suivante (cas où la permutation maximale dans l'ordre lexicographique est passée à la fonction).
Cela permet d'utiliser la fonction dans une boucle, ce qui nous permettra d'itérer sur toutes les permutations à la fois. En raison de l'indexation à 0, en pratique, il est souvent plus pratique de travailler avec une permutation de nombres de 0 à n - 1, bien qu'une permutation contienne formellement des nombres de 1 à n. Mais heureusement, cela n'entraîne pas de superpositions supplémentaires dans le code, car la fonction next_permutation est adaptée aux permutations indexées à 0 (et même aux éléments dupliqués dans un tableau, mais vous pouvez en savoir plus par vous-même).

En général, le code d'itération sur toutes les permutations ressemble à ceci :   international ; // taille de la permutation vecteurperm(n); // perm est l'abréviation de "permutation", c'est-à-dire "permutation" pour (int je = 0; je < n; je++) perm[je] = je ; // initialise la permutation initiale 0, 1, ..., n - 1 faire { // à l'intérieur de la boucle, nous traitons la permutation actuelle } while (next_permutation(perm.begin(), perm.end())); // s'il n'y a pas de permutation suivante, alors termine la boucle

Ce code s'exécute en O(n! * f(n)), où f(n) est le temps qu'il vous faut pour traiter une permutation particulière.