lambda 表达式和 std::sort 也是一对苦命鸳鸯

我们都知道有个很好用的东西叫 lambda 表达式，可以用来代替函数，大概长这样：

CPP

auto calc = [&c, d](int n, std::vector<int> &a) {
  a[1] = d;
  c = n + 1;
};

然后它有个很好用的功能是捕获所有当前作用域的变量，大概是 [&] 引用捕获所有，[=] 按值捕获所有。

诶这个按值捕获是什么意思？就是说我们的 lamdba 表达式调用前会先初始化，把按值捕获的变量复制一份存在自己里面，这样外界的变量值改变了也不影响它内部复制的。

那这个东西会有什么隐患吗？有的兄弟，请看 vcr：

CPP

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);
  // ...
}

这段东西在

n=10^5

下跑了 13s+，非常神秘。

看起来毫无问题啊，为什么呢？

~~我们一度开始怀疑 lambda 是不是每次调用都会重新捕获。~~

问题就出在 lambda 和 std::sort 上，我们来看 std::sort 的定义：

CPP

  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 的定义都长这样：

CPP

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
	   _Compare __comp)；

包括后面一系列的辅助函数，定义都是 _Compare _comp。

有的人可能已经看懂了：这里的 _Compare 不是一个引用类型，每次传递 _comp 的时候都会被最开始传入的比较函数复制一遍。

而那份 T 飞的代码比较函数长这样：

CPP

	auto cmp = [=](temp a, temp b) { /* ... */	};

完整地复制了作用域里的四个 std::vector。

因此这份代码的实际复杂度来到了

\mathcal{O}(n^2\log_2 n)

，快排时每次递归都会复制

\mathcal{O}(n)

长度的数组。

要使复杂度正确，只需把 [=] 改为 [&] 即可，复制引用传递的 lambda 的时间复杂度是正确的。

貌似 STL 里大部分算法都存在这个现象，即传入的函数是非引用传递的。

大概可以理解这个是因为 STL 库出现时间较早，一般处理的都是函数指针这种轻量的东西，用不着加什么引用。

但按值捕获 lambda 这个后来者却不一样，虽然 sizeof 出来也就是一个指针的大小，但实际上可能是一个巨大无比的 class。

~~诶话说 lambda 出来以前不也能用仿函数吗？那个也可以很大啊。~~

传递比较函数的这一部分开销显然是没被考虑在内，而一般人平时也不会想到，不小心写出这一类东西就可能会中招。

~~你说是吧 @XiaoShanYunPan。~~

所以平时可以了解一些不熟语法，场上慎用不熟的语法。

以及，不要写一些莫名其妙的 lambda。

~~诶不是你 lambda 按值传递平时谁用啊，而且你写个只用一次的 lambda 还要定义个 cmp 出来是几个意思啊。~~

lambda 表达式和 std::sort 也是一对苦命鸳鸯

文章操作

相关推荐

评论

lambda 表达式和 std::sort 也是一对苦命鸳鸯