팁

Strict Weak Ordering

비교에도 규칙이 있다

Optatum

2019년 11월 3일 • 4 min read

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을 만족하지 않아서이다.