C++ Algorithm Library<algorithm>

In the C++ standard library,<algorithm>the header file provides a set of algorithms for operating on containers (such as arrays, vectors, lists, etc.). These algorithms include sorting, searching, copying, comparing, etc., and they are important tools for writing efficient, reusable code.

<algorithm>The header file defines a set of template functions that can be applied to containers of any type, as long as the container supports iterators. These algorithms usually accept two or more iterators as parameters, indicating the start and end positions of the operation.

Syntax

Most<algorithm>The functions in it all follow the following basic syntax:

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

herecontaineris a container object,begin()andend()Are member functions of the container, returning iterators that point to the beginning and end of the container.

Example

1. Sorting Algorithms

Functions: sort

Definition: Sorts the elements in the container.

Syntax:

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

where compare_function is an optional comparison function used to customize the sorting method.

Output result:

1 2 5 5 6 9 

std::partial_sort: Sorts a partial range, with the first n elements in sorted order.

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

std::stable_sort: Stable sort, preserving the relative order of equal elements.

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

2. Searching Algorithms

Functions: find

Definition: Finds the first element in the container that matches a given value.

Syntax:

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

If found, it will point to the matching element; if not found, it will equal container.end().

Output result:

Found: 3

std::binary_search: Performs binary search on a sorted interval.

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

std::find_if: Finds the first element that satisfies a specific condition.

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

3. Copying Algorithms

Functions: copy

Definition: Copies elements from one range to another container or array.

Syntax:

copy(source_begin, source_end, destination_begin);

Example:

Output result:

1 2 3 4 5 

4. Comparison Algorithms

Functions: equal

Definition: Compares whether the elements in two containers or two ranges are equal.

Syntax:

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

or 

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

Output result:

Vectors are equal.

5. Modification Algorithms

std::reverse: Reverses the order of elements in the interval.

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

std::fill: Assigns a certain value to all elements in the specified range.

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

std::replace: Replaces a certain value in the range with another value.

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

std::copy: Copies elements in the interval to another interval.

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

6. Permutation Algorithms

std::next_permutation: Generates the next permutation in lexicographical order, and returns false if there is no next permutation.

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: Generates the previous lexicographic permutation.

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

7. Merging Algorithms

std::merge: Merges two sorted ranges into one sorted range.

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: Merges two sorted sub-ranges within a single range.

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

8. Set Algorithms

std::set_union: Computes the union of two sorted sets.

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: Computes the intersection of two sorted sets.

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

std::set_difference: Computes the difference of two sets.

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

9. Other useful algorithms

std::accumulate(requires <numeric> library): Computes the cumulative sum of elements in the range.

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

std::for_each: Performs an operation on each element in the range.

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

std::min_elementandstd::max_element: Finds the minimum and maximum values in the range.

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

<algorithm>Is a very powerful tool in the C++ standard library. It provides a large number of generic algorithms, which can greatly simplify programming.