std::sort 段错误：比较函数写成 <=，n 过了 16 就越界

系列入口在 在浏览器里编译运行 C++。这篇只讲一件事：传给 std::sort 的比较函数里多了一个等号，程序会在某个输入规模之后读到数组外面。

先给结论。std::sort 要求比较函数是严格弱序。a <= b 不是。它在小数组上看不出毛病，排序结果甚至是对的；数组一长，库里那几个不检查边界的循环就会一路走出 end()。

本文的数字都来自同一份最小复现程序：g++ 14.2、-O2，数组里放的全是相同的元素。规模不超过 16 时程序表现正常，排序结果也对；超过 16 以后，AddressSanitizer 开始报告越界读；规模再大，越界读落到未映射的内存页上，进程直接收到段错误。下面按这个顺序逐一说明，最后给出能在测试阶段提前发现问题的编译开关。

一个能复现的最小程序

数组里放 n 个相同的 7，比较函数写成 x <= y：

std::vector<int> a(n, 7);
std::sort(a.begin(), a.end(), [](int x, int y) { return x <= y; });

用 Debian 上的 g++ 14.2（libstdc++）、-O2 编译，在 x86-64 Linux 上按不同的 n 跑了一遍。同一份代码再用 -fsanitize=address（ASan）编一次，看有没有越界读。

这张表里有两个台阶，16 和 32768。它们来自两个不同的地方：第一个是 libstdc++ 的实现，第二个是内存分配器。

17 到 32760 这一段最危险。程序已经在读数组外的内存，却照常打印、照常退出。测试数据一小，CI 永远是绿的；上线以后某天进来一份大输入，才第一次崩。

16：插入排序和快排的分界

libstdc++ 的 std::sort 是 introsort：先做快排式的分区，区间短到一定长度就停，最后统一跑一遍插入排序。这个长度写在 bits/stl_algo.h 里：

enum { _S_threshold = 16 };

n <= 16 时根本不进分区，只跑带边界检查的插入排序。所以 15、16 连 ASan 都不报。

n = 17 开始进分区。分区的核心是 __unguarded_partition，名字里的 unguarded 就是「不检查边界」：

1while (true) {
2    while (__comp(__first, __pivot))
3        ++__first;
4    --__last;
5    while (__comp(__pivot, __last))
6        --__last;
7    if (!(__first < __last))
8        return __first;
9    std::iter_swap(__first, __last);
10    ++__first;
11}

为什么敢不查边界？因为它依赖一个前提：基准本身就在这段区间里，而 comp(pivot, pivot) 一定是 false。左边的指针走到基准那一格必然停下，右边同理。基准充当了哨兵。

把比较函数换成 <=，前提就没了。数组全是 7，comp(7, 7) 恒为 true。左指针遇到谁都不停，越过基准，越过最后一个元素，继续读 end() 后面的内存。直到碰巧读到一个比 7 大的垃圾值才停，或者读到没有映射的页，被系统杀掉。

下标:     0   1   2  ...  15  16 | 17  18  19 ...
值:       7   7   7  ...   7   7 | ?   ?   ?
                                 |
comp(a[i], pivot) = (7 <= 7) = true，first 一直 ++
first: ──────────────────────────┼──────────────▶ 越过 end()
                                 └ 数组到这里结束，循环不知道

不是全相等的数组也会出事。只要区间里有一串和基准相等的元素，而它们刚好排在区间尾部，<= 就会让指针穿过去。全是 7 只是最容易复现的形状。

32768：分配器换了一种拿内存的方式

第二个台阶跟 std::sort 无关。32760 个 int 是 131040 字节，32768 个 int 正好是 131072 字节，也就是 128 KiB。glibc 的 malloc 默认在 128 KiB 以上改用 mmap 单独映射一块内存（M_MMAP_THRESHOLD），以下则从堆里切。

按字节数核对，分界和实测一致：从堆里切出来的数组后面紧跟着别的堆数据，越界读往往还能读到东西，所以不崩；单独 mmap 出来的数组后面常常是未映射页，第一次越界读就是段错误。

换句话说，「不崩」不代表没错，只代表越界读到的地方恰好可读。换一个分配器、换一个平台、换一个编译器版本，台阶会挪位置。浏览器里的 WASM 运行时有一整块线性内存，越界读通常读不到「没映射的页」，更可能悄悄给出一个乱序的结果。

严格弱序到底要求什么

把比较函数记作 less(a, b)。C++ 标准对 std::sort、std::set、std::map、std::lower_bound 的比较函数有同一组要求：

1. 非自反：less(a, a) 必须为 false。
2. 非对称：less(a, b) 为真时，less(b, a) 必须为假。
3. 传递：less(a, b)、less(b, c) 都为真，则 less(a, c) 为真。
4. 「等价」可传递：把「less(a, b) 和 less(b, a) 都为假」叫作 a 与 b 等价。a 等价 b、b 等价 c，则 a 必须等价 c。

