ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 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>

    댓글

Designed by Tistory.