Menü

Algorithmen in STL

algorithms stl

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Eine explizite Untersuchung von Algorithmen und ihren Typen in STL.

Unterschied zwischen linkem Join und linkem äußeren Join in SQL

STL unterstützt verschiedene Algorithmen, die über Iteratoren auf Container einwirken. Da diese Algorithmen auf Iteratoren und nicht direkt auf Container wirken, können sie auf jeder Art von Iteratoren verwendet werden.

STL-Algorithmen sind eingebaut, sparen viel Zeit und sind zudem zuverlässiger. Sie verbessern auch die Wiederverwendbarkeit von Code. Diese Algorithmen sind normalerweise nur ein Funktionsaufruf und wir müssen keinen vollständigen Code schreiben, um sie zu implementieren.

=> Suchen Sie hier nach der gesamten C ++ - Schulungsserie.

ALGORITHMEN IN STL

Was du lernen wirst:

Arten von STL-Algorithmen

STL unterstützt die folgenden Arten von Algorithmen

  • Suchalgorithmen
  • Sortieralgorithmen
  • Numerische Algorithmen
  • Nicht transformierende / modifizierende Algorithmen
  • Algorithmen transformieren / modifizieren
  • Minimale und maximale Operationen

Wir werden jeden dieser Typen in den folgenden Absätzen ausführlich diskutieren.

Such- und Sortieralgorithmen

Der bekannte Suchalgorithmus in STL ist eine binäre Suche. Der binäre Suchalgorithmus arbeitet mit einem sortierten Array und sucht nach dem Element, indem das Array in zwei Hälften geteilt wird.

Dazu wird zuerst das zu durchsuchende Element mit dem mittleren Element des Arrays verglichen und dann die Suche auf 1 begrenztsthalb oder 2ndDie Hälfte des Arrays hängt davon ab, ob das zu durchsuchende Element kleiner oder größer als das mittlere Element ist.

Die binäre Suche ist der am häufigsten verwendete Suchalgorithmus.

Die allgemeine Syntax lautet:

binary_search(startaddr, endaddr, key)

Wo,

startaddr: Adresse des ersten Elements des Arrays.
endaddr: Adresse des letzten Elements des Arrays.
Schlüssel: Das zu durchsuchende Element.

STL bietet uns einen Sortieralgorithmus, mit dem die Elemente in einem Container in einer bestimmten Reihenfolge angeordnet werden.

Allgemeine Syntax des Sortieralgorithmus lautet:

sort(startAddr, endAddr);

Wo,

startAddr: Startadresse des zu sortierenden Arrays.
endAddr: Endadresse des zu sortierenden Arrays.

Intern verwendet STL den Quicksort-Algorithmus, um das Array zu sortieren.

Nehmen wir ein Beispiel, um den binären Such- und Sortieralgorithmus zu demonstrieren:

#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

Ausgabe:

Sortiertes Array ist
0 1 2 3 4 5 6 7 8 9
Schlüssel = 2 im Array gefunden
Schlüssel = 10 nicht im Array gefunden

Im angegebenen Code haben wir ein Array bereitgestellt, in dem wir ein Schlüsselelement mithilfe der binären Suche suchen müssen. Da für die binäre Suche ein sortiertes Array erforderlich ist, sortieren wir das Array zunächst mit dem Algorithmus 'sort' und rufen dann 'binary_search' auf, indem wir die erforderlichen Parameter angeben.

Zuerst rufen wir den binary_search-Algorithmus für key = 2 und dann für key = 10 auf. Auf diese Weise können wir mit nur einem Funktionsaufruf bequem eine binäre Suche in einem Array durchführen oder es sortieren.

Numerische Algorithmen

Der Header in STL enthält verschiedene Funktionen, die mit numerischen Werten arbeiten. Diese Funktionen reichen von der Suche nach lcds, gcds bis hin zur Berechnung der Summe der Elemente in einem Container wie Arrays, Vektoren über einen bestimmten Bereich usw.

Wir werden hier einige wichtige Funktionen anhand von Beispielen diskutieren.

(i) akkumulieren

Die allgemeine Syntax der Akkumulationsfunktion lautet:

accumulate (first, last, sum);

Diese Funktion gibt die Summe aller Elemente innerhalb eines Bereichs (first, last) in einer variablen Summe zurück. In der obigen Syntaxnotation sind first und last die Adressen des ersten und letzten Elements in einem Container und sum ist der Anfangswert der Summenvariablen.

(ii) Teilsumme

Die allgemeine Syntax der Funktion partition_sum lautet:

partial_sum(first, last, b)

Hier

first: Adresse des Startelements des Containers.
Last: Adresse des letzten Elements des Containers.
B: Array, in dem die Teilsumme der entsprechenden Array-Elemente gespeichert wird.

Somit berechnet die Funktion partition_sum die Teilsumme des entsprechenden Arrays oder der Vektorelemente und speichert sie in einem anderen Array.

Wenn a das Element im Bereich (first, last) darstellt und b das Element im resultierenden Array darstellt, lautet partielle_summe:

b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... und so weiter.

Sehen wir uns ein Beispiel an, um beides zu demonstrieren Diese Funktionen in einem Programm:

#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: '<

Ausgabe:

Ergebnis der Akkumulationsfunktion ist: 142

Teilsumme von Array A: 21 46 110 142

Wie im obigen Programm gezeigt, berechnen wir zuerst die Summe der Elemente mit der Akkumulationsfunktion und rufen dann die Funktion Partial_Sum auf, um die Teilsumme der entsprechenden Array-Elemente zu berechnen.

