Библиотека алгоритмов C++<algorithm>

В стандартной библиотеке C++,<algorithm>заголовочный файл предоставляет набор алгоритмов для работы с контейнерами (такими как массивы, векторы, списки и т. д.). Эти алгоритмы включают сортировку, поиск, копирование, сравнение и т. д., и они являются важными инструментами для написания эффективного, многократно используемого кода.

<algorithm>Заголовочный файл определяет набор шаблонных функций, которые можно применять к контейнерам любого типа, если контейнер поддерживает итераторы. Эти алгоритмы обычно принимают два или более итератора в качестве параметров, указывающих начальную и конечную позиции операции.

Синтаксис

Большинство<algorithm>Все функции в нём следуют следующему базовому синтаксису:

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

здесьcontainerявляется объектом-контейнером,begin()иend()Являются функциями-членами контейнера, возвращающими итераторы, указывающие на начало и конец контейнера.

Пример

1. Алгоритмы сортировки

Функции: sort

Определение: сортирует элементы в контейнере.

Синтаксис:

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

где compare_function — необязательная функция сравнения, используемая для настройки метода сортировки.

Пример

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

Результат вывода:

1 2 5 5 6 9

std::partial_sort: Сортирует частичный диапазон, при этом первые n элементов находятся в отсортированном порядке.

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

std::stable_sort: Устойчивая сортировка, сохраняющая относительный порядок равных элементов.

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

2. Алгоритмы поиска

Функции: find

Определение: находит первый элемент в контейнере, совпадающий с заданным значением.

Синтаксис:

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

Если найден, он будет указывать на совпадающий элемент; если не найден, он будет равен container.end().

Пример

#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 << "Найдено: " << *it << std::endl;
    } else {
        std::cout << "Значение не найдено." << std::endl;
    }

    return 0;
}

Результат вывода:

Found: 3

std::binary_search: Выполняет бинарный поиск на отсортированном интервале.

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

std::find_if: Находит первый элемент, удовлетворяющий определённому условию.

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

3. Алгоритмы копирования

Функции: copy

Определение: Копирует элементы из одного диапазона в другой контейнер или массив.

Синтаксис:

copy(source_begin, source_end, destination_begin);

Пример:

Пример

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

Результат вывода:

1 2 3 4 5

4. Алгоритмы сравнения

Функции: equal

Определение: Сравнивает, равны ли элементы в двух контейнерах или двух диапазонах.

Синтаксис:

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

или 

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

Пример

#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 ? "Векторы равны." : "Векторы не равны.") << std::endl;

    return 0;
}

Результат вывода:

Vectors are equal.

5. Алгоритмы модификации

std::reverse: изменяет порядок элементов в интервале на обратный.

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

std::fill: присваивает определённое значение всем элементам в указанном диапазоне.

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

std::replace: заменяет определённое значение в диапазоне другим значением.

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

std::copy: копирует элементы из интервала в другой интервал.

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

6. Алгоритмы перестановок

std::next_permutation: генерирует следующую перестановку в лексикографическом порядке и возвращает false, если следующей перестановки нет.

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: Генерирует предыдущую лексикографическую перестановку.

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

7. Алгоритмы слияния

std::merge: Объединяет два отсортированных диапазона в один отсортированный диапазон.

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: Объединяет два отсортированных поддиапазона в пределах одного диапазона.

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

8. Алгоритмы над множествами

std::set_union: Вычисляет объединение двух отсортированных множеств.

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: Вычисляет пересечение двух отсортированных множеств.

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

std::set_difference: Вычисляет разность двух множеств.

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

9. Другие полезные алгоритмы

std::accumulate(требуется библиотека <numeric>): Вычисляет накопительную сумму элементов в диапазоне.

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

std::for_each: Выполняет операцию для каждого элемента в диапазоне.

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

std::min_elementиstd::max_element: Находит минимальное и максимальное значения в диапазоне.

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

<algorithm>Является очень мощным инструментом в стандартной библиотеке C++. Он предоставляет большое количество обобщённых алгоритмов, которые могут значительно упростить программирование.

Другие расширения