Menu

Algorithmes dans STL

algorithms stl

Essayez Notre Instrument Pour Éliminer Les Problèmes

Une étude explicite des algorithmes et de leurs types dans STL.

faire une copie d'un tableau

STL prend en charge divers algorithmes qui agissent sur les conteneurs via des itérateurs. Comme ces algorithmes agissent sur les itérateurs et non directement sur les conteneurs, ils peuvent être utilisés sur tout type d'itérateurs.

Les algorithmes STL sont intégrés et permettent ainsi de gagner beaucoup de temps et sont également plus fiables. Ils améliorent également la réutilisabilité du code. Ces algorithmes ne sont normalement qu'un seul appel de fonction et nous n'avons pas besoin d'écrire de code exhaustif pour les implémenter.

=> Recherchez la série complète de formations C ++ ici.

ALGORITHMES EN STL

Ce que vous apprendrez:

Types d'algorithmes STL

STL prend en charge les types d'algorithmes suivants

  • Algorithmes de recherche
  • Algorithmes de tri
  • Algorithmes numériques
  • Algorithmes de non-transformation / modification
  • Transformer / Modifier des algorithmes
  • Opérations minimum et maximum

Nous aborderons chacun de ces types en détail dans les paragraphes suivants.

Rechercher et trier les algorithmes

L'algorithme de recherche prédominant dans STL est une recherche binaire. L'algorithme de recherche binaire fonctionne sur un tableau trié et recherche l'élément en divisant le tableau en deux.

Cela se fait en comparant d'abord l'élément à rechercher avec l'élément central du tableau, puis en limitant la recherche à 1stmoitié ou 2ndla moitié du tableau selon que l'élément à rechercher est inférieur ou supérieur à l'élément du milieu.

La recherche binaire est l'algorithme de recherche le plus utilisé.

Sa syntaxe générale est:

binary_search(startaddr, endaddr, key)

Où,

startaddr: adresse du premier élément du tableau.
endaddr: adresse du dernier élément du tableau.
clé: l'élément à rechercher.

STL nous fournit un algorithme de 'tri' qui est utilisé pour organiser les éléments d'un conteneur dans un ordre particulier.

La syntaxe générale de l'algorithme de tri est:

sort(startAddr, endAddr);

Où,

startAddr: adresse de départ du tableau à trier.
endAddr: adresse de fin du tableau à trier.

En interne, STL utilise l'algorithme Quicksort pour trier le tableau.

Prenons un exemple pour illustrer l'algorithme de recherche et de tri binaire:

#include #include using namespace std; int main() { int testAry() = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int arysize = sizeof(testAry) / sizeof(testAry(0)); sort(testAry, testAry + arysize); cout<<' Sorted Array is '; for(int i=0;i

Production:

Le tableau trié est
0 1 2 3 4 5 6 7 8 9
Key = 2 trouvé dans le tableau
Clé = 10 introuvable dans le tableau

Dans le code donné, nous avons fourni un tableau dans lequel nous devons rechercher un élément clé en utilisant la recherche binaire. Puisque la recherche binaire nécessite un tableau trié, nous trions d'abord le tableau en utilisant l'algorithme «sort», puis faisons un appel de fonction à «recherche_binaire» en fournissant les paramètres requis.

Tout d'abord, nous appelons l'algorithme binary_search pour key = 2, puis pour key = 10. De cette façon, avec un seul appel de fonction, nous pouvons effectuer une recherche binaire sur un tableau ou le trier.

Algorithmes numériques

L'en-tête dans STL contient diverses fonctions qui opèrent sur des valeurs numériques. Ces fonctions vont de la recherche de lcds, gcds à même le calcul de la somme des éléments dans un conteneur comme des tableaux, des vecteurs sur une plage donnée, etc.

Nous discuterons ici de quelques fonctions importantes avec des exemples.

(i) accumuler

La syntaxe générale de la fonction d'accumulation est:

accumulate (first, last, sum);

Cette fonction renvoie la somme de tous les éléments d'une plage (premier, dernier) dans une somme variable. Dans la notation syntaxique ci-dessus, le premier et le dernier sont les adresses des premier et dernier éléments d'un conteneur et sum est la valeur initiale de la variable sum.

(ii) somme_partielle

La syntaxe générale de la fonction somme_partielle est:

partial_sum(first, last, b)

Ici

first: adresse de l'élément de départ du conteneur.
Dernier: adresse du dernier élément du conteneur.
B: tableau dans lequel la somme partielle des éléments du tableau correspondants sera stockée.

Ainsi, la fonction partial_sum calcule la somme partielle du tableau correspondant ou des éléments vectoriels et les stocke dans un tableau différent.

Si a représente l'élément dans la plage (premier, dernier) et b représente l'élément dans le tableau résultant, alors partial_sum sera:

b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2… et ainsi de suite.

Voyons un exemple pour démontrer les deux Ces fonctions dans un programme:

#include #include using namespace std; int main() { int A() = {21,25,64,32}; int sum = 0; int b(4); cout<<' Result of accumulate function is: '<

Production:

Le résultat de la fonction d'accumulation est: 142

somme_partielle du tableau A: 21 46110142

Comme indiqué dans le programme ci-dessus, nous calculons d'abord la somme des éléments à l'aide de la fonction d'accumulation, puis nous appelons la fonction partial_sum pour calculer la somme partielle des éléments de tableau correspondants.

