42. 비교자의 strict weak ordering 위반과 표준 알고리즘의 정의되지 않은 동작

// [주제] 비교자(comparator)의 strict weak ordering 요구사항과
//        표준 알고리즘·연관 컨테이너의 동작
//
// 게임서버는 랭킹 정렬, 매칭 대기열 우선순위, std::map/std::set 키 비교에
// 커스텀 비교자를 자주 쓴다. 아래는 실제 코드에서 흔히 보이는 다섯 가지 비교자다.
//
// [과제]
//  1) Case1 ~ Case5 를 각각 실행했을 때 프로그램이 어떻게 동작할지 예측하라.
//     "정렬 결과가 이렇게 나온다" / "결과가 정해지지 않는다" / "예측 불가" 중
//     무엇에 해당하는지, 그리고 그렇게 판단한 근거를 말하라.
//  2) std::sort 가 잘못된 비교자를 받았을 때, 왜 단순히 "잘못 정렬된 결과"가 아니라
//     세그폴트나 힙 손상으로 이어질 수 있는가?
//     libstdc++ 의 introsort 구현이 어떤 루프를 도는지 수준에서 설명하라.
//  3) Case4 의 std::map 은 어떤 키를 "같은 키"로 취급하는가?
//     std::map 이 동치(equivalence)를 판정하는 식을 쓰고, operator== 와 무엇이 다른지 설명하라.
//  4) Case5 처럼 NaN 이 섞였을 때 비교자가 어떤 성질을 잃는지 설명하라.
//  5) 각 비교자를 어떻게 고쳐야 하는지 제시하라.

#include <cmath>
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <string>
#include <vector>
#include <algorithm>

struct Entry {
    std::uint32_t id;
    float         score;
    int           tier;     // 0 = bronze, 1 = silver, 2 = gold
    std::string   name;
};

static std::vector<Entry> MakeRanking() {
    std::vector<Entry> v;
    v.reserve(64);
    for (std::uint32_t i = 0; i < 64; ++i) {
        Entry e;
        e.id    = i;
        e.score = static_cast<float>(i % 8) * 100.0f;   // 같은 점수가 8개씩 겹친다
        e.tier  = static_cast<int>(i % 3);
        e.name  = "player" + std::to_string(i);
        v.push_back(e);
    }
    return v;
}

static void Dump(const char* tag, const std::vector<Entry>& v) {
    std::cout << tag << ": ";
    for (std::size_t i = 0; i < v.size() && i < 8; ++i) std::cout << v[i].id << ' ';
    std::cout << "...\n";
}

// ── Case 1: 랭킹 내림차순 정렬 ────────────────────────────────────────────
void Case1() {
    auto v = MakeRanking();
    std::sort(v.begin(), v.end(), [](const Entry& a, const Entry& b) {
        return a.score >= b.score;
    });
    Dump("Case1", v);
}

// ── Case 2: 티어 우선, 같은 티어면 점수 높은 순 ───────────────────────────
void Case2() {
    auto v = MakeRanking();
    std::sort(v.begin(), v.end(), [](const Entry& a, const Entry& b) {
        return a.tier < b.tier || a.score > b.score;
    });
    Dump("Case2", v);
}

// ── Case 3: 점수가 "거의 같으면" 같은 순위로 본다 ─────────────────────────
void Case3() {
    auto v = MakeRanking();
    for (auto& e : v) e.score = static_cast<float>(e.id) * 0.4f;   // 0.0, 0.4, 0.8, ...
    std::sort(v.begin(), v.end(), [](const Entry& a, const Entry& b) {
        return a.score < b.score - 1.0f;   // 1.0 이내면 동점 취급
    });
    Dump("Case3", v);
}

// ── Case 4: 매칭 대기열을 std::map 으로 관리 ──────────────────────────────
struct QueueKey {
    int           mmr;
    std::uint32_t playerId;
};

struct QueueKeyLess {
    bool operator()(const QueueKey& a, const QueueKey& b) const {
        if (a.mmr / 100 != b.mmr / 100) return a.mmr / 100 < b.mmr / 100;
        return a.playerId <= b.playerId;
    }
};

void Case4() {
    std::map<QueueKey, std::string, QueueKeyLess> q;
    q[QueueKey{1250, 7}]  = "alice";
    q[QueueKey{1299, 7}]  = "bob";
    q[QueueKey{1250, 42}] = "carol";
    q[QueueKey{1310, 7}]  = "dave";

    std::cout << "Case4: size=" << q.size() << '\n';
    auto it = q.find(QueueKey{1250, 7});
    std::cout << "Case4: find(1250,7) -> " << (it == q.end() ? "miss" : it->second) << '\n';
    auto it2 = q.find(QueueKey{1280, 7});
    std::cout << "Case4: find(1280,7) -> " << (it2 == q.end() ? "miss" : it2->second) << '\n';
}

// ── Case 5: 점수 계산에 NaN 이 섞이는 경우 ────────────────────────────────
void Case5() {
    auto v = MakeRanking();
    v[10].score = std::numeric_limits<float>::quiet_NaN();
    v[37].score = std::numeric_limits<float>::quiet_NaN();

    std::sort(v.begin(), v.end(), [](const Entry& a, const Entry& b) {
        return a.score < b.score;
    });
    Dump("Case5", v);

    bool found = std::binary_search(v.begin(), v.end(), v[0],
        [](const Entry& a, const Entry& b) { return a.score < b.score; });
    std::cout << "Case5: binary_search -> " << found << '\n';
}

int main() {
    Case1();
    Case2();
    Case3();
    Case4();
    Case5();
    return 0;
}