【C++】| STL算法库详解 | 修改序列的算法、非修改序列的算法、排序和相关操作、数值算法

C++的标准模板库（STL）中的算法库提供了许多常用的函数，主要用于对容器中的数据进行操作。这些算法可以分为几大类，包括修改序列的算法、非修改序列的算法、排序和相关操作、数值算法等。以下是一些常用的STL算法：

非修改序列的算法

• for_each: 对每个元素执行一个指定的操作。
• find: 查找等于某值的元素。
• find_if: 查找第一个满足特定条件的元素。
• count: 计算等于某值的元素个数。
• count_if: 计算满足特定条件的元素个数。
• all_of: 检查所有元素是否都满足特定条件。
• any_of: 检查是否至少有一个元素满足特定条件。
• none_of: 检查是否没有元素满足特定条件。

修改序列的算法

• copy: 复制一个序列到另一个位置。
• copy_if: 复制满足特定条件的元素到另一个位置。
• transform: 对每个元素应用一个操作，并将结果存储到另一个位置。
• replace: 替换等于某值的元素。
• replace_if: 替换满足特定条件的元素。
• fill: 用指定值填充一个范围。
• remove: 移除等于某值的元素（逻辑删除）。
• remove_if: 移除满足特定条件的元素（逻辑删除）。
• unique: 移除相邻的重复元素。

排序和相关操作

• sort: 对序列进行排序。
• partial_sort: 部分排序，使得前N个元素有序。
• nth_element: 重排元素，使得第N个元素位于它在排序后的位置上。
• stable_sort: 稳定排序，保留相等元素的相对顺序。
• lower_bound: 在已排序范围中查找第一个不小于给定值的元素。
• upper_bound: 在已排序范围中查找第一个大于给定值的元素。
• binary_search: 二分查找，判断是否存在某值。
• merge: 合并两个已排序范围。
• inplace_merge: 原地合并两个相邻的已排序范围。

数值算法

• accumulate: 计算范围内所有元素的累加和。
• inner_product: 计算两个范围内元素的内积。
• adjacent_difference: 计算相邻元素的差值。
• partial_sum: 计算部分和。

这些算法可以极大地简化常见的数据处理任务，提高代码的可读性和可维护性。在使用这些算法时，需要熟悉相应的头文件和函数签名，并且注意算法的复杂度和适用范围。

非修改序列的算法

for_each

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，用于打印每个元素
void print(int n) {std::cout << n << " ";
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用for_each算法，对每个元素应用print函数std::for_each(v.begin(), v.end(), print);return 0;
}

优点：

• 简洁性：使用for_each可以让代码更加简洁、易读。例如，在需要对容器中的每个元素执行相同操作时，for_each的表达能力更强。
  抽象程度高：for_each使用了函数对象或lambda表达式，使得代码更加模块化和复用性更高。
• STL一致性：for_each是STL的一部分，使用它有助于保持代码风格的一致性，尤其是在处理STL容器和算法时。

缺点：

• 灵活性：在某些复杂情况下，for_each可能不如传统的for循环灵活。例如，for_each不直接支持循环中的控制语句（如break和continue），尽管可以通过其他方式实现，但会增加复杂性。
• 性能开销：虽然for_each在大多数情况下性能差异不大，但在某些极端性能要求的场合，传统for循环可能表现得更好。

💦输出结果：

1 2 3 4 5 

find

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用find算法查找值为3的元素auto it = std::find(v.begin(), v.end(), 3);// 如果找到了元素，输出该元素if (it != v.end()) {std::cout << "Found: " << *it << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}

输出结果：

Found: 3

find_if

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为偶数
bool is_even(int n) {return n % 2 == 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用find_if算法查找第一个偶数auto it = std::find_if(v.begin(), v.end(), is_even);// 如果找到了偶数，输出该元素if (it != v.end()) {std::cout << "Found even: " << *it << std::endl;} else {std::cout << "No even number found" << std::endl;}return 0;
}

输出结果：

Found even: 2

count

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 2, 3, 4, 2, 5};// 使用count算法统计值为2的元素个数int count = std::count(v.begin(), v.end(), 2);std::cout << "Count of 2: " << count << std::endl;return 0;
}

输出结果：

Count of 2: 3

count_if

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为奇数
bool is_odd(int n) {return n % 2 != 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用count_if算法统计奇数的个数int count = std::count_if(v.begin(), v.end(), is_odd);std::cout << "Count of odd numbers: " << count << std::endl;return 0;
}

