algorithms stl
Un studiu explicit al algoritmilor și tipurilor sale în STL.
testarea bazată pe date în soapui folosind script groovy
STL acceptă diferiți algoritmi care acționează asupra containerelor prin iteratoare. Deoarece acești algoritmi acționează asupra iteratorilor și nu direct asupra containerelor, pot fi folosiți pe orice tip de iteratori.
Algoritmii STL sunt încorporați și astfel economisesc mult timp și sunt și mai fiabili. De asemenea, îmbunătățesc reutilizarea codului. Acești algoritmi sunt în mod normal doar o singură funcție de apel și nu trebuie să scriem un cod exhaustiv pentru a le implementa.
=> Căutați întreaga serie de formare C ++ aici.
Ce veți învăța:
Tipuri de algoritmi STL
STL acceptă următoarele tipuri de algoritmi
- Algoritmi de căutare
- Algoritmi de sortare
- Algoritmi numerici
- Algoritmi netransformatori / modificatori
- Transformarea / modificarea algoritmilor
- Operațiuni minime și maxime
Vom discuta fiecare dintre aceste tipuri în detaliu în paragrafele următoare.
Algoritmi de căutare și sortare
Algoritmul de căutare proeminent din STL este o căutare binară. Algoritmul de căutare binară funcționează pe o matrice sortată și caută elementul împărțind matricea în jumătate.
Acest lucru se face comparând mai întâi elementul de căutat cu elementul de mijloc al matricei și apoi limitând căutarea la 1Sfjumătate sau 2ndjumătate din matrice, în funcție de faptul dacă elementul de căutat este mai mic sau mai mare decât elementul din mijloc.
Căutarea binară este cel mai utilizat algoritm de căutare.
Sintaxa sa generală este:
binary_search(startaddr, endaddr, key) Unde,
startaddr: adresa primului element al matricei.
endaddr: adresa ultimului element al matricei.
cheie: elementul de căutat.
STL ne oferă un algoritm de „Sortare” care este folosit pentru a aranja elementele dintr-un container într-o anumită ordine.
Sintaxa generală a algoritmului de sortare este:
sort(startAddr, endAddr); Unde,
startAddr: adresa de pornire a tabloului de sortat.
endAddr: adresa finală a matricei de sortat.
Intern STL utilizează algoritmul Quicksort pentru a sorta matricea.
Să luăm un exemplu pentru a demonstra algoritmul de căutare și sortare binară:
#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 Ieșire:
Matricea sortată este
0 1 2 3 4 5 6 7 8 9
Cheie = 2 găsită în matrice
Cheia = 10 nu a fost găsită în matrice
În codul dat, am furnizat o matrice în care trebuie să căutăm un element cheie folosind căutarea binară. Deoarece căutarea binară necesită o matrice sortată, mai întâi sortăm matricea folosind algoritmul „sortare” și apoi facem un apel funcțional către „binary_search” furnizând parametrii necesari.
Mai întâi, numim algoritmul binary_search pentru cheia = 2 și apoi pentru cheia = 10. În acest fel, cu o singură funcție de apel, putem efectua în mod convenabil o căutare binară pe o matrice sau o putem sorta.
Algoritmi numerici
antetul în STL conține diverse funcții care operează pe valori numerice. Aceste funcții variază de la găsirea lcd-urilor, gcds-urilor până la calcularea sumei elementelor dintr-un container, cum ar fi matrici, vectori într-un interval dat etc.
Vom discuta câteva funcții importante aici cu exemple.
(i) acumula
Sintaxa generală a funcției de acumulare este:
accumulate (first, last, sum); Această funcție returnează suma tuturor elementelor dintr-un interval (primul, ultimul) dintr-o sumă variabilă. În notația de sintaxă de mai sus, prima și ultima sunt adresele primului și ultimului element dintr-un container, iar suma este valoarea inițială a variabilei sumă.
(ii) suma_parțială
Sintaxa generală a funcției partial_sum este:
partial_sum(first, last, b) Aici
prima: adresa elementului de pornire al containerului.
Ultimul: adresa ultimului element al containerului.
B: matrice în care va fi stocată suma parțială a elementelor matrice corespunzătoare.
Astfel funcția partial_sum calculează suma parțială a matricei corespunzătoare sau a elementelor vectoriale și le stochează într-o matrice diferită.
Dacă a reprezintă elementul din intervalul (primul, ultimul) și b reprezintă elementul din matricea rezultată, atunci partial_sum va fi:
b0 = a0
b1 = a0+a1
b2 = a0 + a1 + a2 ... și așa mai departe.
Să vedem un exemplu pentru a demonstra atât Aceste funcții într-un program:
#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: '< Ieșire:
Rezultatul funcției de acumulare este: 142
sumă_parțială a matricei A: 21 46 110 142
Așa cum se arată în programul de mai sus, calculăm mai întâi suma elementelor folosind funcția de acumulare și apoi numim funcția sumă_parțială pentru a calcula suma parțială a elementelor matrice corespunzătoare.
Alți algoritmi suportați de STL și antet:
- iotă: Umple un interval cu creșteri succesive ale valorii inițiale.
- reduce: Asemănător acumulării, cu excepția căderii din funcțiune
- produs intern: Calculează produsul interior a două game de elemente.
- diferență_adiacentă: Calculează diferențele dintre elementele adiacente dintr-un interval.
- scan_inclusiv: Similar cu partial_sum, include elementul de intrare ith în suma ith.
- scan_exclusiv: Similar cu partial_sum, exclude elementul de intrare ith din suma ith.
Algoritmi nemodificatori
Algoritmii care nu modifică sau care nu se transformă sunt cei care nu modifică conținutul containerului în care operează. STL acceptă mulți algoritmi care nu modifică.
Am enumerat câteva dintre ele mai jos:
- numara: Returnează numărul de valori din intervalul dat.
- egal: Compară elementele din două intervale și returnează o valoare booleană.
- nepotrivire: Returnează o pereche de iteratoare atunci când sunt comparate două iteratoare și apare o nepotrivire.
- căutare: Caută o secvență dată într-un interval dat.
- căutare_n: Căutați într-un interval dat o secvență a valorii de numărare.
Să elaborăm mai multe despre funcțiile „numărare” și „egală” !!
count (first, last, value) returnează de câte ori apare „value” în intervalul (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= '< Ieșire:
cum să adăugați lucruri la o matrice Java
De câte ori apare „5” într-o matrice = 4
După cum vedeți în acest cod, definim o valoare a matricei și apoi apelăm funcția de numărare oferind intervalul valorii și valorii de 5. Funcția returnează numărul de ori (numărare) valoarea 5 apare în interval.
Să luăm un exemplu pentru a demonstra funcția „egală”.
equal (first1, last1, first2) compară elementele din intervalul (first1, last1) cu primul element indicat de first2 și returnează true dacă toate elementele sunt egale altfel 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'; } Ieșire:
Elementele din două game nu sunt egale.
În codul de mai sus, definim două matrice întregi și comparăm elementele lor corespunzătoare utilizând funcția „egal”. Deoarece elementele matricei nu sunt aceleași, egal returnează fals.
Modificarea algoritmilor
Algoritmii de modificare modifică sau transformă conținutul containerelor atunci când sunt executate.
Cele mai populare și utilizate pe scară largă algoritmi de modificare includ „swap” și „reverse” care schimbă două valori și inversează elementele din container.
Să vedem exemplele pentru aceste funcții:
#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< Ieșire:
Vector 1: 2 4 6 8 10
Vector 2: 1 1 2 3 5
Vector inversat 1: 10 8 6 4 2
Vector inversat 2: 5 3 2 1 1
După cum s-a văzut, avem doi vectori definiți în program. Mai întâi folosind funcția swap schimbăm conținutul vectorilor1 și vectorului2. Apoi, inversăm conținutul fiecărui vector folosind funcția inversă.
Programul transmite Vector 1 și Vector 2 după schimbarea conținutului și, de asemenea, după inversarea conținutului.
Operațiuni minime și maxime
Această categorie este formată din funcții min și max care află valorile minime și maxime, respectiv, din cele două valori date.
Sintaxa generală a acestor funcții este:
max(objecta, objectb); min(objecta, objectb); De asemenea, putem furniza un al treilea parametru pentru a furniza „compare_function” sau criteriile care ar fi utilizate pentru a găsi valoarea minimă / maximă. Dacă acest lucru nu este furnizat, atunci funcția max folosește operatorul „>” pentru comparație, în timp ce funcția min folosește „<’ operator for comparison.
Să demonstrăm aceste funcții folosind un program.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Ieșire:
Max de 4 și 5: 5
Min de 4 și 5: 4
Șir maxim: șir mai mic
Min String: șir mai lung
Programul de mai sus este auto-explicativ, deoarece folosim funcțiile min și max pe numerele mai întâi și apoi pe șiruri. Deoarece nu am oferit opțiunea „compare_function”, funcțiile min / max au acționat respectiv asupra operatorilor „”.
Concluzie
Cu aceasta, am ajuns la sfârșitul acestui tutorial despre algoritmi majori utilizați în STL.
În tutorialele noastre ulterioare, vom discuta iteratorii în detaliu, împreună cu funcțiile comune utilizate în STL, indiferent de containere.
=> Citiți seria Easy C ++ Training.
Lectură recomandată