lambda 表达式和 std::sort 也是一对苦命鸳鸯
我们都知道有个很好用的东西叫 lambda 表达式，可以用来代替函数，大概长这样：
auto calc = [&c, d](int n, std::vector<int> &a) {
a[1] = d;
c = n + 1;
};然后它有个很好用的功能是捕获所有当前作用域的变量，大概是 [&] 引用捕获所有，[=] 按值捕获所有。
诶这个按值捕获是什么意思？就是说我们的 lamdba 表达式调用前会先初始化，把按值捕获的变量复制一份存在自己里面，这样外界的变量值改变了也不影响它内部复制的。
那这个东西会有什么隐患吗？有的兄弟，请看 vcr：
vector<int> find_union(int n, vector<int> A, vector<int> B, vector<int> C, vector<int> D) {
// ...
struct temp {
int id, type;
};
vector<temp> op;
for (int i = 1; i <= n; i++) op.push_back({i, 0}), op.push_back({i, 1});
auto cmp = [=](temp a, temp b) {
int ta = a.type ? A[a.id - 1] : C[a.id - 1];
int tb = b.type ? A[b.id - 1] : C[b.id - 1];
return ta == tb ? a.type > b.type : ta < tb;
};
sort(op.begin(), op.end(), cmp);
// ...
}这段东西在
看起来毫无问题啊，为什么呢？
我们一度开始怀疑 lambda 是不是每次调用都会重新捕获。
问题就出在 lambda 和 std::sort 上，我们来看 std::sort 的定义：
template<typename _RandomAccessIterator, typename _Compare>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
}注意这个地方是 _Compare __comp，然后我们实际执行排序的函数是 std::__sort，它手里的比较函数是在 __comp 外面包了一层，传入两个指针状物然后用 __comp 比较对应的值。
而在 std::__sort 的定义都长这样：
template<typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)；包括后面一系列的辅助函数，定义都是 _Compare _comp。
有的人可能已经看懂了：这里的 _Compare 不是一个引用类型，每次传递 _comp 的时候都会被最开始传入的比较函数复制一遍。
而那份 T 飞的代码比较函数长这样：
auto cmp = [=](temp a, temp b) { /* ... */ };完整地复制了作用域里的四个 std::vector。
因此这份代码的实际复杂度来到了
要使复杂度正确，只需把 [=] 改为 [&] 即可，复制引用传递的 lambda 的时间复杂度是正确的。
貌似 STL 里大部分算法都存在这个现象，即传入的函数是非引用传递的。
大概可以理解这个是因为 STL 库出现时间较早，一般处理的都是函数指针这种轻量的东西，用不着加什么引用。
但按值捕获 lambda 这个后来者却不一样，虽然 sizeof 出来也就是一个指针的大小，但实际上可能是一个巨大无比的 class。
诶话说 lambda 出来以前不也能用仿函数吗？那个也可以很大啊。
传递比较函数的这一部分开销显然是没被考虑在内，而一般人平时也不会想到，不小心写出这一类东西就可能会中招。
你说是吧 @XiaoShanYunPan。
所以平时可以了解一些不熟语法，场上慎用不熟的语法。
以及，不要写一些莫名其妙的 lambda。
诶不是你 lambda 按值传递平时谁用啊，而且你写个只用一次的 lambda 还要定义个 cmp 出来是几个意思啊。