-
std::priority_queue 정리C++/STL 2022. 4. 7. 15:02
헤더
#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>