[C++] 맵과 우선 순위 큐에서 정렬 기준 재정의하기

1. 맵에서 비교 연산자 재정의하기

#include <iostream>
#include <map>

// std::pair의 비교 연산자를 재정의하여 첫 번째 요소를 기준으로 정렬
struct PairCompare {
    bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) const {
        return a.first < b.first;
    }
};

int main() {
    std::map<std::pair<int, int>, std::string, PairCompare> myMap;

    myMap[{1, 2}] = "One Two";
    myMap[{3, 4}] = "Three Four";
    myMap[{2, 1}] = "Two One";

    for (const auto& entry : myMap) {
        std::cout << "(" << entry.first.first << ", " << entry.first.second << "): " << entry.second << std::endl;
    }

    return 0;
}

PairCompare을 비교 연산자로 사용한 맵은 어떻게 정렬될까? 첫 번째 원소를 기준으로 오름차순으로 정렬된다. 

 

맵은 내부적으로 레드-블랙 트리를 사용한다. 레드-블랙 트리는 높이를 유지해 주는 이진 검색 트리이다. 중요한 점은 맵이 이진 검색 트리라는 점이다. 비교 연산자는 원소의 삽입이 일어날 때 사용된다. 

 

기본적으로 맵은 < 연산자를 사용하여 키를 비교하고 정렬한다. 만약 a < b가 true를 반환하면 a는 b보다 작은 값으로 간주되어 왼쪽에 위치하게 된다. 따라서 맵에 < 연산자를 a < b로 정의한다면 오름차순이 되는 것이다. 맵을 순회할 때 가장 왼쪽 원소부터 순회하고 < 연산자가 a < b라면 작은 값이 왼쪽에 위치하기 때문이다.

 

반대로 < 연산자를 return a > b로 정의하면 큰 값이 왼쪽에 오게 되고 따라서 내림차순으로 정렬된다.

---

2. 우선순위 큐에서 연산자 재정의하기

#include <iostream>
#include <queue>

struct PairCompare {
    bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) const {
        return a.first < b.first;
    }
};

int main() {
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, PairCompare> pq;

    // 예시로 몇 개의 원소를 추가
    pq.push({1, 2});
    pq.push({3, 4});
    pq.push({2, 1});

    // 우선순위 큐에서 원소를 하나씩 꺼내어 출력
    while (!pq.empty()) {
        std::pair<int, int> top = pq.top();
        std::cout << "(" << top.first << ", " << top.second << ") ";
        pq.pop();
    }

    return 0;
}

이번에는 맵과 같은 연산자를 썼음에도 반대로 내림차순으로 정렬된다. 우선순위 큐는 true를 반환하면 더 높은 우선순위를 가지기 때문이다. 예시에서 {2, 1}을 삽입할 때를 보자. {3, 4}와 비교하면 < 연산자가 false를 반환하므로 {2, 1}이 더 낮은 우선순위를 가진다. 따라서 first 값이 클수록 높은 우선순위를 가지는 것이다. 꼭 주의하자!

---

3. 번외

맵의 디폴트 정렬 기준은 오름차순이고 우선순위 큐는 내림차순이다. 특히 맵에서 키를 pair <int, int> 이런 식으로 사용하는 경우가 많을 텐데 pair형의 기본 정렬 기준은 first 기준 오름차순, first가 같다면 second로 오름차순이다. first는 오름차순으로 second는 내림차순으로 적용하고 싶다면 연산자 재정의를 해야 할까?

 

헷갈리게 연산자 재정의 하지 말고 간단하게 second에 -를 붙여보자!

---

4. 결론

우선순위 큐 정렬 기준 설정

우선순위 큐는 기본적으로 최대 힙으로 작동하므로 less <int>를 사용하거나 생략하면 최대 힙, greater<int>를 사용하면 최소 힙으로 동작한다!

struct Person {
    string name;
    int age;

    bool operator<(const Person& other) const {
        return age < other.age; // 나이 기준 내림차순 (최대 힙)
    }

    bool operator>(const Person& other) const {
        return age > other.age; // 나이 기준 오름차순 (최소 힙)
    }
};

연산자 재정의도 똑같이 age < other.age가 디폴트, 즉 최대 힙이라고 외우면 편하다. 최대 힙에서 < 연산자를 사용하므로 같은 말이긴 하다.

 

맵 정렬 기준 설정

맵은 기본적으로 키를 오름차순으로 정렬한다. 따라서 less <int>를 사용하거나 생략하면 키를 오름차순으로 정렬하고 greater <int>를 사용하면 키를 내림차순으로 정렬한다.

연산자 재정의를 할 때 주의해야 하는게, 맵은 < 연산자만 사용한다. 따라서 오름차순으로 정렬하려면 디폴트 값으로

struct Person {
    string name;
    int age;

    bool operator<(const Person& other) const {
        return age < other.age; // 나이 기준 오름차순 정렬
    }
};

이렇게 사용하면 되고, 내림차순으로 하려면 < 연산자를 다르게 재정의해서

struct Person {
    string name;
    int age;

    // 내림차순 정렬을 위해 연산자 재정의
    bool operator<(const Person& other) const {
        return age > other.age; // 나이 기준 내림차순 정렬
    }
};

이렇게 써주면 된다.