algorithms stl
En explicit studie av algoritmer och dess typer i STL.
hur man öppnar en binär fil i Windows
STL stöder olika algoritmer som fungerar på behållare genom iteratorer. Eftersom dessa algoritmer verkar på iteratorer och inte direkt på containrar kan de användas på alla typer av iteratorer.
STL-algoritmer är inbyggda och sparar därmed mycket tid och är också mer tillförlitliga. De förbättrar också återanvändning av kod. Dessa algoritmer är normalt bara ett funktionsanrop och vi behöver inte skriva uttömmande kod för att implementera dem.
=> Leta efter hela C ++ träningsserien här.
Vad du kommer att lära dig:
Typer av STL-algoritmer
STL stöder följande typer av algoritmer
- Sökalgoritmer
- Sorteringsalgoritmer
- Numeriska algoritmer
- Icke-transformerande / modifierande algoritmer
- Transformera / modifiera algoritmer
- Minsta och maximala operationer
Vi kommer att diskutera var och en av dessa typer i detalj i följande stycken.
Sök och sortera algoritmer
Den framträdande sökalgoritmen i STL är en binär sökning. Binär sökalgoritm fungerar på en sorterad matris och söker efter elementet genom att dela upp matrisen i hälften.
Detta görs genom att först jämföra elementet som ska sökas med mittelementet i matrisen och sedan begränsa sökningen till 1sthalv eller 2ndhälften av matrisen beroende på om elementet som ska sökas är mindre än eller större än mittelementet.
Binär sökning är de mest använda sökalgoritmerna.
Dess allmänna syntax är:
binary_search(startaddr, endaddr, key) Var,
startaddr: adress till det första elementet i matrisen.
endaddr: adress till det sista elementet i matrisen.
nyckel: det element som ska sökas.
STL ger oss en 'sorteringsalgoritm' som används för att ordna elementen i en container i en viss ordning.
Allmän syntax för sorteringsalgoritm är:
sort(startAddr, endAddr); Var,
startAddr: startadress för matrisen som ska sorteras.
endAddr: slutadress för den matris som ska sorteras.
Internt använder STL Quicksort-algoritmen för att sortera matrisen.
Låt oss ta ett exempel för att visa binär sök- och sorteringsalgoritm:
#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:
Sorterad matris är
0 1 2 3 4 5 6 7 8 9
Nyckel = 2 hittades i matrisen
Nyckel = 10 hittades inte i matrisen
I den givna koden har vi tillhandahållit en matris där vi behöver söka efter ett nyckelelement med binär sökning. Eftersom binär sökning kräver en sorterad matris sorterar vi först matrisen med hjälp av 'sorterings' -algoritmen och gör sedan ett funktionsanrop till 'binär_sökning' genom att tillhandahålla nödvändiga parametrar.
Först kallar vi algoritmen för binär_sökning för nyckel = 2 och sedan för nyckel = 10. På detta sätt med bara ett funktionsanrop kan vi enkelt göra en binär sökning på en matris eller sortera den.
Numeriska algoritmer
sidhuvud i STL innehåller olika funktioner som fungerar på numeriska värden. Dessa funktioner sträcker sig från att hitta lcds, gcds till och med att beräkna summan av elementen i en behållare som matriser, vektorer över ett visst intervall etc.
Vi kommer att diskutera några viktiga funktioner här med exempel.
(i) ackumuleras
Den allmänna syntaxen för ackumuleringsfunktionen är:
accumulate (first, last, sum); Denna funktion returnerar summan av alla element inom ett område (första, sista) i en variabel summa. I ovanstående syntaxnotation är första och sista adresserna till de första och sista elementen i en behållare och summan är det initiala värdet av sumvariabeln.
(ii) delsumma
Den allmänna syntaxen för partial_sum-funktionen är:
partial_sum(first, last, b) Här
först: adress till behållarens startelement.
Senaste: adress för det sista elementet i containern.
B: array där den partiella summan av motsvarande arrayelement kommer att lagras.
Således beräknar partial_sum-funktionen den partiella summan av motsvarande array eller vektorelementen och lagrar dem i en annan array.
Om a representerar elementet i intervallet (första, sista) och b representerar elementet i den resulterande matrisen blir partial_sum:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... och så vidare.
Låt oss se ett exempel för att demonstrera båda dessa dessa funktioner i ett 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 av ackumuleringsfunktionen är: 142
partial_sum of array A: 21 46 110 142
Som visas i ovanstående program beräknar vi först summan av elementen med hjälp av ackumuleringsfunktionen och sedan kallar vi funktionen partial_sum för att beräkna den partiella summan av motsvarande arrayelement.
Andra algoritmer som stöds av STL och header:
- iota: Fyller ett intervall med successiva steg av startvärdet.
- minska: Liknar att ackumuleras, utom i ordning.
- inre produkt: Beräknar den inre produkten av två olika element.
- intilliggande_skillnad: Beräknar skillnaderna mellan angränsande element i ett intervall.
- inklusive_scan: Liknar partial_sum, inkluderar ith-ingångselementet i ith-summan.
- exklusiv_scan: Liknar partial_sum, exkluderar ith-ingångselementet från ith-summan.
Icke-modifierande algoritmer
Icke-modifierande eller icke-transformerande algoritmer är de som inte ändrar innehållet i behållaren de arbetar i. STL stöder många icke-modifierande algoritmer.
Vi har listat några av dem nedan:
- räkna: Returnerar antalet värden i det angivna intervallet.
- likvärdig: Jämför elementen i två intervall och returnerar ett booleskt värde.
- missanpassning: Returnerar ett par iterator när två iteratorer jämförs och en obalans uppstår.
- Sök: Söker efter en given sekvens inom ett givet intervall.
- sök_n: Söker inom ett givet intervall efter en sekvens av räknevärdet.
Låt oss utarbeta mer om 'räkna' och 'lika' funktioner !!
räkna (första, sista, värde) returnerar antalet gånger ”värdet” visas i intervallet (första, sista).
#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:
Antalet gånger '5' visas i en matris = 4
Som du ser i den här koden definierar vi ett matrisvärde och anropar sedan räkningsfunktionen genom att ange värdeområdet och värdet 5. Funktionen returnerar antalet gånger (räkna) värde 5 visas i intervallet.
Låt oss ta ett exempel för att visa ”lika” -funktionen.
lika (first1, last1, first2) jämför elementen i intervallet (first1, last1) med det första elementet som pekas av first2 och returnerar true om alla element är lika annars falska.
#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:
Element i två intervall är inte lika.
I koden ovan definierar vi två heltalmatriser och jämför deras motsvarande element med 'lika' -funktionen. Eftersom elementen i matrisen inte är desamma returnerar lika falskt.
Modifiera algoritmer
Modifierande algoritmer modifierar eller transformerar innehållet i behållarna när de körs.
De populäraste och mest använda modifieringsalgoritmerna inkluderar 'swap' och 'reverse' som byter två värden och reverserar elementen i behållaren respektive.
Låt oss se exemplen för dessa 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
Omvänd vektor 1: 10 8 6 4 2
Omvänd vektor 2: 5 3 2 1 1
Som vi ser har vi två vektorer definierade i programmet. Först med swap-funktionen byter vi ut innehållet i vector1 och vector2. Därefter vänder vi innehållet i varje vektor med omvänd funktion.
bästa gratisoptimeraren för Windows 7
Programmet matar ut Vector 1 och Vector 2 efter att ha bytt innehåll och även efter att ha vänt innehållet.
Minsta och högsta drift
Denna kategori består av min- och maxfunktioner som tar reda på lägsta respektive högsta värden från de givna två värdena.
Den allmänna syntaxen för dessa funktioner är:
max(objecta, objectb); min(objecta, objectb); Vi kan också tillhandahålla en tredje parameter för att tillhandahålla 'jämför_funktion' eller de kriterier som skulle användas för att hitta min / max-värde. Om detta inte tillhandahålls använder maxfunktionen operatören '>' för jämförelse medan minfunktionen använder '<’ operator for comparison.
Låt oss demonstrera dessa funktioner med hjälp av ett 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:
Max 4 och 5: 5
Min 4 och 5: 4
Max sträng: mindre sträng
Min sträng: längre sträng
Ovanstående program är självförklarande eftersom vi använder min- och maxfunktioner på siffrorna först och sedan på strängar. Eftersom vi inte tillhandahöll valfri jämförelsesfunktion, fungerade min / max-funktionerna på respektive operatörer.
Slutsats
Med detta har vi kommit till slutet av denna handledning om viktiga algoritmer som används i STL.
I våra efterföljande handledning kommer vi att diskutera iteratorer i detalj tillsammans med de vanliga funktionerna som används i STL oavsett behållare.
=> Läs igenom Easy C ++ Training Series.
Rekommenderad läsning