C++标准库 第十一章 STL 算法 前半部分

C++标准库算法头文件是一组用于处理容器的算法函数的集合。这些算法函数可以应用于各种容器，如数组、向量、列表等。这些头文件提供了许多常见的算法操作，如排序、搜索、合并等，以及其他一些辅助函数。

以下是一些常用的C++标准库算法头文件及其功能的举例：

1. `<algorithm>`：提供了许多基本的算法函数，如排序、查找、交换等。

- `sort()`：对容器进行排序。

- `find()`：在容器中查找指定的元素。

- `swap()`：交换两个元素的值。

2. `<numeric>`：提供了一些数值算法函数，如求和、累积等。

- `accumulate()`：计算容器中元素的总和。

- `inner_product()`：计算两个容器的内积。

3. `<functional>`：提供了一些函数对象，如比较、算术等。

- `plus()`：将两个数相加。

- `less()`：比较两个数的大小。

4. `<iterator>`：提供了一些迭代器相关的函数。

- `distance()`：计算两个迭代器之间的距离。

- `advance()`：将迭代器向前或向后移动指定的距离。

这些头文件中的算法函数可以用于各种容器，并且它们是通用的，可以适用于不同类型的元素。通过使用这些算法函数，可以简化代码并提高开发效率。

C++标准库中的算法是一组用于处理容器的函数模板。这些函数模板提供了各种算法操作，如排序、搜索、合并、转换等。这些算法函数可以应用于各种容器，如数组、向量、列表等。

C++标准库算法可以大大简化编写和管理代码的过程，并提供了高效的实现。它们是经过优化和测试的，可以在各种场景下提供高性能和可靠性。

以下是一些常见的C++标准库算法及其用法的示例：

1. 排序算法（Sorting algorithms）：

- std::sort：对容器中的元素进行排序。

- std::partial_sort：部分排序容器中的元素。

- std::stable_sort：稳定排序容器中的元素。

2. 查找算法（Searching algorithms）：

- std::find：在容器中查找指定的元素。

- std::binary_search：在已排序的容器中执行二分查找。

- std::count：计算容器中指定元素的数量。

3. 变换算法（Transforming algorithms）：

- std::transform：将容器中的元素转换为另一种形式。

- std::replace：将容器中的元素替换为另一个值。

- std::reverse：反转容器中的元素顺序。

4. 合并算法（Merging algorithms）：

- std::merge：将两个已排序的容器合并为一个已排序的容器。

- std::inplace_merge：在已排序的容器中原地合并两个相邻的有序序列。

5. 数值算法（Numeric algorithms）：

- std::accumulate：计算容器中元素的总和。

- std::min_element：找到容器中的最小元素。

- std::max_element：找到容器中的最大元素。

这些只是C++标准库中算法的一小部分，还有许多其他有用的算法可供使用。使用这些算法可以提高代码的可读性、可维护性和性能。

C++标准库是C++语言的核心库，它包含了一组丰富的功能模块，用于支持各种常用的编程任务。标准库被分为两个主要部分：标准函数库和标准模板库。

1. 标准函数库：
2. <iostream>：提供了输入和输出的功能，包括cin和cout等。
3. <string>：提供了对字符串的操作函数，如拼接、查找、替换等。
4. <cmath>：提供了数学函数，如求平方根、三角函数、对数函数等。
5. <ctime>：提供了时间和日期的函数，如获取当前时间、延时等。
6. 标准模板库（STL）：
7. <vector>：提供了可变大小的动态数组。
8. <list>：提供了双向链表。
9. <map>：提供了键值对的关联容器。
10. <algorithm>：提供了一系列算法函数，如排序、查找、合并等。

举例：

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

int main() {
    std::vector<int> nums = {5, 2, 8, 1, 9};

    // 使用标准库算法对向量进行排序
    std::sort(nums.begin(), nums.end());

    // 输出排序后的向量
    for (int num : nums) {
        std::cout << num << " ";
    }

    return 0;
}

