1. C++标准库算法概述
作为C++开发者,我们每天都在与各种数据结构和算法打交道。STL(Standard Template Library)提供了一套强大而高效的算法库,可以极大地提升我们的开发效率。这些算法主要定义在<algorithm>和<numeric>头文件中,涵盖了从简单的查找、排序到复杂的数值计算等各种场景。
STL算法的一个显著特点是它们都是通用的,不依赖于特定的容器类型。这意味着同一个算法可以应用于vector、list、array等多种容器,只要提供了适当的迭代器。这种设计体现了C++的泛型编程思想,让我们可以写出更灵活、可复用的代码。
2. 非修改序列算法详解
2.1 查找算法
查找算法是日常开发中最常用的算法之一。STL提供了多种查找方式,适用于不同场景:
cpp复制vector<int> nums = {1, 3, 5, 7, 9};
// 基本查找:find
auto it = find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
cout << "Found: " << *it << endl;
}
// 条件查找:find_if
auto it2 = find_if(nums.begin(), nums.end(), [](int x) {
return x > 6;
});
// 子序列查找:find_end
vector<int> sub = {3, 5};
auto it3 = find_end(nums.begin(), nums.end(), sub.begin(), sub.end());
注意:对于已排序的序列,应该优先使用binary_search等更高效的查找算法,时间复杂度可以从O(n)降到O(log n)。
2.2 计数算法
计数算法可以帮助我们快速统计满足特定条件的元素数量:
cpp复制vector<int> vec = {1, 2, 3, 2, 4, 2};
// 统计特定值出现次数
int cnt = count(vec.begin(), vec.end(), 2); // 结果为3
// 统计满足条件的元素数量
int even_cnt = count_if(vec.begin(), vec.end(), [](int x) {
return x % 2 == 0;
}); // 偶数个数,结果为4
2.3 遍历算法
for_each算法提供了一种简洁的方式来遍历容器并对每个元素执行操作:
cpp复制vector<int> vec = {1, 2, 3, 4, 5};
// 使用lambda表达式处理每个元素
for_each(vec.begin(), vec.end(), [](int& x) {
x *= 2;
});
// 现在vec变为{2, 4, 6, 8, 10}
2.4 比较算法
equal和mismatch算法用于比较两个序列:
cpp复制vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 4};
// 检查两个序列是否相等
bool is_equal = equal(a.begin(), a.end(), b.begin()); // false
// 查找第一个不匹配的元素
auto mis = mismatch(a.begin(), a.end(), b.begin());
if (mis.first != a.end()) {
cout << "First mismatch: " << *mis.first << " vs " << *mis.second << endl;
}
2.5 条件检查算法
all_of、any_of和none_of可以方便地检查容器元素是否满足特定条件:
cpp复制vector<int> vec = {2, 4, 6, 8};
// 检查是否所有元素都是偶数
bool all_even = all_of(vec.begin(), vec.end(), [](int x) {
return x % 2 == 0;
}); // true
// 检查是否存在奇数元素
bool any_odd = any_of(vec.begin(), vec.end(), [](int x) {
return x % 2 != 0;
}); // false
// 检查是否没有负数
bool none_negative = none_of(vec.begin(), vec.end(), [](int x) {
return x < 0;
}); // true
3. 修改序列算法详解
3.1 复制算法
复制算法是处理数据时最基础的操作之一:
cpp复制vector<int> src = {1, 2, 3, 4, 5};
vector<int> dest(5); // 必须预先分配足够空间
// 基本复制
copy(src.begin(), src.end(), dest.begin());
// 条件复制
vector<int> evens;
copy_if(src.begin(), src.end(), back_inserter(evens), [](int x) {
return x % 2 == 0;
}); // evens: [2,4]
提示:使用back_inserter可以避免预先分配空间,它会自动调用push_back添加元素。
3.2 转换算法
transform算法可以对元素进行转换处理:
cpp复制vector<int> nums = {1, 2, 3};
vector<int> squares(3);
// 单参数转换
transform(nums.begin(), nums.end(), squares.begin(), [](int x) {
return x * x;
}); // squares: [1,4,9]
// 双参数转换(两个序列运算)
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;
}); // sum: [5,7,9]
3.3 替换算法
替换算法可以批量修改容器中的元素:
cpp复制vector<int> nums = {1, 2, 3, 2, 5};
// 简单替换
replace(nums.begin(), nums.end(), 2, 20); // nums: [1,20,3,20,5]
// 条件替换
replace_if(nums.begin(), nums.end(), [](int x) {
return x > 10;
}, 0); // nums: [1,0,3,0,5]
// 复制时替换(不修改原容器)
vector<int> res;
replace_copy(nums.begin(), nums.end(), back_inserter(res), 3, 300); // res: [1,0,300,0,5]
3.4 删除算法
删除算法需要特别注意,因为STL的删除操作有其特殊性:
cpp复制vector<int> nums = {1, 2, 3, 2, 4};
// 逻辑删除(元素被移动到末尾)
auto new_end = remove(nums.begin(), nums.end(), 2); // nums: [1,3,4,2,2]
// 物理删除(真正移除元素)
nums.erase(new_end, nums.end()); // nums: [1,3,4]
// 结合lambda删除偶数
nums = {1, 2, 3, 4, 5};
nums.erase(remove_if(nums.begin(), nums.end(), [](int x) {
return x % 2 == 0;
}), nums.end()); // nums: [1,3,5]
重要说明:remove算法实际上并不删除元素,而是将要保留的元素移动到前面,返回新的逻辑终点。要真正删除元素,必须结合erase使用,这就是著名的"erase-remove"惯用法。
3.5 去重算法
unique算法可以去除相邻的重复元素:
cpp复制vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 5};
// 逻辑去重
auto last = unique(vec.begin(), vec.end());
// vec现在为{1, 2, 3, 4, 5, 3, 3, 4, 5}
// 物理去重
vec.erase(last, vec.end()); // vec变为{1, 2, 3, 4, 5}
注意:unique只去除相邻的重复元素,如果要删除所有重复元素,需要先对容器排序。
3.6 其他修改算法
STL还提供了其他有用的修改算法:
cpp复制// 反转元素顺序
vector<int> vec = {1, 2, 3, 4, 5};
reverse(vec.begin(), vec.end()); // vec变为{5, 4, 3, 2, 1}
// 旋转元素
vector<int> vec2 = {1, 2, 3, 4, 5};
rotate(vec2.begin(), vec2.begin() + 2, vec2.end()); // vec2变为{3, 4, 5, 1, 2}
// 随机打乱
random_device rd;
mt19937 g(rd());
shuffle(vec.begin(), vec.end(), g); // 随机打乱vec中的元素
4. 排序和相关算法
4.1 排序算法
STL提供了多种排序算法,适用于不同场景:
cpp复制vector<int> vec = {5, 3, 1, 4, 2};
// 基本排序(快速排序)
sort(vec.begin(), vec.end()); // 默认升序,vec变为{1, 2, 3, 4, 5}
// 降序排序
sort(vec.begin(), vec.end(), greater<int>()); // vec变为{5, 4, 3, 2, 1}
// 自定义排序
vector<pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
return a.first < b.first || (a.first == b.first && a.second < b.second);
});
// 稳定排序(保持相等元素的相对顺序)
stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
return a.first < b.first;
});
4.2 部分排序
当只需要对部分元素排序时,可以使用partial_sort:
cpp复制vector<int> vec = {5, 3, 1, 4, 2, 6};
// 将最小的3个元素放在前面并排序
partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// 现在vec前三个元素是1, 2, 3,后面是未排序的4, 5, 6
4.3 第n元素选择
nth_element可以在不完全排序的情况下找到第n小的元素:
cpp复制vector<int> vec = {5, 3, 1, 4, 2, 6};
// 找到第三小的元素(索引2)
nth_element(vec.begin(), vec.begin() + 2, vec.end());
// 现在vec[2]是3,它左边的元素<=3,右边的>=3
4.4 二分查找
对于已排序的序列,二分查找算法效率更高:
cpp复制vector<int> sorted = {1, 3, 3, 5, 7};
// 判断元素是否存在
bool exists = binary_search(sorted.begin(), sorted.end(), 3); // true
// 查找第一个不小于3的元素
auto lb = lower_bound(sorted.begin(), sorted.end(), 3);
cout << "Lower bound index: " << lb - sorted.begin() << endl; // 输出:1
// 查找第一个大于3的元素
auto ub = upper_bound(sorted.begin(), sorted.end(), 3);
cout << "Upper bound index: " << ub - sorted.begin() << endl; // 输出:3
4.5 合并算法
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());
// merged: [1,2,3,4,5,6]
5. 堆算法
STL提供了一组堆算法,可以将任何序列作为堆来处理:
cpp复制vector<int> vec = {4, 1, 3, 2, 5};
// 构建最大堆
make_heap(vec.begin(), vec.end()); // vec变为{5, 4, 3, 2, 1}
// 添加新元素到堆
vec.push_back(6);
push_heap(vec.begin(), vec.end()); // vec变为{6, 4, 5, 2, 1, 3}
// 弹出堆顶元素
pop_heap(vec.begin(), vec.end()); // 将最大元素移到末尾
int max_val = vec.back(); // 获取最大元素6
vec.pop_back(); // 移除最大元素
// 堆排序
sort_heap(vec.begin(), vec.end()); // 将堆排序为升序序列
6. 数值算法
6.1 累加算法
cpp复制vector<int> vec = {1, 2, 3, 4, 5};
// 求和
int sum = accumulate(vec.begin(), vec.end(), 0); // 15
// 求积
int product = accumulate(vec.begin(), vec.end(), 1, multiplies<int>()); // 120
6.2 内积算法
cpp复制vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
// 计算点积
int dot = inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32
6.3 填充序列
cpp复制vector<int> vec(5);
// 用连续值填充
iota(vec.begin(), vec.end(), 10); // 填充为10, 11, 12, 13, 14
6.4 部分和与相邻差
cpp复制vector<int> src = {1, 2, 3, 4, 5};
vector<int> dst(src.size());
// 计算部分和
partial_sum(src.begin(), src.end(), dst.begin()); // dst变为{1, 3, 6, 10, 15}
// 计算相邻差
adjacent_difference(src.begin(), src.end(), dst.begin()); // dst变为{1, 1, 1, 1, 1}
7. 其他实用算法
7.1 生成算法
cpp复制vector<int> vec(5);
// 用生成函数填充
int n = 0;
generate(vec.begin(), vec.end(), [&n]() { return n++; }); // 填充为0,1,2,3,4
// 填充前n个元素
generate_n(vec.begin(), 3, [&n]() { return n++; }); // 前三个元素为5,6,7
7.2 集合算法
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));
// result为{1,2,3,4,5,6,7}
// 交集
result.clear();
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
// result为{3,4,5}
// 差集
result.clear();
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
// result为{1,2}
// 对称差集
result.clear();
set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
// result为{1,2,6,7}
8. 算法选择与性能考虑
在实际开发中选择合适的算法非常重要。以下是一些选择建议:
-
查找算法选择:
- 无序序列:find/find_if (O(n))
- 有序序列:binary_search/lower_bound (O(log n))
-
排序算法选择:
- 基本排序:sort (快速排序变种,O(n log n))
- 稳定排序:stable_sort (归并排序,O(n log n))
- 部分排序:partial_sort (堆排序,O(n log k))
-
删除元素:
- 总是使用erase-remove惯用法,而不是手动循环删除
-
数值计算:
- 优先使用
中的算法,它们通常经过高度优化
- 优先使用
-
容器适配:
- 对于list等节点式容器,考虑使用成员函数版本的算法(如list::sort),它们可能更高效
9. 实际应用案例
9.1 统计文本词频
cpp复制vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
// 统计每个单词出现的次数
map<string, int> word_counts;
for_each(words.begin(), words.end(), [&](const string& word) {
word_counts[word]++;
});
// 找出出现次数最多的单词
auto max_it = max_element(word_counts.begin(), word_counts.end(),
[](const auto& a, const auto& b) {
return a.second < b.second;
});
cout << "Most frequent word: " << max_it->first << endl;
9.2 过滤无效数据
cpp复制vector<int> data = {1, -2, 3, -4, 5, -6};
// 移除所有负数
data.erase(remove_if(data.begin(), data.end(),
[](int x) { return x < 0; }), data.end());
// 现在data只包含正数:{1, 3, 5}
9.3 自定义排序
cpp复制struct Person {
string name;
int age;
};
vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};
// 按年龄排序
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
return a.age < b.age;
});
// 也可以按名字长度排序
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
return a.name.size() < b.name.size();
});
10. 常见问题与解决方案
10.1 迭代器失效问题
在使用算法修改容器时,迭代器可能会失效:
cpp复制vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2;
// 危险:在修改操作后使用迭代器
vec.erase(remove(vec.begin(), vec.end(), 2), vec.end());
// it可能已经失效
// 安全做法:在修改后重新获取迭代器
it = vec.begin() + 2;
10.2 性能陷阱
某些算法组合可能导致性能问题:
cpp复制vector<int> vec = {...};
// 低效做法:多次遍历
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
// 更高效的做法:使用一次排序和一次遍历
sort(vec.begin(), vec.end());
auto last = unique(vec.begin(), vec.end());
vec.erase(last, vec.end());
10.3 自定义比较函数
自定义比较函数需要满足严格弱序:
cpp复制// 错误的比较函数:不满足严格弱序
sort(vec.begin(), vec.end(), [](int a, int b) {
return a <= b; // 错误!应该使用 <
});
// 正确的比较函数
sort(vec.begin(), vec.end(), [](int a, int b) {
return a < b;
});
10.4 算法与容器成员函数
某些容器提供了自己的成员函数版本算法:
cpp复制list<int> lst = {3, 1, 4, 2, 5};
// 使用成员函数版本(对list更高效)
lst.sort();
// 而不是通用算法版本
sort(lst.begin(), lst.end()); // 错误!list需要随机访问迭代器
11. C++17/20新增算法
现代C++标准引入了一些新算法:
11.1 C++17新增
cpp复制// 样本算法:从序列中随机选择n个元素
vector<int> src = {1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<int> out;
sample(src.begin(), src.end(), back_inserter(out), 3, mt19937{random_device{}()});
// 并行算法
vector<int> vec = {...};
sort(execution::par, vec.begin(), vec.end()); // 并行排序
11.2 C++20新增
cpp复制// 范围算法(更简洁的语法)
vector<int> vec = {3, 1, 4, 2, 5};
ranges::sort(vec); // 等同于sort(vec.begin(), vec.end())
// 新的查找算法
if (auto it = ranges::find(vec, 3); it != vec.end()) {
cout << "Found: " << *it << endl;
}
12. 最佳实践总结
-
优先使用算法而非手写循环:STL算法通常经过高度优化,且代码更简洁。
-
理解算法复杂度:选择适合当前数据规模的算法。
-
善用lambda表达式:使自定义操作更简洁清晰。
-
注意迭代器有效性:特别是在修改容器后。
-
利用移动语义:对于大型对象,考虑使用移动而非复制。
-
考虑并行算法:对于大型数据集,C++17的并行算法可以显著提升性能。
-
保持代码可读性:复杂的算法组合应添加适当注释。
-
测试边界条件:特别是对于自定义比较函数和谓词。