우선순위 큐 사용시 비교기 정의가 기억나지 않을 때

 

사용자 정의 자료형을 사용해 우선순위 큐를 사용할 때는 보통 아래와 같이 사용한다.

• 비교기 클래스를 선언하고, 크기를 비교하는 () 연산자를 오버로딩한다.
• priority_queue<TYPE, vector<TYPE>, 비교기> 형식으로 선언한다.

 

#include <iostream>
#include <queue>

using namespace std;

struct Job
{
    int start;
    int duration;
};

class compare
{
public:
    bool operator () (const Job& A, const Job& B) { return A.duration > B.duration; }
};

void main()
{
    priority_queue<Job, vector<Job>, compare> prQue;

    prQue.emplace(Job {0, 4});
    prQue.emplace(Job {1, 2});
    prQue.emplace(Job {2, 7});
    prQue.emplace(Job {3, 5});

    cout << "[top] start = " << prQue.top().start << ", duration = " << prQue.top().duration << endl;
}

 

출력

[top] start = 1, duration = 2

 

근데 이 비교기 정의가 생각이 안 날 수도 있다.

 

그럴 때는 좀 더 쉽고 직관적인 방법을 사용할 수 있다.

 

사용자 정의 자료형 안에 < 연산자를 직접 오버로딩하는 것이다.

• 비교기를 구현하지 선언하지 않아도 된다.
• () 연산자 대신 직관적인 < 연산자를 오버로딩한다.
• priority_queue<TYPE> 형태 그대로 선언할 수 있다.

 

friend 키워드를 붙인 이유는 실제로는 클래스 밖에 구현해야 할 인자를 2개 받는 함수이기 때문이다.

 

#include <iostream>
#include <queue>

using namespace std;

struct Job
{
    int start;
    int duration;

    friend bool operator < (const Job& A, const Job& B) { return A.duration > B.duration; }
};

void main()
{
    priority_queue<Job> prQue;

    prQue.emplace(Job {0, 4});
    prQue.emplace(Job {1, 2});
    prQue.emplace(Job {2, 7});
    prQue.emplace(Job {3, 5});

    cout << "[top] start = " << prQue.top().start << ", duration = " << prQue.top().duration << endl;
}

 

출력

[top] start = 1, duration = 2