以上代码使用了<iostream>、<vector>和<algorithm>头文件。它创建了一个包含一些整数的向量，然后使用std::sort()函数对向量进行排序，并使用std::cout输出排序后的结果。

C++标准库中的算法可以分为以下几类：

1. 非修改序列操作（Non-modifying sequence operations）：
2. std::all_of：检查容器中的所有元素是否都满足某个条件。
3. std::any_of：检查容器中是否存在满足某个条件的元素。
4. std::none_of：检查容器中是否不存在满足某个条件的元素。
5. std::count：计算容器中满足某个条件的元素个数。
6. std::find：在容器中查找第一个满足某个条件的元素。
7. 修改序列操作（Modifying sequence operations）：
8. std::copy：将一个容器中的元素复制到另一个容器中。
9. std::transform：对容器中的元素进行转换操作。
10. std::replace：将容器中所有满足某个条件的元素替换为新值。
11. std::fill：将容器中的所有元素设置为给定值。
12. std::remove：从容器中移除满足某个条件的元素。
13. 排序和相关操作（Sorting and related operations）：
14. std::sort：对容器中的元素进行排序。
15. std::partial_sort：部分排序容器中的元素。
16. std::merge：将两个已排序的容器合并为一个有序容器。
17. std::binary_search：在已排序的容器中进行二分查找。
18. 数值操作（Numeric operations）：
19. std::accumulate：计算容器中元素的累加和。
20. std::inner_product：计算两个容器的内积。
21. std::transform_reduce：对容器中的元素进行转换和累积操作。

这只是C++标准库算法的一小部分，还有许多其他有用的算法可以帮助开发人员更高效地处理容器中的数据。

C++标准库中的辅助函数提供了一些常用的功能函数，用于辅助编程任务。以下是一些常见的辅助函数及其功能：

1. std::swap：用于交换两个对象的值。
2. int a = 1; int b = 2; std::swap(a, b); // 现在 a 的值为 2，b 的值为 1
3. std::min 和 std::max：用于返回两个对象中的最小值和最大值。
4. int a = 1; int b = 2; int min_value = std::min(a, b); // 返回 1 int max_value = std::max(a, b); // 返回 2
5. std::abs：用于返回一个数的绝对值。
6. int a = -5; int abs_value = std::abs(a); // 返回 5
7. std::sqrt：用于计算一个数的平方根。
8. double x = 9.0; double sqrt_value = std::sqrt(x); // 返回 3.0
9. std::to_string：将基本数据类型转换为字符串。
10. int num = 123; std::string str = std::to_string(num); // 返回 "123"

这些辅助函数在编程中经常被使用，可以提高代码的可读性和简洁性。

C++标准库中的for_each()算法用于对容器中的每个元素执行某个操作。它接受一个范围（容器的起始和结束迭代器）和一个可调用对象（函数、函数指针、函数对象等），并对范围内的每个元素依次调用该可调用对象。

for_each()算法的语法如下：

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function fn);

其中，first和last是表示范围的迭代器，fn是可调用对象。

以下是一个示例，演示如何使用for_each()算法对容器中的每个元素进行打印：

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

void print(int num) {
    std::cout << num << " ";
}

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

    std::for_each(nums.begin(), nums.end(), print);

    return 0;
}

输出结果为：1 2 3 4 5

在上面的示例中，我们定义了一个print()函数，用于打印每个元素。然后，我们使用for_each()算法对nums容器中的每个元素调用print()函数，从而实现了打印每个元素的功能。

C++标准库中的非修改型算法（Nonmodifying Algorithm）是指那些不会修改容器中元素值的算法。这些算法通常用于对容器中的元素进行查找、计数、比较等操作，而不会改变容器本身。以下是一些常见的非修改型算法及其功能：

