概述
继上一篇的排序与查找算法之后，本文将介绍 STL algorithm 中同样重要的数值计算和变换类算法。这些工具在日常开发中使用频率极高，熟练掌握能显著减少手写循环的代码量。
使用这些算法需要 #include <numeric>（数值算法）和 #include <algorithm>（变换算法）。
accumulate —— 累加
std::accumulate 对区间内的元素依次执行累加操作。它位于 <numeric> 头文件中。
基本累加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
int sum = std::accumulate(v.begin(), v.end(), 0);
std::cout << "Sum: " << sum << std::endl;
long long bigSum = std::accumulate(v.begin(), v.end(), 0LL);
sum = std::accumulate(v.begin(), v.end(), 100);
std::cout << "Sum with init 100: " << sum << std::endl;
return 0;
}
|
自定义操作
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 <numeric>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
std::cout << "Product: " << product << std::endl;
std::vector<std::string> words = {"Hello", " ", "World", "!"};
std::string result = std::accumulate(words.begin(), words.end(), std::string());
std::cout << "Concat: " << result << std::endl;
int maxVal = std::accumulate(v.begin(), v.end(), v[0], [](int a, int b) {
return std::max(a, b);
});
std::cout << "Max: " << maxVal << std::endl;
return 0;
}
|
⚠️ 初始值的陷阱
1
2
3
4
5
6
7
8
| std::vector<int> v = {1, 2, 3};
long long sum = std::accumulate(v.begin(), v.end(), 0LL);
double avg = std::accumulate(v.begin(), v.end(), 0.0) / v.size();
|
accumulate 的返回值类型由初始值决定，而不是元素类型。这是非常常见的坑。
partial_sum —— 前缀和
std::partial_sum 计算前缀和序列。
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
| #include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());
std::partial_sum(v.begin(), v.end(), result.begin());
for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;
std::partial_sum(v.begin(), v.end(), result.begin(), std::multiplies<int>());
for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;
std::vector<int> base(5, 2);
std::partial_sum(base.begin(), base.end(), result.begin(), [](int a, int b) {
return a * b;
});
for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
实际应用：区间和查询
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 <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
std::vector<int> prefix(arr.size() + 1, 0);
std::partial_sum(arr.begin(), arr.end(), prefix.begin() + 1);
auto rangeSum = [&](int l, int r) {
return prefix[r + 1] - prefix[l];
};
std::cout << "Sum [0,2]: " << rangeSum(0, 2) << std::endl;
std::cout << "Sum [2,5]: " << rangeSum(2, 5) << std::endl;
std::cout << "Sum [0,7]: " << rangeSum(0, 7) << std::endl;
return 0;
}
|
adjacent_difference —— 相邻差分
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
| #include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> v = {1, 3, 6, 10, 15};
std::vector<int> diff(v.size());
std::adjacent_difference(v.begin(), v.end(), diff.begin());
for (int x : diff) {
std::cout << x << " ";
}
std::cout << std::endl;
std::vector<int> v2 = {1, 2, 6, 24, 120};
std::adjacent_difference(v2.begin(), v2.end(), diff.begin(),
std::divides<int>());
for (int x : diff) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
next_permutation —— 全排列
std::next_permutation 将当前排列变为字典序的下一个排列。如果已经是最后一个排列，则变为第一个排列并返回 false。
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 <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3};
do {
for (int x : v) {
std::cout << x << " ";
}
std::cout << std::endl;
} while (std::next_permutation(v.begin(), v.end()));
return 0;
}
|
⚠️ 使用前必须排序
1
2
3
4
5
6
7
8
9
10
| std::vector<int> v = {3, 1, 2};
std::sort(v.begin(), v.end());
do {
} while (std::next_permutation(v.begin(), v.end()));
|
prev_permutation —— 上一个排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v = {3, 2, 1};
do {
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
} while (std::prev_permutation(v.begin(), v.end()));
return 0;
}
|
std::transform 对每个元素应用一个函数，将结果写入目标位置。
一元变换
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
| #include <iostream>
#include <algorithm>
#include <vector>
#include <cctype>
#include <string>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());
std::transform(v.begin(), v.end(), result.begin(), [](int x) {
return x * x;
});
for (int x : result) std::cout << x << " ";
std::cout << std::endl;
std::string s = "hello world";
std::transform(s.begin(), s.end(), s.begin(), ::toupper);
std::cout << s << std::endl;
std::vector<int> v2 = {1, -2, 3, -4, 5};
std::transform(v2.begin(), v2.end(), v2.begin(), [](int x) {
return x > 0 ? x : -x;
});
for (int x : v2) std::cout << x << " ";
std::cout << std::endl;
return 0;
}
|
二元变换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {10, 20, 30, 40, 50};
std::vector<int> result(a.size());
std::transform(a.begin(), a.end(), b.begin(), result.begin(),
[](int x, int y) { return x + y; });
for (int x : result) std::cout << x << " ";
std::cout << std::endl;
std::transform(a.begin(), a.end(), b.begin(), result.begin(),
[](int x, int y) { return std::max(x, y); });
for (int x : result) std::cout << x << " ";
std::cout << std::endl;
return 0;
}
|
fill 与 fill_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
25
26
27
28
29
30
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v(10);
std::fill(v.begin(), v.end(), 42);
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
std::fill(v.begin(), v.begin() + 5, 99);
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
std::fill_n(v.begin(), 3, 0);
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
std::vector<int> v2;
v2.resize(5);
std::fill_n(v2.begin(), 5, 1);
return 0;
}
|
generate 与 generate_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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <iostream>
#include <algorithm>
#include <vector>
#include <random>
int main() {
std::vector<int> v(10);
std::mt19937 rng(42);
std::generate(v.begin(), v.end(), [&rng]() {
return rng() % 100;
});
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
int counter = 1;
std::generate(v.begin(), v.end(), [&counter]() {
return counter++;
});
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
counter = 0;
std::generate_n(v.begin(), 5, [&counter]() {
counter += 2;
return counter;
});
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
int a = 0, b = 1;
std::generate(v.begin(), v.end(), [&a, &b]() {
int result = a;
int next = a + b;
a = b;
b = next;
return result;
});
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
return 0;
}
|
iota —— 递增填充
std::iota（希腊字母 ι，读作 iota）以递增的方式填充序列，从给定初始值开始。
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 <numeric>
#include <vector>
int main() {
std::vector<int> v(10);
std::iota(v.begin(), v.end(), 0);
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
std::iota(v.begin(), v.end(), 1);
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
std::vector<char> letters(26);
std::iota(letters.begin(), letters.end(), 'a');
for (char c : letters) std::cout << c;
std::cout << std::endl;
return 0;
}
|
实际应用：生成索引
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 <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> data = {30, 10, 20, 50, 40};
int n = data.size();
std::vector<int> idx(n);
std::iota(idx.begin(), idx.end(), 0);
std::sort(idx.begin(), idx.end(), [&](int i, int j) {
return data[i] < data[j];
});
std::cout << "Sorted by index: ";
for (int i : idx) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
return 0;
}
|
merge —— 合并有序序列
std::merge 将两个已排序的序列合并为一个新的有序序列。
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
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> a = {1, 3, 5, 7};
std::vector<int> b = {2, 4, 6, 8};
std::vector<int> result(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());
for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;
std::vector<int> c = {1, 2, 4, 5};
std::vector<int> d = {2, 3, 5, 6};
std::vector<int> result2(c.size() + d.size());
std::merge(c.begin(), c.end(), d.begin(), d.end(), result2.begin());
for (int x : result2) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
merge 降序序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> a = {7, 5, 3, 1};
std::vector<int> b = {8, 6, 4, 2};
std::vector<int> result(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin(),
std::greater<int>());
for (int x : result) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
inplace_merge —— 原地合并
当两个有序子序列在同一个容器中相邻时，可以用 inplace_merge：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v = {1, 3, 5, 2, 4, 6};
std::inplace_merge(v.begin(), v.begin() + 3, v.end());
for (int x : v) {
std::cout << x << " ";
}
std::cout << std::endl;
return 0;
}
|
更多实用算法速览
remove / remove_if —— 移除元素（不实际删除）
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 <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 2, 6, 2, 7};
auto newEnd = std::remove(v.begin(), v.end(), 2);
v.erase(newEnd, v.end());
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
auto ne = std::remove_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
});
v.erase(ne, v.end());
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
return 0;
}
|
replace / replace_if —— 替换元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
std::replace(v.begin(), v.end(), 2, 99);
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
v = {1, 2, 3, 4, 5, 6, 7};
std::replace_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
}, 0);
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
return 0;
}
|
for_each —— 遍历操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::for_each(v.begin(), v.end(), [](int& x) {
x *= 2;
});
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
int index = 0;
std::for_each(v.begin(), v.end(), [&index](int x) {
std::cout << "[" << index++ << "] = " << x << std::endl;
});
return 0;
}
|
常见陷阱总结
1. accumulate 初始值类型决定返回类型
1
2
3
| std::vector<double> v = {1.5, 2.5, 3.5};
|
2. remove 不实际删除元素
和 unique 一样，remove 和 remove_if 只是把不需要的元素移到后面，必须搭配 erase：
1
2
3
4
5
|
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
|
3. next_permutation 需要排序后的起点
1
2
3
4
5
6
| std::vector<int> v = {2, 1, 3};
std::sort(v.begin(), v.end());
do { } while (std::next_permutation(v.begin(), v.end()));
|
总结
本系列两篇文章覆盖了 STL algorithm 中最核心的算法。记住一个原则：优先使用标准库算法而不是手写循环——这不仅代码更简洁，而且经过充分优化和测试。当你在写一个 for 循环来对元素做变换、查找或计算时，先想想 <algorithm> 里有没有现成的。
| 算法 |
用途 |
头文件 |
accumulate |
累加/累乘 |
<numeric> |
partial_sum |
前缀和 |
<numeric> |
iota |
递增填充 |
<numeric> |
adjacent_difference |
差分 |
<numeric> |
transform |
元素变换 |
<algorithm> |
fill/fill_n |
填充值 |
<algorithm> |
generate/generate_n |
生成值 |
<algorithm> |
next_permutation |
下一排列 |
<algorithm> |
merge |
合并有序序列 |
<algorithm> |
remove/remove_if |
移除元素 |
<algorithm> |
replace/replace_if |
替换元素 |
<algorithm> |
for_each |
遍历操作 |
<algorithm> |
