algorithms stl
Explicitná štúdia algoritmov a ich typov v STL.
STL podporuje rôzne algoritmy, ktoré pôsobia na kontajnery prostredníctvom iterátorov. Pretože tieto algoritmy pôsobia na iterátory a nie priamo na kontajnery, môžu sa použiť na akýkoľvek typ iterátorov.
Algoritmy STL sú zabudované a šetria tak veľa času a sú tiež spoľahlivejšie. Tiež zvyšujú opätovnú použiteľnosť kódu. Tieto algoritmy sú zvyčajne iba jedným volaním funkcie a na ich implementáciu nemusíme písať vyčerpávajúci kód.
=> Celú sériu školení pre C ++ nájdete tu.
Čo sa dozviete:
Typy STL algoritmov
STL podporuje nasledujúce typy algoritmov
- Vyhľadávacie algoritmy
- Algoritmy triedenia
- Numerické algoritmy
- Netransformačné / modifikujúce algoritmy
- Transformačné / modifikačné algoritmy
- Minimálna a maximálna prevádzka
Každému z týchto typov sa budeme podrobne venovať v nasledujúcich odsekoch.
Hľadať a triediť algoritmy
Prominentný vyhľadávací algoritmus v STL je binárne vyhľadávanie. Algoritmus binárneho vyhľadávania pracuje na triedenom poli a vyhľadáva prvok rozdelením poľa na polovicu.
To sa deje tak, že sa najskôr porovná hľadaný prvok so stredným prvkom poľa a potom sa vyhľadávanie obmedzí na 1svpolovica alebo 2ndpolovica poľa v závislosti od toho, či je hľadaný prvok menší alebo väčší ako stredný prvok.
Binárne vyhľadávanie je najbežnejšie používaným vyhľadávacím algoritmom.
Jeho všeobecná syntax je:
binary_search(startaddr, endaddr, key) Kde,
startaddr: adresa prvého prvku poľa.
endaddr: adresa posledného prvku poľa.
kľúč: hľadaný prvok.
STL nám poskytuje algoritmus „Zoradenie“, ktorý sa používa na usporiadanie prvkov v kontajneri v konkrétnom poradí.
Všeobecná syntax algoritmu triedenia je:
sort(startAddr, endAddr); Kde,
startAddr: počiatočná adresa poľa, ktoré sa má zoradiť.
endAddr: koncová adresa poľa, ktoré sa má triediť.
Interne STL používa na triedenie poľa algoritmus Quicksort.
Uveďme si príklad na demonštráciu algoritmu binárneho vyhľadávania a triedenia:
#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 Výkon:
Zoradené pole je
0 1 2 3 4 5 6 7 8 9
Kľúč = 2 nájdený v poli
Kľúč = 10 sa v poli nenašiel
V danom kóde sme poskytli pole, v ktorom potrebujeme prehľadať kľúčový prvok pomocou binárneho vyhľadávania. Pretože binárne vyhľadávanie vyžaduje zoradené pole, najskôr radíme pole pomocou algoritmu „sort“ a potom pomocou požadovaných parametrov vykonáme volanie funkcie na „binary_search“.
Najskôr zavoláme algoritmus binary_search pre key = 2 a potom pre key = 10. Takto iba s jedným volaním funkcie môžeme pohodlne vykonať binárne vyhľadávanie v poli alebo ho zoradiť.
Numerické algoritmy
hlavička v STL obsahuje rôzne funkcie, ktoré pracujú s číselnými hodnotami. Tieto funkcie siahajú od nájdenia LCD, GCD až po výpočet súčtu prvkov v kontajneri, ako sú polia, vektory v danom rozsahu atď.
Tu si ukážeme niekoľko dôležitých funkcií s príkladmi.
i) sa hromadia
Všeobecná syntax funkcie akumulácie je:
accumulate (first, last, sum); Táto funkcia vráti súčet všetkých prvkov v rozsahu [prvý, posledný] v premennom súčte. Vo vyššie uvedenom označení syntaxe sú prvý a posledný adresy prvého a posledného prvku v kontajneri a súčet je počiatočná hodnota premennej súčet.
(ii) čiastočné_sum
Všeobecná syntax funkcie partial_sum je:
partial_sum(first, last, b) Tu
first: adresa východiskového prvku kontajnera.
Posledná: adresa posledného prvku kontajnera.
B: pole, v ktorom bude uložený čiastočný súčet zodpovedajúcich prvkov poľa.
java java rozhovor otázky s odpoveďami
Funkcia partial_sum teda vypočíta čiastočný súčet zodpovedajúceho poľa alebo vektorových prvkov a uloží ich do iného poľa.
Ak a predstavuje prvok v rozsahu [prvý, posledný] a b predstavuje prvok vo výslednom poli, čiastočný_čet bude:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... a tak ďalej.
Pozrime sa na príklad, ktorý demonštruje obe th tieto funkcie v programe:
#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: '< Výkon:
Výsledok akumulačnej funkcie je: 142
čiastočné_číslo poľa A: 21 46 110 142
Ako je znázornené vo vyššie uvedenom programe, najskôr pomocou funkcie akumulácie vypočítame súčet prvkov a potom zavoláme funkciu partial_sum na výpočet čiastočného súčtu zodpovedajúcich prvkov poľa.
Ďalšie algoritmy podporované STL a hlavičkou:
- iota: Vyplní rozsah postupnými prírastkami počiatočnej hodnoty.
- znížiť: Podobné sa hromadí, s výnimkou mimo prevádzky.
- vnútorný_produkt: Vypočíta vnútorný súčin dvoch rozsahov prvkov.
- susedný_rozdiel: Vypočíta rozdiely medzi susednými prvkami v rozsahu.
- inclusive_scan: Podobne ako partial_sum, zahŕňa i-tý vstupný prvok do i-tého súčtu.
- exclusive_scan: Podobne ako čiastočný_čet, vylučuje i-tý vstupný prvok zo i-tého súčtu.
Nemodifikujúce algoritmy
Nemodifikujúce alebo netransformačné algoritmy sú algoritmy, ktoré nemenia obsah kontajnera, v ktorom pracujú. STL podporuje mnoho nemodifikujúcich algoritmov.
Niektoré z nich sme uviedli nižšie:
- počet: Vráti počet hodnôt v danom rozsahu.
- rovnaké: Porovná prvky v dvoch rozsahoch a vráti boolovskú hodnotu.
- nesúlad: Vráti pár iterátorov, keď sa porovnajú dva iterátory a dôjde k nesúladu.
- Vyhľadávanie: Vyhľadá danú sekvenciu v danom rozsahu.
- search_n: Vyhľadá v danom rozsahu postupnosť hodnoty počítania.
Poďme si podrobnejšie vysvetliť funkcie „počítať“ a „rovnaké“ !!
count (first, last, value) vráti počet zobrazení hodnoty v rozsahu [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= '< Výkon:
Počet výskytov „5“ v poli = 4
Ako vidíte v tomto kóde, definujeme hodnotu poľa a potom zavoláme funkciu count poskytnutím rozsahu hodnoty a hodnoty 5. Funkcia vráti počet výskytov (count) hodnoty 5 v rozsahu.
Vezmime si príklad na demonštráciu funkcie „rovnosti“.
Rovný (first1, last1, first2) porovnáva prvky v rozsahu [first1, last1] s prvým prvkom označeným first2 a vracia true, ak sú všetky prvky rovnaké, inak 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'; } Výkon:
Prvky v dvoch rozsahoch nie sú rovnaké.
Vo vyššie uvedenom kóde definujeme dve celočíselné polia a pomocou funkcie „rovnaké“ porovnáme ich zodpovedajúce prvky. Pretože prvky poľa nie sú rovnaké, rovná sa vráti nepravdivá.
Úpravy algoritmov
Modifikačné algoritmy upravujú alebo transformujú obsah kontajnerov pri ich vykonávaní.
Medzi najobľúbenejšie a najbežnejšie používané modifikujúce algoritmy patria „zámena“ a „obrátenie“, ktoré zamenia dve hodnoty a obrátia prvky v kontajneri.
ako inicializovať zoznam v
Pozrime sa na príklady týchto funkcií:
#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< Výkon:
Vektor 1: 2 4 6 8 10
Vektor 2: 1 1 2 3 5
Obrátený vektor 1:10 8 6 4 2
Obrátený vektor 2: 5 3 2 1 1
Ako je vidieť, v programe máme definované dva vektory. Najskôr pomocou funkcie swap zameníme obsah vektorov1 a vektorov2. Ďalej obrátime obsah každého vektora pomocou funkcie obrátenia.
Program vydá Vector 1 a Vector 2 po výmene ich obsahu a tiež po obrátení obsahu.
Minimálna a maximálna prevádzka
Táto kategória pozostáva z funkcií min a max, ktoré zisťujú minimálnu a maximálnu hodnotu z daných dvoch hodnôt.
Všeobecná syntax týchto funkcií je:
max(objecta, objectb); min(objecta, objectb); Môžeme tiež poskytnúť tretí parameter poskytujúci funkciu „compare_function“ alebo kritériá, ktoré by sa použili na nájdenie minimálnej / maximálnej hodnoty. Ak to nie je uvedené, potom funkcia max používa na porovnanie operátor „>“, zatiaľ čo funkcia min používa „<’ operator for comparison.
Ukážme si tieto funkcie pomocou programu.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Výkon:
Maximálne 4 a 5: 5
Min. 4 a 5: 4
Max. Reťazec: menší reťazec
Min. Reťazec: dlhší reťazec
Vyššie uvedený program je samozrejmý, pretože najskôr a najskôr na číslach použijeme funkcie min a max. Pretože sme neposkytli voliteľnú funkciu „compare_function“, na operátory „“ pôsobili funkcie min / max.
Záver
Týmto sme sa dostali na koniec tohto tutoriálu o hlavných algoritmoch používaných v STL.
V našich ďalších tutoriáloch si podrobne rozoberieme iterátory spolu s bežnými funkciami používanými v STL bez ohľadu na kontajnery.
=> Prečítajte si sériu Easy C ++ Training Series.
Odporúčané čítanie