algorithms stl
Eksplicitna studija algoritama i njegovih vrsta u STL-u.
najbolji softver za održavanje sustava za Windows 10
STL podržava razne algoritme koji djeluju na spremnike putem iteratora. Kako ti algoritmi djeluju na iteratore, a ne izravno na spremnike, mogu se koristiti na bilo kojoj vrsti iteratora.
STL algoritmi su ugrađeni i tako štede puno vremena te su i pouzdaniji. Oni također poboljšavaju ponovnu upotrebu koda. Ti su algoritmi obično samo jedan poziv funkcije i ne trebamo pisati iscrpan kôd da bismo ih implementirali.
=> Ovdje potražite cijelu seriju treninga za C ++.
Što ćete naučiti:
Vrste STL algoritama
STL podržava sljedeće vrste algoritama
- Algoritmi pretraživanja
- Algoritmi sortiranja
- Numerički algoritmi
- Algoritmi koji se ne transformiraju / modificiraju
- Transformiranje / modificiranje algoritama
- Minimalni i Maksimalni rad
O svakoj od ovih vrsta detaljno ćemo razgovarati u sljedećim odlomcima.
Pretraživanje i sortiranje algoritama
Istaknuti algoritam pretraživanja u STL-u je binarno pretraživanje. Binarni algoritam pretraživanja djeluje na razvrstanom nizu i traži element dijeljenjem niza na pola.
To se postiže tako da se prvo usporedi element koji se traži sa srednjim elementom niza, a zatim ograniči pretragu na 1svpola ili 2ndpolovica niza, ovisno o tome je li element koji se traži manji ili veći od srednjeg elementa.
Binarno pretraživanje najčešće su korišteni algoritmi pretraživanja.
Njegova opća sintaksa je:
binary_search(startaddr, endaddr, key) Gdje,
startaddr: adresa prvog elementa niza.
endaddr: adresa posljednjeg elementa niza.
ključ: element koji se traži.
STL nam pruža algoritam 'Sort' koji se koristi za raspoređivanje elemenata u spremniku određenim redoslijedom.
Općenita sintaksa algoritma sortiranja je:
sort(startAddr, endAddr); Gdje,
startAddr: početna adresa niza za sortiranje.
endAddr: krajnja adresa niza za sortiranje.
Interno STL koristi Quicksort algoritam za sortiranje niza.
Uzmimo primjer za demonstraciju binarnog algoritma pretraživanja i sortiranja:
#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 Izlaz:
Sortirani niz je
0 1 2 3 4 5 6 7 8 9
Ključ = 2 pronađen u polju
Ključ = 10 nije pronađen u polju
U danom kodu dali smo niz u kojem trebamo pretražiti ključni element pomoću binarnog pretraživanja. Budući da binarno pretraživanje zahtijeva razvrstani niz, prvo sortiramo niz pomoću algoritma 'sortiraj', a zatim upućujemo poziv funkcije 'binarni_traženje' davanjem potrebnih parametara.
Prvo pozivamo algoritam binarnog_traženja za ključ = 2, a zatim za ključ = 10. Na taj način sa samo jednim pozivom funkcije možemo prikladno izvršiti binarno pretraživanje niza ili ga sortirati.
Numerički algoritmi
zaglavlje u STL-u sadrži razne funkcije koje djeluju na numeričke vrijednosti. Te se funkcije kreću od pronalaska lcds-a, gcds-a do čak izračunavanja zbroja elemenata u spremniku poput nizova, vektora u zadanom rasponu itd.
Ovdje ćemo s primjerima razgovarati o nekoliko važnih funkcija.
(i) akumulirati
Opća sintaksa funkcije akumuliranja je:
accumulate (first, last, sum); Ova funkcija vraća zbroj svih elemenata u rasponu (prvi, zadnji) u varijabilnom zbroju. U gornjoj sintaksnoj notaciji first i last su adrese prvog i zadnjeg elementa u spremniku, a sum je početna vrijednost varijable sum.
(ii) djelomična_zbroj
Općenita sintaksa funkcije parcijalne_sume je:
partial_sum(first, last, b) Ovdje
prvo: adresa početnog elementa spremnika.
Posljednje: adresa zadnjeg elementa spremnika.
B: niz u kojem će se pohraniti djelomični zbroj odgovarajućih elemenata niza.
Dakle, funkcija djelomične sume izračunava djelomični zbroj odgovarajućeg niza ili vektorskih elemenata i pohranjuje ih u drugi niz.
Ako a predstavlja element u rasponu (prvi, zadnji), a b predstavlja element u rezultantnom nizu, tada će parcijalni_zbroj biti:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... i tako dalje.
Pogledajmo primjer za demonstraciju oba Ese funkcije u programu:
#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: '< Izlaz:
Rezultat funkcije akumuliranja je: 142
djelomična_suma niza A: 21 46 110 142
Kao što je prikazano u gornjem programu, prvo izračunavamo zbroj elemenata pomoću funkcije akumuliranja, a zatim pozivamo funkciju parcijalni_zbroj za izračunavanje djelomičnog zbroja odgovarajućih elemenata niza.
Ostali algoritmi podržani od STL-a i zaglavlja:
- jota: Ispunjava raspon uzastopnim povećanjem početne vrijednosti.
- smanjiti: Slično akumuliranju, osim izvan reda.
- unutarnji proizvod: Izračunava unutarnji umnožak dvaju raspona elemenata.
- susjedna_razlika: Izračunava razlike između susjednih elemenata u rasponu.
- inclusive_scan: Slično djelomičnoj_sumi, uključuje i-ti ulazni element u i-tom zbroju.
- exclusive_scan: Slično djelomičnoj_sumi, isključuje i-i ulazni element iz i-tog zbroja.
Algoritmi koji se ne mijenjaju
Algoritmi koji ne mijenjaju ili ne transformiraju oni su koji ne mijenjaju sadržaj spremnika u kojem rade. STL podržava mnoge algoritme koji se ne mijenjaju.
Neke smo naveli u nastavku:
- računati: Vraća broj vrijednosti u danom rasponu.
- jednak: Uspoređuje elemente u dva raspona i vraća logičku vrijednost.
- neusklađenost: Vraća par iteratora kada se usporede dva iteratora i dogodi se neusklađenost.
- traži: Pretražuje zadani slijed u zadanom rasponu.
- search_n: Pretražuje niz zadanih vrijednosti u nizu vrijednosti brojanja.
Razradimo više o funkcijama 'brojanja' i 'jednakih' !!
count (prva, zadnja, vrijednost) vraća koliko se puta vrijednost pojavljuje u rasponu (prva, zadnja).
#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= '< Izlaz:
Koliko se puta niz 5 pojavljuje u nizu = 4
Kao što vidite u ovom kodu, definiramo vrijednost niza i zatim pozivamo funkciju count pružajući raspon vrijednosti i vrijednosti 5. Funkcija vraća broj puta (count) vrijednosti 5 koja se pojavljuje u rasponu.
Uzmimo primjer za demonstraciju funkcije ‘jednake’.
jednak (first1, last1, first2) uspoređuje elemente u rasponu (first1, last1) s prvim elementom na koji pokazuje first2 i vraća true ako su svi elementi jednaki, inače 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'; } Izlaz:
Elementi u dva raspona nisu jednaki.
U gornjem kodu definiramo dva cjelovita niza i uspoređujemo njihove odgovarajuće elemente pomoću funkcije ‘jednako’. Kako elementi niza nisu isti, jednak vraća false.
Modificiranje algoritama
Modificirajući algoritmi mijenjaju ili transformiraju sadržaj spremnika kada se izvršavaju.
Najpopularniji i široko korišteni algoritmi za modificiranje uključuju 'zamjenu' i 'obrnuto' koji zamjenjuju dvije vrijednosti i preokreću elemente u spremniku.
Pogledajmo primjere za ove funkcije:
kopirajte DVD na tvrdi disk besplatno
#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< Izlaz:
Vektor 1: 2 4 6 8 10
Vektor 2: 1 1 2 3 5
Obrnuti vektor 1: 10 8 6 4 2
Obrnuti vektor 2: 5 3 2 1 1
Kao što se vidi, u programu su definirana dva vektora. Prvo pomoću funkcije swap zamijenimo sadržaj vektora1 i vektora2. Dalje, preokrećemo sadržaj svakog vektora pomoću funkcije obrnute.
Program izbacuje Vector 1 i Vector 2 nakon zamjene njihovog sadržaja i također nakon preokretanja sadržaja.
Minimalne i maksimalne operacije
Ova se kategorija sastoji od min i max funkcija koje doznaju minimalne i maksimalne vrijednosti iz dane dvije vrijednosti.
Opća sintaksa ovih funkcija je:
max(objecta, objectb); min(objecta, objectb); Također možemo pružiti treći parametar za pružanje funkcije 'usporedi_funkciju' ili kriterije koji će se koristiti za pronalaženje min / max vrijednosti. Ako to nije navedeno, tada funkcija max koristi operator '>' za usporedbu, dok funkcija min koristi '<’ operator for comparison.
Pokažimo ove funkcije pomoću programa.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Izlaz:
Maksimalno 4 i 5: 5
Min od 4 i 5: 4
Maks. Niz: manji niz
Min string: duži niz
Gornji program sam po sebi objašnjava jer prvo koristimo min i max funkcije na brojevima, a zatim na žicama. Budući da nismo pružili opcionalnu funkciju 'usporedi_funkciju', funkcije min / max djelovale su na operatore ''.
Zaključak
Ovim smo došli do kraja ovog vodiča o glavnim algoritmima koji se koriste u STL-u.
U našim slijedećim vodičima detaljno ćemo raspravljati o iteratorima zajedno sa uobičajenim funkcijama koje se koriste u STL-u, bez obzira na spremnike.
=> Pročitajte seriju Easy C ++ Training Series.
Preporučena literatura