C++의 sort() 함수는 직접 비교함수를 작성해서 정렬할 수 있다. 비교함수는 두 개의 파라미터를 가지며(비교하려는 원소 a와 b) bool값을 반환하도록 작성해야 한다. 이때, 두 원소의 순서가 올바르면 true, 아니면 false를 반환토록 한다. 예를 들어 오름차순 정렬을 하고 싶다면 a < b이면 true, else는 false를 반환하면 된다.
비교함수는 Strict Weak Ordering을 준수해야 한다. 이를 준수하지 않고 프로그램을 작성하면 비주얼 스튜디오에서는 "Expression: invalid comparator"라는 에러를 맞닥뜨릴 것이다.
Strict Weak Ordering은 다음의 네 가지 조건을 만족해야 한다.
1) irreflexivity(비반사성)
- 모든 x에 대해 R(x, x)는 거짓.
- 즉, cmp(a, a)는 false를 반환해야 한다.
2) antisymmetry(비대칭성)
- 모든 x, y에 대해 R(x, y)가 참이면 R(y, x)는 거짓.
- 즉 cmp(a, b) != cmp(b, a)이다.
3) transitivity(추이성)
- 모든 x, y, z에 대해 R(x, y)와 R(y, z)가 참이면 R(x, z)도 참.
- 즉, cmp(a, b)와 cmp(b, c)가 모두 true를 반환했다면 cmp(a, c)도 true를 반환해야 한다.
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)는 거짓
- 즉, cmp(a, b)와 cmp(b, a)가 모두 false를 반환하고 cmp(b, c)와 cmp(c, a)가 모두 false를 반환하면 cmp(a, c)와 cmp(c, a)도 false를 반환해야 한다.
'프로그래밍 > C++' 카테고리의 다른 글
| C++ - 힙 관련 STL(make_heap, push_heap, pop_heap) (0) | 2022.01.04 |
|---|