C++ STL sort()第三参数写法复杂度与性能差异疑问

两种写法的渐近时间复杂度完全一致，都是C++标准sort的O(n log n)，不存在算法层面的量级差距，出现超时完全是写法不当带来的巨额常数开销导致的，和时间复杂度无关。

核心原因有两点：

• 首要原因是参数传递的拷贝开销
  方法1的自定义比较函数使用值传递接收参数：

  static bool cmp(vector<int> a, vector<int> b) {
      return a[1] < b[1];
  }
  

  每次排序流程调用比较函数时，都会对传入的两个vector<int>做深拷贝——vector的拷贝会把容器内存储的所有int元素完整复制一份，单次比较就会产生和子vector长度正相关的额外耗时。排序过程总共需要执行O(n log n)次比较，累积下来的拷贝开销会非常高，数据量稍大就会触发超时。
  而方法2的lambda表达式使用引用传递参数，传参时仅传递vector的别名，不会触发整个容器的深拷贝，访问a[1]时直接读取原内存的数据，完全没有这部分额外开销。
• 次要原因是编译器优化难度差异
  lambda的类型在编译期是唯一确定的，编译器实例化sort模板时，可以很轻松地把比较逻辑直接内联到排序代码中，省掉函数调用的栈帧开销。普通函数作为比较器传递时本质是传函数指针，编译器做内联优化的难度稍高，但这部分开销和值传递的拷贝开销比起来几乎可以忽略，不是超时的核心诱因。

只要把方法1的比较函数参数改成const引用，性能就会和lambda版本基本持平，不会出现超时问题，修正后的写法如下：

static bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
}

补充说明：你写的lambda版本中第二个参数没有加const，属于不规范写法——比较函数不应该修改待比较元素，最好统一写成const vector<int>& b，不过这个问题不会影响实际运行性能。

内容的提问来源于stack exchange，提问作者Md Morsalin Hossain