输出结果：

Count of odd numbers: 3

all_of

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为正数
bool is_positive(int n) {return n > 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用all_of算法检查是否所有元素都是正数bool all_positive = std::all_of(v.begin(), v.end(), is_positive);std::cout << "All positive: " << (all_positive ? "Yes" : "No") << std::endl;return 0;
}

输出结果：

All positive: Yes

any_of

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为负数
bool is_negative(int n) {return n < 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, -4, 5};// 使用any_of算法检查是否至少有一个元素是负数bool any_negative = std::any_of(v.begin(), v.end(), is_negative);std::cout << "Any negative: " << (any_negative ? "Yes" : "No") << std::endl;return 0;
}

输出结果：

Any negative: Yes

none_of

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为负数
bool is_negative(int n) {return n < 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用none_of算法检查是否没有一个元素是负数bool none_negative = std::none_of(v.begin(), v.end(), is_negative);std::cout << "None negative: " << (none_negative ? "Yes" : "No") << std::endl;return 0;
}

输出结果：

None negative: Yes

修改序列的算法

copy

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些整数的向量std::vector<int> v1 = {1, 2, 3, 4, 5};// 创建另一个向量用于存储复制结果std::vector<int> v2(v1.size());// 使用copy算法将v1的内容复制到v2std::copy(v1.begin(), v1.end(), v2.begin());// 输出v2的内容for (int n : v2) {std::cout << n << " ";}return 0;
}

输出结果：

1 2 3 4 5 

copy_if

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为偶数
bool is_even(int n) {return n % 2 == 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v1 = {1, 2, 3, 4, 5};// 创建另一个向量用于存储复制结果std::vector<int> v2;// 使用copy_if算法将v1中所有偶数复制到v2std::copy_if(v1.begin(), v1.end(), std::back_inserter(v2), is_even);// 输出v2的内容for (int n : v2) {std::cout << n << " ";}return 0;
}

输出结果：

2 4 

transform

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，将整数加倍
int double_value(int n) {return n * 2;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v1 = {1, 2, 3, 4, 5};// 创建另一个向量用于存储变换结果std::vector<int> v2(v1.size());// 使用transform算法将v1中的每个元素加倍并存储到v2std::transform(v1.begin(), v1.end(), v2.begin(), double_value);// 输出v2的内容for (int n : v2) {std::cout << n << " ";}return 0;
}

输出结果：

2 4 6 8 10 

replace

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 2, 5};// 使用replace算法将所有值为2的元素替换为10std::replace(v.begin(), v.end(), 2, 10);// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：
``

`
1 10 3 10 5

#### `replace_if`
```cpp
#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为奇数
bool is_odd(int n) {return n % 2 != 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用replace_if算法将所有奇数替换为0std::replace_if(v.begin(), v.end(), is_odd, 0);// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

0 2 0 4 0 

fill

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些整数的向量std::vector<int> v(5);// 使用fill算法将所有元素填充为7std::fill(v.begin(), v.end(), 7);// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

7 7 7 7 7 

remove

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 2, 5};// 使用remove算法将所有值为2的元素移到序列末尾auto it = std::remove(v.begin(), v.end(), 2);// 通过擦除（erase）方法实际删除这些元素v.erase(it, v.end());// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

1 3 5 

remove_if

#include <iostream>
#include <vector>
#include <algorithm>// 自定义函数，判断一个整数是否为奇数
bool is_odd(int n) {return n % 2 != 0;
}int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用remove_if算法将所有奇数移到序列末尾auto it = std::remove_if(v.begin(), v.end(), is_odd);// 通过擦除（erase）方法实际删除这些元素v.erase(it, v.end());// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

2 4 

unique

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些重复整数的向量std::vector<int> v = {1, 2, 2, 3, 3, 4, 5};// 使用unique算法将相邻重复的元素移到序列末尾auto it = std::unique(v.begin(), v.end());// 通过擦除（erase）方法实际删除这些元素v.erase(it, v.end());// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

1 2 3 4 5 

排序和相关操作

sort

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些无序整数的向量std::vector<int> v = {5, 3, 1, 4, 2};// 使用sort算法对v进行排序std::sort(v.begin(), v.end());// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

1 2 3 4 5 

partial_sort

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些无序整数的向量std::vector<int> v = {5, 3, 1, 4, 2};// 使用partial_sort算法将v的前3个元素排序std::partial_sort(v.begin(), v.begin() + 3, v.end());// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

1 2 3 5 4 

