std::priority_queue 정리

헤더

#include <queue>

 

기본 형태

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

priority_queue는 heap 자료구조로 compare 기준으로 정렬되서 나열되어 있는 컨테이너이다.

default로 compare가 less 로 설정(내림차순)으로 설정되어있다.

 

파라미터

T	저장되는 element type
Container	elememt를 저장할 때 사용하는 컨테이너
Compare	정렬할 기준 priority_queue는 가장 큰 element를 먼저 output하기 때문에  queue의 앞에는 약간 순서 대로 정렬되어 있다.

 

멤버 타입

member type	definition
container_type	Container
value_compare	Compare
value_type	Container::value_type
size_type	Container::size_type
reference	Container::reference
const_reference	Container::const_reference

 

멤버 함수

Element access

top

top 요소 접근

Capacity

empty	컨테이너가 비어있는지 확인
size	element 수

Modifiers

push	element 삽입
emplace	push와 비슷한데 construct elements in-place 해서 바로 삽입 pair<int,int> 데이터 타입 경우 emplace(1,1)로 가능 make_pair 안써도 됨
pop	top element 제거
swap	내부에서 element swap

 

C++17 Deduction guides

다양한 형태

template <class Comp, class Container>
priority_queue(Comp, Container)
 -> priority_queue<typename Container::value_type, Container, Comp>;
 
template<class InputIt,
         class Comp = std::less</*iter-value-type*/<InputIt>>,
         class Container = std::vector</*iter-value-type*/<InputIt>>
priority_queue(InputIt, InputIt, Comp = Comp(), Container = Container())
  -> priority_queue</*iter-value-type*/<InputIt>, Container, Comp>;
  
template<class Comp, class Container, class Alloc>
priority_queue(Comp, Container, Alloc)
  -> priority_queue<typename Container::value_type, Container, Comp>;
  
template<class InputIt, class Alloc>
priority_queue(InputIt, InputIt, Alloc)
  -> priority_queue</*iter-value-type*/<InputIt>,
                    std::vector</*iter-value-type*/<InputIt>, Alloc>,
                    std::less</*iter-value-type*/<InputIt>>>;
                    
template<class InputIt, class Comp, class Alloc>
priority_queue(InputIt, InputIt, Comp, Alloc)
  -> priority_queue</*iter-value-type*/<InputIt>,
                    std::vector</*iter-value-type*/<InputIt>, Alloc>, Comp>;

template<class InputIt, class Comp, class Container, class Alloc>
priority_queue(InputIt, InputIt, Comp, Container, Alloc)
  -> priority_queue<typename Container::value_type, Container, Comp>;

예시

priority_queue pq {std::greater<int>{}, v}; // deduces std::priority_queue<
                                                     //   int, std::vector<int>,
                                                     //   std::greater<int>>

priority_queue pq {v.begin(), v.end()}; // deduces std::priority_queue<int>