【C++】std::sortの比較関数に「<=」を書くとどうなる？｜Debugだけ止まる「invalid comparator」と、Releaseで静かに崩れる並びを実測

▼e1_le.cpp
// 比較関数に < ではなく <= を書いて、std::sort を呼ぶ
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <random>
#include <vector>
#ifdef _DEBUG
#include <crtdbg.h>
static int ReportHook(int, char* message, int*)
{
    std::printf("[Debugの診断] %s\n", message);
    std::fflush(stdout);
    std::exit(77);
    return 1;
}
#endif

int main(int argc, char** argv)
{
    std::setvbuf(stdout, nullptr, _IONBF, 0);
#ifdef _DEBUG
    _CrtSetReportHook(ReportHook);
#endif
    int n = std::atoi(argv[1]);
    bool same = std::strcmp(argv[2], "same") == 0;     // same: 全部同じ値 / dup: 0〜9のランダム(重複だらけ)
    bool le = std::strcmp(argv[3], "le") == 0;         // le: <= / lt: <

    std::mt19937 rng(1);
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = same ? 5 : (int)(rng() % 10);

    if (le)
        std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
    else
        std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

    std::printf("n=%d  %s  %s : 最後まで実行できた  整列済み=%s\n", n, same ? "全部同じ値" : "重複だらけ", le ? "<=" : "< ", std::is_sorted(v.begin(), v.end()) ? "はい" : "いいえ");
    return 0;
}

[Debugの診断] C:\Program Files\Microsoft Visual Studio\2022\Enterprise\VC\Tools\MSVC\14.44.35207\include\xutility(1602) : Assertion failed: invalid comparator

▼e3_hunt.cpp
// <= の比較関数で、Release でも壊れる条件があるかを、たくさんの乱数で探す
#include <windows.h>
#include <algorithm>
#include <cstdio>
#include <random>
#include <vector>

// SEH(構造化例外)で、アクセス違反を拾う。オブジェクトを持たない関数に分ける
static int sortLE(int* p, int n)
{
    __try
    {
        std::sort(p, p + n, [](int a, int b) { return a <= b; });
        return 0;
    }
    __except (EXCEPTION_EXECUTE_HANDLER)
    {
        return (int)GetExceptionCode();
    }
}

int main()
{
    std::setvbuf(stdout, nullptr, _IONBF, 0);
    std::mt19937 rng(12345);
    const int trials = 3000;
    int crashes = 0, unsorted = 0, ok = 0;
    DWORD firstCode = 0;
    int firstN = 0, firstK = 0;
    for (int t = 0; t < trials; ++t)
    {
        int n = 34 + (int)(rng() % 5000);
        int k = 1 + (int)(rng() % 4);          // 値は 0 〜 k-1 の、k 種類だけ
        std::vector<int> v(n);
        for (int i = 0; i < n; ++i) v[i] = (int)(rng() % k);
        int rc = sortLE(v.data(), n);
        if (rc != 0) { ++crashes; if (!firstCode) { firstCode = rc; firstN = n; firstK = k; } }
        else if (!std::is_sorted(v.begin(), v.end())) ++unsorted;
        else ++ok;
    }
    std::printf("<= で std::sort を %d 回(要素 34〜5033 個・値は 1〜4 種類)\n", trials);
    std::printf("  正しく整列できた : %d 回\n", ok);
    std::printf("  整列できていない : %d 回\n", unsorted);
    std::printf("  落ちた           : %d 回", crashes);
    if (firstCode) std::printf("  (最初の例: n=%d, 値の種類=%d, 例外コード 0x%08X)", firstN, firstK, (unsigned)firstCode);
    std::printf("\n");
    return 0;
}

<= で std::sort を 3000 回(要素 34〜5033 個・値は 1〜4 種類)
  正しく整列できた : 3000 回
  整列できていない : 0 回
  落ちた           : 0 回

▼e4_set.cpp
// set の比較に <= (std::less_equal) を使うと、同じ値が見つからなくなる
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <set>
#ifdef _DEBUG
#include <crtdbg.h>
static int ReportHook(int, char* message, int*)
{
    std::printf("[Debugの診断] %s\n", message);
    std::fflush(stdout);
    std::exit(77);
    return 1;
}
#endif

