[C++] Priority Queue의 custom sort

부제: Custom sort의 늪에 빠진 꼬부기... 이제 탈출 각 보이나?

 

이전에도 한번 custom sort의 늪에 빠져서 @mttw2820에게 궁금증을 쏟아낸 적이 있었다. 그때 해결한 궁금증은 맽튜가 정리한 이곳에서 확인하실 수 있음.

 

아무튼, 지난번에는 functional 함수 객체 (less<int> 이런 애들), bool compare 함수 정의, operator < 오버로딩 등에 대해서 알아보았다.

 

오늘의 문제는 priority_queue에서 발생하였다.

 

나는 보통 문제를 풀 때, 구조체를 만들어서 사용하는 것을 선호한다. 뭔가 깔꼼쓰한 모양새랄까. 그래서 sort 등을 할 때도 compare 함수를 만들어서 사용할 수 밖에 없는 경우가 많은데, 오늘은 priority queue를 정렬하는데 문제가 생겼다.

---

사건의 발단

분명히 맽튜와 지난번에 발견한 바로는, 여기에서 확인한 것과 같이 bool 리턴 형식의 compare 함수를 만들 때 앞의 원소가 그대로 앞에 남길 원한다면 true를 반환 하도록 함수를 정의하면 됐다.

 

예를 들어, 내림차순 정렬을 위한 compare 함수는 다음과 같이 정의된다.

bool compare(const int a, const int b)
{
    return a > b;
}

a가 배열에서 앞에 오는 원소이고, b가 배열에서 뒤에 오는 원소이므로 앞의 원소가 뒤의 원소보다 크면 이미 내림차순이므로 앞의 원소가 그대로 앞에 남길 원한다. 따라서, 그럴 경우 true를 리턴하도록 하면 됐다.

 

그래서 난 오늘도 아무 생각 없이 이걸 떠올리고, priority queue에서 bool compare 함수를 쓰려 했지만 컴파일러가 응 안돼 돌아가 하고 거부했다.

/solution0.cpp:33:42: error: template argument for template type parameter must be a type
    priority_queue<stock, vector<stock>, compare> pq;
                                         ^~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:442:14: note: template parameter is declared here
           typename _Compare  = less<typename _Sequence::value_type> >
                    ^
1 error generated.

대충 보면 template type을 위한 template argument는 아래의 타입이어야만 해!!! 라는 뜻인 것 같은데

뭔소리야 저게

 

대충 생각해보면, 이게 priority_queue를 선언하는 도중 <어쩌구> 여기에 들어가는 template argument 이므로, 이 브라켓 안에 들어가는 애들은 template type이어야 한다는 소리일 것이다.

 

그럼 어떻게 priority queue를 custom sort할까?

Custom sort 방법

잡설

열심히 찾아보니, 구조체 형식으로 bool operator() 를 오버라이딩 해서 사용하면 된다고 한다.

 

근데 사실 얘를 왜 이렇게 오버라이딩을 해야하는지는 아직 찾지 못했다.

 

어떤 곳에서는 priority queue가 () 연산자를 사용한다고 하기도 하는데, 대충 조금 더 찾아본 바로는 Stackoverflow - Why override operator()? 여기에서와 같이 functor 를 만들면서 객체를 함수로 사용할 수 있도록 한다.

 

근데 정확한 이유는 모르겠다. 이렇게 오버라이딩을 하면 만든 구조체가 template type이 되는 건가?

 

아시는 분은 댓글 남겨주세요.. 저도 알고싶어요..

 

방법

CPlusPlus - std::priority_queue를 살펴보면, 아래와 같다.

 

priority queue는 위의 설명과 같이 heap 구조와 비슷하게 작동하는 것이다. heap 구조처럼 언제나 새로운 객체가 삽입될 수 있고, priority queue의 top에 있는 원소만이 반환된다.

 

여기서 우리가 헷갈리지 말야아 할 부분이 있다.

비록 나는 헷갈렸지만

 

위에서 sort와 같은 함수에서 bool을 return 하는 compare 함수를 작성할 때에는, 앞에 있는 원소가 뒤에 있는 원소보다 앞에 와야할 때 true를 리턴하도록 한다. 그래서 내림차순을 구현하기 위해 아까 위에서 다음과 같이 compare 함수를 구성했었다.

bool compare(const int a, const int b)
{
    return a > b;
}

그래. 내림차순을 기준으로, 배열을 정렬했을 때에는 배열의 앞 (arr[0])에 있는 것이 가장 큰 원소일 것이다.

 

하지만, priority queue는 다르다.

 

위의 사진에서 마지막 줄을 보면, priority queue의 top 원소는 container의 back 에 있는 원소이다.

 

container가 배열은 아니지만, 배열로 대충 생각을 해서 이해를 해 보면 내림차순을 정렬했을 때 가장 마지막 원소가 가장 큰 원소여야 한다.

 

다만, compare 함수는 다음과 같이 true를 리턴했을 때 앞에 있는 원소 a가 뒤에 있는 원소 b보다 앞에 와야 하나는 것으로 위와 똑같다. 따라서, 내림차순으로 정렬해야 할 때는 앞의 원소가 뒤의 원소보다 크다면 false를 리턴하여 a를 뒤로 보내야 한다는 것이다!

 

따라서, 내림차순으로 priority queue를 정렬하기 위해서는 아래와 같이 사용해야 한다. 아래의 코드는 priority queue를 stock 타입으로 만들고, stock의 price를 기준으로 내림차순 정렬을 하도록 하는 함수이다.

struct stock{
    int index;
    int price;

    stock(int _index, int _price){
        index = _index;
        price = _price;
    }
};

// price를 기준으로 내림차순 정렬할때 사용
struct compare{
    bool operator()(const stock a, const stock b){
        return a.price < b.price;
    }
};

int main()
{
    priority_queue<stock, vector<stock>, compare> pq;
}

안까먹어야지..