STL 算法与迭代器
用标准算法替代手写循环并掌握 Lambda 表达式
#为什么算法是自由函数
Python 里你在对象上调用方法:lst.sort()、lst.count(x)。JS 也一样:arr.map(fn)。而 C++ 的 <algorithm> 是自由函数:std::sort(v.begin(), v.end())、std::count(v.begin(), v.end(), x)。
这不是历史包袱,而是解耦设计:算法通过迭代器操作,不关心容器类型。同一个 std::sort 既能排 vector,也能排 deque、数组,甚至 C 风格数组。代价是调用时多写两个迭代器参数(C++20 的 Ranges 库用 std::ranges::sort(v) 解决了这点,本教程以 C++17 为主,会另行标注)。
另一个重要差异:Python 的 filter/map 返回惰性迭代器,而 C++ 的 std::transform 是立即执行并写入你指定的目标。Python 的 sorted() 返回新列表、list.sort() 原地排序;C++ 的 std::sort 一律原地排序,且不稳定(需要稳定排序用 std::stable_sort)。
#迭代器分类回顾
上一章提到迭代器分五类,这里讲清它对算法选择的实际影响。算法在头文件里会通过"迭代器标签"声明自己需要的最低能力,用错类型会在编译期(往往是模板错误信息)报错。
| 类别 | 能力 | 典型代表 | 支持的操作 |
|---|---|---|---|
| 输入迭代器 | 只读、单趟前进 | istream_iterator | *it、++it、== |
| 输出迭代器 | 只写、单趟前进 | back_inserter | *it = v、++it |
| 前向迭代器 | 可读写、多趟前进 | forward_list | 输入 + 多次遍历 |
| 双向迭代器 | 可后退 | list、set、map | 前向 + --it |
| 随机访问迭代器 | 跳跃访问 | vector、deque、string、数组 | 双向 + it + n、<、[] |
实践含义:std::sort 需要随机访问迭代器,所以不能对 std::list 排序(list 自带 sort() 成员函数);std::find 只需要输入迭代器,所以任何容器都能用。
#include <algorithm>
#include <functional> // std::greater
#include <iostream>
#include <iterator>
#include <list>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>
int main() {
std::vector<int> v{5, 2, 8, 1, 9};
// 1) sort 需要随机访问迭代器,vector 满足
std::sort(v.begin(), v.end()); // 升序
std::sort(v.begin(), v.end(), std::greater<int>()); // 降序,需要 <functional>
std::cout << "降序: ";
for (int x : v) { std::cout << x << " "; }
std::cout << "\n";
// 部分排序:只保证前 3 个是最小的(不必整体有序),比全排快
std::partial_sort(v.begin(), v.begin() + 3, v.end());
std::cout << "前 3 小: " << v[0] << " " << v[1] << " " << v[2] << "\n";
// 2) list 没有随机访问迭代器,不能用 std::sort,只能用成员函数
std::list<int> lst{5, 2, 8, 1, 9};
lst.sort(); // 成员函数,OK
// std::sort(lst.begin(), lst.end()); // 编译错误
std::cout << "list 排序后: ";
for (int x : lst) { std::cout << x << " "; }
std::cout << "\n";
// 3) 输入迭代器:istream_iterator 把输入流当容器遍历
std::istringstream iss("10 20 30");
int sum = 0;
for (auto it = std::istream_iterator<int>(iss);
it != std::istream_iterator<int>(); ++it) {
sum += *it;
}
std::cout << "从流里读到的和 = " << sum << "\n";
// 4) 输出迭代器:back_inserter 让算法自动扩容容器
std::vector<int> dst;
std::copy(v.begin(), v.end(), std::back_inserter(dst));
std::cout << "copy 后大小 = " << dst.size() << "\n";
// 5) 编译期查询迭代器类别,理解模板背后的机制
using It = std::vector<int>::iterator;
static_assert(std::is_same<std::iterator_traits<It>::iterator_category,
std::random_access_iterator_tag>::value,
"vector 的迭代器应是随机访问类别");
std::cout << "vector 迭代器确认为随机访问\n";
return 0;
}#查找与统计:非修改型算法
这一组算法不改动容器内容,对应 Python 的 in、len([x for x in ...])、all()、any(),以及 JS 的 includes、find、 every、some。
返回值约定要记牢:找不到时返回 end()(不是 -1,也不是 null)。这和 Python 的 list.index() 抛异常、JS 的 indexOf 返回 -1 都不一样,是 C++ 最容易被写错的地方之一——忘记检查就直接解引用 end() 是经典 bug。
#include <algorithm>
#include <iostream>
#include <iterator> // std::distance
#include <string>
#include <vector>
struct User {
int id;
std::string name;
int score;
};
int main() {
std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6};
// 1) find:线性查找,找不到返回 end()
auto it = std::find(data.begin(), data.end(), 5);
if (it != data.end()) {
std::cout << "找到 5,下标 = " << std::distance(data.begin(), it) << "\n";
} else {
std::cout << "未找到\n";
}
// 2) find_if:按谓词查找,等价于 Python 的 next(x for x in ... if ...)
auto even = std::find_if(data.begin(), data.end(),
[](int x) { return x % 2 == 0; });
if (even != data.end()) {
std::cout << "第一个偶数 = " << *even << "\n";
}
// 3) count / count_if:等价于 Python 的 list.count(x) 和 sum(1 for ... if ...)
std::cout << "1 的个数 = " << std::count(data.begin(), data.end(), 1) << "\n";
std::cout << "偶数个数 = " << std::count_if(data.begin(), data.end(),
[](int x) { return x % 2 == 0; })
<< "\n";
// 4) all_of / any_of / none_of:对应 Python 的 all() / any()
bool all_positive = std::all_of(data.begin(), data.end(),
[](int x) { return x > 0; });
bool has_big = std::any_of(data.begin(), data.end(),
[](int x) { return x > 5; });
std::cout << std::boolalpha << "全为正数 " << all_positive
<< ",存在大于 5 的 " << has_big << "\n";
// 5) 在自定义类型里查找:谓词拿到的是元素本身
std::vector<User> users{{1, "Alice", 90}, {2, "Bob", 85}, {3, "Carol", 92}};
auto u = std::find_if(users.begin(), users.end(),
[](const User& user) { return user.name == "Bob"; });
if (u != users.end()) {
std::cout << "Bob 的分数 = " << u->score << "\n";
}
// 6) 有序容器的二分查找:必须先排序,O(log n)
std::sort(data.begin(), data.end());
bool found = std::binary_search(data.begin(), data.end(), 5);
auto range = std::equal_range(data.begin(), data.end(), 1);
std::cout << "二分查找 5 = " << found
<< ",值 1 的区间长度 = "
<< std::distance(range.first, range.second) << "\n";
// 7) min_element / max_element:返回迭代器,不是值
auto [min_it, max_it] = std::minmax_element(data.begin(), data.end());
std::cout << "最小 " << *min_it << ",最大 " << *max_it << "\n";
return 0;
}#修改型算法与 erase-remove 惯用法
std::sort、std::reverse、std::transform、std::fill、std::copy 属于修改型算法。其中 transform 对应 Python/JS 的 map,但必须提供输出位置。
最有价值的是 erase-remove 惯用法,它是 C++ 独有的模式,其他语言没有对应物:
std::remove 并不真的删除元素(它无法改变容器大小,只操作迭代器),而是把"不该删除的元素"往前搬,返回新的逻辑终点。真正的删除要靠容器自己的 erase。所以标准写法是 v.erase(std::remove(...), v.end())。
对比 Python 的 lst.remove(x) 或 [x for x in lst if x != v](直接得到新列表),C++ 的两步拆分看起来啰嗦,但它避免了多次内存分配,且对任何容器统一。C++20 的 std::erase(v, value) 终于把这个惯用法封装成了一行。
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
// 1) erase-remove 惯用法:删除所有等于 3 的元素
// remove 把不等于 3 的元素前移,返回新的逻辑末尾;erase 才真正缩短容器
v.erase(std::remove(v.begin(), v.end(), 3), v.end());
std::cout << "删除 3 后: ";
for (int x : v) { std::cout << x << " "; } // 1 2 4 5 6
std::cout << "\n";
// 2) remove_if:删除所有偶数
v.erase(std::remove_if(v.begin(), v.end(),
[](int x) { return x % 2 == 0; }),
v.end());
std::cout << "删除偶数后: ";
for (int x : v) { std::cout << x << " "; } // 1 5
std::cout << "\n";
// 3) transform:等价于 Python 的 map,但要指定输出位置
std::vector<int> src{1, 2, 3, 4};
std::vector<int> dst;
dst.reserve(src.size());
std::transform(src.begin(), src.end(), std::back_inserter(dst),
[](int x) { return x * x; });
std::cout << "平方: ";
for (int x : dst) { std::cout << x << " "; } // 1 4 9 16
std::cout << "\n";
// 原地 transform:把输出位置设回自身
std::transform(src.begin(), src.end(), src.begin(),
[](int x) { return x + 10; });
// 4) reverse / rotate / fill
std::reverse(src.begin(), src.end());
std::cout << "反转后首元素 = " << src.front() << "\n";
std::rotate(src.begin(), src.begin() + 1, src.end()); // 左旋一位
std::fill(src.begin(), src.end(), 7); // 全部填 7
std::cout << "填充后大小 = " << src.size() << "\n";
// 5) unique:去重前必须先排序,同样要配合 erase
std::vector<int> with_dup{3, 1, 3, 2, 1, 3};
std::sort(with_dup.begin(), with_dup.end());
with_dup.erase(std::unique(with_dup.begin(), with_dup.end()), with_dup.end());
std::cout << "去重后: ";
for (int x : with_dup) { std::cout << x << " "; } // 1 2 3
std::cout << "\n";
// 6) copy_if:带条件的复制,等价于 Python 的 filter
std::vector<int> big;
std::copy_if(with_dup.begin(), with_dup.end(), std::back_inserter(big),
[](int x) { return x >= 2; });
std::cout << "筛出 >= 2 的有 " << big.size() << " 个\n";
// 7) 对字符串排序:算法对任何支持迭代器的容器都有效
std::string s = "hello";
std::sort(s.begin(), s.end());
std::cout << "排序后的字符串 = " << s << "\n"; // ehllo
return 0;
}#数值算法
<numeric> 里的三个常用函数对应 Python 的 sum、itertools.accumulate、functools.reduce:
std::accumulate:求和/折叠,等价于 Python 的sum()或reduce()。std::inner_product:内积。std::iota:填充递增序列,等价于 Python 的range(n)。
#include <iostream>
#include <iterator> // std::back_inserter
#include <numeric>
#include <string>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
// 1) accumulate:第三个参数是初始值,类型决定累加的类型
int sum = std::accumulate(v.begin(), v.end(), 0);
double dsum = std::accumulate(v.begin(), v.end(), 0.0); // 注意初值类型
int prod = std::accumulate(v.begin(), v.end(), 1,
[](int a, int b) { return a * b; }); // 阶乘
std::cout << "和 = " << sum << ",浮点和 = " << dsum
<< ",积 = " << prod << "\n";
// 2) 用 accumulate 做字符串拼接(大数据量时先 reserve 更高效)
std::vector<std::string> words{"C++", "与", "Qt"};
std::string joined = std::accumulate(
words.begin(), words.end(), std::string(),
[](const std::string& a, const std::string& b) { return a + b; });
std::cout << "拼接 = " << joined << "\n";
// 3) iota:填充 0,1,2,...,等价于 Python 的 list(range(n))
std::vector<int> seq(10);
std::iota(seq.begin(), seq.end(), 0);
std::cout << "序列末元素 = " << seq.back() << "\n";
// 4) inner_product:两个容器的点积
std::vector<int> a{1, 2, 3}, b{4, 5, 6};
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);
std::cout << "点积 = " << dot << "\n"; // 4 + 10 + 18 = 32
// 5) partial_sum:前缀和,等价于 Python 的 itertools.accumulate
std::vector<int> prefix;
std::partial_sum(v.begin(), v.end(), std::back_inserter(prefix));
std::cout << "前缀和: ";
for (int x : prefix) { std::cout << x << " "; } // 1 3 6 10 15
std::cout << "\n";
return 0;
}#Lambda 表达式:就地定义的小函数
Lambda 是 C++11 引入的匿名函数,语法是 [捕获列表](参数列表) -> 返回类型 { 函数体 }。返回类型通常可省略(编译器推导),捕获列表是它区别于普通函数的关键——它能带着外部变量一起走,这是函数指针做不到的(回顾第 3 章)。
对照其他语言:Python 的 lambda 只能写单个表达式(lambda x: x * 2),复杂逻辑得用 def;JS 的箭头函数 (x) => x * 2 自动捕获外层作用域;Java 的 Lambda 只能捕获事实上不可变的局部变量。C++ 的捕获是显式声明的,你必须写明要捕获什么、按值还是按引用——啰嗦,但也让你清楚知道 Lambda 持有了什么、会不会造成悬垂。
捕获方式:
[=]:按值捕获所有用到的外部变量(C++20 起不推荐,容易误捕this)。[&]:按引用捕获所有(危险:Lambda 若比被捕获变量活得久,就是悬垂引用)。[x]/[&x]:只按值 / 按引用捕获x,推荐显式写法。[this]:捕获当前对象指针;C++17 起[*this]可捕获对象副本。[x = std::move(p)]:初始化捕获(C++14),可移动不可拷贝的对象靠它进入 Lambda。
#include <algorithm>
#include <functional>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
int main() {
std::vector<int> v{5, 3, 8, 1, 9, 2};
// 1) 最简单的 Lambda:无捕获,用做排序比较器
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // 降序
std::cout << "降序: ";
for (int x : v) { std::cout << x << " "; }
std::cout << "\n";
// 2) 按值捕获 [threshold]:Lambda 内部持有副本
int threshold = 5;
auto count_big = std::count_if(v.begin(), v.end(),
[threshold](int x) { return x > threshold; });
std::cout << "大于 " << threshold << " 的有 " << count_big << " 个\n";
// 3) 按引用捕获 [&sum]:可以修改外部变量
int sum = 0;
std::for_each(v.begin(), v.end(), [&sum](int x) { sum += x; });
std::cout << "总和 = " << sum << "\n";
// 4) mutable:按值捕获的变量默认只读,加 mutable 才能在内部修改副本
int counter = 0;
auto tick = [counter]() mutable { return ++counter; };
std::cout << "tick: " << tick() << " " << tick() << " "
<< "外部 counter 仍是 " << counter << "\n";
// 5) 显式返回类型:分支返回不同类型时必须写明,否则推导失败
auto classify = [](int x) -> std::string {
if (x > 5) { return "大"; }
return "小";
};
std::cout << "8 是" << classify(8) << "\n";
// 6) 初始化捕获(C++14):把不可拷贝的对象移进 Lambda
auto ptr = std::make_unique<int>(42);
auto use_ptr = [p = std::move(ptr)]() { return *p; };
std::cout << "移动进 Lambda 的值 = " << use_ptr() << "\n";
// 7) 存进 std::function:跨越函数边界传递,代价是类型擦除开销
std::function<bool(int)> is_even = [](int x) { return x % 2 == 0; };
std::cout << "偶数个数 = " << std::count_if(v.begin(), v.end(), is_even) << "\n";
// 8) 泛型 Lambda(C++14):参数用 auto,等价于函数模板
auto twice = [](auto x) { return x + x; };
std::cout << "int: " << twice(3)
<< ",string: " << twice(std::string("ab")) << "\n";
// 9) 用 Lambda 自定义复杂排序:先按长度、再按字典序
std::vector<std::string> names{"Qt", "C++", "Python", "Java"};
std::sort(names.begin(), names.end(),
[](const std::string& a, const std::string& b) {
if (a.size() != b.size()) { return a.size() < b.size(); }
return a < b;
});
for (const auto& n : names) { std::cout << n << " "; }
std::cout << "\n";
return 0;
}一条重要提醒:不要默认用 [&]。按引用捕获的 Lambda 一旦被存起来异步执行(比如 Qt 的信号槽、std::thread),被捕获的局部变量早已销毁,访问它就是悬垂引用。需要长期存活的 Lambda 按值捕获,或用 shared_ptr 持有共享数据。
#小结
- STL 算法是自由函数,通过迭代器与容器解耦,同一个算法可作用于任何容器;Python/JS 则是容器的方法。
- 迭代器分五类,
sort需要随机访问迭代器(所以list用成员函数sort()),find/count只要输入迭代器。 - 查找类算法找不到时返回
end(),务必先比较再解引用;这与 Python 抛异常、JS 返回-1都不同。 - erase-remove 惯用法:
std::remove只搬移元素不缩短容器,必须配合erase才是真删除;unique同理且去重前要先排序。 transform≈Python/JS 的map,copy_if≈filter,accumulate≈sum/reduce,all_of/any_of≈all()/any()。- Lambda 的捕获必须显式声明:优先
[x]按值、[&x]按引用;异步场景下禁用[&],避免悬垂引用。
#练习
- 用
std::sort+ Lambda 对std::vector<Student>(含name、score、age)排序:先按分数降序,分数相同按年龄升序。 - 用
std::accumulate计算一个std::vector<double>的平均值和标准差,体会初值类型(0vs0.0)对结果的影响——先用0试一次,看结果错在哪。 - 用 erase-remove 惯用法删除
std::vector<std::string>中所有长度小于 3 的字符串,并打印删除前后的 size 和 capacity,验证remove不改变容器大小。 - 用
std::find_if在一个std::vector<User>中查找"名字以 A 开头且分数大于 80"的第一个用户,找不到时返回提示而不是崩溃。再练习 Lambda 捕获:分别用[=]、[&]、[x]三种方式写计数器 Lambda,把[&]版本存进std::function后在原变量已销毁的作用域调用,观察未定义行为(开-fsanitize=address会直接报错)。