<= 第一条就挂了。第四条最容易被忽略。常见的写法是「差得不多就当相等」：

// 只有 b 比 a 大 2 以上才算 a 在前，差 1 以内视为相等
auto less = [](int a, int b) { return a < b - 1; };

1 和 2 相等，2 和 3 相等，但 1 和 3 不相等。等价关系断了，排序算法没法把「相等」的元素归成一组。浮点数里的 NaN 也是这一类：NaN < x 和 x < NaN 都为假，NaN 和谁都「等价」，于是 1.0 等价 NaN、NaN 等价 2.0，1.0 却小于 2.0。含 NaN 的 double 数组直接用 < 排序，同样违反要求。

在这里跑：给比较函数做个体检

下面的程序拿一小组样本，逐条检查前面说的 1、2、4 三条性质（第 3 条在样本小的时候和第 4 条一起暴露，这里不单列）。它不调用 std::sort，所以不会越界，在任何平台上输出都一样。

本机用 g++ 14.2（-O0、-O2、-O3）和 clang++ 19.1（-O0、-O2）各编一次，-Wall -Wextra 无警告，五次输出完全相同：

int <        irreflexive=yes asymmetric=yes equiv-transitive=yes -> ok
int <=       irreflexive=NO asymmetric=NO equiv-transitive=yes -> BROKEN
near-equal   irreflexive=yes asymmetric=yes equiv-transitive=NO -> BROKEN

<= 在样本 {3, 1, 3, 2} 上，同一个元素和自己比就返回真，两个 3 互相「小于」对方。near-equal 前两条都过，只在等价传递上失败，正是 1、2、3 这条链。

这个体检是三重循环，O(n³)，样本放十几个值足够，不要把整份数据塞进去。

正确的写法

降序排列不要写 >=，写 >，或者直接用 std::greater<>()。多个字段比较时，先比主键，主键相等再比次键，最后一层用 < 或 >，不要出现等号。

下面是一个按优先级降序、同优先级保持输入顺序的例子。它读 n，再读 n 行「名字 优先级」：

本机 g++ 14.2 和 clang++ 19.1 编译运行，默认 stdin 的输出：

test 5
deploy 5
build 2
docs 1

test 和 deploy 优先级都是 5，test 先输入，所以在前。只想要「相等元素保持原顺序」的话，也可以不加 seq，改用 std::stable_sort 配 a.priority > b.priority。stdin 改成 2 和 x 1，只给一行，程序在 stderr 打印 Expected 2 'name priority' pairs.，退出码 1。

字段多了以后，std::tie(a.x, a.y) < std::tie(b.x, b.y) 比手写 if 链更不容易出错，它按字典序比较，天然满足严格弱序。

怎么在出事前抓住它

对上面那份 <= 的最小程序，三种编译配置差别很大：

调试模式最早发现问题。它在 std::sort 入口就拿首元素和自己比一次，n = 3 就停下，报错是：

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

ASan 要等真的越界才报，n <= 16 抓不到，但它不挑比较函数的写法，任何越界都管。两个开关都会让程序变慢，适合放在测试构建里，不放在发布构建里。

用 clang 和 libc++ 的话，对应的开关是 libc++ 的加固模式（hardening mode，debug 级别），也会检查比较函数。用法因 libc++ 版本而异，以你所用版本的文档为准。

一个可以直接照做的配置是：测试构建里加 -D_GLIBCXX_DEBUG，另一套测试构建里加 -fsanitize=address，发布构建两者都不加。前者在 std::sort 入口检查比较函数是否满足非自反，后者兜底所有真正发生的越界读写。注意 _GLIBCXX_DEBUG 会改变标准容器的内部布局，同一个程序里互相传递容器的各个编译单元和库，必须使用一致的设置，否则可能出现难以理解的崩溃。

和这个站上其他几篇的关系

快排退化成 O(n²) 里那份手写分区带着 lo、hi 两个边界，基准选得再差也只是慢，不会越界。标准库为了快，把边界检查换成了「基准一定能让指针停下」这个约定，约定的另一半写在比较函数里。

二分查找的中点和窗口 里的 lower_bound 也吃同一个比较函数。数组如果是用 <= 排的（碰巧没崩），再拿 < 去二分，两边对「相等」的理解不一致，查出来的位置可能是错的。

把这篇的两段代码贴进 Playground 就能跑。想看 <= 版本在浏览器里会怎样，可以自己把 sort-tasks.cpp 的比较函数改成 a.priority >= b.priority，再输入一串优先级相同的任务。浏览器里的线性内存和 Linux 进程不一样，表现不一定是段错误，可能是输出乱序或者多出奇怪的值，这本身就是未定义行为的样子。系列目录在 浏览器里的 C++。