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

난이도: 상

요약

std::sort, std::map, std::set, std::binary_search 는 비교자가 strict weak ordering(SWO) 을 만족한다는 것을 전제 조건(precondition) 으로 요구한다. 전제 조건을 어기면 결과가 이상해지는 것이 아니라 정의되지 않은 동작(UB) 이다. 표준 라이브러리는 성능을 위해 경계 검사를 의도적으로 제거해 두었기 때문에, SWO 위반은 실제로 버퍼 밖 쓰기 → 힙 손상 → 세그폴트로 이어진다.

Case1 은 비반사성 위반, Case2 는 추이성 위반, Case3 은 "비교 불가의 추이성" 위반, Case4 는 std::map 의 동치 정의를 깨뜨리고, Case5 는 NaN 때문에 세 성질을 한꺼번에 잃는다. 다섯 개 모두 UB 이며, 그중 Case1 은 실측에서 원소 수가 조금만 커져도 즉시 죽는다.

핵심 개념

strict weak ordering 의 네 가지 요구

비교자 comp(a, b) 가 "a 가 b 보다 앞선다"를 의미할 때, 다음을 모두 만족해야 한다.

성질	정의
비반사성(irreflexive)	`comp(a, a)` 는 항상 `false`
비대칭성(asymmetric)	`comp(a, b)` 가 참이면 `comp(b, a)` 는 거짓
추이성(transitive)	`comp(a,b)` 이고 `comp(b,c)` 이면 `comp(a,c)`
비교 불가의 추이성	`equiv(a,b)` 이고 `equiv(b,c)` 이면 `equiv(a,c)`

여기서 동치는 < 나 == 가 아니라 비교 불가(incomparable) 로 정의된다.

equiv(a, b)  ⟺  !comp(a, b) && !comp(b, a)

네 번째 조건이 가장 자주 간과된다. equiv 가 추이적이지 않으면 SWO 가 아니라 단순한 "partial order" 가 되고, 정렬·이분 탐색·map 의 전제가 전부 무너진다.

`<=` 와 `>=` 는 절대 비교자가 될 수 없다

comp(a, a) 를 계산해 보면 a <= a 는 true 다. 비반사성이 바로 깨진다. 비교자는 항상 strict(< 또는 >)여야 한다. 이것이 이름에 "strict" 가 들어간 이유다.

단계별 내부 동작

Case 1 — `a.score >= b.score` (비반사성·비대칭성 위반)

comp(a, a) 가 true 다. 점수가 같은 두 원소 x, y 에 대해 comp(x, y) 와 comp(y, x) 가 동시에 참이 되고, 알고리즘은 "x 는 y 앞이고 y 는 x 앞"이라는 모순된 정보를 받는다.

libstdc++ 의 std::sort 는 introsort 다.

std::sort
 ├─ __introsort_loop     : 구간 길이 > 16 인 동안 quicksort, 재귀 깊이 초과 시 heapsort
 └─ __final_insertion_sort : 남은 짧은 구간들을 insertion sort 로 마무리

두 단계 모두 경계 검사가 없는 루프를 쓴다.

// __unguarded_partition (개념)
while (true) {
    while (__comp(*__first, __pivot)) ++__first;    // 경계 검사 없음
    --__last;
    while (__comp(__pivot, *__last)) --__last;      // 경계 검사 없음
    if (!(__first < __last)) return __first;
    std::iter_swap(__first, __last);
    ++__first;
}

// __unguarded_linear_insert (개념)
_Tp __val = std::move(*__last);
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, *__next)) {                    // 경계 검사 없음
    *__last = std::move(*__next);
    __last = __next;
    --__next;                                        // 배열 앞으로 계속 간다
}
*__last = std::move(__val);

이 두 루프가 안전한 이유는 오직 하나, "구간 안 어딘가에 반드시 루프를 멈출 원소(sentinel)가 있다" 는 것을 SWO 가 보장하기 때문이다. __unguarded_linear_insert 는 앞쪽 16 개를 먼저 경계 검사 있는 __insertion_sort 로 정렬해 최솟값을 맨 앞에 박아 두고, "최솟값보다 작은 값은 없다"는 성질로 루프가 멈춘다고 가정한다.

>= 는 그 가정을 깨뜨린다. comp(val, *next) 가 최솟값에서도 true 가 되어 --next 가 배열 시작 지점을 지나 계속 뒤로 간다. 그 상태로 *__last = std::move(*__next) 를 실행하므로 벡터가 소유하지 않은 힙 메모리를 읽고 쓴다. 힙 메타데이터가 깨지고, Entry 가 std::string 을 갖고 있으니 쓰레기 포인터에 대한 std::string 이동 대입이 일어나 free 되지 않아야 할 주소를 free 한다.

