strict weak ordering은 수학의 순서론에 등장하는 한 개념으로, 이것저것 깊게 파고들어가면 끝이 없을 것 같으므로 딱 본론만 말하겠다(사실 내가 깊이있게 설명할 수 있을 정도로 지식을 갖추지 못했다).

이게 어디에 쓰이는가?

갑자기 웬 수학얘기를 하는가 싶을 수도 있지만, 이는 프로그래밍에서도 중요한 부분이다. 가장 친숙하게 이 개념을 볼 수 있는 부분은 정렬할 때 std::sort 함수를 사용하는 상황이 아닐까 싶다.

#include <vector>    // vector
#include <algorithm> // sort

vector<int> vec{ 1, 6, 3, 7, 9, 4, 2 };
sort(vec.begin(), vec.end());

기본적으로, 이렇게 앞 뒤 이터레이터를 넘겨주면 < 연산자를 사용하여 오름차순으로 정렬해준다. 이는 다음과 같이 써도 같은 결과를 얻을 수 있다.

#include <functional> // less

sort(vec.begin(), vec.end(), less<int>());

less는 operator()가 오버로딩 되어있는 템플릿 구조체로, 생성자를 호출하여 넘겨주면 sort 함수의 comp가 이를 받아서 사용하는데, less가 곧 < 연산자를 사용하기 때문에 그게 그거다. 만약 내림차순으로 정렬하고자 한다면 다음처럼 하면 된다.

sort(vec.begin(), vec.end(), greater<int>());

sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });

greater 내부는 > 연산자를 사용한다. greater를 쓰든, 람다 함수를 작성하든, 적절히 일반 콜백함수를 만들어서 넘겨주든 하면 된다.

지금까진 단순히 오름차순 또는 내림차순을 확인해봤지만, 만약 비교의 조건이 복잡해지면 어떨까? 가령, 사용자 정의 구조체에 여러 개의 멤버 변수가 있어서 여러 우선순위에 의해 비교가 정해지는 상황을 생각해 보자. 이 경우 직접 비교함수를 작성할 수밖에 없을 것이다.

여기서 strict weak ordering이 등장

만약 어설프게 비교함수를 작성하면 프로그램을 돌렸을 때 런타임 에러를 내뿜으며 죽어버리는 모습을 볼 수 있다.

bool cmp(const T& a, const T& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y <= b.y;
}

sort(vec.begin(), vec.end(), cmp);

vec에 적당히 만든 T라는 구조체가 있고, 이를 정렬하고자 한다. 하지만 이 코드는 에러를 내는 코드다. 그 이유는 cmp 함수가 strict weak ordering을 만족하지 않아서이다.

strict weak ordering

어떤 이항연산 R에 대해서, 다음의 4가지 조건을 만족하면 strict weak ordering을 만족하는 관계라고 할 수 있다.

  1. 비반사성(irreflexivity): 모든 x에 대해 R(x, x)는 거짓
  2. 비대칭성(asymmetry): 모든 x, y에 대해 R(x, y)가 참이면 R(y, x)는 거짓
  3. 추이성(transitivity): 모든 x, y, z에 대해 R(x, y)와 R(y, z)가 참이면 R(x, z)는 참
  4. 비비교성의 추이성(transitivity of incomparability): 모든 x, y, z에 대해 R(x, y)와 R(y, x)가 거짓이고 R(y, z)와 R(z, y)가 거짓이면 R(x, z)와 R(z, x)는 거짓

뭔가 말이 상당히 어렵다. 추이성? 비비고 왕교자? 간단히 예시를 들어보자. 여기서 이항연산 R을 <라는 연산으로 대입해서 생각하면 쉽다. 참고로 비비교성이란 비교할 수 없다는 뜻인데, x < y도 거짓이고 y < x도 거짓이면 x와 y는 비교할 수 없음을 의미이며 여기서 이는 곧 동등하다는 뜻이다. 즉, 비비교성은 동등성과 같다.

  1. 모든 x에 대해 x < x는 거짓 (비반사성!)
  2. 모든 x, y에 대해 x < y이면 y < x는 거짓 (비대칭성!)
  3. 모든 x, y, z에 대해 x < y이고 y < z이면 x < z (추이성!)
  4. 모든 x, y, z에 대해 x == y이고 y == z이면 x == z (동등성의 추이성!)

따라서, < 연산은 strict weak ordering을 만족한다.

결론

strict weak ordering을 만족하게 비교 연산을 정의해야 한다. 이는 비단 sort 함수에서만 신경쓸 게 아니라 set, priority_queue, lower_bound, merge, includes, make_heap, max_element, next_permutation 등 다양한 표준 라이브러리에서도 사용되고 있으므로 계속 염두에 두고 코딩하는 습관을 들이는 것이 좋을 것이다.

Reference