为何使用看似合规的严格弱序比较的std::sort仍崩溃？

问题重现 #

使用std::sort排序二维vector时触发段错误，代码如下：

#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
void test()
{
    vector<vector<int>> info = {{0,0,999}, {0,1,1000}, {0,2,1001},
                {0,3,1002}, {0,4,1003}, {0,5,1004},
                {0,6,1005}, {0,7,1006}, {1,0,1000},
                {1,1,999}, {1,2,1000}, {1,3,1001},
                {1,4,1002}, {1,5,1003}, {1,6,1004},
                {1,7,1005}, {2,0,1001}, {2,1,1000},
                {2,2,999}, {2,3,1000}, {2,4,1001},
                {2,5,1002}, {2,6,1003}, {2,7,1004},
                {3,0,1002}, {3,1,1001}, {3,2,1000},
                {3,3,999}, {3,4,1000}, {3,5,1001},
                {3,6,1002}, {3,7,1003}, {4,0,1003},
                {4,1,1002}, {4,2,1001}, {4,3,1000},
                {4,4,999}, {4,5,1000}, {4,6,1001},
                {4,7,1002}, {5,0,1004}, {5,1,1003},
                {5,2,1002}, {5,3,1001}, {5,4,1000},
                {5,5,999}, {5,6,1000}, {5,7,1001},
                {6,0,1005}, {6,1,1004}, {6,2,1003},
                {6,3,1002}, {6,4,1001}, {6,5,1000},
                {6,6,999}, {6,7,1000}, {7,0,1006},
                {7,1,1005}, {7,2,1004}, {7,3,1003},
                {7,4,1002},{7,5,1001}};  
    auto cmp=[](const auto& a,const auto& b){
      if(a[2]<b[2])return true;
      if(a[0]<b[0])return true;
      return a[1]<b[1];       
 };

 sort(begin(info),end(info),cmp);

}
int main()
{
  test();
}

编译环境：Ubuntu 24.04 LTS（Linux 6.8.0-39-generic），g++ 13.2，C++20标准。运行时错误：

zzhao@zzhao-System-Version:~$ g++  -std=c++20 z3.cpp

zzhao@zzhao-System-Version:~$ ./a.out

Segmentation fault (core dumped)

问题根源：比较器违反严格弱序规则 #

你的比较器逻辑存在缺陷，没有满足std::sort要求的严格弱序（strict weak ordering），这会导致排序算法内部逻辑混乱，触发未定义行为（比如段错误）。

严格弱序的核心要求之一是：对于任意两个元素a和b，如果cmp(a,b)为true，则cmp(b,a)必须为false（不对称性）。

你的比较器逻辑的问题在于，当a[2] > b[2]时，直接进入第二步比较a[0]，这会导致出现cmp(a,b)和cmp(b,a)同时为true的矛盾情况。举个具体例子：

• 元素A：{1,1,999}（a[2]=999）
• 元素B：{0,1,1000}（b[2]=1000）

调用cmp(A,B)：A[2] < B[2]为true，返回true。
调用cmp(B,A)：B[2] < A[2]为false，接着判断B[0] < A[0]（0 < 1）为true，返回true。

此时两个比较结果同时为true，完全违反严格弱序规则，std::sort依赖比较器的正确性维护内部数据结构，这种矛盾会直接导致内存访问错误，也就是段错误。

修复方案 #

修正比较器，确保只有当前面的字段相等时，才比较下一个字段：

方案1：显式链式判断 #

auto cmp=[](const auto& a,const auto& b){
  if(a[2] != b[2]) return a[2] < b[2];
  if(a[0] != b[0]) return a[0] < b[0];
  return a[1] < b[1];       
};

方案2：使用std::tie简化（推荐） #

利用tuple的默认比较规则自动实现严格弱序，代码更简洁且不易出错：

#include <tuple> // 需要包含这个头文件

auto cmp=[](const auto& a,const auto& b){
  return std::tie(a[2], a[0], a[1]) < std::tie(b[2], b[0], b[1]);
};

这两种方案都能保证比较器符合严格弱序规则，std::sort可以正常运行，不会触发段错误。

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