실측(GCC 11, -O2, 원소는 int score + 패딩 28 바이트, 점수는 0~50 랜덤):

원소 수	결과
100	정상 종료 (우연)
1,000	SIGSEGV
20,000	SIGSEGV
200,000	SIGSEGV

원소가 16 개 이하면 __introsort_loop 를 아예 타지 않고 경계 검사가 있는 __insertion_sort 만 돌기 때문에 살아남는다. "작은 데이터로 테스트해서 괜찮았다"가 아무 보증이 되지 않는 이유다. 문제의 Case1() 은 원소 64 개에 점수가 8 종류뿐이라 실행 환경에 따라 그냥 통과하기도 한다. UB 는 "항상 죽는다"가 아니라 "아무 일이나 일어난다"이다.

-D_GLIBCXX_DEBUG 로 빌드하면 정확히 이 위반을 잡아 준다.

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

Case 2 — `a.tier < b.tier || a.score > b.score` (추이성·비대칭성 위반)

|| 로 두 키를 이어 붙인 것이 오류다. 다중 키 비교는 || 가 아니라 "앞 키가 다르면 그것으로 결정, 같으면 다음 키로" 라는 계단식이어야 한다.

비대칭성부터 깨진다. a = {tier:0, score:10}, b = {tier:1, score:5} 라면

comp(a, b) = (0 < 1) || (10 > 5) = true
comp(b, a) = (1 < 0) || (5 > 10) = false

여기까진 우연히 맞지만, a = {tier:0, score:5}, b = {tier:1, score:10} 은

comp(a, b) = (0 < 1) || (5 > 10) = true
comp(b, a) = (1 < 0) || (10 > 5) = true ← 둘 다 참

추이성도 깨진다. a={0,100}, b={2,50}, c={1,80} 에서

comp(a, b) = (0<2) || ... = true
comp(b, c) = (2<1) || (50>80) = false

반대로 comp(c, b) = (1<2) = true, comp(a,c) = (0<1) = true 인데 comp(b,a) = (2<0) || (50>100) = false. 조합에 따라 순환(cycle)이 만들어지고, quicksort 의 파티션이 "피벗보다 작은 것"과 "큰 것"으로 나뉜다는 불변식이 깨진다.

실측에서는 크래시 없이 뒤죽박죽인 순서가 나왔지만(39 63 15 7 31 55 23 47 ...), 이것 역시 우연이다. 데이터가 바뀌면 Case1 과 같은 경로로 죽을 수 있다.

올바른 형태는 이렇다.

[](const Entry& a, const Entry& b) {
    if (a.tier != b.tier) return a.tier < b.tier;
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;                 // 전순서(total order)로 만들어 결과를 결정적으로
}

C++20 이상이면 std::tie 나 operator<=> 로 실수를 원천 차단한다.

[](const Entry& a, const Entry& b) {
    return std::tie(a.tier, b.score, a.id) < std::tie(b.tier, a.score, b.id);
}   // 내림차순 키는 부호를 뒤집어 넣는 편이 안전하다

Case 3 — `a.score < b.score - 1.0f` (비교 불가의 추이성 위반)

"거의 같으면 동점" 은 게임 랭킹에서 자주 요구되는 규칙이지만, 비교자로 표현하면 안 된다. 비반사성과 비대칭성은 만족한다. 문제는 네 번째 조건이다.

score 가 각각 0.0, 0.8, 1.6 인 세 원소를 보자.

equiv(0.0, 0.8): 0.0 < -0.2 거짓, 0.8 < -1.0 거짓 → 동치
equiv(0.8, 1.6): 0.8 < 0.6 거짓, 1.6 < -0.2 거짓 → 동치
equiv(0.0, 1.6): 0.0 < 0.6 참 → 동치가 아니다 (0.0 < 1.6)

동치 관계가 추이적이지 않다. 이것은 "근사 동등(approximate equality)" 이 본질적으로 동치 관계가 아니기 때문이며(수학적으로 tolerance 관계는 추이적이지 않다), 비교자를 아무리 잘 짜도 해결되지 않는다.

결과적으로 정렬 결과는 입력 순서와 파티션 순서에 따라 달라지고, 실측에서도 1 0 3 4 2 5 6 7 ... 처럼 앞뒤가 뒤집힌 구간이 나온다. 크래시로 이어질 수도 있다.