int main()
{
    std::setvbuf(stdout, nullptr, _IONBF, 0);
#ifdef _DEBUG
    _CrtSetReportHook(ReportHook);
#endif
    std::set<int, std::less_equal<int>> s;
    s.insert(5);
    s.insert(5);
    s.insert(5);
    std::printf("5 を3回 insert したあと  : size = %zu (std::set は重複しないはず)\n", s.size());
    std::printf("find(5)                  : %s\n", s.find(5) != s.end() ? "見つかった" : "見つからない");
    std::printf("count(5)                 : %zu\n", s.count(5));
    size_t erased = s.erase(5);
    std::printf("erase(5) で消えた数      : %zu / 残り size = %zu\n", erased, s.size());

    std::set<int> ok;
    ok.insert(5); ok.insert(5); ok.insert(5);
    std::printf("(参考) 普通の set<int>    : size = %zu, find(5) = %s\n", ok.size(), ok.find(5) != ok.end() ? "見つかった" : "見つからない");
    return 0;
}

5 を3回 insert したあと  : size = 3 (std::set は重複しないはず)
find(5)                  : 見つからない
count(5)                 : 0

[Debugの診断] C:\Program Files\Microsoft Visual Studio\2022\Enterprise\VC\Tools\MSVC\14.44.35207\include\xutility(1602) : Assertion failed: invalid comparator

▼e2_multikey.cpp
// 「点数が高い順、同点なら名前順」を、間違った書き方と正しい書き方で比べる
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <random>
#include <string>
#include <tuple>
#include <vector>
#ifdef _DEBUG
#include <crtdbg.h>
static int ReportHook(int, char* message, int*)
{
    std::printf("[Debugの診断] %s\n", message);
    std::fflush(stdout);
    std::exit(77);
    return 1;
}
#endif

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

// 間違い: 「点数が上」または「名前が前」なら、前に置く
static bool buggy(const Player& a, const Player& b) { return a.score > b.score || a.name < b.name; }

// 正しい書き方その1: 違うほうのキーだけで決める
static bool good1(const Player& a, const Player& b)
{
    if (a.score != b.score) return a.score > b.score;
    return a.name < b.name;
}
// 正しい書き方その2: std::tie で、辞書順に比べる(点数は降順なので、左右を入れ替える)
static bool good2(const Player& a, const Player& b) { return std::tie(b.score, a.name) < std::tie(a.score, b.name); }

// 「点数が高い順、同点なら名前順」に、なっているか
static int violations(const std::vector<Player>& v)
{
    int bad = 0;
    for (size_t i = 1; i < v.size(); ++i)
        if (good1(v[i], v[i - 1])) ++bad;
    return bad;
}

int main()
{
    std::setvbuf(stdout, nullptr, _IONBF, 0);
#ifdef _DEBUG
    _CrtSetReportHook(ReportHook);
#endif
    Player a{"zed", 10}, b{"amy", 5};
    std::printf("buggy(a,b) = %d, buggy(b,a) = %d   (a=zed/10点, b=amy/5点)\n", buggy(a, b), buggy(b, a));
    std::printf("good1(a,b) = %d, good1(b,a) = %d\n\n", good1(a, b), good1(b, a));

    std::mt19937 rng(7);
    std::vector<Player> base;
    for (int i = 0; i < 200; ++i)
    {
        char nm[8];
        std::snprintf(nm, sizeof nm, "p%03d", i);
        base.push_back({nm, (int)(rng() % 10)});
    }
    std::shuffle(base.begin(), base.end(), rng);

    auto v1 = base;
    std::sort(v1.begin(), v1.end(), good1);
    std::printf("good1 : 並びの食い違い %3d 件\n", violations(v1));
    auto v2 = base;
    std::sort(v2.begin(), v2.end(), good2);
    std::printf("good2 : 並びの食い違い %3d 件 (good1と同じ並び: %s)\n", violations(v2), (v1.size() == v2.size() && std::equal(v1.begin(), v1.end(), v2.begin(), [](const Player& x, const Player& y) { return x.name == y.name; })) ? "はい" : "いいえ");
    auto v3 = base;
    std::sort(v3.begin(), v3.end(), buggy);
    std::printf("buggy : 並びの食い違い %3d 件\n", violations(v3));
    return 0;
}

buggy(a,b) = 1, buggy(b,a) = 1   (a=zed/10点, b=amy/5点)
good1(a,b) = 1, good1(b,a) = 0

good1 : 並びの食い違い   0 件
good2 : 並びの食い違い   0 件 (good1と同じ並び: はい)
buggy : 並びの食い違い  64 件

▼直し方
// 1つのキー: 昇順は <、降順は >(<= や >= は使わない)
std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

// 複数のキー(その1): 違うキーが見つかった時点で、そのキーだけで決める
bool good1(const Player& a, const Player& b)
{
    if (a.score != b.score) return a.score > b.score;   // 点数の高い順
    return a.name < b.name;                              // 同点なら、名前順
}

// 複数のキー(その2): std::tie で、タプルの辞書順比較にまかせる
// (降順にしたいキーは、左右を入れ替える)
bool good2(const Player& a, const Player& b)
{
    return std::tie(b.score, a.name) < std::tie(a.score, b.name);
}