개요

priority_queue에서 구조체나 pair같은 다수의 값을 사용할 때 비교함수 작성하는 법이다.

priority_queue

우선순위 큐는 기본적으로
priority_queue<자료형, 구현체 , 비교 연산자> 순으로 정의된다.

• 자료형에는 기본자료형 int, float등등 부터 직접 구현한 구조체나 클래스가 들어간다.
• 구현체에는 자료형을 담을 컨테이너를 말하는데 디폴트값은 자료구조 vector이다.
• 비교연산자에는 디폴트로는 less<자료형>이며 큰 값부터 나온다.
  greater<자료형>을 사용시 작은 값부터 나온다.

priority_queue의 자료형으로 구조체를 이용할 때

#include<iostream>
#include<queue>
using namespace std;

//구조체 
struct abcd {
	int first;
	int second;
};

//구조체 연산자 구현 
bool operator <(abcd a, abcd b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

priority_queue<abcd> pq;

int main() {

	pq.push({ 1, 3 });
	pq.push({ 2, 1 });
	pq.push({3, 4});
	pq.push({ 4, 5 });
	pq.push({ 5, 7 });
	while (!pq.empty()) {
		cout << pq.top().second<<'\n';
		pq.pop();
	}
	
}

이런식으로 구조체의 연산자를 두번째 값이 내림차순으로 정렬되게 구현한 후
priority_queue< abcd >에 값들을 넣어주니

잘 작동이 된다.

//구조체 연산자 구현 
bool operator <(abcd a, abcd b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

이 비교연산자 <을 오버라이딩 하는 과정에서 return a.second< b.second라고 작성하면
second값이 큰값부터 top에 나오도록 정렬된다.

작은 값부터 나오게 하려면 반대로 return a.second>b.second이렇게 돌려주면 된다.

구조체 비교함수 작성

위의 코드는 연산자를 오바리이딩 하는식으로 구현 했다면,
비교함수를 직접 작성할 수도 있다.

위의 코드의 연산자< 오버라이딩하는 부분을

struct cmp {
	bool operator() (abcd a, abcd b) {
		if (a.second != b.second) {
			return a.second < b.second;
		}
		else {
			return a.first > b.first;
		}
	}
};

이와 같이 구조체 cmp안에 operator()를 overload 하는 구조로 작성한 뒤,

priority_queue<abcd,vector<abcd>,cmp> pq;

이런식으로 자료형, 구현체, 비교함수 순으로 priority_queue를 선언해주면 된다.

생각

pair<>같은 경우는 이미 연산자 <가 overload 되어있어 first값 기준으로 동작하더라.
비교함수를 따로 작성해서 넣어줬더니 second값을 기준으로 잘 정렬된다.