올바른 접근은 정렬 전에 값을 양자화(quantize)하는 것이다. 관계를 흐리는 대신 데이터를 이산화해서 진짜 동치 관계로 만든다.

// 점수를 버킷으로 접어 넣고, 버킷을 키로 정렬한다 — 동치가 추이적이 된다
auto bucket = [](float s) { return static_cast<std::int64_t>(std::floor(s / 1.0f)); };
std::sort(v.begin(), v.end(), [&](const Entry& a, const Entry& b) {
    auto ba = bucket(a.score), bb = bucket(b.score);
    if (ba != bb) return ba < bb;
    return a.id < b.id;
});

Case 4 — `std::map` 의 동치 판정

std::map 은 키 비교에 operator== 를 전혀 쓰지 않는다. 두 키가 같은지는 오직

!comp(a, b) && !comp(b, a)

로 판정한다. find, count, operator[], 중복 키 거부가 모두 이 식 위에 서 있다. (구현은 lower_bound 로 위치를 찾은 뒤 !comp(key, *it) 하나만 확인한다. 탐색 경로에서 이미 !comp(*it, key) 가 성립하기 때문이다.)

QueueKeyLess 는 같은 버킷 안에서 a.playerId <= b.playerId 를 반환한다. comp(k, k) 가 true 이므로 비반사성이 깨졌고, std::map 의 전제가 무너진다.

실측 결과는 이렇다.

Case4: size=4
Case4: find(1250,7) -> miss
Case4: find(1280,7) -> miss

(1250,7) 과 (1299,7) 은 버킷이 둘 다 12 이고 playerId 도 같아서 원래 같은 키로 취급되어야 하지만, comp 가 양방향으로 true 라 동치 판정식이 거짓이 되고 둘 다 별개 노드로 들어간다 → size=4.
반대로 find 는 !comp(key, *it) 를 확인하는데 comp(k, k) 가 true 라 항상 실패한다. 넣은 키를 자기 자신으로도 찾지 못한다. operator[] 로 넣은 값에 접근할 수 없는 "유령 엔트리"가 생긴다.

여기에 더해 mmr / 100 버킷화 자체도 문제다. 1299 와 1310 은 실제 MMR 차이가 11 인데 버킷이 달라 다른 키가 되고, 1250 과 1299 는 49 차이인데 같은 키가 된다. 경계 근처에서 매칭 품질이 불연속으로 튄다.

올바른 비교자는 계단식 + strict 이어야 한다.

struct QueueKeyLess {
    bool operator()(const QueueKey& a, const QueueKey& b) const {
        if (a.mmr != b.mmr) return a.mmr < b.mmr;
        return a.playerId < b.playerId;     // < 이지 <= 가 아니다
    }
};

버킷 매칭이 목적이라면 버킷을 키의 일부로 명시적으로 저장하고, 검색 시 lower_bound/upper_bound 로 범위 질의를 하는 편이 훨씬 안전하다.

Case 5 — NaN

a.score < b.score 에서 어느 한쪽이 NaN 이면 IEEE 754 규칙에 따라 모든 비교가 false 다. NaN < x 도 거짓, x < NaN 도 거짓, NaN < NaN 도 거짓.

비반사성은 지켜지지만(NaN < NaN 은 거짓) 나머지가 무너진다.

equiv(NaN, 0) = !false && !false = 참
equiv(NaN, 5000) = 참
그런데 equiv(0, 5000) 은 거짓 (0 < 5000)

즉 NaN 은 모든 값과 동치가 되어 비교 불가의 추이성을 즉시 깨뜨린다. NaN 이 하나만 있어도 SWO 가 성립하지 않으며, std::sort 는 UB 에 들어간다.

실측에서 Case5 는 크래시 없이 0 56 48 40 8 1 57 49 ... 처럼 완전히 뒤섞인 결과를 냈다. NaN 이 파티션의 sentinel 역할을 못 하면서 정렬이 사실상 무작위 셔플이 된 것이다. 이어지는 std::binary_search 는 정렬된 구간을 전제로 하는데 구간이 정렬돼 있지 않으므로 반환값이 아무 의미가 없다(실측 1 이 나왔지만 우연이다).

게임서버에서 NaN 은 흔히 이렇게 들어온다.

0.0f / 0.0f — 판정 수가 0 인 승률 계산
std::sqrt(음수) — 부동소수 오차로 음수가 된 분산
inf - inf — 누적 점수 오버플로 후 보정
클라이언트나 DB 에서 그대로 들어온 값