Andere von STL und Header unterstützte Algorithmen:

  • Jota: Füllt einen Bereich mit aufeinanderfolgenden Schritten des Startwerts.
  • reduzieren: Ähnlich zu akkumulieren, außer außer Betrieb.
  • Innenprodukt: Berechnet das innere Produkt zweier Elementbereiche.
  • benachbart_differenz: Berechnet die Unterschiede zwischen benachbarten Elementen in einem Bereich.
  • inclusive_scan: Enthält ähnlich wie Partial_Sum das i-te Eingabeelement in der i-ten Summe.
  • exklusiver_scan: Schließt ähnlich wie partielle_summe das i-te Eingabeelement von der i-ten Summe aus.

Nicht modifizierende Algorithmen

Nicht modifizierende oder nicht transformierende Algorithmen sind diejenigen, die den Inhalt des Containers, in dem sie arbeiten, nicht ändern. STL unterstützt viele nicht modifizierende Algorithmen.

Wir haben einige davon unten aufgeführt:

  • Anzahl: Gibt die Anzahl der Werte im angegebenen Bereich zurück.
  • gleich: Vergleicht die Elemente in zwei Bereichen und gibt einen Booleschen Wert zurück.
  • Nichtübereinstimmung: Gibt ein Iteratorpaar zurück, wenn zwei Iteratoren verglichen werden und eine Nichtübereinstimmung auftritt.
  • Suche: Sucht nach einer bestimmten Sequenz in einem bestimmten Bereich.
  • search_n: Sucht in einem bestimmten Bereich nach einer Sequenz des Zählwerts.

Lassen Sie uns näher auf die Funktionen 'Zählen' und 'Gleich' eingehen.

count (first, last, value) gibt an, wie oft der Wert im Bereich (first, last) angezeigt wird.

#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= '<

Ausgabe:

Was sind die verschiedenen E-Mail-Anbieter

Die Häufigkeit, mit der '5' in einem Array angezeigt wird = 4

Wie Sie in diesem Code sehen, definieren wir einen Array-Wert und rufen dann die Zählfunktion auf, indem wir den Wertebereich und den Wert 5 angeben. Die Funktion gibt zurück, wie oft (Zählwert) Wert 5 im Bereich erscheint.

Nehmen wir ein Beispiel, um die Funktion 'Gleich' zu demonstrieren.

gleich (first1, last1, first2) vergleicht die Elemente im Bereich (first1, last1) mit dem ersten Element, auf das first2 zeigt, und gibt true zurück, wenn alle Elemente gleich sind, andernfalls 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'; }

Ausgabe:

Elemente in zwei Bereichen sind nicht gleich.

Im obigen Code definieren wir zwei ganzzahlige Arrays und vergleichen ihre entsprechenden Elemente mit der Funktion 'gleich'. Da die Elemente des Arrays nicht identisch sind, gibt gleich false zurück.

Algorithmen ändern

Änderungsalgorithmen ändern oder transformieren den Inhalt der Container, wenn sie ausgeführt werden.

Zu den beliebtesten und am häufigsten verwendeten Änderungsalgorithmen gehören 'Swap' und 'Reverse', bei denen zwei Werte ausgetauscht und die Elemente im Container umgekehrt werden.

Sehen wir uns die Beispiele für diese Funktionen an:

#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<

Ausgabe:

Vektor 1: 2 4 6 8 10

Vektor 2: 1 1 2 3 5

Umgekehrter Vektor 1: 10 8 6 4 2

Umgekehrter Vektor 2: 5 3 2 1 1

Wie zu sehen ist, haben wir zwei Vektoren im Programm definiert. Zuerst tauschen wir mit der Swap-Funktion den Inhalt von Vektor1 und Vektor2 aus. Als nächstes kehren wir den Inhalt jedes Vektors mit der Umkehrfunktion um.

Das Programm gibt Vektor 1 und Vektor 2 nach dem Austauschen ihres Inhalts und auch nach dem Umkehren des Inhalts aus.

Minimale und maximale Operationen

Diese Kategorie besteht aus Min- und Max-Funktionen, die die Minimal- und Maximalwerte aus den beiden angegebenen Werten ermitteln.

Die allgemeine Syntax dieser Funktionen lautet:

max(objecta, objectb); min(objecta, objectb);

Wir können auch einen dritten Parameter angeben, um 'compare_function' oder die Kriterien anzugeben, anhand derer der Min / Max-Wert ermittelt wird. Wenn dies nicht vorgesehen ist, verwendet die Max-Funktion zum Vergleich den Operator '>', während die Min-Funktion '<’ operator for comparison.

Lassen Sie uns diese Funktionen mit einem Programm demonstrieren.

#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout<

Ausgabe:

Maximal 4 und 5: 5

Min von 4 und 5: 4

Max String: kleinerer String

Min String: längerer String

Das obige Programm ist selbsterklärend, da wir zuerst die Min- und Max-Funktionen für die Zahlen und dann für die Zeichenfolgen verwenden. Da wir keine optionale 'compare_function' bereitgestellt haben, haben die min / max-Funktionen jeweils auf '' -Operatoren gewirkt.

Fazit

Damit sind wir am Ende dieses Tutorials zu den wichtigsten in STL verwendeten Algorithmen angelangt.

In unseren nachfolgenden Tutorials werden wir Iteratoren zusammen mit den allgemeinen Funktionen, die in STL unabhängig von Containern verwendet werden, ausführlich behandeln.

=> Lesen Sie die Easy C ++ - Schulungsserie durch.

Literatur-Empfehlungen

^