C++-Algorithmenbibliothek<algorithm>

In der C++-Standardbibliothek,<algorithm>bietet die Header-Datei eine Reihe von Algorithmen für die Arbeit mit Containern (wie Arrays, Vektoren, Listen usw.). Diese Algorithmen umfassen Sortieren, Suchen, Kopieren, Vergleichen usw. und sind wichtige Werkzeuge zum Schreiben von effizientem, wiederverwendbarem Code.

<algorithm>Die Header-Datei definiert eine Reihe von Vorlagenfunktionen, die auf Container jedes Typs angewendet werden können, solange der Container Iteratoren unterstützt. Diese Algorithmen akzeptieren normalerweise zwei oder mehr Iteratoren als Parameter, die die Start- und Endposition der Operation angeben.

Syntax

Die meisten<algorithm>Die darin enthaltenen Funktionen folgen alle der folgenden grundlegenden Syntax:

algorithm_name(container.begin(), container.end(), ...);

hiercontainerist ein Containerobjekt,begin()undend()Sind Memberfunktionen des Containers, die Iteratoren zurückgeben, die auf den Anfang und das Ende des Containers zeigen.

Beispiel

1. Sortieralgorithmen

Funktionen: sort

Definition: Sortiert die Elemente im Container.

Syntax:

sort(container.begin(), container.end(), compare_function);

wobei compare_function eine optionale Vergleichsfunktion ist, die verwendet wird, um die Sortiermethode anzupassen.

Beispiel

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    std::sort(numbers.begin(), numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Ausgabeergebnis:

1 2 5 5 6 9

std::partial_sort: Sortiert einen Teilbereich, wobei die ersten n Elemente in sortierter Reihenfolge stehen.

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

std::stable_sort: Stabile Sortierung, die die relative Reihenfolge gleicher Elemente bewahrt.

std::stable_sort(vec.begin(), vec.end());

2. Suchalgorithmen

Funktionen: find

Definition: Findet das erste Element im Container, das einem gegebenen Wert entspricht.

Syntax:

auto it = find(container.begin(), container.end(), value);

Wenn es gefunden wird, zeigt es auf das passende Element; andernfalls ist es gleich container.end().

Beispiel

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    auto it = std::find(numbers.begin(), numbers.end(), 3);

    if (it != numbers.end()) {
        std::cout << "Gefunden: " << *it << std::endl;
    } else {
        std::cout << "Wert nicht gefunden." << std::endl;
    }

    return 0;
}

Ausgabeergebnis:

Found: 3

std::binary_search: Führt eine binäre Suche auf einem sortierten Intervall durch.

std::sort(vec.begin(), vec.end());  // 先排序
bool found = std::binary_search(vec.begin(), vec.end(), 4);

std::find_if: Findet das erste Element, das eine bestimmte Bedingung erfüllt.

auto it = std::find_if(vec.begin(), vec.end(), [](int x) { return x > 3; });

3. Kopieralgorithmen

Funktionen: copy

Definition: Kopiert Elemente von einem Bereich in einen anderen Container oder ein Array.

Syntax:

copy(source_begin, source_end, destination_begin);

Beispiel:

Beispiel

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    int destination[5];
    std::copy(source.begin(), source.end(), destination);

    for (int i = 0; i < 5; ++i) {
        std::cout << destination[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Ausgabeergebnis:

1 2 3 4 5

4. Vergleichsalgorithmen

Funktionen: equal

Definition: Vergleicht, ob die Elemente in zwei Containern oder zwei Bereichen gleich sind.

Syntax:

bool result = equal(first1, last1, first2);

oder 

bool result = equal(first1, last1, first2, compare_function);

Beispiel

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {1, 2, 3, 4, 5};

    bool are_equal = std::equal(v1.begin(), v1.end(), v2.begin());
    std::cout << (are_equal ? "Vektoren sind gleich." : "Vektoren sind nicht gleich.") << std::endl;

    return 0;
}

Ausgabeergebnis:

Vectors are equal.

5. Modifizierende Algorithmen

std::reverse: Kehrt die Reihenfolge der Elemente im Intervall um.

std::reverse(vec.begin(), vec.end());

std::fill: Weist allen Elementen im angegebenen Bereich einen bestimmten Wert zu.

std::fill(vec.begin(), vec.end(), 0);  // 所有元素设为 0

std::replace: Ersetzt einen bestimmten Wert im Bereich durch einen anderen Wert.

std::replace(vec.begin(), vec.end(), 1, 99);  // 将所有 1 替换为 99

std::copy: Kopiert Elemente aus dem Intervall in ein anderes Intervall.

std::vector<int> vec2(6);
std::copy(vec.begin(), vec.end(), vec2.begin());

6. Permutationsalgorithmen

std::next_permutation: Erzeugt die nächste Permutation in lexikografischer Reihenfolge und gibt false zurück, wenn es keine nächste Permutation gibt.

std::vector<int> vec = {1, 2, 3};
do {
    for (int n : vec) std::cout << n << " ";
    std::cout << std::endl;
} while (std::next_permutation(vec.begin(), vec.end()));

std::prev_permutation: Erzeugt die vorherige lexikografische Permutation.

std::prev_permutation(vec.begin(), vec.end());

7. Algorithmen zum Zusammenführen

std::merge: Führt zwei sortierte Bereiche zu einem sortierten Bereich zusammen.

std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};
std::vector<int> result(6);
std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

std::inplace_merge: Führt zwei sortierte Teilbereiche innerhalb eines einzelnen Bereichs zusammen.

std::inplace_merge(vec.begin(), middle, vec.end());

8. Mengenalgorithmen

std::set_union: Berechnet die Vereinigung zweier sortierter Mengen.

std::vector<int> result(10);
auto it = std::set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_intersection: Berechnet die Schnittmenge zweier sortierter Mengen.

auto it = std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_difference: Berechnet die Differenz zweier Mengen.

auto it = std::set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

9. Weitere nützliche Algorithmen

std::accumulate(erfordert die <numeric>-Bibliothek): Berechnet die kumulative Summe der Elemente im Bereich.

#include <numeric>
int sum = std::accumulate(vec.begin(), vec.end(), 0);

std::for_each: Führt eine Operation an jedem Element im Bereich aus.

std::for_each(vec.begin(), vec.end(), [](int& x) { x += 1; });

std::min_elementundstd::max_element: Findet die minimalen und maximalen Werte im Bereich.

auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());

<algorithm>Ist ein sehr mächtiges Werkzeug in der C++-Standardbibliothek. Es bietet eine große Anzahl generischer Algorithmen, die die Programmierung erheblich vereinfachen können.

Weitere Erweiterungen