방어는 정렬 직전이 아니라 값이 만들어지는 지점에서 해야 한다.

// 1) 진입 시 검증 — 오염된 값을 아예 들이지 않는다
if (!std::isfinite(e.score)) {
    LOG_ERROR("non-finite score for player {}", e.id);
    e.score = 0.0f;
}

// 2) 그래도 방어가 필요하면 NaN 을 한쪽 끝으로 몰아 전순서를 복원한다
auto key = [](float s) { return std::isnan(s) ? -std::numeric_limits<float>::infinity() : s; };
std::sort(v.begin(), v.end(), [&](const Entry& a, const Entry& b) {
    float ka = key(a.score), kb = key(b.score);
    if (ka != kb) return ka < kb;
    return a.id < b.id;
});

C++20 의 std::strong_order / std::weak_order 는 NaN 을 포함해 부동소수에 전순서를 부여하므로 이런 상황에 바로 쓸 수 있다.

흔한 오해·함정

"비교자가 이상하면 정렬 결과만 이상해진다" — 아니다. 전제 조건 위반이므로 UB 다. 표준은 Compare 요구사항을 만족하지 않으면 동작을 정의하지 않으며, 실제 구현은 성능을 위해 경계 검사를 뺐기 때문에 메모리를 밟는다.
"작은 데이터로 테스트했는데 안 죽더라" — 원소 16 개 이하면 introsort 를 타지 않는다. 운영 데이터 규모에서 처음 터진다.
"std::stable_sort 는 안전하다" — 아니다. merge sort 기반이라 out-of-bounds 는 덜하지만 SWO 는 똑같이 요구되며 결과는 여전히 UB 다. 안정성은 SWO 를 지킨 다음의 이야기다.
"동점이면 <= 로 써야 안정 정렬이 된다" — 정반대다. <= 는 비반사성을 깨서 UB 를 만든다. 안정성이 필요하면 std::stable_sort 를 쓰거나 tie-breaker 키(id)를 넣는다.
"std::map 의 키 비교는 operator== 를 쓴다" — 쓰지 않는다. !comp(a,b) && !comp(b,a) 만으로 판정한다. 그래서 operator== 와 비교자의 의미가 어긋나면 find 는 되는데 == 는 false 인(또는 그 반대인) 상황이 생긴다.
"부동소수 비교는 epsilon 을 써야 한다" — 값의 동등성 판단에는 맞지만 정렬 비교자에는 쓰면 안 된다. tolerance 관계는 추이적이지 않다. 정렬이 필요하면 먼저 양자화한다.
-D_GLIBCXX_DEBUG 나 MSVC 의 반복자 디버그 레벨을 디버그 빌드에 켜 두면 이 부류의 버그를 릴리스 전에 잡을 수 있다. 성능이 크게 떨어지므로 CI 전용으로 쓴다.

면접 포인트

"strict weak ordering 의 네 조건을 말하고, 그중 가장 자주 어기는 것은?" — 비교 불가의 추이성. epsilon 비교, NaN, 다중 키를 || 로 이은 비교자가 전형적인 사례다.
"std::sort 에 <= 를 넘기면 무슨 일이 나는가?" — 비반사성이 깨져 UB. __unguarded_linear_insert 와 __unguarded_partition 의 경계 검사 없는 루프가 구간 밖으로 나가 힙을 손상시킨다. 실측상 원소 1,000 개면 즉시 SIGSEGV.
"왜 표준 라이브러리는 경계 검사를 넣지 않는가?" — 정렬의 내부 루프에서 매번 반복자를 비교하면 상수 배로 느려진다. SWO 라는 전제를 사용자에게 요구하는 대신 sentinel 성질로 검사를 제거한 것이 introsort 성능의 핵심이다. 전제와 성능의 교환이다.
"std::map 은 두 키가 같은지 어떻게 판단하는가?" — !comp(a,b) && !comp(b,a). operator== 는 관여하지 않는다.
"랭킹에서 동점자 처리를 어떻게 하나?" — 비교자를 느슨하게 만들지 말고 tie-breaker 키를 추가해 전순서를 만든다(점수 → 달성 시각 → 플레이어 ID). 전순서가 되면 서버 재시작이나 샤드가 달라도 순위가 동일하게 재현된다.
"NaN 이 섞인 데이터를 정렬하려면?" — 진입 시점에 std::isfinite 로 걸러 내는 것이 원칙이고, 꼭 정렬해야 하면 NaN 을 한쪽 끝으로 사상하거나 C++20 의 std::strong_order 를 쓴다.

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