algorithms stl
En eksplicit undersøgelse af algoritmer og dens typer i STL.
STL understøtter forskellige algoritmer, der virker på containere gennem iteratorer. Da disse algoritmer virker på iteratorer og ikke direkte på containere, kan de bruges på alle typer iteratorer.
STL-algoritmer er indbyggede og sparer således meget tid og er også mere pålidelige. De forbedrer også genanvendelighed af kode. Disse algoritmer er normalt kun et funktionsopkald, og vi behøver ikke skrive udtømmende kode for at implementere dem.
=> Se efter hele C ++ træningsserien her.
Hvad du vil lære:
Typer af STL-algoritmer
STL understøtter følgende typer algoritmer
- Søg algoritmer
- Sorteringsalgoritmer
- Numeriske algoritmer
- Ikke-transformerende / modificerende algoritmer
- Transformering / ændring af algoritmer
- Mindste og maksimale operationer
Vi vil diskutere hver af disse typer i detaljer i de følgende afsnit.
Søg og sorter algoritmer
Den fremtrædende søgealgoritme i STL er en binær søgning. Binær søgealgoritme fungerer på et sorteret array og søger efter elementet ved at opdele arrayet i halvdelen.
Dette gøres ved først at sammenligne det element, der skal søges, med det midterste element i arrayet og derefter begrænse søgningen til 1St.halv eller 2ndhalvdelen af arrayet afhængigt af, om det element, der skal søges, er mindre end eller større end det midterste element.
Binær søgning er den mest anvendte søgealgoritme.
Dens generelle syntaks er:
binary_search(startaddr, endaddr, key) Hvor,
startaddr: adresse på det første element i arrayet.
endaddr: adresse på det sidste element i arrayet.
nøgle: det element, der skal søges i.
STL giver os en 'Sort' -algoritme, der bruges til at arrangere elementerne i en container i en bestemt rækkefølge.
Generel syntaks af sorteringsalgoritme er:
sort(startAddr, endAddr); Hvor,
startAddr: startadresse for det array, der skal sorteres.
endAddr: slutadresse på det array, der skal sorteres.
Internt bruger STL Quicksort-algoritmen til at sortere arrayet.
Lad os tage et eksempel for at demonstrere binær søgning og sorteringsalgoritme:
#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 Produktion:
Sorted Array er
0 1 2 3 4 5 6 7 8 9
Nøgle = 2 fundet i arrayet
Nøgle = 10 blev ikke fundet i arrayet
I den givne kode har vi angivet et array, hvor vi skal søge på et nøgleelement ved hjælp af binær søgning. Da binær søgning kræver et sorteret array, sorterer vi først arrayet ved hjælp af 'sorterings' -algoritmen og foretager derefter et funktionsopkald til 'binary_search' ved at angive de nødvendige parametre.
Først kalder vi binær_søgningsalgoritmen for nøgle = 2 og derefter nøgle = 10. På denne måde med kun et funktionsopkald kan vi nemt foretage en binær søgning på en matrix eller sortere den.
Numeriske algoritmer
header i STL indeholder forskellige funktioner, der fungerer på numeriske værdier. Disse funktioner spænder fra at finde lcds, gcds til endda at beregne summen af elementerne i en beholder som arrays, vektorer over et givet område osv.
Vi vil diskutere et par vigtige funktioner her med eksempler.
(i) ophobes
Den generelle syntaks for akkumuleringsfunktionen er:
accumulate (first, last, sum); Denne funktion returnerer summen af alle elementerne inden for et område [første, sidste] i en variabel sum. I ovenstående syntaksnotation er første og sidste adresserne til det første og sidste element i en container, og sum er den indledende værdi af sumvariablen.
(ii) delvis_sum
Den generelle syntaks for funktionen partial_sum er:
partial_sum(first, last, b) Her
først: adresse på containerens startelement.
Sidste: adresse på det sidste element i containeren.
B: matrix, hvor den delvise sum af de tilsvarende matrixelementer lagres.
den bedste software til at rense din computer
Således beregner partial_sum-funktionen delsummen af det tilsvarende array eller vektorelementerne og gemmer dem i et andet array.
Hvis a repræsenterer elementet i området [første, sidste] og b repræsenterer elementet i den resulterende matrix, vil partial_sum være:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... og så videre.
Lad os se et eksempel for at demonstrere begge disse disse funktioner i et 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: '< Produktion:
Resultatet af akkumuleringsfunktionen er: 142
partial_sum af array A: 21 46 110 142
Som vist i ovenstående program beregner vi først summen af elementerne ved hjælp af akkumuleringsfunktionen, og derefter kalder vi funktionen partial_sum for at beregne den delvise sum af de tilsvarende arrayelementer.
hvordan man finder netværkssikkerhedsnøgle på Android
Andre algoritmer understøttet af STL og header:
- iota: Udfylder et interval med successive intervaller af startværdien.
- reducere: Svarende til at akkumulere, undtagen ude af drift.
- indvendige: Beregner det indre produkt af to serier af elementer.
- tilstødende_forskel: Beregner forskellene mellem tilstødende elementer i et interval.
- inklusive_scan: Svarende til partial_sum, inkluderer ith-inputelementet i ith-summen.
- eksklusiv_scan: Svarende til partial_sum, ekskluderer ith-inputelementet fra ith-summen.
Ikke-modificerende algoritmer
Ikke-modificerende eller ikke-transformerende algoritmer er dem, der ikke ændrer indholdet af beholderen, de arbejder i. STL understøtter mange ikke-modificerende algoritmer.
Vi har listet nogle af dem nedenfor:
- tælle: Returnerer antallet af værdier i det givne interval.
- lige: Sammenligner elementerne i to områder og returnerer en boolsk værdi.
- uoverensstemmelse: Returnerer et par iterator, når to iteratorer sammenlignes, og der opstår en uoverensstemmelse.
- Søg: Søger efter en given sekvens i et givet interval.
- search_n: Søger inden for et givet interval for en sekvens af tællingsværdien.
Lad os uddybe mere om 'tælle' og 'lige' funktioner !!
count (første, sidste, værdi) returnerer antallet af gange, hvor 'værdien' vises i området [første, sidste].
#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= '< Produktion:
Antallet af gange '5' vises i en matrix = 4
Som du ser i denne kode, definerer vi en matrixværdi og kalder derefter tællefunktionen ved at angive værdiområdet og værdien på 5. Funktionen returnerer antallet af gange (optælling) værdi 5 vises i området.
Lad os tage et eksempel for at demonstrere den 'lige' funktion.
lige (first1, last1, first2) sammenligner elementerne i området [first1, last1] med det første element peget på first2 og returnerer true, hvis alle elementerne er ens ellers falske.
#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'; } Produktion:
Elementer i to områder er ikke ens.
I koden ovenfor definerer vi to heltal arrays og sammenligner deres tilsvarende elementer ved hjælp af funktionen 'lige'. Da elementerne i arrayet ikke er de samme, returnerer lige falsk.
Ændring af algoritmer
Modificerende algoritmer ændrer eller transformerer indholdet af containerne, når de udføres.
De mest populære og udbredte modificeringsalgoritmer inkluderer 'swap' og 'reverse', der bytter to værdier og vender henholdsvis elementerne i containeren.
Lad os se eksemplerne på disse funktioner:
#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< Produktion:
Vektor 1: 2 4 6 8 10
Vektor 2: 1 1 2 3 5
Omvendt vektor 1: 10 8 6 4 2
Omvendt vektor 2: 5 3 2 1 1
Som set har vi to vektorer defineret i programmet. Først ved hjælp af swap-funktionen bytter vi indholdet af vector1 og vector2. Derefter vender vi indholdet af hver vektor ved hjælp af omvendt funktion.
Programmet udsender Vector 1 og Vector 2 efter at have byttet indholdet og også efter at have vendt indholdet.
Minimum og maksimal drift
Denne kategori består af min- og max-funktioner, der finder henholdsvis minimums- og maksimumværdier ud fra de givne to værdier.
Den generelle syntaks for disse funktioner er:
max(objecta, objectb); min(objecta, objectb); Vi kan også give en tredje parameter til at levere 'sammenligne_funktion' eller de kriterier, der ville blive brugt til at finde min / maks værdi. Hvis dette ikke er angivet, bruger max-funktionen operatoren '>' til sammenligning, mens min-funktionen bruger '<’ operator for comparison.
Lad os demonstrere disse funktioner ved hjælp af et program.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Produktion:
Maks. 4 og 5: 5
Min. 4 og 5: 4
Max streng: mindre streng
Min streng: længere streng
Ovenstående program er selvforklarende, da vi bruger min- og max-funktioner på numrene først og derefter på strenge. Da vi ikke leverede valgfri 'sammenligningsfunktion', handlede min / max-funktionerne på henholdsvis '' operatører.
Konklusion
Med dette er vi kommet til slutningen af denne vejledning om vigtige algoritmer, der bruges i STL.
I vores efterfølgende tutorials vil vi diskutere iteratorer i detaljer sammen med de almindelige funktioner, der bruges i STL, uanset containere.
=> Læs gennem Easy C ++ træningsserien.
Anbefalet læsning