algorithms stl
Een expliciete studie van algoritmen en de typen ervan in STL.
gekoppelde lijst pointers c ++
STL ondersteunt verschillende algoritmen die via iterators op containers werken. Omdat deze algoritmen op iterators werken en niet rechtstreeks op containers, kunnen ze op elk type iterator worden gebruikt.
STL-algoritmen zijn ingebouwd en besparen dus veel tijd en zijn ook betrouwbaarder. Ze verbeteren ook de herbruikbaarheid van code. Deze algoritmen zijn normaal gesproken slechts één functieaanroep en we hoeven geen volledige code te schrijven om ze te implementeren.
Zoek hier de volledige C ++-trainingsserie.
Wat je leert:
Soorten STL-algoritmen
STL ondersteunt de volgende soorten algoritmen
- Zoekalgoritmen
- Sorteeralgoritmen
- Numerieke algoritmen
- Niet-transformerende / wijzigende algoritmen
- Algoritmen transformeren / wijzigen
- Minimale en maximale bewerkingen
We zullen elk van deze typen in de volgende paragrafen in detail bespreken.
Algoritmen zoeken en sorteren
Het prominente zoekalgoritme in STL is een binaire zoekopdracht. Het binaire zoekalgoritme werkt op een gesorteerde array en zoekt naar het element door de array in tweeën te delen.
Dit wordt gedaan door eerst het te zoeken element te vergelijken met het middelste element van de array en vervolgens de zoekopdracht te beperken tot 1stde helft of 2ndde helft van de array, afhankelijk van of het element dat moet worden doorzocht kleiner of groter is dan het middelste element.
Binair zoeken is de meest gebruikte zoekalgoritmen.
De algemene syntaxis is:
Waar,
startaddr: adres van het eerste element van de array.
endaddr: adres van het laatste element van de array.
key: het element dat moet worden doorzocht.
STL biedt ons een “Sort” -algoritme dat wordt gebruikt om de elementen in een bepaalde volgorde in een container te rangschikken.
De algemene syntaxis van het sorteeralgoritme is:
Waar,
startAddr: startadres van de te sorteren array.
endAddr: eindadres van de array die moet worden gesorteerd.
Intern gebruikt STL het Quicksort-algoritme om de array te sorteren.
Laten we een voorbeeld nemen om het binaire zoek- en sorteeralgoritme te demonstreren:
Uitgang:
Gesorteerde matrix is
0 1 2 3 4 5 6 7 8 9
Key = 2 gevonden in de array
Sleutel = 10 niet gevonden in de array
In de gegeven code hebben we een array voorzien waarin we een sleutelelement moeten zoeken met behulp van de binaire zoekopdracht. Aangezien binair zoeken een gesorteerde array vereist, sorteren we eerst de array met behulp van het 'sort' -algoritme en doen vervolgens een functieaanroep naar 'binary_search' door de vereiste parameters op te geven.
Eerst noemen we het algoritme binary_search voor key = 2 en vervolgens voor key = 10. Op deze manier kunnen we met slechts één functieaanroep gemakkelijk een binaire zoekopdracht op een array uitvoeren of deze sorteren.
Numerieke algoritmen
header in STL bevat verschillende functies die werken op numerieke waarden. Deze functies variëren van het vinden van lcd's, gcd's tot zelfs het berekenen van de som van de elementen in een container zoals arrays, vectoren over een bepaald bereik, enz.
Met voorbeelden bespreken we hier enkele belangrijke functies.
(i) accumuleren
De algemene syntaxis van de accumulatiefunctie is:
Deze functie retourneert de som van alle elementen binnen een bereik (eerste, laatste) in een variabele som. In de bovenstaande syntaxisnotatie zijn eerste en laatste de adressen van de eerste en laatste elementen in een container en is som de beginwaarde van de variabele som.
(ii) gedeeltelijke som
De algemene syntaxis van de functie gedeeltelijke_som is:
Hier
first: adres van het startelement van de container.
Last: adres van het laatste element van de container.
B: array waarin de gedeeltelijke som van de corresponderende array-elementen wordt opgeslagen.
De functie gedeeltelijke som berekent dus de gedeeltelijke som van de overeenkomstige reeks of de vectorelementen en slaat ze op in een andere reeks.
Als a het element in het bereik (eerste, laatste) vertegenwoordigt en b het element in de resulterende array vertegenwoordigt, is de gedeeltelijke som:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2… enzovoort.
Laten we een voorbeeld bekijken om beide te demonstreren Deze functies in een programma:
Uitgang:
Het resultaat van de accumulatiefunctie is: 142
gedeeltelijke som van array A: 21 46110142
Zoals getoond in het bovenstaande programma, berekenen we eerst de som van de elementen met behulp van de accumulatiefunctie en vervolgens noemen we de functie partiële_som om de gedeeltelijke som van de overeenkomstige array-elementen te berekenen.
Andere algoritmen ondersteund door STL en header:
- jota: Vult een bereik met opeenvolgende verhogingen van de startwaarde.
- verminderen: Vergelijkbaar met accumuleren, behalve buiten gebruik.
- inner_product: Berekent het inproduct van twee reeksen elementen.
- aangrenzend_verschil: Berekent de verschillen tussen aangrenzende elementen in een bereik.
- inclusieve_scan: Vergelijkbaar met partiële_som, bevat het ih invoerelement in de ih som.
- exclusieve_scan: Vergelijkbaar met partiële_som, sluit het ie invoerelement uit van de ie som.
Niet-wijzigende algoritmen
Niet-modificerende of niet-transformerende algoritmen zijn degene die de inhoud van de container waarin ze werken niet veranderen. STL ondersteunt veel niet-modificerende algoritmen.
We hebben er een aantal hieronder op een rijtje gezet:
- tellen: Retourneert het aantal waarden in het opgegeven bereik.
- Gelijk: Vergelijkt de elementen in twee bereiken en retourneert een Booleaanse waarde.
- mismatch: Retourneert een iteratorpaar wanneer twee iteratoren worden vergeleken en er een mismatch optreedt.
- zoeken: Zoekt naar een bepaalde reeks in een bepaald bereik.
- search_n: Zoekt in een bepaald bereik naar een reeks van de telwaarde.
Laten we meer ingaan op de functies 'tellen' en 'gelijk' !!
count (first, last, value) geeft het aantal keren terug dat de ‘waarde’ voorkomt in het bereik (first, last).
Uitgang:
Het aantal keren dat ‘5’ voorkomt in een array = 4
Zoals je in deze code ziet, definiëren we een matrixwaarde en roepen we de count-functie aan door het waardebereik en de waarde 5 op te geven. De functie retourneert het aantal keren dat (count) waarde 5 in het bereik voorkomt.
Laten we een voorbeeld nemen om de ‘gelijk’ functie te demonstreren.
equal (first1, last1, first2) vergelijkt de elementen in het bereik (first1, last1) met het eerste element aangegeven door first2 en geeft true terug als alle elementen gelijk zijn, anders false.
Uitgang:
Elementen in twee bereiken zijn niet gelijk.
In de bovenstaande code definiëren we twee integer-arrays en vergelijken we hun overeenkomstige elementen met behulp van de ‘gelijk’ -functie. Omdat de elementen van de array niet hetzelfde zijn, geeft gelijk als resultaat false.
Algoritmen aanpassen
Het aanpassen van algoritmen verandert of transformeert de inhoud van de containers wanneer ze worden uitgevoerd.
De meest populaire en meest gebruikte wijzigingsalgoritmen zijn onder meer 'swap' en 'reverse' die twee waarden verwisselen en de elementen in de container respectievelijk omkeren.
Laten we de voorbeelden van deze functies bekijken:
Uitgang:
Vector 1: 2 4 6 8 10
Vector 2: 1 1 2 3 5
Omgekeerde vector 1:10 8 6 4 2
Omgekeerde vector 2: 5 3 2 1 1
Zoals we hebben gezien, hebben we twee vectoren gedefinieerd in het programma. Door eerst de swap-functie te gebruiken, wisselen we de inhoud van vector1 en vector2. Vervolgens keren we de inhoud van elke vector om met behulp van de omgekeerde functie.
Het programma voert Vector 1 en Vector 2 uit na het wisselen van hun inhoud en ook na het omkeren van de inhoud.
Minimale en maximale operaties
Deze categorie bestaat uit min- en max-functies die respectievelijk de minimum- en maximumwaarden achterhalen uit de opgegeven twee waarden.
De algemene syntaxis van deze functies is:
We kunnen ook een derde parameter opgeven om ‘vergelijk_functie’ te geven of de criteria die zouden worden gebruikt om de min / max-waarde te vinden. Als dit niet is opgegeven, gebruikt de max-functie de ‘>’ -operator ter vergelijking, terwijl de min-functie ‘<’ operator for comparison.
Laten we deze functies demonstreren met een programma.
Uitgang:
Max van 4 en 5: 5
Min van 4 en 5: 4
c / c ++ interviewvragen
Max String: kleinere string
Min String: langere string
Het bovenstaande programma spreekt voor zich omdat we de min- en max-functies eerst op de getallen en vervolgens op strings gebruiken. Omdat we geen optionele ‘vergelijk_functie’ hebben geleverd, werkten de min / max-functies respectievelijk op ‘’ operatoren.
Gevolgtrekking
Hiermee zijn we aan het einde gekomen van deze tutorial over belangrijke algoritmen die in STL worden gebruikt.
In onze volgende tutorials zullen we iteratoren in detail bespreken, samen met de algemene functies die in STL worden gebruikt, ongeacht containers.
Lees de Easy C ++ Training Series door.