questions d'entretien de test manuel pour 3 ans d'expérience

Autres algorithmes pris en charge par STL et en-tête:

  • iota: Remplit une plage avec des incréments successifs de la valeur de départ.
  • réduire: Similaire à accumuler, sauf dans le désordre.
  • produit_interne: Calcule le produit interne de deux plages d'éléments.
  • adjacent_difference: Calcule les différences entre les éléments adjacents d'une plage.
  • inclusive_scan: Similaire à partial_sum, inclut le ième élément d'entrée dans la ième somme.
  • scan_exclusif: Similaire à partial_sum, exclut le ième élément d'entrée de la ième somme.

Algorithmes non modificateurs

Les algorithmes qui ne modifient pas ou ne transforment pas sont ceux qui ne changent pas le contenu du conteneur dans lequel ils opèrent. STL prend en charge de nombreux algorithmes sans modification.

Nous en avons énuméré quelques-uns ci-dessous:

  • compter: Renvoie le nombre de valeurs dans la plage donnée.
  • égal: Compare les éléments de deux plages et renvoie une valeur booléenne.
  • décalage: Renvoie une paire d'itérateurs lorsque deux itérateurs sont comparés et qu'une incompatibilité se produit.
  • chercher: Recherche une séquence donnée dans une plage donnée.
  • search_n: Recherche dans une plage donnée une séquence de la valeur de comptage.

Expliquons plus en détail les fonctions «compter» et «égal» !!

count (first, last, value) renvoie le nombre de fois où la «valeur» apparaît dans la plage (first, last).

#include #include using namespace std; int main () { int values() = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46}; int count_5 = count(values, values+15, 5); cout<<'The number of times '5' appears in array= '<

Production:

Le nombre de fois que «5» apparaît dans un tableau = 4

Comme vous le voyez dans ce code, nous définissons une valeur de tableau, puis appelons la fonction de comptage en fournissant la plage de valeur et la valeur de 5. La fonction renvoie le nombre de fois (count) valeur 5 apparaît dans la plage.

Prenons un exemple pour démontrer la fonction «égal».

equal (first1, last1, first2) compare les éléments de la plage (first1, last1) au premier élément pointé par first2 et renvoie true si tous les éléments sont égaux sinon false.

#include #include using namespace std; int main() { int inputs1() = { 1,2,3,4,5,6,7,8}; int inputs2() = { -1,2,1,2,3,4,6,7,8,9}; if (equal( inputs1 , inputs1+8 , inputs2 )==1) cout<<'Elements in Two ranges are equal'; else cout<<'Elements in two ranges are not equal'; }

Production:

Les éléments de deux plages ne sont pas égaux.

Dans le code ci-dessus, nous définissons deux tableaux d'entiers et comparons leurs éléments correspondants en utilisant la fonction «égal». Comme les éléments du tableau ne sont pas les mêmes, égal renvoie false.

Modifier les algorithmes

La modification des algorithmes modifie ou transforme le contenu des conteneurs lors de leur exécution.

Les algorithmes de modification les plus populaires et les plus largement utilisés incluent «swap» et «reverse» qui permute respectivement deux valeurs et inverse les éléments dans le conteneur.

Voyons les exemples de ces fonctions:

#include #include #include #include using namespace std; int main () { vector vec1 = {1,1,2,3,5}; vector vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<'Vector 1 : '; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << ' '; cout<

Production:

Vecteur 1: 2 4 6 8 10

Vecteur 2: 1 1 2 3 5

Vecteur inversé 1:10 8 6 4 2

Vecteur inversé 2: 5 3 2 1 1

Comme on le voit, nous avons deux vecteurs définis dans le programme. En utilisant d'abord la fonction swap, nous échangeons le contenu de vector1 et vector2. Ensuite, nous inversons le contenu de chaque vecteur en utilisant la fonction inverse.

Le programme sort le vecteur 1 et le vecteur 2 après avoir échangé leur contenu et également après avoir inversé le contenu.

Opérations minimum et maximum

Cette catégorie se compose de fonctions min et max qui déterminent respectivement les valeurs minimale et maximale à partir des deux valeurs données.

La syntaxe générale de ces fonctions est:

max(objecta, objectb); min(objecta, objectb);

Nous pouvons également fournir un troisième paramètre pour fournir «compare_function» ou les critères qui seraient utilisés pour trouver la valeur min / max. Si ce n’est pas le cas, la fonction max utilise l’opérateur «>» pour la comparaison tandis que la fonction min utilise «<’ operator for comparison.

Voyons ces fonctions à l’aide d’un programme.

#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout<

Production:

Max de 4 et 5: 5

Min de 4 et 5: 4

Chaîne maximale: chaîne plus petite

Chaîne minimale: chaîne plus longue

Le programme ci-dessus est explicite car nous utilisons les fonctions min et max sur les nombres d'abord, puis sur les chaînes. Comme nous n’avons pas fourni la fonction optionnelle «compare_function», les fonctions min / max agissaient respectivement sur les opérateurs «».

Conclusion

Avec cela, nous sommes arrivés à la fin de ce tutoriel sur les principaux algorithmes utilisés en STL.

Dans nos didacticiels suivants, nous aborderons les itérateurs en détail ainsi que les fonctions courantes utilisées dans STL indépendamment des conteneurs.

=> Lisez la série de formations Easy C ++.

lecture recommandée

^