algorithms stl
Výslovná studie algoritmů a jejich typů v STL.
software testovací rozhovor otázka a odpověď pro čerstvější
STL podporuje různé algoritmy, které působí na kontejnery prostřednictvím iterátorů. Protože tyto algoritmy působí na iterátory a ne přímo na kontejnery, lze je použít na jakýkoli typ iterátorů.
Algoritmy STL jsou integrovány, a tak šetří spoustu času a jsou také spolehlivější. Zlepšují také opakovanou použitelnost kódu. Tyto algoritmy jsou obvykle jen jedno volání funkce a pro jejich implementaci nemusíme psát vyčerpávající kód.
=> Podívejte se na celou sérii školení C ++ zde.
Co se naučíte:
Typy STL algoritmů
STL podporuje následující typy algoritmů
- Vyhledávací algoritmy
- Algoritmy řazení
- Numerické algoritmy
- Netransformační / modifikační algoritmy
- Transformační / modifikační algoritmy
- Minimální a maximální operace
Každému z těchto typů se budeme podrobně věnovat v následujících odstavcích.
Hledat a třídit algoritmy
Prominentní vyhledávací algoritmus v STL je binární vyhledávání. Algoritmus binárního vyhledávání pracuje na tříděném poli a vyhledává prvek rozdělením pole na polovinu.
To se provádí tak, že se nejprve porovná prvek, který se má prohledat, se středním prvkem pole a poté se hledání omezí na 1Svatýnapůl nebo 2ndpolovina pole v závislosti na tom, zda je prohledávaný prvek menší nebo větší než prostřední prvek.
Binární vyhledávání je nejpoužívanějším vyhledávacím algoritmem.
Jeho obecná syntaxe je:
binary_search(startaddr, endaddr, key) Kde,
startaddr: adresa prvního prvku pole.
endaddr: adresa posledního prvku pole.
klíč: prvek, který má být prohledán.
STL nám poskytuje algoritmus „Řazení“, který se používá k uspořádání prvků v kontejneru v určitém pořadí.
Obecná syntaxe třídicího algoritmu je:
sort(startAddr, endAddr); Kde,
startAddr: počáteční adresa pole, které má být tříděno.
endAddr: koncová adresa pole, které má být tříděno.
Interně STL používá k řazení pole algoritmus Quicksort.
Uveďme si příklad, který předvede algoritmus binárního vyhledávání a řazení:
#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ýstup:
Tříděné pole je
0 1 2 3 4 5 6 7 8 9
Klíč = 2 nalezen v poli
Klíč = 10 nebyl v poli nalezen
V daném kódu jsme poskytli pole, ve kterém musíme prohledat klíčový prvek pomocí binárního vyhledávání. Vzhledem k tomu, že binární vyhledávání vyžaduje seřazené pole, nejprve seřadíme pole pomocí algoritmu „sort“ a poté provedeme volání funkce „binary_search“ poskytnutím požadovaných parametrů.
Nejprve zavoláme algoritmus binary_search pro key = 2 a poté pro key = 10. Tímto způsobem s pouhým jedním voláním funkce můžeme pohodlně provést binární vyhledávání v poli nebo jej seřadit.
Numerické algoritmy
záhlaví v STL obsahuje různé funkce, které pracují s číselnými hodnotami. Tyto funkce sahají od hledání lcds, gcds až po výpočet součtu prvků v kontejneru, jako jsou pole, vektory v daném rozsahu atd.
Zde probereme několik důležitých funkcí s příklady.
i) se hromadí
Obecná syntaxe funkce akumulace je:
accumulate (first, last, sum); Tato funkce vrací součet všech prvků v rozsahu (první, poslední) v proměnném součtu. Ve výše uvedeném zápisu syntaxe first and last je adresa prvního a posledního prvku v kontejneru a sum je počáteční hodnota proměnné sum.
(ii) částečné_součet
Obecná syntaxe funkce partial_sum je:
partial_sum(first, last, b) Tady
first: adresa počátečního prvku kontejneru.
Poslední: adresa posledního prvku kontejneru.
B: pole, ve kterém bude uložen částečný součet odpovídajících prvků pole.
Funkce partial_sum tedy vypočítá částečný součet odpovídajícího pole nebo vektorových prvků a uloží je do jiného pole.
Pokud a představuje prvek v rozsahu (první, poslední) a b představuje prvek ve výsledném poli, pak částečné_čet bude:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... atd.
Podívejme se na příklad, který předvede obojí tyto funkce v 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: '< Výstup:
Výsledek funkce akumulace je: 142
částečné_součet pole A: 21 46 110 142
Jak je znázorněno ve výše uvedeném programu, nejprve spočítáme součet prvků pomocí funkce akumulace a potom zavoláme funkci partial_sum pro výpočet částečného součtu odpovídajících prvků pole.
Další algoritmy podporované STL a hlavičkou:
- jota: Vyplní rozsah postupnými přírůstky počáteční hodnoty.
- snížit: Podobně se hromadí, s výjimkou mimo provoz.
- vnitřní_produkt: Vypočítá vnitřní součin dvou rozsahů prvků.
- sousední_diference: Vypočítá rozdíly mezi sousedními prvky v rozsahu.
- inclusive_scan: Podobně jako částečný_čet zahrnuje i-tý vstupní prvek do i-tého součtu.
- exclusive_scan: Podobně jako částečný_čet, vylučuje i-tý vstupní prvek ze i-tého součtu.
Nemodifikační algoritmy
Nemodifikující nebo netransformující algoritmy jsou ty, které nemění obsah kontejneru, ve kterém pracují. STL podporuje mnoho nemodifikujících algoritmů.
Níže uvádíme některé z nich:
- počet: Vrátí počet hodnot v daném rozsahu.
- rovnat se: Porovná prvky ve dvou rozsazích a vrátí logickou hodnotu.
- nesoulad: Vrátí dvojici iterátorů, když jsou porovnány dva iterátory a dojde k neshodě.
- Vyhledávání: Vyhledá danou sekvenci v daném rozsahu.
- hledat_n: Hledá v daném rozsahu posloupnost hodnoty počítání.
Pojďme se podrobněji zabývat funkcemi „počítání“ a „rovnosti“ !!
count (first, last, value) vrací 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ýstup:
Počet výskytů „5“ v poli = 4
Jak vidíte v tomto kódu, definujeme hodnotu pole a poté zavoláme funkci count zadáním rozsahu hodnoty a hodnoty 5. Funkce vrací počet, kolikrát (count) se v rozsahu objeví hodnota 5.
Vezměme si příklad, který předvede funkci „rovnosti“.
rovná (first1, last1, first2) porovná prvky v rozsahu (first1, last1) s prvním prvkem, na který ukazuje first2, a vrátí true, pokud jsou všechny prvky stejné, jinak 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ýstup:
Prvky ve dvou rozsazích nejsou stejné.
V kódu výše definujeme dvě celočíselná pole a porovnáme jejich odpovídající prvky pomocí funkce „rovná se“. Protože prvky pole nejsou stejné, rovná se vrátí false.
Úpravy algoritmů
Modifikační algoritmy upravují nebo transformují obsah kontejnerů při jejich provádění.
Mezi nejoblíbenější a nejpoužívanější modifikační algoritmy patří „swap“ a „reverse“, které zamění dvě hodnoty a obrátí prvky v kontejneru.
Podívejme se na příklady těchto funkcí:
#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ýstup:
Vektor 1: 2 4 6 8 10
Vektor 2: 1 1 2 3 5
Obrácený vektor 1:10 8 6 4 2
Obrácený vektor 2: 5 3 2 1 1
Jak je vidět, máme v programu definované dva vektory. Nejprve pomocí funkce swap zaměňujeme obsah vektoru 1 a vektoru 2. Dále převrátíme obsah každého vektoru pomocí reverzní funkce.
Program vydá vektory 1 a 2 po výměně jejich obsahu a také po převrácení obsahu.
Minimální a maximální počet operací
Tato kategorie se skládá z funkcí min a max, které z daných dvou hodnot zjišťují minimální a maximální hodnoty.
Obecná syntaxe těchto funkcí je:
max(objecta, objectb); min(objecta, objectb); Můžeme také poskytnout třetí parametr poskytující funkci „compare_function“ nebo kritéria, která by byla použita k nalezení minimální / maximální hodnoty. Pokud to není k dispozici, pak funkce max používá pro srovnání operátor „>“, zatímco funkce min používá „<’ operator for comparison.
Ukažme si tyto funkce pomocí 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ýstup:
Maximálně 4 a 5: 5
Min. 4 a 5: 4
Max. Řetězec: menší řetězec
Min. Řetězec: delší řetězec
Výše uvedený program je vysvětlující, protože nejprve používáme funkce min a max na čísla a poté na řetězce. Protože jsme neposkytli volitelnou funkci „compare_function“, funkce min / max působila na operátory „“.
Závěr
S tímto jsme se dostali na konec tohoto tutoriálu o hlavních algoritmech používaných v STL.
V našich následujících výukách budeme podrobně diskutovat iterátory spolu s běžnými funkcemi používanými v STL bez ohledu na kontejnery.
=> Přečtěte si sérii školení Easy C ++.
klidné webové služby, otázky a odpovědi pro zkušené
Doporučené čtení