1. std::find：用于在容器中查找指定值的第一个匹配项，并返回指向该元素的迭代器。
2. std::vector<int> vec = {1, 2, 3, 4, 5}; auto it = std::find(vec.begin(), vec.end(), 3); // it 指向容器中值为 3 的元素
3. std::count：用于计算容器中某个值的出现次数，并返回结果。
4. std::vector<int> vec = {1, 2, 2, 3, 2}; int count = std::count(vec.begin(), vec.end(), 2); // count 的值为 3，表示值为 2 的元素在容器中出现了 3 次
5. std::all_of、std::any_of 和 std::none_of：用于判断容器中的元素是否满足某个条件，返回一个布尔值。
6. std::vector<int> vec = {1, 2, 3, 4, 5}; bool all_positive = std::all_of(vec.begin(), vec.end(), [](int n) { return n > 0; }); // all_positive 的值为 true，表示容器中的所有元素都大于 0 bool any_negative = std::any_of(vec.begin(), vec.end(), [](int n) { return n < 0; }); // any_negative 的值为 false，表示容器中的元素中没有小于 0 的元素 bool none_zero = std::none_of(vec.begin(), vec.end(), [](int n) { return n == 0; }); // none_zero 的值为 true，表示容器中的元素中没有等于 0 的元素

这些非修改型算法提供了一种方便、高效的方式来处理容器中的元素，而不需要直接修改容器本身。

C++标准库中的元素计数算法用于统计容器中某个特定元素出现的次数。这个算法接受一个范围（容器的起始和结束迭代器）和一个要计数的元素值，并返回该元素在范围内出现的次数。

元素计数算法的语法如下：

template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value);

其中，first和last是表示范围的迭代器，value是要计数的元素值。

以下是一个示例，演示如何使用元素计数算法count()统计一个容器中某个元素出现的次数：

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

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

    int count = std::count(numbers.begin(), numbers.end(), 3);

    std::cout << "Number of occurrences of 3: " << count << std::endl;

    return 0;
}

输出结果为：

Number of occurrences of 3: 2

这个示例中，我们使用count()算法统计了容器numbers中元素值为3的出现次数，结果为2。

C++标准库提供了最小值和最大值算法，用于查找容器中的最小值和最大值。这两个算法分别是std::min_element和std::max_element。

1. std::min_element：该算法接受一个范围（容器的起始和结束迭代器），并返回指向范围内最小元素的迭代器。
2. std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6}; auto minIt = std::min_element(vec.begin(), vec.end()); // minIt指向值为1的元素
3. std::max_element：该算法接受一个范围（容器的起始和结束迭代器），并返回指向范围内最大元素的迭代器。
4. std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6}; auto maxIt = std::max_element(vec.begin(), vec.end()); // maxIt指向值为9的元素

这些算法适用于任何支持迭代器的容器，包括数组、向量、列表等。如果容器为空，则返回的迭代器将指向容器的end()位置。

C++标准库提供了多个查找元素的算法，用于在容器中查找指定的元素。这些算法包括std::find、std::find_if、std::find_if_not、std::find_end、std::find_first_of等。

1. std::find：在给定范围内查找指定的值，并返回第一个匹配的元素的迭代器。如果没有找到匹配的元素，则返回结束迭代器。

