第10章：泛型算法（Generic Algorithms）
一、导读
1.1 本章学习目标
第10章介绍C++标准库的泛型算法。本章核心目标：
- 掌握常用算法：查找、排序、变换、计数
- 理解迭代器在算法中的作用：算法如何通过迭代器操作容器
- 学会使用lambda与算法配合：自定义算法行为
- 了解算法的性能考虑：时间复杂度
- 掌握数值算法：accumulate、inner_product
1.2 为什么本章如此重要
泛型算法是STL的核心组成部分。熟练使用这些算法能大大提高编程效率，避免重复造轮子。算法与迭代器的组合提供了强大的数据处理能力。
1.3 核心问题引导
为什么算法使用迭代器而不是直接操作容器？
find和find_if有什么区别？
sort和stable_sort有什么区别？
lambda表达式在算法中如何使用？
二、核心概念详解
10.1 查找算法
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
// find
auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) {
std::cout << "Found 5 at position " << (it - v.begin()) << std::endl;
}
// find_if
auto even = std::find_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
});
if (even != v.end()) {
std::cout << "First even: " << *even << std::endl;
}
// count
std::vector<int> nums = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
int cnt = std::count(nums.begin(), nums.end(), 3);
std::cout << "Count of 3: " << cnt << std::endl;
// count_if
int even_count = std::count_if(nums.begin(), nums.end(), [](int x) {
return x % 2 == 0;
});
std::cout << "Even count: " << even_count << std::endl;
// binary_search（需要已排序）
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 5);
std::cout << "Binary search 5: " << found << std::endl;
return 0;
}10.2 排序算法
cpp
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
// sort（不稳定排序）
std::sort(v.begin(), v.end());
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
// 降序
std::sort(v.begin(), v.end(), std::greater<int>());
// 自定义排序
std::sort(v.begin(), v.end(), [](int a, int b) {
return a > b;
});
// stable_sort（稳定排序）
std::stable_sort(v.begin(), v.end());
// partial_sort（部分排序）
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// nth_element（第n小的元素）
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
std::cout << "Median: " << v[v.size()/2] << std::endl;
// is_sorted
bool sorted = std::is_sorted(v.begin(), v.end());
std::cout << "Is sorted: " << sorted << std::endl;
return 0;
}10.3 变换算法
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
// transform
std::vector<int> doubled(v.size());
std::transform(v.begin(), v.end(), doubled.begin(), [](int x) {
return x * 2;
});
for (int x : doubled) std::cout << x << " ";
std::cout << std::endl;
// 原地变换
std::transform(v.begin(), v.end(), v.begin(), [](int x) {
return x * x;
});
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
// replace
std::replace(v.begin(), v.end(), 4, 40);
// fill
std::fill(v.begin(), v.end(), 0);
// generate
int n = 0;
std::generate(v.begin(), v.end(), [&n]() { return n++; });
// remove（不删除元素，只是移动）
v = {1, 2, 3, 2, 4, 2, 5};
auto new_end = std::remove(v.begin(), v.end(), 2);
v.erase(new_end, v.end()); // 真正删除
// unique（删除相邻重复）
std::sort(v.begin(), v.end());
new_end = std::unique(v.begin(), v.end());
v.erase(new_end, v.end());
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
return 0;
}10.4 数值算法
cpp
#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);
std::cout << "Sum: " << sum << std::endl;
// accumulate with custom operation
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());
std::cout << "Product: " << product << std::endl;
// inner_product
std::vector<int> w = {2, 3, 4, 5, 6};
int dot = std::inner_product(v.begin(), v.end(), w.begin(), 0);
std::cout << "Dot product: " << dot << std::endl;
// partial_sum
std::vector<int> partial(v.size());
std::partial_sum(v.begin(), v.end(), partial.begin());
for (int x : partial) std::cout << x << " ";
std::cout << std::endl;
// adjacent_difference
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;
return 0;
}三、实战案例
3.1 数据处理管道
cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
struct Student {
std::string name;
int score;
};
int main() {
std::vector<Student> students = {
{"Alice", 90}, {"Bob", 85}, {"Charlie", 92},
{"David", 78}, {"Eve", 88}, {"Frank", 95}
};
// 找出及格的学生
std::vector<Student> passed;
std::copy_if(students.begin(), students.end(),
std::back_inserter(passed),
[](const Student &s) { return s.score >= 80; });
// 按分数排序
std::sort(passed.begin(), passed.end(),
[](const Student &a, const Student &b) {
return a.score > b.score;
});
// 计算平均分
double avg = std::accumulate(passed.begin(), passed.end(), 0.0,
[](double sum, const Student &s) {
return sum + s.score;
}) / passed.size();
std::cout << "Passed students (sorted):" << std::endl;
for (const auto &s : passed) {
std::cout << s.name << ": " << s.score << std::endl;
}
std::cout << "Average: " << avg << std::endl;
return 0;
}四、本章小结
第10章介绍了C++泛型算法：查找（find、binary_search）、排序（sort、stable_sort）、变换（transform、replace）、数值（accumulate、inner_product）。算法通过迭代器操作容器，与lambda配合非常强大。
五、思考与练习
思考题
为什么算法不直接操作容器，而是使用迭代器？
remove算法为什么不直接删除元素？
sort和stable_sort有什么区别？什么时候需要稳定排序？
accumulate的初始值有什么作用？
编程练习
使用算法实现一个简单的文本搜索引擎。
使用transform和accumulate计算加权平均。
实现一个自定义排序算法，按多个条件排序。