1. C++标准库算法概览
C++标准库提供了丰富的算法,主要定义在
- 非修改序列算法:不改变容器内容,如find、count等
- 修改序列算法:会改变容器内容,如copy、replace等
- 排序和相关算法:如sort、binary_search等
- 数值算法:如accumulate、inner_product等
这些算法大多以迭代器作为参数,因此可以适用于各种容器,具有很高的通用性。理解这些算法的使用场景和实现原理,是每个C++开发者必备的技能。
2. 非修改序列算法详解
2.1 查找算法
2.1.1 find和find_if
find算法用于在指定范围内查找特定值:
cpp复制vector<int> nums = {1, 3, 5, 7, 9};
auto it = find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
cout << "Found: " << *it << endl;
}
find_if则是根据谓词条件查找:
cpp复制auto it = find_if(nums.begin(), nums.end(), [](int x){
return x > 6;
});
注意:find_if的谓词函数应该尽可能简单高效,因为它会被频繁调用。复杂的谓词会显著影响查找性能。
2.1.2 find_end和search
find_end用于查找子序列最后一次出现的位置:
cpp复制vector<int> main = {1,2,3,4,1,2,3};
vector<int> sub = {1,2};
auto it = find_end(main.begin(), main.end(), sub.begin(), sub.end());
search则是查找子序列第一次出现的位置,用法与find_end类似。
2.2 计数算法
2.2.1 count和count_if
count统计特定值出现的次数:
cpp复制vector<int> vec = {1, 2, 3, 2, 4, 2};
int cnt = count(vec.begin(), vec.end(), 2); // 3
count_if则统计满足条件的元素个数:
cpp复制int even_cnt = count_if(vec.begin(), vec.end(), [](int x){
return x % 2 == 0;
});
2.3 遍历算法for_each
for_each对范围内的每个元素应用一个函数:
cpp复制vector<int> vec = {1, 2, 3, 4, 5};
for_each(vec.begin(), vec.end(), [](int& x){
x *= 2;
});
提示:C++17引入了执行策略参数,可以指定并行执行:
cpp复制for_each(execution::par, vec.begin(), vec.end(), [](int& x){...});
2.4 比较算法
2.4.1 equal和mismatch
equal判断两个范围是否相等:
cpp复制vector<int> a = {1,2,3};
vector<int> b = {1,2,3};
bool same = equal(a.begin(), a.end(), b.begin());
mismatch返回第一个不匹配的位置:
cpp复制auto p = mismatch(a.begin(), a.end(), b.begin());
if(p.first != a.end()){
cout << "Mismatch at " << *p.first << " vs " << *p.second;
}
2.4.2 all_of/any_of/none_of
这些算法检查范围内的元素是否满足特定条件:
cpp复制vector<int> vec = {2,4,6,8};
bool allEven = all_of(vec.begin(), vec.end(), [](int x){
return x % 2 == 0;
});
3. 修改序列算法详解
3.1 复制算法
3.1.1 copy和copy_if
copy算法将源范围复制到目标位置:
cpp复制vector<int> src = {1,2,3,4,5};
vector<int> dest(5);
copy(src.begin(), src.end(), dest.begin());
copy_if只复制满足条件的元素:
cpp复制vector<int> evens;
copy_if(src.begin(), src.end(), back_inserter(evens), [](int x){
return x % 2 == 0;
});
重要提示:使用back_inserter可以自动处理目标容器空间不足的问题,它会调用push_back来添加元素。
3.2 变换算法transform
transform对范围内的元素进行转换:
cpp复制vector<int> nums = {1,2,3};
vector<int> squares(3);
transform(nums.begin(), nums.end(), squares.begin(), [](int x){
return x * x;
});
双范围版本:
cpp复制vector<int> a = {1,2,3};
vector<int> b = {4,5,6};
vector<int> sum(3);
transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y){
return x + y;
});
3.3 替换算法
3.3.1 replace和replace_if
replace替换特定值:
cpp复制vector<int> nums = {1,2,3,2,5};
replace(nums.begin(), nums.end(), 2, 20);
replace_if根据条件替换:
cpp复制replace_if(nums.begin(), nums.end(), [](int x){
return x > 10;
}, 0);
3.3.2 replace_copy
replace_copy在复制时替换:
cpp复制vector<int> res;
replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300);
3.4 删除算法
3.4.1 remove和remove_if
remove"逻辑"删除元素:
cpp复制vector<int> nums = {1,2,3,2,4};
auto new_end = remove(nums.begin(), nums.end(), 2);
nums.erase(new_end, nums.end());
remove_if根据条件删除:
cpp复制nums.erase(remove_if(nums.begin(), nums.end(), [](int x){
return x % 2 == 0;
}), nums.end());
关键理解:remove算法实际上并不删除元素,而是把要保留的元素前移,返回新的"逻辑"终点。真正的删除需要配合erase完成。
3.4.2 unique
unique删除连续的重复元素:
cpp复制vector<int> vec = {1,1,2,2,3,3,3,4,5};
auto last = unique(vec.begin(), vec.end());
vec.erase(last, vec.end());
注意:unique只处理相邻的重复元素。如果需要删除所有重复元素,应先排序。
3.5 其他修改算法
3.5.1 reverse
reverse反转序列:
cpp复制vector<int> vec = {1,2,3,4,5};
reverse(vec.begin(), vec.end());
3.5.2 rotate
rotate旋转序列:
cpp复制vector<int> vec = {1,2,3,4,5};
rotate(vec.begin(), vec.begin()+2, vec.end());
3.5.3 shuffle
shuffle随机打乱序列:
cpp复制random_device rd;
mt19937 g(rd());
shuffle(vec.begin(), vec.end(), g);
4. 排序和相关算法
4.1 排序算法
4.1.1 sort
sort进行快速排序:
cpp复制vector<int> vec = {5,3,1,4,2};
sort(vec.begin(), vec.end()); // 升序
sort(vec.begin(), vec.end(), greater<int>()); // 降序
4.1.2 stable_sort
stable_sort保持相等元素的相对顺序:
cpp复制vector<pair<int,int>> vec = {{1,2},{2,1},{1,1},{2,2}};
stable_sort(vec.begin(), vec.end(), [](auto& a, auto& b){
return a.first < b.first;
});
4.1.3 partial_sort
partial_sort部分排序:
cpp复制vector<int> vec = {5,3,1,4,2,6};
partial_sort(vec.begin(), vec.begin()+3, vec.end());
4.2 选择算法nth_element
nth_element重新排列使第n个元素就位:
cpp复制vector<int> vec = {5,3,1,4,2,6};
nth_element(vec.begin(), vec.begin()+2, vec.end());
4.3 二分查找算法
4.3.1 binary_search
binary_search检查元素是否存在:
cpp复制vector<int> sorted = {1,3,3,5,7};
bool exists = binary_search(sorted.begin(), sorted.end(), 3);
4.3.2 lower_bound和upper_bound
lower_bound返回第一个不小于给定值的迭代器:
cpp复制auto lb = lower_bound(sorted.begin(), sorted.end(), 3);
upper_bound返回第一个大于给定值的迭代器:
cpp复制auto ub = upper_bound(sorted.begin(), sorted.end(), 3);
4.4 合并算法merge
merge合并两个已排序的范围:
cpp复制vector<int> a = {1,3,5};
vector<int> b = {2,4,6};
vector<int> merged(a.size() + b.size());
merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());
5. 堆算法
5.1 make_heap
make_heap将范围转换为堆:
cpp复制vector<int> vec = {4,1,3,2,5};
make_heap(vec.begin(), vec.end());
5.2 push_heap和pop_heap
push_heap向堆中添加元素:
cpp复制vec.push_back(6);
push_heap(vec.begin(), vec.end());
pop_heap从堆中移除最大元素:
cpp复制pop_heap(vec.begin(), vec.end());
int max_val = vec.back();
vec.pop_back();
5.3 sort_heap
sort_heap将堆转换为有序序列:
cpp复制sort_heap(vec.begin(), vec.end());
6. 数值算法
6.1 accumulate
accumulate计算累加和或自定义操作:
cpp复制vector<int> vec = {1,2,3,4,5};
int sum = accumulate(vec.begin(), vec.end(), 0);
int product = accumulate(vec.begin(), vec.end(), 1, multiplies<int>());
6.2 inner_product
inner_product计算内积:
cpp复制vector<int> a = {1,2,3};
vector<int> b = {4,5,6};
int dot = inner_product(a.begin(), a.end(), b.begin(), 0);
6.3 iota
iota用连续值填充范围:
cpp复制vector<int> vec(5);
iota(vec.begin(), vec.end(), 10); // 10,11,12,13,14
6.4 partial_sum
partial_sum计算部分和:
cpp复制vector<int> src = {1,2,3,4,5};
vector<int> dst(src.size());
partial_sum(src.begin(), src.end(), dst.begin());
6.5 adjacent_difference
adjacent_difference计算相邻差值:
cpp复制vector<int> src = {1,2,3,4,5};
vector<int> dst(src.size());
adjacent_difference(src.begin(), src.end(), dst.begin());
7. 其他实用算法
7.1 generate和generate_n
generate用生成函数填充范围:
cpp复制vector<int> vec(5);
int n = 0;
generate(vec.begin(), vec.end(), [&n](){ return n++; });
generate_n填充前n个元素:
cpp复制generate_n(vec.begin(), 3, [&n](){ return n++; });
7.2 includes
includes检查一个排序范围是否包含另一个:
cpp复制vector<int> vec1 = {1,2,3,4,5};
vector<int> vec2 = {2,4};
bool contains = includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
7.3 集合算法
7.3.1 set_union
set_union计算并集:
cpp复制vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {3,4,5,6,7};
vector<int> result;
set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
7.3.2 set_intersection
set_intersection计算交集:
cpp复制result.clear();
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
7.3.3 set_difference
set_difference计算差集:
cpp复制result.clear();
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
7.3.4 set_symmetric_difference
set_symmetric_difference计算对称差集:
cpp复制result.clear();
set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
8. 算法使用经验与技巧
8.1 算法选择指南
-
查找操作:
- 无序范围:find/find_if
- 有序范围:binary_search/lower_bound
- 子序列查找:search/find_end
-
排序需求:
- 普通排序:sort
- 稳定排序:stable_sort
- 部分排序:partial_sort/nth_element
-
修改操作:
- 复制:copy/copy_if
- 替换:replace/replace_if
- 删除:remove/remove_if + erase
8.2 性能优化建议
- 避免在循环中重复调用算法,尽量一次处理
- 对大型容器,考虑使用并行算法(execution::par)
- 预分配足够空间避免多次重新分配
- 对频繁查找的操作,先排序再使用二分查找
8.3 常见错误与解决方法
-
迭代器失效:
- 在修改容器后继续使用旧的迭代器
- 解决方法:每次修改后重新获取迭代器
-
未排序范围使用二分查找:
- 导致未定义行为
- 解决方法:确保范围已排序
-
未检查算法返回值:
- 如find返回end表示未找到
- 解决方法:总是检查返回值
-
目标空间不足:
- copy等算法不检查目标空间
- 解决方法:使用back_inserter或提前reserve
8.4 自定义比较函数
许多算法允许自定义比较函数,使用时需注意:
- 严格弱序:比较函数必须满足严格弱序关系
- 无副作用:比较函数不应修改元素
- 性能考虑:简单比较函数有利于优化
cpp复制struct Person {
string name;
int age;
};
vector<Person> people;
sort(people.begin(), people.end(), [](const Person& a, const Person& b){
return a.age < b.age;
});
9. C++20新增算法
C++20引入了一些新算法,值得关注:
9.1 ranges版本算法
更安全、更易用的范围版本:
cpp复制vector<int> vec = {1,2,3,4,5};
auto result = ranges::find(vec, 3);
9.2 shift_left和shift_right
移动元素范围:
cpp复制vector<int> v = {1,2,3,4,5};
shift_left(v.begin(), v.end(), 2);
9.3 starts_with和ends_with
检查序列前缀或后缀:
cpp复制vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {1,2,3};
bool starts = starts_with(v1.begin(), v1.end(), v2.begin(), v2.end());
9.4 contains
检查范围是否包含元素:
cpp复制vector<int> v = {1,2,3,4,5};
bool has3 = ranges::contains(v, 3);
10. 实际应用案例
10.1 统计单词频率
cpp复制string text = "hello world hello cpp world algorithm";
istringstream iss(text);
vector<string> words(istream_iterator<string>{iss}, {});
sort(words.begin(), words.end());
vector<pair<string, int>> counts;
for(auto it = words.begin(); it != words.end();) {
auto end = find_if_not(it, words.end(), [&](const string& s){
return s == *it;
});
counts.emplace_back(*it, distance(it, end));
it = end;
}
sort(counts.begin(), counts.end(), [](auto& a, auto& b){
return a.second > b.second;
});
10.2 合并多个排序范围
cpp复制vector<vector<int>> sorted_vecs = {{1,4,7}, {2,5,8}, {3,6,9}};
vector<int> result;
for(auto& vec : sorted_vecs) {
vector<int> temp;
merge(result.begin(), result.end(), vec.begin(), vec.end(), back_inserter(temp));
result = move(temp);
}
10.3 高效去重
cpp复制vector<int> vec = {1,2,2,3,3,3,4,5,5};
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
10.4 查找最大N个元素
cpp复制vector<int> vec = {5,3,1,4,2,6};
nth_element(vec.begin(), vec.begin()+3, vec.end());
vector<int> top3(vec.begin(), vec.begin()+3);
sort(top3.begin(), top3.end(), greater<int>());
11. 算法性能分析
了解算法的复杂度有助于选择合适的算法:
-
O(1):
- min/max
- 不修改的单个元素访问
-
O(log n):
- binary_search
- lower_bound/upper_bound
-
O(n):
- find/count
- copy/replace
- accumulate
-
O(n log n):
- sort/stable_sort
- set_union/intersection
-
O(n²):
- 某些最坏情况下的排序算法
实际性能还受以下因素影响:
- 数据局部性
- 分支预测
- 内存分配
- 并行化可能性
12. 自定义算法实现
理解标准算法后,我们可以实现自己的通用算法:
12.1 实现find_if
cpp复制template<typename InputIt, typename UnaryPredicate>
InputIt my_find_if(InputIt first, InputIt last, UnaryPredicate p) {
for(; first != last; ++first) {
if(p(*first)) {
return first;
}
}
return last;
}
12.2 实现transform
cpp复制template<typename InputIt, typename OutputIt, typename UnaryOp>
OutputIt my_transform(InputIt first, InputIt last, OutputIt d_first, UnaryOp op) {
for(; first != last; ++first, ++d_first) {
*d_first = op(*first);
}
return d_first;
}
12.3 实现accumulate
cpp复制template<typename InputIt, typename T, typename BinaryOp>
T my_accumulate(InputIt first, InputIt last, T init, BinaryOp op) {
for(; first != last; ++first) {
init = op(init, *first);
}
return init;
}
13. 算法与并行编程
现代C++支持并行算法执行:
13.1 并行执行策略
- seq:顺序执行(默认)
- par:并行执行
- par_unseq:并行+向量化
13.2 并行算法示例
cpp复制vector<int> vec(1000000);
iota(vec.begin(), vec.end(), 0);
// 并行排序
sort(execution::par, vec.begin(), vec.end());
// 并行transform
vector<int> result(vec.size());
transform(execution::par, vec.begin(), vec.end(), result.begin(), [](int x){
return x * x;
});
// 并行reduce
int sum = reduce(execution::par, vec.begin(), vec.end());
13.3 并行算法注意事项
- 操作必须线程安全
- 避免数据竞争
- 考虑负载均衡
- 小任务可能不适合并行
14. 算法与容器选择
不同容器适合不同的算法操作:
-
vector/array:
- 随机访问快
- 适合排序、查找等密集操作
-
list/forward_list:
- 插入删除快
- 适合merge、splice等操作
- 不支持随机访问算法
-
deque:
- 首尾操作快
- 适合两端操作
-
set/map:
- 自动排序
- 已有高效的find操作
选择容器时应考虑:
- 主要操作类型
- 数据规模
- 内存限制
- 线程安全需求
15. 现代C++算法技巧
15.1 使用std::invoke
C++17引入invoke,可以统一调用各种可调用对象:
cpp复制template<typename InputIt, typename Callable>
void my_for_each(InputIt first, InputIt last, Callable op) {
for(; first != last; ++first) {
std::invoke(op, *first);
}
}
15.2 结构化绑定与算法
结合结构化绑定处理复杂数据:
cpp复制vector<pair<int, string>> data = {{1,"a"}, {2,"b"}, {3,"c"}};
for_each(data.begin(), data.end(), [](const auto& p) {
auto [num, str] = p;
cout << num << ":" << str << endl;
});
15.3 使用std::optional处理可能失败的操作
cpp复制optional<int> find_value(const vector<int>& v, int value) {
auto it = find(v.begin(), v.end(), value);
if(it != v.end()) {
return *it;
}
return nullopt;
}
16. 算法测试与调试
16.1 单元测试算法
使用测试框架验证算法正确性:
cpp复制TEST(AlgorithmTest, FindTest) {
vector<int> v = {1,3,5,7,9};
auto it = find(v.begin(), v.end(), 5);
ASSERT_NE(it, v.end());
EXPECT_EQ(*it, 5);
it = find(v.begin(), v.end(), 2);
EXPECT_EQ(it, v.end());
}
16.2 调试技巧
-
使用断言检查前置条件:
cpp复制void my_algorithm(auto first, auto last) { assert(is_sorted(first, last)); // ... } -
打印中间结果:
cpp复制for_each(v.begin(), v.end(), [](int x){ cout << x << " "; }); -
使用调试器检查迭代器位置
16.3 性能分析
使用profiler工具分析算法热点:
- 时间消耗
- 内存使用
- 缓存命中率
- 并行效率
17. 跨语言算法比较
了解其他语言的算法实现有助于深入理解:
-
Python:
- 内置sorted、min/max等
- list comprehension类似transform
- 通常比C++慢但更简洁
-
Java:
- Collections类的静态方法
- Stream API类似C++ ranges
- 受JVM影响性能特征不同
-
Rust:
- 迭代器方法链
- 所有权系统影响算法设计
- 零成本抽象类似C++
关键差异:
- 内存模型
- 错误处理
- 泛型实现
- 并发支持
18. 算法最佳实践总结
- 优先使用标准算法而非手写循环
- 理解算法复杂度及其适用场景
- 注意迭代器有效性和范围有效性
- 为自定义类型提供合适的比较操作
- 考虑并行化可能性和数据竞争
- 编写清晰、可维护的谓词和操作函数
- 对性能关键路径进行测量而非猜测
- 保持算法代码的可测试性
- 适时使用现代C++特性简化代码
- 深入理解标准库实现而非仅会使用
19. 常见问题解答
19.1 为什么有些算法需要已排序的范围?
二分查找和相关算法依赖有序性来实现O(log n)的复杂度。如果范围未排序,这些算法无法保证正确工作。
19.2 remove算法为什么不直接删除元素?
remove被设计为通用算法,不知道底层容器的具体实现。它通过移动元素来"逻辑"删除,而实际删除应由容器自己的erase方法完成。
19.3 sort和stable_sort如何选择?
如果需要保持相等元素的相对顺序,使用stable_sort。否则,sort通常更快且使用更少内存。
19.4 如何高效合并多个已排序的容器?
可以连续使用merge算法,或者使用优先队列(priority queue)进行多路归并。
19.5 为什么我的自定义比较函数导致排序崩溃?
确保比较函数满足严格弱序关系:
- a < a永远为false
- 如果a < b为true,则b < a必须为false
- 如果a < b和b < c为true,则a < c必须为true
20. 进阶学习资源
-
书籍:
- 《C++标准库》(The C++ Standard Library)
- 《Effective STL》
- 《C++ Templates: The Complete Guide》
-
在线资源:
- cppreference.com
- C++标准文档
- 各种编译器对STL的实现代码
-
视频课程:
- C++标准库算法详解
- 现代C++编程技巧
- 高性能STL应用
-
开源项目:
- LLVM的libc++实现
- GNU的libstdc++实现
- Boost算法库