[C++] std::sort 사용시 invalid comparator가 발생한 경우.

std::sort를 사용해서 정렬을 해보고 있었는데 아래와 같은 스크린샷이 나오면서 invalid comparator라는 메시지를 던지고 죽어버렸다.

무엇인지 살펴보자.   

 

 

첫번째의 MessageBox에서 다시 시도를 눌러보니 두번째 스크린샷의 지점을 가리키고 있었다.

// test if _Pred(_Left, _Right) and _Pred is strict weak ordering, when the arguments are the cv-same-type

친절하게도 주석에 위와같이 적혀있었다.

번역하자면 

// 인수가 cv-same-type일 때 _Pred(_Left, _Right) 및 _Pred가 엄격한 약한 순서인지 테스트합니다.

이 엄격한 약한 순서(strict weak ordering)인지 테스트한다는게 무슨말인가..

 

찾다보니 cppreference에서 위키피디아의 글로 링크가 걸려있었다.

https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

Weak ordering - Wikipedia

대강 읽어 보자면...

Two elements  x and y of S are said to be incomparable with respect to  if neither x < y nor y < x is true.

S의 두 요소 x와 y는 x < y도 y < x도 참이 아닌 경우 비교할 수 없다고 합니다.

`x < y도 y < x도 참이 아닌 경우 비교할 수 없다` 그렇다는것은 x == y 인 경우 밖에 없다.

저런 예 처럼 비교 할 수 없을때 invalid comparator가 발생 하는것 같다.

->구글링으로 invalid comparator를 찾아보니 보통 같다고 판단되어 비교가 불가능한 경우에 발생한 사람들이 많은것 같다.

 

일단 잘못 작성한 코드를 보자.

int main()
{
	std::vector<std::pair<int, int>> Result = { {1,10}, {8,4}, {2,5}, {6,7}, {-3,45} };
	
	std::sort(Result.begin(), Result.end(), 
    		[](const std::pair<int, int>& left, const std::pair<int, int>& right) -> bool
		{
			return left.first > right.second;
		});

	return 0;
}

원래 의도는 pair의 first값으로 정렬을 하고 싶었으나 first와 second를 비교하라고 오타를 내서 문제가 생겨났다.

디버깅을 해보니 문제가 되었던것은 아래와 같았다.

8, 4	>	1, 10		false
2, 5	>	1, 10		false
2, 5	>	8, 4		false
6, 7	>	1, 10		false
6, 7	>	2, 5		true
2, 5	>	6, 7		false
6, 7	>	8, 4		true
8, 4	>	6, 7		true	---> invalid comparator

(6,7) > (8,4)가 true라고 했지만 뒤집어서 (8,4)와 (6,7)도 true라는 결과가 나와버려서 발생했다.

적절하게 고쳐주면...

int main()
{
	std::vector<std::pair<int, int>> Result = { {1,10}, {8,4}, {2,5}, {6,7}, {-3,45} };
	
	std::sort(Result.begin(), Result.end(), 
    		[](const std::pair<int, int>& left, const std::pair<int, int>& right) -> bool
		{
			return (left.first == right.first) ? false : (left.first > right.first);
		});

	return 0;
}

일단 같은 first끼리 비교를 하도록 했고 혹시 모를 둘이 같다면 그냥 false를 리턴하도록 수정했다.

 

정렬이 잘된 모습이다.

 

---

아래는 정보를 찾다가 방문한 페이지들이다.

 

https://en.cppreference.com/w/cpp/algorithm/sort

std::sort - cppreference.com

https://en.cppreference.com/w/cpp/named_req/Compare

C++ named requirements: Compare - cppreference.com

https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

Weak ordering - Wikipedia