Stl算法
Stl算法
[TOC]
1. STL函数介绍
C++标准库中的泛型算法可以操作多种容器类型，包括标准库类型和内置数组。
这些 STL 算法主要定义在 <algorithm> 中，有些还会在 <numeric> 、 <functional> 等头文件中。
2. 常见函数简介
STL常见算法：1
- 排序算法，如
sort,reverse,nth_element。 - 查找与统计算法，如
find,binary_search,count。 - 可变序列算法，如
copy,replace,fill,unique,remove。 - 排列算法，如
next_permutation,prev_permutation。 - 前缀和与差分算法，如
partial_sum,adjacent_difference。 - 数学算法，如：
pow（指数运算）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
// 使用STL容器时将数组指针改为迭代器即可
int a[5] = { 1, 2, 3, 4, 5 };
int b[5] = { 0 };
// 排序算法：
sort(a, a + 5); // 将区间[0, 5)内元素按字典序从小到大排序（默认）
sort(a, a + 5, greater<int>()); // 从大到小排序，第三个参数也可以通过lamda或仿函数自定义排序方法
reverse(a, a + 5); // 将区间[0, 5)内元素翻转
nth_element(a, a + 3, a + 5); // 将区间[0, 5)中第a+3个数归位，即将第3大的元素放到正确的位置上，该元素前后的元素不一定有序
// 查找与统计算法：
find(a, a + 5, 3); // 在区间[0, 5)内查找等于3的元素，返回迭代器，若不存在则返回end()
binary_search(a, a + 5, 2); // 二分查找区间[0, 5)内是否存在元素2，存在返回true否则返回false
count(a, a + 5, 3); // 返回区间[0, 5)内元素3的个数
// 可变序列算法：
copy(a, a + 2, a + 3); // 将区间[0, 2)的元素复制到以a+3开始的区间，即[3, 5)
replace(a, a + 5, 3, 4); // 将区间[0, 5)内等于3的元素替换为4
fill(a, a + 5, 1); // 将1写入区间[0, 5)中(初始化数组函数)
unique(a, a + 5); // 将相邻元素间的重复元素全部移动至末端，返回去重之后数组最后一个元素之后的地址
remove(a, a + 5, 3); // 将区间[0, 5)中的元素3移至末端，返回新数组最后一个元素之后的地址
// 排列算法：
next_permutation(a, a + 5); // 产生下一个排列{ 1, 2, 3, 5, 4 }
prev_permutation(a, a + 5); // 产生上一个排列{ 1, 2, 3, 4, 5 }
// 前缀和算法：
partial_sum(a, a + 5, b); // 计算数组a在区间[0,5)内的前缀和并将结果保存至数组b中，b = { 1, 3, 6, 10, 15 }
// 差分算法：
adjacent_difference(a, a + 5, b);// 计算数组a区间[0,5)内的差分并将结果保存至数组b中，b = { 1, 1, 1, 1, 1 }
adjacent_difference(a, a + 5, b, plus<int>()); // 计算相邻两元素的和，b = { 1, 3, 5, 7, 9 }
adjacent_difference(a, a + 5, b, multiplies<int>()); // 计算相邻两元素的乘积，b = { 1, 2, 6, 12, 20 }
return 0;
}
std::remove 和 std::remove_if
std::remove 和 std::remove_if 定义于 <algorithm>，用于移除序列中满足条件的元素。2 3
注意：这两个函数不会改变容器大小，也不会真正删除元素——它们只将保留的元素往前搬，返回”新末尾”的迭代器（该位置之后是垃圾数据）。要真正删除，需配合 erase（即 erase-remove 惯用法）。C++20 起推荐直接用 std::erase / std::erase_if。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// remove：移除等于 3 的元素
auto it = std::remove(vec.begin(), vec.end(), 3);
vec.erase(it, vec.end());
// vec = {1, 2, 4, 5}
// remove_if：移除偶数（一行写法）
vec = {1, 2, 3, 4, 5};
vec.erase(std::remove_if(vec.begin(), vec.end(),
[](int x) { return x % 2 == 0; }),
vec.end());
// vec = {1, 3, 5}
return 0;
}
std::erase 和 std::erase_if (C++20)
C++20 引入了 std::erase 和 std::erase_if，直接删除容器中满足条件的元素，一步到位，不再需要 erase-remove 惯用法。3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector>
#include <iostream>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
// erase：删除等于 2 的元素
std::erase(nums, 2);
// nums = {1, 3, 4, 5}
// erase_if：删除偶数
std::erase_if(nums, [](int x) { return x % 2 == 0; });
// nums = {1, 3, 5}
return 0;
}
std::format
std::format 是 C++20 引入的一个新特性，它提供了一种更现代、更安全的方式来格式化字符串。这个函数类似于 Python 中的 str.format() 方法或者 C语言中的 printf，但它更安全，因为它避免了许多 printf 风格的格式化函数中常见的类型不匹配和缓冲区溢出问题。4
下面是一些使用 std::format 的例子：2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <format>
#include <iostream>
#include <string>
int main() {
// 基本用法
std::string s = std::format("Hello, {}!", "World");
std::cout << s << std::endl; // 输出: Hello, World!
// 使用位置参数
s = std::format("{1} is prior to {0}", "Second", "First");
std::cout << s << std::endl; // 输出: First is prior to Second
// 格式化数字
s = std::format("The number is: {0:.2f}", 3.14159);
std::cout << s << std::endl; // 输出: The number is: 3.14
// 定义宽度和填充
s = std::format("{:*>10}", "right");
std::cout << s << std::endl; // 输出: *****right
// 组合使用
int year = 2020, month = 5, day = 20;
s = std::format("The date is: {0}-{1:02}-{2:02}", year, month, day);
std::cout << s << std::endl; // 输出: The date is: 2020-05-20
return 0;
}
在上面的例子中，我们可以看到：
{}用于标识需要插入参数的位置。{1}和{0}这样的数字表示参数的位置索引。:.2f用于指定浮点数的格式，其中.2表示显示两位小数，f表示固定点表示法。:*>10表示用*填充，直到字符串宽度为 10，>表示右对齐。{1:02}表示取第二个参数，且参数格式化为至少两位数，如果数值小于两位数，则在前面填充0。
std::sort
std::sort 定义于 <algorithm>，对序列进行排序。默认升序，时间复杂度 O(n log n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
int main() {
std::vector<int> vec = {5, 3, 1, 4, 2};
// 默认升序
std::sort(vec.begin(), vec.end());
// vec = {1, 2, 3, 4, 5}
// 降序（传入 greater）
std::sort(vec.begin(), vec.end(), std::greater<int>());
// vec = {5, 4, 3, 2, 1}
// 自定义排序：按绝对值
std::vector<int> v2 = {-3, 1, -4, 2, 5};
std::sort(v2.begin(), v2.end(),
[](int a, int b) { return std::abs(a) < std::abs(b); });
// v2 = {1, 2, -3, -4, 5}
return 0;
}
std::find / std::find_if / std::find_if_not
定义于 <algorithm>，线性查找，时间复杂度 O(n)。若范围已排序，应改用 std::lower_bound 等二分算法。2
find— 查找等于val的第一个元素。find_if— 查找第一个满足谓词的元素。find_if_not(C++11) — 查找第一个不满足谓词的元素。
未找到时均返回 last。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 3, 5, 7, 9};
// find：查找等于 5 的元素
auto it = std::find(vec.begin(), vec.end(), 5);
if (it != vec.end())
std::cout << "found: " << *it << std::endl; // 输出: 5
// find_if：查找第一个偶数
it = std::find_if(vec.begin(), vec.end(),
[](int x) { return x % 2 == 0; });
// 没有偶数，返回 vec.end()
// find_if_not：查找第一个不等于 5 的元素
it = std::find_if_not(vec.begin(), vec.end(),
[](int x) { return x == 5; });
std::cout << "first != 5: " << *it << std::endl; // 输出: 1
return 0;
}
std::count 和 std::count_if
std::count 和 std::count_if 定义于 <algorithm>，统计序列中满足条件的元素个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
// count：统计等于 2 的元素个数
std::cout << std::count(vec.begin(), vec.end(), 2) << std::endl; // 输出: 3
// count_if：统计偶数的个数
auto n = std::count_if(vec.begin(), vec.end(),
[](int x) { return x % 2 == 0; });
std::cout << n << std::endl; // 输出: 4
return 0;
}
std::any_of / all_of / none_of (C++11)
定义于 <algorithm>，检查序列中是否存在 / 全部 / 没有元素满足谓词，返回 bool。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 3, 5, 7, 9};
std::cout << std::boolalpha;
std::cout << std::any_of(vec.begin(), vec.end(),
[](int x) { return x % 2 == 0; })
<< std::endl; // false（没有偶数）
std::cout << std::all_of(vec.begin(), vec.end(),
[](int x) { return x % 2 == 1; })
<< std::endl; // true（全是奇数）
std::cout << std::none_of(vec.begin(), vec.end(),
[](int x) { return x > 10; })
<< std::endl; // true（没有 >10 的）
return 0;
}
std::min_element 和 std::max_element
定义于 <algorithm>，返回指向序列中最小 / 最大元素的迭代器。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9, 3};
auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());
std::cout << "min: " << *min_it << std::endl; // 输出: 1
std::cout << "max: " << *max_it << std::endl; // 输出: 9
// 自定义比较：按绝对值找最小
std::vector<int> v2 = {-5, 2, -8, 1, 9, -3};
auto abs_min = std::min_element(v2.begin(), v2.end(),
[](int a, int b) { return std::abs(a) < std::abs(b); });
std::cout << "abs min: " << *abs_min << std::endl; // 输出: 1
return 0;
}
std::lower_bound 和 std::upper_bound
std::lower_bound 和 std::upper_bound 定义于 <algorithm>，均使用二分查找，要求范围已按非降序排序，时间复杂度 O(log n)。2
lower_bound— 返回第一个>= val的元素的迭代器。upper_bound— 返回第一个> val的元素的迭代器。
函数原型：
1
2
3
4
5
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val);
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val);
first、last 定义查找范围，val 为要查找的值。若所有元素都不满足条件，则返回 last（即 end()）。
另外还有一个接受自定义比较器的版本：
1
2
3
4
5
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
(1) 基本用法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 4, 4, 5, 6, 7};
auto lo4 = std::lower_bound(vec.begin(), vec.end(), 4);
auto hi4 = std::upper_bound(vec.begin(), vec.end(), 4);
// lo4 指向第一个 4（vec[2]），hi4 指向 4 之后第一个元素 vec[4] = 5
std::cout << "lower_bound(4) at index: " << (lo4 - vec.begin()) << std::endl;
std::cout << "upper_bound(4) at index: " << (hi4 - vec.begin()) << std::endl;
// 输出：
// lower_bound(4) at index: 2
// upper_bound(4) at index: 4
// 区间 [lo4, hi4) 内的元素全都是 4
std::cout << "count of 4: " << (hi4 - lo4) << std::endl;
// 输出：count of 4: 2
return 0;
}
(2) val 不存在时的行为
当 val 不在序列中时，lower_bound 和 upper_bound 返回相同的迭代器 — 都指向第一个 > val 的位置（即 val 按序插入时应放的位置）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 4, 4, 5, 6, 7};
// 3 不在数组中
auto lo3 = std::lower_bound(vec.begin(), vec.end(), 3);
auto hi3 = std::upper_bound(vec.begin(), vec.end(), 3);
std::cout << "lower_bound(3) == upper_bound(3): "
<< (lo3 == hi3) << std::endl; // 输出 1 (true)
std::cout << "insert position for 3: " << (lo3 - vec.begin()) << std::endl;
// 输出：insert position for 3: 2 （vec[2] = 4，3 应插在 2 和 4 之间）
// 小于所有元素时，都返回 begin()
auto lo0 = std::lower_bound(vec.begin(), vec.end(), 0);
std::cout << "lower_bound(0) == begin(): "
<< (lo0 == vec.begin()) << std::endl; // 输出 1
// 大于所有元素时，都返回 end()
auto lo9 = std::lower_bound(vec.begin(), vec.end(), 9);
std::cout << "lower_bound(9) == end(): "
<< (lo9 == vec.end()) << std::endl; // 输出 1
return 0;
}
(3) 配合使用：统计等于 val 的元素个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 5, 5, 6, 7};
int val = 5;
auto lo = std::lower_bound(vec.begin(), vec.end(), val);
auto hi = std::upper_bound(vec.begin(), vec.end(), val);
// hi - lo 就是 val 出现的次数
std::cout << "count of " << val << ": " << (hi - lo) << std::endl;
// 输出：count of 5: 3
return 0;
}
(4) 自定义比较器（降序数组）
如果序列是降序排列的，需要传入 greater 或自定义比较函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>
int main() {
std::vector<int> vec = {7, 6, 5, 4, 4, 2, 1}; // 降序
// 降序查找：传入 greater
auto lo4 = std::lower_bound(vec.begin(), vec.end(), 4, std::greater<int>());
auto hi4 = std::upper_bound(vec.begin(), vec.end(), 4, std::greater<int>());
std::cout << "lower_bound(4) at index: " << (lo4 - vec.begin()) << std::endl;
std::cout << "upper_bound(4) at index: " << (hi4 - vec.begin()) << std::endl;
// 输出：
// lower_bound(4) at index: 3
// upper_bound(4) at index: 5
std::cout << "count of 4: " << (hi4 - lo4) << std::endl;
// 输出：count of 4: 2
return 0;
}
(5) 在自定义结构体上使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <vector>
#include <iostream>
struct Student {
std::string name;
int score;
// 按 score 升序排序
bool operator<(const Student& other) const {
return score < other.score;
}
};
int main() {
std::vector<Student> students = {
{"Alice", 70}, {"Bob", 80}, {"Carol", 80}, {"Dave", 90}
};
// 查找第一个 score >= 80 的学生
auto it = std::lower_bound(students.begin(), students.end(), Student{"", 80},
[](const Student& a, const Student& b) { return a.score < b.score; });
std::cout << "first student with score >= 80: " << it->name << std::endl;
// 输出：first student with score >= 80: Bob
return 0;
}
std::binary_search
std::binary_search 定义于 <algorithm>，二分查找序列中是否存在 val，返回 bool。要求范围已排序，复杂度 O(log n)。2
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 4, 5, 6, 7};
std::cout << std::boolalpha;
std::cout << std::binary_search(vec.begin(), vec.end(), 4) << std::endl; // true
std::cout << std::binary_search(vec.begin(), vec.end(), 3) << std::endl; // false
return 0;
}
std::for_each
std::for_each 定义于 <algorithm>，对序列中每个元素执行指定操作。
C++11 引入范围 for 循环后，大多数场景 for (auto& x : vec) 更简洁，但 for_each 配合 C++17 执行策略（std::execution::par）可实现并行遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::for_each(vec.begin(), vec.end(),
[](int x) { std::cout << x << ' '; });
// 输出: 1 2 3 4 5
// 按引用修改元素
std::for_each(vec.begin(), vec.end(),
[](int& x) { x *= 2; });
// vec = {2, 4, 6, 8, 10}
return 0;
}
std::transform
std::transform 定义于 <algorithm>，对序列中每个元素执行变换，结果写入目标序列。相当于函数式编程中的 map。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());
// 一元：每个元素 ×2
std::transform(src.begin(), src.end(), dst.begin(),
[](int x) { return x * 2; });
// dst = {2, 4, 6, 8, 10}
// 二元：两个序列对应元素相加
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::transform(a.begin(), a.end(), b.begin(), dst.begin(),
[](int x, int y) { return x + y; });
// dst = {5, 7, 9}
return 0;
}
std::copy 和 std::copy_if
std::copy 和 std::copy_if 定义于 <algorithm>，将序列元素复制到目标位置。目标需有足够空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());
// copy：全部复制
std::copy(src.begin(), src.end(), dst.begin());
// dst = {1, 2, 3, 4, 5}
// copy_if：只复制偶数
auto end = std::copy_if(src.begin(), src.end(), dst.begin(),
[](int x) { return x % 2 == 0; });
dst.erase(end, dst.end());
// dst = {2, 4}
return 0;
}
std::unique
std::unique 定义于 <algorithm>，将相邻重复元素移至末尾，返回新末尾迭代器。通常先排序再使用，配合 erase 实现真正去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 2, 3, 3, 3, 4};
auto it = std::unique(vec.begin(), vec.end());
vec.erase(it, vec.end());
// vec = {1, 2, 3, 4} — 只去掉了相邻重复
return 0;
}
std::begin 和 std::end
std::begin 和 std::end 定义于 <iterator>（通常通过 <algorithm> 等间接包含），用于获取容器或 C 风格数组的首尾指针。相比 .begin() / .end() 成员函数，它们的优势在于对数组也能统一使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iterator>
#include <algorithm>
#include <iostream>
int main() {
int arr[] = {5, 3, 1, 4, 2};
// 数组没有 .begin() / .end()，但可以用 std::begin / std::end
std::sort(std::begin(arr), std::end(arr));
for (auto x : arr)
std::cout << x << ' '; // 输出: 1 2 3 4 5
return 0;
}
std::iota
std::iota 定义于 <numeric>，用递增序列填充范围。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec(5);
std::iota(vec.begin(), vec.end(), 1);
// vec = {1, 2, 3, 4, 5}
std::iota(vec.begin(), vec.end(), 10);
// vec = {10, 11, 12, 13, 14}
return 0;
}
std::merge
std::merge 定义于 <algorithm>，合并两个已排序序列，结果保持有序。不会修改原序列，目标容器需提前分配空间。2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
int main() {
std::vector<int> v1 = {1, 3, 5, 7};
std::vector<int> v2 = {2, 4, 6, 8};
std::vector<int> result(v1.size() + v2.size());
// 升序合并（默认 <）
std::merge(v1.begin(), v1.end(),
v2.begin(), v2.end(),
result.begin());
// result = {1, 2, 3, 4, 5, 6, 7, 8}
// 降序合并（传入比较器）
v1 = {7, 5, 3, 1};
v2 = {8, 6, 4, 2};
std::merge(v1.begin(), v1.end(),
v2.begin(), v2.end(),
result.begin(),
std::greater<int>());
// result = {8, 7, 6, 5, 4, 3, 2, 1}
return 0;
}
std::accumulate
std::accumulate 定义于 <numeric>，对序列元素进行累积运算。2
第三个参数 init 既是累积的初始值，也决定了返回类型——写 0 返回 int，写 0.0 返回 double，写 std::string("") 返回字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <functional>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
// 求和（默认 std::plus）
auto sum = std::accumulate(nums.begin(), nums.end(), 0);
std::cout << "sum: " << sum << std::endl; // 输出: 15
// 求乘积（传入 std::multiplies）
auto prod = std::accumulate(nums.begin(), nums.end(), 1,
std::multiplies<int>());
std::cout << "product: " << prod << std::endl; // 输出: 120
// 字符串拼接（用 lambda 将数字转字符串后拼接）
auto s = std::accumulate(nums.begin(), nums.end(), std::string(""),
[](std::string acc, int x) { return acc + std::to_string(x); });
std::cout << s << std::endl; // 输出: 12345
return 0;
}
参考文章56789
本文由作者按照
CC BY 4.0
进行授权