[C++ 기초] STL priority_queue 템플릿 클래스

 

 

 

 

STL priority_queue 템플릿 클래스

std::priority_queue<> 클래스는 <queue> 헤더 내에 포함된 컨테이너로, 비선형 자료 구조 중의 하나인 우선순위 큐(priority queue) 역할을 하는 컨테이너이다. 우선순위 큐는 종종 알고리즘 문제를 해결하기 위해 쓰이는데 힙(heap) 트리를 직접 만들어 구현할 수도 있으나, 편의상 매번 해당 자료 구조들을 직접 구현하는 것이 번거로워 STL에서 제공하는 템플릿 클래스 사용법을 정리해놓으려고 한다.

 

// std::priority_queue<> 클래스의 템플릿 매개변수

template
<
	class _Ty,
	class _Container = vector<_Ty>,
	class _Pr = less<typename _Container::value_type>
>

 

• _Ty : 일반화 된 자료형.
• _Container : 임의 접근 반복자(random access iterator)를 가지는 시퀀스 컨테이너.
• _Pr: 이항 조건(binary predicate)인 함수 객체(펑터, functor)로, strict weak ordering을 따르는 관계 연산이어야 한다.

 

용법이 어려워보이지만, 일반적으로 _Container로는 STL 컨테이너 중 가장 익숙한 것 중의 하나인 std::vector를 사용하며(이때 <vector> 헤더를 포함하지 않아도 된다) _Pr는 <functional> 헤더를 포함하여 사용 가능한 less<> 또는 greater<>와 같은 펑터를 이용하거나 아래와 같이 직접 정의한 자료형에 맞게 구현하여 사용할 수 있다.

 

// 함수 호출 연산자 ()를 오버로딩을 통한 함수 객체(펑터, functor) 구현

struct MyStruct
{
	int X;
	int Priority;
};

struct cmp
{
	bool operator()(MyStruct a, MyStruct b)
	{
		if (a.Priority == b.Priority)
			return a.X > b.X;

		return a.Priority > b.Priority;
	}
};

 

std::priority_queue<> 클래스의 템플릿 매개변수 _Container와 _Pr의 경우에는 별도로 지정하지 않으면 디폴트 값이 주어지는 매개변수이므로, std::priority_queue<int> 와 같이 사용할 수도 있다. 이 경우에는 int 형의 데이터 값이 클 수록 우선순위가 높은 경우에 사용할 수 있는 우선순위 큐를 나타낸다.

 

 

---

 

std::priority_queue<> 클래스의 사용 시 주의점

위의 코드와 같이 사용자 정의 자료형에 대해서도 비교 연산 결과를 정의하는 이항 조건(반환형이 bool 형인 함수 객체)을 만들어 사용하는 것이 코드적으로는 크게 어렵지 않지만 주의점이 몇 가지 있다.

 

• 이항 조건이 나타내는 관계 연산은 strict weak ordering을 따라야 한다.
• 값이 작은 요소의 우선순위를 높게 설정하려면 '>' 연산자를, 반대의 경우는 '<' 연산자를 사용한다.

 

첫 번째 주의점과 같은 경우는 순서론(order theory)이라는 분야에서 등장하는 개념으로, 이론적으로 파고들려면 조금 어렵다. 일반적으로 비교 함수를 짤 때, 모순이 발생하지 않도록 하기 위한 조건이라고 생각해도 된다. Strict weak ordering을 만족하기 위한 디테일한 조건은 별도로 포스팅하였다.

 

두 번째 주의점은 값이 작은 순으로 데이터의 우선순위를 설정하려면 less 연산자('<')가 아닌 greater 연산자('>')를 사용해야된다는 점이다. 이 점이 헷갈리고 궁금해서 구글링을 한 결과, 이항 조건이 나타내는 관계 연산 결과가 참이 되도록 요소들을 나열했을 때, priority_queue는 가장 마지막(가장 오른쪽에 위치)의 요소를 우선순위가 가장 높은(largest element) 것으로 간주하기 때문이라고 한다(참고 링크).

 

즉, 10, 2, 7이라는 값과 '<' 연산자를 예로 들면 2 < 7 < 10 순으로 나열되므로 10이라는 값이 가장 우선순위가 높은 것으로 간주된다는 뜻이다. '<' 연산자를 사용하였더니 가장 큰 값부터 차례대로 데이터를 빼내는 우선순위 큐가 되는 것이다.

 

이와 같은 점에 주의하여 이항 조건을 선언하고 priority_queue를 사용하면 다양한 알고리즘 문제를 해결할 때 편리하게 우선순위 큐 자료 구조를 사용할 수 있을 것 같다.

 

---

 

* 해당 카테고리의 글은 Microsoft 공식 홈페이지의 기술 문서 페이지와 Stephan Prata의 저서 C++ 기초 플러스 (6판, 번역본) 서적 및 기타 구글링을 통한 정보 수집 등을 토대로 개인적으로 요약/정리해 본 글입니다. 만약 잘못 정리된 내용이 있다면, 댓글이나 이메일로 공유해주시면 수정하도록 하겠습니다.