std::vector<int> nums = {1, 2, 3, 4, 5};
auto it = std::find(nums.begin(), nums.end(), 3);
if (it != nums.end()) {
    std::cout << "Found at index: " << std::distance(nums.begin(), it) << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

2. std::find_if：在给定范围内查找满足指定条件的元素，并返回第一个满足条件的元素的迭代器。如果没有找到满足条件的元素，则返回结束迭代器。

std::vector<int> nums = {1, 2, 3, 4, 5};
auto it = std::find_if(nums.begin(), nums.end(), [](int num) { return num % 2 == 0; });
if (it != nums.end()) {
    std::cout << "Found at index: " << std::distance(nums.begin(), it) << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

3. std::find_if_not：在给定范围内查找不满足指定条件的元素，并返回第一个不满足条件的元素的迭代器。如果没有找到不满足条件的元素，则返回结束迭代器。

std::vector<int> nums = {1, 2, 3, 4, 5};
auto it = std::find_if_not(nums.begin(), nums.end(), [](int num) { return num % 2 == 0; });
if (it != nums.end()) {
    std::cout << "Found at index: " << std::distance(nums.begin(), it) << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

4. std::find_end：在给定范围内查找最后一次出现另一个范围的位置，并返回第一个匹配的元素的迭代器。如果没有找到匹配的元素，则返回结束迭代器。

std::vector<int> nums = {1, 2, 3, 4, 5, 1, 2, 3};
std::vector<int> sub = {1, 2, 3};
auto it = std::find_end(nums.begin(), nums.end(), sub.begin(), sub.end());
if (it != nums.end()) {
    std::cout << "Found at index: " << std::distance(nums.begin(), it) << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

5. std::find_first_of：在给定范围内查找第一次出现另一个范围中的任意元素的位置，并返回第一个匹配的元素的迭代器。如果没有找到匹配的元素，则返回结束迭代器。

std::vector<int> nums = {1, 2, 3, 4, 5};
std::vector<int> targets = {6, 7, 3};
auto it = std::find_first_of(nums.begin(), nums.end(), targets.begin(), targets.end());
if (it != nums.end()) {
    std::cout << "Found at index: " << std::distance(nums.begin(), it) << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

这些算法都接受一个范围（容器的起始和结束迭代器）和一个要查找的元素或条件，并返回匹配的元素的迭代器。如果没有找到匹配的元素，则返回结束迭代器。

C++标准库提供了多个用于比较区间的算法，用于比较两个区间的元素是否相等或者在某种排序规则下的顺序关系。这些算法包括std::equal、std::lexicographical_compare、std::mismatch等。

1. std::equal：该算法接受两个范围（容器的起始和结束迭代器），并比较两个范围中的元素是否相等。如果两个范围中的元素都相等，则返回true；否则返回false。
2. std::vector<int> vec1 = {1, 2, 3, 4, 5}; std::vector<int> vec2 = {1, 2, 3, 4, 5}; bool isEqual = std::equal(vec1.begin(), vec1.end(), vec2.begin()); // 返回true
3. std::lexicographical_compare：该算法接受两个范围（容器的起始和结束迭代器），并比较两个范围中的元素在字典序上的大小关系。如果第一个范围在字典序上小于第二个范围，则返回true；否则返回false。
4. std::vector<int> vec1 = {1, 2, 3}; std::vector<int> vec2 = {1, 2, 4}; bool isLess = std::lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()); // 返回true
5. std::mismatch：该算法接受两个范围（容器的起始和结束迭代器），并返回两个范围中第一个不匹配的元素的迭代器对。如果两个范围完全相等，则返回两个范围的结束迭代器对。
6. std::vector<int> vec1 = {1, 2, 3}; std::vector<int> vec2 = {1, 2, 4}; auto mismatchIt = std::mismatch(vec1.begin(), vec1.end(), vec2.begin()); // 返

C++标准库中的Predicate是一个函数对象，用于对区间中的元素进行检验。Predicate接受一个参数并返回一个bool值，用于判断元素是否满足特定条件。

在C++标准库中，有一些算法接受Predicate作为参数，用于对区间中的元素进行筛选、判断等操作。这些算法包括std::find_if、std::remove_if、std::count_if等。

下面是一个使用std::find_if和Predicate的示例：

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

bool isEven(int num) {
    return num % 2 == 0;
}

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

    auto it = std::find_if(nums.begin(), nums.end(), isEven);

    if (it != nums.end()) {
        std::cout << "First even number found: " << *it << std::endl;
    } else {
        std::cout << "No even number found" << std::endl;
    }

    return 0;
}

在上面的示例中，我们定义了一个Predicate函数对象isEven，用于判断一个整数是否为偶数。然后我们使用std::find_if算法在nums容器中查找第一个满足isEven条件的元素，并输出结果。如果找到了满足条件的元素，则输出该元素的值；如果没有找到满足条件的元素，则输出提示信息。

C++标准库中的更易型算法（Modifying Algorithm）用于修改容器中的元素或者对容器进行重新排列。这些算法包括std::copy、std::move、std::transform等。

1. std::copy：该算法用于将一个范围中的元素复制到另一个范围中。它接受源范围的起始和结束迭代器，以及目标范围的起始迭代器。被复制的元素从源范围的起始位置开始，按照顺序复制到目标范围中，返回目标范围的结束迭代器。
2. std::vector<int> vec1 = {1, 2, 3, 4, 5}; std::vector<int> vec2(5); std::copy(vec1.begin(), vec1.end(), vec2.begin()); // vec2: {1, 2, 3, 4, 5}
3. std::move：该算法用于将一个范围中的元素移动到另一个范围中。它接受源范围的起始和结束迭代器，以及目标范围的起始迭代器。被移动的元素从源范围的起始位置开始，按照顺序移动到目标范围中，返回目标范围的结束迭代器。移动后，源范围中的元素将变为未定义状态。
4. std::vector<std::string> vec1 = {"hello", "world"}; std::vector<std::string> vec2(2); std::move(vec1.begin(), vec1.end(), vec2.begin()); // vec2: {"hello", "world"} // vec1: {"", ""}
5. std::transform：该算法用于对一个范围中的元素进行转换，并将结果存储到另一个范围中。它接受源范围的起始和结束迭代器，目标范围的起始迭代器，以及一个一元或二元函数对象。该函数对象将被应用于源范围中的每个元素，并将结果存储到目标范围中。
6. std::vector<int> vec1 = {1, 2, 3, 4, 5}; std::vector<int> vec2(5); std::transform(vec1.begin(), vec1.end(), vec2.begin(), [](int x) { return x * 2; }); // vec2: {2, 4, 6, 8, 10}

C++标准库中的复制元素（Copying Element）算法用于将一个容器中的元素复制到另一个容器中。这些算法包括std::copy、std::copy_if、std::copy_n等。

1. std::copy：该算法用于将一个范围中的元素复制到另一个范围中。它接受三个参数，分别是源范围的起始迭代器、源范围的结束迭代器和目标范围的起始迭代器。例如：

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);

std::copy(source.begin(), source.end(), destination.begin());

// 输出目标容器中的元素
for (int num : destination) {
    std::cout << num << " ";
}
// 输出结果：1 2 3 4 5

2. std::copy_if：该算法用于将满足特定条件的元素从一个范围复制到另一个范围。它接受四个参数，分别是源范围的起始迭代器、源范围的结束迭代器、目标范围的起始迭代器和一个谓词（Predicate）函数对象。例如：

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);

std::copy_if(source.begin(), source.end(), destination.begin(), [](int num) {
    return num % 2 == 0; // 复制偶数
});

// 输出目标容器中的元素
for (int num : destination) {
    std::cout << num << " ";
}
// 输出结果：2 4 0 0 0

3. std::copy_n：该算法用于将一个范围中的指定数量的元素复制到另一个范围中。它接受三个参数，分别是源范围的起始迭代器、要复制的元素数量和目标范围的起始迭代器。例如：

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(3);

std::copy_n(source.begin(), 3, destination.begin());

// 输出目标容器中的元素
for (int num : destination) {
    std::cout << num << " ";
}
// 输出结果：1 2 3

这些算法都是通过迭代器来操作容器中的元素，可以灵活地对容器进行复制操作。

C++标准库中的搬移元素（Moving Element）算法用于将一个容器中的元素搬移到另一个容器中，而不是复制它们。这些算法包括std::move、std::move_backward等。

1. std::move：该算法用于将一个范围中的元素搬移到另一个范围中。它接受源范围的起始和结束迭代器，以及目标范围的起始迭代器。被搬移的元素从源范围的起始位置开始，按照顺序搬移到目标范围中，返回目标范围的结束迭代器。
2. std::vector<int> vec1 = {1, 2, 3, 4, 5}; std::vector<int> vec2(5); std::move(vec1.begin(), vec1.end(), vec2.begin()); // vec1现在为空 // vec2包含搬移后的元素：1, 2, 3, 4, 5
3. std::move_backward：该算法用于将一个范围中的元素搬移到另一个范围中，逆序搬移。它接受源范围的起始和结束迭代器，以及目标范围的结束迭代器。被搬移的元素从源范围的结束位置开始，按照逆序搬移到目标范围中，返回目标范围的起始迭代器。
4. std::vector<int> vec1 = {1, 2, 3, 4, 5}; std::vector<int> vec2(5); std::move_backward(vec1.begin(), vec1.end(), vec2.end()); // vec1现在为空 // vec2包含逆序搬移后的元素：5, 4, 3, 2, 1

这些搬移元素的算法对于需要转移资源所有权的情况非常有用，比如移动语义和右值引用的使用。搬移元素可以提高程序的性能，避免不必要的复制操作。

C++标准库中的转换和结合元素（Transforming and Combining Element）算法用于对容器中的元素进行转换或结合操作。这些算法包括std::transform、std::accumulate、std::inner_product等。

1. std::transform：该算法用于对一个范围中的元素进行转换操作，并将结果存储到另一个范围中。它接受四个参数，分别是源范围的起始迭代器、源范围的结束迭代器、目标范围的起始迭代器和一个一元或二元操作函数。例如：

std::vector<int> source = {1, 2, 3};
std::vector<int> destination(source.size());

std::transform(source.begin(), source.end(), destination.begin(), [](int n) {
    return n * 2;
});

在上面的例子中，源容器中的每个元素都会乘以2，并将结果存储到目标容器中。

2. std::accumulate：该算法用于对一个范围中的元素进行累加操作。它接受三个参数，分别是范围的起始迭代器、范围的结束迭代器和一个初始值。例如：

std::vector<int> numbers = {1, 2, 3, 4, 5};

int sum = std::accumulate(numbers.begin(), numbers.end(), 0);

在上面的例子中，将对numbers中的元素进行累加操作，初始值为0，最终得到的结果是15。

3. std::inner_product：该算法用于计算两个范围中的元素的内积。它接受四个参数，分别是两个范围的起始迭代器、两个范围的结束迭代器和一个初始值。例如：

std::vector<int> numbers1 = {1, 2, 3};
std::vector<int> numbers2 = {4, 5, 6};

int result = std::inner_product(numbers1.begin(), numbers1.end(), numbers2.begin(), 0);

在上面的例子中，将对numbers1和numbers2中的元素进行内积计算，初始值为0，最终得到的结果是32。

C++标准库中的互换元素（Swapping Elements）算法用于交换容器中的元素位置。这些算法包括std::swap、std::iter_swap等。

1. std::swap：该算法用于交换两个元素的值。它接受两个参数，通过引用传递这两个参数，并交换它们的值。

int a = 10;
int b = 20;
std::swap(a, b);
// 现在a的值为20，b的值为10

2. std::iter_swap：该算法用于交换两个迭代器指向的元素的值。它接受两个迭代器作为参数，并交换它们指向的元素的值。

std::vector<int> vec = {1, 2, 3, 4};
std::iter_swap(vec.begin(), vec.begin() + 2);
// 现在vec中的元素顺序变为3, 2, 1, 4

这些算法可以用于任何支持随机访问迭代器的容器，如vector、deque和数组等。它们提供了一种方便的方式来交换容器中的元素，而无需手动编写交换逻辑。