C++ lambda按值捕获触发TLE、按引用捕获运行正常是什么原因？

问题原因 #

你遇到的TLE问题核心是lambda捕获方式带来的额外内存拷贝开销，具体逻辑如下：

• C++ lambda的值捕获[nums]会将外部的nums数组完整拷贝一份，存到lambda的闭包对象中；而引用捕获[&nums]仅存储nums的引用（本质是指针），闭包对象体积只有8字节左右，拷贝成本可以忽略。
• priority_queue的构造函数会拷贝你传入的比较器对象：如果使用值捕获的lambda作为比较器，构造队列时相当于要把整个大体积的nums数组再完整拷贝一次，仅这一步在LeetCode大长度测试用例（比如nums长度达到1e5甚至更高）中，就会多出数MB的内存拷贝开销。
• 除此之外，STL优先队列在内部进行堆调整、元素增删操作的过程中，也可能产生比较器的拷贝操作，每次拷贝都要重复复制整个nums数组，累积的时间开销会远高于引用捕获的版本，最终触发时间超限。

你可以做个简单验证：给lambda加上mutable关键字，在比较器里打印&nums的地址，会发现值捕获的lambda内部的nums地址和原数组完全不同，确实是独立的拷贝。

内容的提问来源于stack exchange，提问作者nerd