std::sort排序std::vector出现非法元素引发核心转储问题

开发的应用中，std::sort有时会导致核心转储（core dump），已将问题隔离为以下最小可复现示例：

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

class DF {
  public:
    DF() = default;

    std::vector<int> row_mapping;
    std::vector<int> idx = {0, 1};
    std::vector<std::vector<int>> vals = {
        {0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,
         4,  4,  4,  4,  5,  5,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,
         8,  8,  8,  8,  9,  9,  9,  9,  10, 10, 10, 10, 11, 11, 11, 11,
         12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14},

        {2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017,
         2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016,
         2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015,
         2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021,
         2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2014, 2015, 2016,
         2017, 2021, 2015, 2016, 2017, 2021}};

    void sort(void) {
        int n = vals[0].size();
        std::cerr << "n = " << n << std::endl;

        row_mapping.resize(n);
        std::iota(begin(row_mapping), end(row_mapping), 0);

        std::cerr << "row map:";
        for (auto v : row_mapping) std::cerr << " " << v;
        std::cerr << std::endl;

        std::sort(
            begin(row_mapping), end(row_mapping), [&](int i1, int i2) -> bool {
                std::cerr << "cmp " << i1 << " " << i2 << std::endl;
                for (auto gi : idx) {
                    if (vals[gi][i1] < vals[gi][i2]) return true;
                }
                return false;
            });
    }
};

int main() {
    DF df;
    df.sort();
}

使用命令 g++ -std=c++17 mwe.cpp 编译并运行后，得到精简后的输出：

n = 61
row map: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
cmp 1 30
cmp 30 60
(...)
cmp 52 257
(...)
cmp 59 55
cmp 60 56
double free or corruption (out)
Aborted (core dumped)

问题现象：待排序的row_mapping仅包含0到60的合法索引，但比较lambda却收到257这类非法参数，最终触发内存损坏和核心转储。

问题根源 #

核心问题在于比较函数违反了C++标准对std::sort要求的严格弱序（Strict Weak Ordering）规则。

当前的lambda仅在vals[gi][i1] < vals[gi][i2]时返回true，但当vals[gi][i1] > vals[gi][i2]时，并未及时返回false，而是继续循环所有维度后返回false。这种逻辑会导致std::sort无法正确判断元素间的顺序关系，触发未定义行为——内存越界写入、容器内部结构破坏等，最终出现非法参数和核心转储。

std::sort要求比较函数必须满足：

1. 非自反性：comp(a,a)必须返回false
2. 不对称性：若comp(a,b)为true，则comp(b,a)必须为false
3. 传递性：若comp(a,b)和comp(b,c)为true，则comp(a,c)必须为true
4. 等价传递性：若a与b等价（comp(a,b)和comp(b,a)均为false），b与c等价，则a与c必须等价

解决方案 #

修改比较lambda，补充对vals[gi][i1] > vals[gi][i2]的判断，确保每一步都能明确元素的顺序关系，满足严格弱序：

std::sort(
    begin(row_mapping), end(row_mapping), [&](int i1, int i2) -> bool {
        std::cerr << "cmp " << i1 << " " << i2 << std::endl;
        for (auto gi : idx) {
            if (vals[gi][i1] < vals[gi][i2]) {
                return true;
            } else if (vals[gi][i1] > vals[gi][i2]) {
                return false;
            }
            // 维度相等时，继续比较下一个维度
        }
        // 所有维度均相等，i1与i2等价，返回false
        return false;
    });

修改后的逻辑：

• 按idx指定的维度依次比较
• 若i1的当前维度值小于i2，返回true（i1排在i2前）
• 若i1的当前维度值大于i2，返回false（i1不排在i2前）
• 所有维度相等时，返回false（元素等价，无需交换）

这样的比较函数完全符合严格弱序要求，std::sort可以正常工作，不会出现内存损坏和非法参数问题。

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