The Comparator Ranked a Tie as Less

The comparator treated a matching pair as less. Then std::sort walked into undefined behavior. Green tests on three unique keys will not save you.

I rebuilt the failure in a tiny harness. No vendor core dump. No secret production trace. Just a polite predicate that broke the named requirement.

Why did it look polite? It handled equality on purpose. That choice was the bug. Have you shipped that comment too?

The symptom I started from

I sorted a vector of records. Most permutations looked fine. One permutation dropped a name.

Another permutation duplicated a name. The size stayed constant. The multiset did not.

Have you seen that shape? Length matches. Contents lie. That is not a stability complaint. That is contract failure under std::sort.

I printed the vector before the call. I printed it after the call. Same size(). Different bags of values.

What I blamed first

I blamed the swap. I blamed a user-written move. I blamed a dangling string_view.

Wrong. Wrong. And wrong again. The record was a boring aggregate. Two fields. Trivial moves. No views.

So I read the comparator slowly. It even had a comment. "Handle ties by name." Cute. Deadly.

struct Rec {
    int score;
    std::string name;
};

bool by_score_then_name(const Rec& a, const Rec& b) {
    if (a.score != b.score) {
        return a.score > b.score;
    }
    return a.name <= b.name; // looks careful. it is not.
}

See the <=? Equal names return true. std::sort wants a strict weak ordering. comp(x, x) must be false.

Ask it out loud. Does comp(x, x) return false? If not, stop coding. Fix the predicate first.

Shrink the input until the law is visible

Do not debug this on ten thousand production rows. Three records can be enough. Four if you want a real tie.

Label this clearly. The listing below is a reconstructed example. It is not a client trace.

// sort_predicate_check.cpp
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

struct Rec {
    int score;
    std::string name;
};

bool bad_less(const Rec& a, const Rec& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.name <= b.name;
}

bool good_less(const Rec& a, const Rec& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.name < b.name;
}

template <class Cmp>
bool irreflexive(const std::vector<Rec>& v, Cmp cmp) {
    for (const auto& x : v) {
        if (cmp(x, x)) return false;
    }
    return true;
}

template <class Cmp>
bool both_ways_true(const std::vector<Rec>& v, Cmp cmp) {
    for (const auto& a : v) {
        for (const auto& b : v) {
            if (cmp(a, b) && cmp(b, a)) return false;
        }
    }
    return true;
}

int main() {
    std::vector<Rec> v{
        {10, "ada"},
        {10, "ada"},
        {7, "bek"},
        {10, "cy"}
    };

    std::cout << std::boolalpha;
    std::cout << "irreflexive bad: "
              << irreflexive(v, bad_less) << "\n";
    std::cout << "asymmetric bad: "
              << both_ways_true(v, bad_less) << "\n";
    std::cout << "irreflexive good: "
              << irreflexive(v, good_less) << "\n";
    std::cout << "asymmetric good: "
              << both_ways_true(v, good_less) << "\n";
}

Compile it with symbols. Read the booleans. Do not skip that print.

c++ -std=c++17 -O0 -g sort_predicate_check.cpp -o sort_predicate_check
./sort_predicate_check

You want this shape of output. Anything else means the law already failed.

irreflexive bad: false
asymmetric bad: false
irreflexive good: true
asymmetric good: true

The bad predicate fails before std::sort runs. That is the whole trick. Catch the contract. Do not wait for the crash.

Debug steps I now reuse

1. Freeze one permutation. Dump it as a brace list.
2. Ask comp(x, x) on every element. Demand false.
3. Ask both directions on every pair. Ban two trues.
4. Check transitivity on triples. Yes, it is tedious.
5. Only then call std::sort under sanitizers.

Step four is the one people skip. Why skip it? Because it is boring. Undefined behavior loves boring predicates.

c++ -std=c++17 -O1 -g -fsanitize=address,undefined \
    sort_predicate_check.cpp -o sort_san
./sort_san

Sanitizers do not always fire here. Treat a clean run as inconclusive. The pair checks are the test. The sanitizer is a spare net.

A debug standard library can help. It is not a portable promise. Keep the property checks anyway.

The patch that made it worse

I asked a coding model for a fix. It kept the tie comment. It wrote a still-illegal predicate.

bool still_bad(const Rec& a, const Rec& b) {
    if (a.score > b.score) return true;
    if (a.score < b.score) return false;
    if (a.name == b.name) return true; // "stable on equals"
    return a.name < b.name;
}

