algorithms stl
En eksplisitt studie av algoritmer og dens typer i STL.
den beste videokonvertereren for mac
STL støtter forskjellige algoritmer som virker på containere gjennom iteratorer. Siden disse algoritmene virker på iteratorer og ikke direkte på containere, kan de brukes på alle typer iteratorer.
STL-algoritmer er innebygd og sparer dermed mye tid og er også mer pålitelige. De forbedrer også gjenbrukbarhet. Disse algoritmene er normalt bare ett funksjonsanrop, og vi trenger ikke skrive uttømmende kode for å implementere dem.
=> Se etter hele C ++ treningsserien her.
Hva du vil lære:
Typer STL-algoritmer
STL støtter følgende typer algoritmer
- Søk algoritmer
- Sorteringsalgoritmer
- Numeriske algoritmer
- Ikke-transformerende / modifiserende algoritmer
- Transformerende / modifiserende algoritmer
- Minimum og maksimal drift
Vi vil diskutere hver av disse typene i detalj i de følgende avsnittene.
Søk og sorter algoritmer
Den fremtredende søkealgoritmen i STL er et binært søk. Binær søkealgoritme opererer på en sortert matrise og søker etter elementet ved å dele matrisen i halvparten.
Dette gjøres ved å først sammenligne elementet som skal søkes med midtelementet i matrisen, og deretter begrense søket til 1St.halv eller 2ndhalvparten av matrisen avhengig av om elementet som skal søkes, er mindre enn eller større enn det midterste elementet.
Binært søk er de mest brukte søkealgoritmene.
Den generelle syntaksen er:
binary_search(startaddr, endaddr, key) Hvor,
startaddr: adresse til det første elementet i matrisen.
endaddr: adresse til det siste elementet i matrisen.
nøkkel: elementet som skal søkes.
STL gir oss en 'sorterings' -algoritme som brukes til å ordne elementene i en container i en bestemt rekkefølge.
Generell syntaks av sorteringsalgoritme er:
sort(startAddr, endAddr); Hvor,
startAddr: startadressen til matrisen som skal sorteres.
endAddr: sluttadresse til matrisen som skal sorteres.
Internt bruker STL Quicksort-algoritmen til å sortere matrisen.
La oss ta et eksempel for å demonstrere binær søk 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 Produksjon:
Sorted Array er
0 1 2 3 4 5 6 7 8 9
Nøkkel = 2 funnet i matrisen
Nøkkel = 10 ble ikke funnet i matrisen
I den gitte koden har vi gitt en matrise der vi trenger å søke på et nøkkelelement ved hjelp av binært søk. Siden binært søk krever en sortert matrise, sorterer vi først matrisen ved hjelp av 'sorterings' -algoritmen, og deretter ringer vi en funksjon til 'binærsøk' ved å oppgi de nødvendige parametrene.
Først kaller vi binærsøk-algoritmen for nøkkel = 2 og deretter for nøkkel = 10. På denne måten med bare en funksjonsanrop kan vi enkelt gjøre et binært søk på en matrise eller sortere den.
Numeriske algoritmer
topptekst i STL inneholder forskjellige funksjoner som fungerer på numeriske verdier. Disse funksjonene spenner fra å finne lcds, gcds til til og med å beregne summen av elementene i en beholder som matriser, vektorer over et gitt område, etc.
Vi vil diskutere noen viktige funksjoner her med eksempler.
(i) akkumulere
Den generelle syntaksen for akkumuleringsfunksjonen er:
accumulate (first, last, sum); Denne funksjonen returnerer summen av alle elementene i et område (første, siste) i en variabel sum. I ovennevnte syntaksnotasjon er første og siste adressene til det første og siste elementet i en container, og sum er den opprinnelige verdien av sumvariabelen.
(ii) delvis_sum
Den generelle syntaksen til partial_sum-funksjonen er:
partial_sum(first, last, b) Her
først: adresse til startelementet til containeren.
Siste: adresse til det siste elementet i containeren.
B: matrise der delsummen av de tilsvarende matriseelementene vil bli lagret.
Dermed beregner partial_sum-funksjonen delsummen av den tilsvarende matrisen eller vektorelementene og lagrer dem i en annen matrise.
Hvis a representerer elementet i området (første, siste) og b representerer elementet i den resulterende matrisen, vil partial_sum være:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... og så videre.
La oss se et eksempel for å demonstrere begge disse disse funksjonene 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: '< Produksjon:
Resultatet av akkumuleringsfunksjonen er: 142
partial_sum of array A: 21 46 110 142
Som vist i programmet ovenfor, beregner vi først summen av elementene ved hjelp av akkumuleringsfunksjonen, og deretter kaller vi funksjonen partial_sum for å beregne den delvise summen av de tilsvarende matriseelementene.
Andre algoritmer som støttes av STL og header:
- iota: Fyller et område med påfølgende trinn av startverdien.
- redusere: Ligner på å akkumulere, unntatt ute av drift.
- indre skap: Beregner det indre produktet av to utvalg av elementer.
- tilstøtende_forskjell: Beregner forskjellene mellom tilstøtende elementer i et område.
- inklusive_skanning: Ligner på partial_sum, inkluderer ith-inngangselementet i ith-summen.
- eksklusiv_skanning: I likhet med partial_sum, ekskluderer ith-inngangselementet fra ith-summen.
Ikke-modifiserende algoritmer
Ikke-modifiserende eller ikke-transformerende algoritmer er de som ikke endrer innholdet i beholderen de opererer i. STL støtter mange ikke-modifiserende algoritmer.
Vi har listet opp noen av dem nedenfor:
- telle: Returnerer antall verdier i det gitte området.
- lik: Sammenligner elementene i to områder og returnerer en boolsk verdi.
- uoverensstemmelse: Returnerer et par iteratorer når to iteratorer sammenlignes og det oppstår en uoverensstemmelse.
- Søk: Søker etter en gitt sekvens i et gitt område.
- søk_n: Søker i et gitt område etter en sekvens av telleverdien.
La oss utdype mer om 'telling' og 'like' funksjoner !!
count (first, last, value) returnerer antall ganger ‘verdien’ vises i området (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= '< Produksjon:
Antall ganger ‘5’ vises i en matrise = 4
Som du ser i denne koden, definerer vi en matriseverdi og kaller deretter tellefunksjonen ved å oppgi verdiområdet og verdien 5. Funksjonen returnerer antall ganger (telle) verdi 5 vises i området.
La oss ta et eksempel for å demonstrere den 'like' funksjonen.
like (first1, last1, first2) sammenligner elementene i området (first1, last1) med det første elementet som er pekt av first2 og returnerer true hvis alle elementene er like 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'; } Produksjon:
Elementer i to områder er ikke like.
I koden ovenfor definerer vi to heltallmatriser og sammenligner de tilsvarende elementene ved hjelp av 'lik' -funksjonen. Siden elementene i matrisen ikke er de samme, returnerer like false.
Endring av algoritmer
Modifiserende algoritmer endrer eller transformerer innholdet i containerne når de kjøres.
De mest populære og mest brukte modifiseringsalgoritmene inkluderer 'bytte' og 'omvendt' som bytter to verdier og reverserer elementene i henholdsvis beholderen.
La oss se eksemplene på disse funksjonene:
c ++ røye til int
#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< Produksjon:
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 sett har vi to vektorer definert i programmet. Først ved å bruke byttefunksjonen bytter vi innholdet av vektor1 og vector2. Deretter reverserer vi innholdet i hver vektor ved hjelp av reversfunksjonen.
Programmet sender ut Vector 1 og Vector 2 etter å ha byttet innholdet og også etter å ha reversert innholdet.
Minimum og maksimal drift
Denne kategorien består av min- og maksfunksjoner som finner ut henholdsvis minimums- og maksimumsverdiene fra de gitte to verdiene.
Den generelle syntaksen for disse funksjonene er:
max(objecta, objectb); min(objecta, objectb); Vi kan også gi en tredje parameter for å gi 'sammenligne_funksjon' eller kriteriene som vil bli brukt for å finne min / maks verdi. Hvis dette ikke er gitt, bruker maksfunksjonen operatøren ‘>’ til sammenligning mens min-funksjonen bruker ‘<’ operator for comparison.
La oss demonstrere disse funksjonene ved hjelp av 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< Produksjon:
Maks 4 og 5: 5
Min. 4 og 5: 4
Maks streng: mindre streng
Min streng: lengre streng
Ovennevnte program er selvforklarende ettersom vi bruker min og maks funksjoner på tallene først og deretter på strenger. Siden vi ikke ga valgfri 'sammenligningsfunksjon', handlet min / maks-funksjonene på henholdsvis '' operatører.
Konklusjon
Med dette har vi kommet til slutten av denne veiledningen om viktige algoritmer som brukes i STL.
I de påfølgende veiledningene vil vi diskutere iteratorer i detalj sammen med de vanlige funksjonene som brukes i STL, uavhengig av containere.
=> Les gjennom Easy C ++ Training Series.
Anbefalt lesing