C++ 비교함수 오버라이딩
1. 비교함수 오버라이딩
C++에서 algorithm 헤더의 sort 함수를 쓰거나, Priority Queue를 사용할 때
std::sort는 오름차순으로, 우선순위큐는 최대힙으로만 정렬되기 때문에
사용자가 원하는 순서대로 정렬할 수 없다
또한 하나의 원소는 std::less<>, std::greater<>,
두개의 원소는 std::less<pair<>>, std::greater<pair<>>로 어떻게 정렬 가능하지만
세개 이상부터 혹은, 직접 원하는 우선순위가 있을 경우는 비교함수를 오버라이딩이 필요하다
1
2
3
bool compare(const T& a, const T& b) {
// 비교 로직 : 순서가 제대로 되어있다면 true, 바꿔야한다면 false를 리턴
}
정렬과 우선순위 큐 모두 parameter로 compare함수를 넣으면, 원하는 순서로 정렬할 수 있다
2. 하나의 원소 정렬
1
2
3
4
5
template <typename T>
void sort(T start, T end);
template <typename T>
void sort(T start, T end, Compare comp);
sort 함수는 다음 형태로 오버로딩 되어있다
comp 함수를 명시하지 않으면 자동으로 오름차순으로 정렬된다
내림차순으로 정렬하고 싶다면
sort(v.begin(), v.end(), greater<자료형>()); 처럼 std::less<>, std::greater<>를 사용하거나
비교함수 오버라이딩을 통해 비교함수를 만들고 이를 콜백하도록 해주면 된다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 비교함수 오버라이딩 예제
struct compare {
bool operator()(int first, int second) {
return first > second; // 내림차순으로 정렬
/* 위와 동작은 같으나 더 풀어서 쓴 버전
if (first < second) return false;
else return true;
*/
}
};
int main() {
vector<int> v;
v.push_back(5);
v.push_back(3);
v.push_back(4);
v.push_back(2);
v.push_back(1);
sort(v.begin(), v.end(), compare()); // 오버라이딩한 비교함수를 콜백
for (int e : v) {
cout << e << " ";
}
// v : 5 4 3 2 1
return 0;
}
비교 함수를 작성시에 언제 true를 리턴하는지 이해하는것이 매우 중요하다
비교함수는 두 개의 인자를 받아 첫 번째 인자가 두 번째 인자보다 앞에 위치해야 한다고 판단되면 true 를 반환한다
위의 비교함수에서 자리를 바꾸는 과정을 살펴보면
- 첫번째 원소와 두번째 원소 비교 : compare(5, 3)
first=5 > second=3이므로 true (즉,first가 크다)first > second는true이므로, 자리를 바꿀 필요 없음- 비교함수는
true를 리턴함 - sort는
true를 리턴받았으므로 원소의 자리를 바꾸지 않음 - 큰 값이 앞으로 가게 된다
- 두번째 원소와 세번째 원소 비교 : compare(3, 4)
first=3 <= second=4이므로, false (즉, second가 크다)first > second는 false이므로, 비교함수는false를 리턴함- sort는
false를 리턴 받았으므로, 원소의 자리를 교환함 - 큰 값인 4가 3의 앞으로 간다
정 햇갈리면
오름차순은 <, 내림차순은 >로 외우고 작성하면 된다
- sort 기본 사용법 다양한 sort 기법들을 잘 정리해둔 글
3. 구조체 비교에서 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Person {
string name;
int age;
double height;
};
bool compare(const Person& a, const Person& b) {
// 1순위: 나이 (내림차순)
if (a.age != b.age) {
return a.age > b.age;
}
// 2순위: 이름 (사전순)
if (a.name != b.name) {
return a.name < b.name;
}
// 3순위: 키 (오름차순)
return a.height < b.height;
}
그냥 sort 해버리면 일치하는 호출 연산자를 찾을 수 없다고 오류 발생하므로,
직접 원하는 순서대로 비교 함수를 정의해주면 된다
여러 조건이 겹치면 은근 햇갈리는데, 사람마다 작성하는 방법도 가지각색이므로
자신만의 작성법을 만들어두는게 좋다고 생각함
개인적으로는 순위별로 작성하는게 가독성이 좋고 이해도 쉬웠다
4. 우선순위 큐에서 사용
이 포스팅을 작성하게 된 계기
우선순위 큐에 비교할 요소가 3개 이상있을 경우, 구조체의 비교와 마찬가지로
비교함수를 마찬가지로 오버라이딩을 해야한다
코드는 위의 코드에 우선순위 큐만 비교를 위해 추가했다
그러나 같은 비교함수를 사용했음에도 불구하고, 구조체 비교와 다른 결과를 출력한다
이는 C++의 우선순위큐가 최대힙으로 동작하기 때문인데
구조체 비교함수의 반대로 작성해야 의도대로 동작한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct compare {
bool operator()(const Person& a, const Person& b) {
// 1순위 : 나이(우선순위 큐 기준 내림차순, 구조체 기준 오름차순)
if (a.age != b.age) {
return a.age < b.age;
}
// 2순위 : 이름(우선순위 큐 기준 사전순, 구조체 기준 역사전순)
if (a.name != b.name) {
return a.name > b.name;
}
// 3순위 : 키(우선순위 큐 기준 오름차순, 구조체 기준 내림차순)
return a.height > b.height;
}
};
즉, C++에서 우선순위 큐는 최대힙으로 동작하기 때문에, 비교함수를 구현 시 한번 더 뒤집어줘야한다