83 Advanced The Hundred
The Comparator That Corrupts
the ties that unbind
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> scores;
for (int i = 0; i < 100; ++i)
scores.push_back(70 + i % 3);
std::sort(scores.begin(), scores.end(),
[](int a, int b) { return a <= b; }); // ascending... right?
std::cout << "low " << scores.front() << ", high " << scores.back() << "\n";
}
Run it. What does it print?
Answer
Not low 70, high 72. Typical output (GCC on x86-64):
A corrupted result — "low" should be 70 — printed just before glibc aborts on the
mangled heap. It varies run to run: other runs segfault silently inside std::sort
and print nothing at all.
Why¶
std::sort requires a strict weak ordering: equal elements must compare false both
ways, so comp(a, a) is never true — and <= breaks exactly that. libstdc++ spends the
guarantee on speed: its quicksort partition scan — while (comp(first, pivot)) ++first;
— has no bounds check, because a conforming comparator must say stop at the pivot
itself. With <= ties never say stop — and this vector is nearly all ties — so the scan
runs straight off the end of the buffer: undefined behavior, an instant segfault or
a heap scribble caught only when the vector is freed. At 30 elements it survived every
run here — which is why this bug loves to pass code review and unit tests. No typo
needed to fall in: plain < on doubles containing NaN breaks the same laws.
-Wall -Wextra say nothing, but -D_GLIBCXX_DEBUG catches it red-handed — the program
halts with Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).
The fix¶
A comparator answers one question — does a come strictly before b? For ties: no.
[](int a, int b) { return a < b; } // ascending — ties compare false
[](int a, int b) { return a > b; } // descending — never >=
Takeaway: sort comparators mean "strictly before" — use < (or >), never <=,
and make equal elements compare false both ways.
Try it: g++ -std=c++17 main.cpp -o demo && ./demo