Stable on equals? std::sort is not std::stable_sort. Returning true for equals stays illegal. The draft optimized for a story. Not for [alg.sorting].

That is vibe-shaped C++. It compiles. It sounds kind. It is still undefined behavior. Would you merge it after a unique-key unit test? I would not.

Disclosure: This article was prepared as part of MonkeyCode's product outreach.

I used MonkeyCode's free model access and free server option as a draft source. Not as an oracle. I pasted the ordering laws. I did not paste customer rows. Then every candidate hit the same irreflexive check.

Most drafts failed comp(x, x). Good. The harness did the engineering. The model only did the typing. A local compiler still owned the verdict.

The real fix

Use <. Never <=. Never return true for equal keys. Split fields with std::tie when the key grows.

#include <tuple>

bool good_less(const Rec& a, const Rec& b) {
    // descending score, then ascending name
    return std::tie(b.score, a.name) < std::tie(a.score, b.name);
}

Wait. Did I invert score by swapping operands? Yes. Write that once. Test it twice. A table beats a comment.

a	b	good_less(a,b)	good_less(b,a)	note
{10, ada}	{10, ada}	false	false	equal, both false
{10, ada}	{10, cy}	true	false	name order
{10, ada}	{7, bek}	true	false	higher score first
{7, bek}	{10, cy}	false	true	lower score later

If any row shows two trues, you failed. If an equal row shows a true, you failed. Print the row. Do not argue with it.

A cheap shuffle net

Four rows are not a proof. Shuffle. Repeat. Keep the asserts.

#include <numeric>
#include <random>

void fuzz_ordering(std::vector<Rec> v, unsigned seed) {
    std::mt19937 rng(seed);
    for (int i = 0; i < 200; ++i) {
        std::shuffle(v.begin(), v.end(), rng);
        assert(irreflexive(v, good_less));
        assert(both_ways_true(v, good_less));
        auto w = v;
        std::sort(w.begin(), w.end(), good_less);
        assert(w.size() == v.size());
        assert(std::is_sorted(w.begin(), w.end(), good_less));
    }
}

Two hundred shuffles. Not a benchmark. A cheap net. Illegal comparators often explode early. A quiet run still needs the pair checks.

Seed the generator. Log the seed. Replay the failing permutation. That replay is the debugging technique. The model output is not.

What I now refuse to merge

A comparator with <=. A comparator that returns true "for stability." A comparator that calls abs on the key. A comparator that reads a field the sort mutates.

Would I trust a green test that sorts three unique scores? No. Unique keys hide the tie bug. Ties are the actual test. Unique keys are theater.

I also refuse silent operator< on types I do not own. Wrapping those types is fine. Pretending they already order is not.

Limitations

This harness does not prove transitivity on infinite domains. Finite samples miss hostile keys. Floating-point keys are another swamp. NaN breaks < even when you were careful.

Debug iterators in libstdc++ or libc++ can catch some of this. They are build flags, not proofs. Do not drop property checks because a debug STL exists.

I did not measure model quality. I did not collect pass rates. One illegal <= is enough to reject a patch. Do not turn this into a leaderboard.

The free remote path is a draft source. It is not a verifier. If the code cannot leave your machine, do not paste it anywhere remote. Keep secrets local. Generate the harness locally.

Who should skip this approach

Skip it if you sort pointers and think addresses are keys. Skip it if your "tie" is a live timestamp. Skip it if you need a total order over NaN.

Do not point a remote free model at customer records. Do not use this loop as cover for missing operator< on foreign types. Do not call a unique-key sort a proof of ordering.

And do not skip step four because the sanitizer was quiet. Quiet is not evidence. Quiet is a missing assert.

The reusable bit

The technique is older than coding models. Write the ordering laws first. Irreflexive. Asymmetry. Transitivity. Then type the predicate. Then sort.

I still write two-field predicates by hand. I let a draft appear when the key has six nested fields. Then I run the table. Then I run the shuffle loop.

Did a draft type std::tie faster than I did? Sometimes. Did it catch <= alone? Not until the harness returned false.

That false is the engineering. Keep the false. Drop the story in the comment.

If you need a second draft of a synthetic comparator, MonkeyCode's free models and free server option are one place to run that loop. Keep the checks. Leave the vibes out of the merge.