nth_element

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些无序整数的向量std::vector<int> v = {5, 3, 1, 4, 2};// 使用nth_element算法将v的第3个元素放置在它排序后的位置上std::nth_element(v.begin(), v.begin() + 2, v.end());// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

1 2 3 5 4 

stable_sort

#include <iostream>
#include <vector>
#include <algorithm>struct Item {int value;int order;
};// 比较函数，根据value排序
bool compare(const Item& a, const Item& b) {return a.value < b.value;
}int main() {// 创建一个包含一些Item对象的向量std::vector<Item> v = {{5, 1}, {3, 2}, {1, 3}, {4, 4}, {2, 5}};// 使用stable_sort算法对v进行稳定排序std::stable_sort(v.begin(), v.end(), compare);// 输出v的内容for (const Item& item : v) {std::cout << item.value << "(" << item.order << ") ";}return 0;
}

输出结果：

1(3) 2(5) 3(2) 4(4) 5(1) 

lower_bound

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些有序整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用lower_bound算法查找第一个不小于3的元素auto it = std::lower_bound(v.begin(), v.end(), 3);// 输出结果std::cout << "Lower bound of 3: " << (it != v.end() ? std::to_string(*it) : "Not found") << std::endl;return 0;
}

输出结果：

Lower bound of 3: 3

upper_bound

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些有序整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用upper_bound算法查找第一个大于3的元素auto it = std::upper_bound(v.begin(), v.end(), 3);// 输出结果std::cout << "Upper bound of 3: " << (it != v.end() ? std::to_string(*it) : "Not found") << std::endl;return 0;
}

输出结果：

Upper bound of 3: 4

binary_search

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含一些有序整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用binary_search算法检查是否存在值为3的元素bool found = std::binary_search(v.begin(), v.end(), 3);// 输出结果std::cout << "Binary search for 3: " << (found ? "Found" : "Not found") << std::endl;return 0;
}

输出结果：

Binary search for 3: Found

merge

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建两个有序向量std::vector<int> v1 = {1, 3, 5};std::vector<int> v2 = {2, 4, 6};// 创建一个向量用于存储合并结果std::vector<int> v3(v1.size() + v2.size());// 使用merge算法将v1和v2合并到v3std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());// 输出v3的内容for (int n : v3) {std::cout << n << " ";}return 0;
}

输出结果：

1 2 3 4 5 6 

inplace_merge

#include <iostream>
#include <vector>
#include <algorithm>int main() {// 创建一个包含两个有序部分的向量std::vector<int> v = {1, 3, 5, 2, 4, 6};// 使用inplace_merge算法将两个有序部分合并std::inplace_merge(v.begin(), v.begin() + 3, v.end());// 输出v的内容for (int n : v) {std::cout << n << " ";}return 0;
}

输出结果：

1 2 3 4 5 6 

数值算法

accumulate

#include <iostream>
#include <vector>
#include <numeric>int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 使用accumulate算法计算所有元素的累加和int sum = std::accumulate(v.begin(), v.end(), 0); // 初始值为0// 输出结果std::cout << "Sum: " << sum << std::endl;return 0;
}

输出结果：

Sum: 15

inner_product

#include <iostream>
#include <vector>
#include <numeric>int main() {// 创建两个包含一些整数的向量std::vector<int> v1 = {1, 2, 3};std::vector<int> v2 = {4, 5, 6};// 使用inner_product算法计算v1和v2的内积int product = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0); // 初始值为0// 输出结果std::cout << "Inner product: " << product << std::endl;return 0;
}

输出结果：

Inner product: 32

adjacent_difference

#include <iostream>
#include <vector>
#include <numeric>int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 4, 7, 11};// 创建一个向量用于存储相邻差异std::vector<int> diff(v.size());// 使用adjacent_difference算法计算相邻差异std::adjacent_difference(v.begin(), v.end(), diff.begin());// 输出diff的内容for (int n : diff) {std::cout << n << " ";}return 0;
}

输出结果：

1 1 2 3 4 

partial_sum

#include <iostream>
#include <vector>
#include <numeric>int main() {// 创建一个包含一些整数的向量std::vector<int> v = {1, 2, 3, 4, 5};// 创建一个向量用于存储部分和std::vector<int> sum(v.size());// 使用partial_sum算法计算部分和std::partial_sum(v.begin(), v.end(), sum.begin());// 输出sum的内容for (int n : sum) {std::cout << n << " ";}return 0;
}

输出结果：

1 3 6 10 15