[C++] std::priority_queue

2025. 3. 16. 16:00·C | C++/STL
반응형

개요

 C++에서는 우선 순위 큐 자료구조를 갖는 컨테이너 어댑터로 표준 라이브러리의 priority_queue를 사용할 수 있습니다.

priority_queue<int, vector<int>, less<int>> qp;

 priority_queue는 queue의 특징과 다르게 선입선출이 아닌 특정 조건에 따른 우선 순위에 따라 데이터가 처리됩니다. std::queue의 주요 특징은 아래 링크에서 자세히 확인할 수 있습니다.

 

 

[C++] std::queue

개요 C++에서는 큐 자료구조를 갖는 컨테이너 어댑터로 표준 라이브러리의 queue를 사용할 수 있습니다.queue q; queue는 요컨대 선입선출의 특징을 가지며, 주로 비슷하지만 후입선출(LIFO)의 특징을

hyeokjunjjang.tistory.com


특징

  • 컨테이너 어댑터 (Container Adapter)
    • 우선 순위 큐의 자료구조를 사용하면서 실제로 저장되는 컨테이너 형식을 선택할 수 있습니다.
    • 기본적으로 std::vector를 사용하고, 그 외에도 list 등 다른 컨테이너를 사용할 수도 있습니다.
  • 우선 순위에 따른 자동 정렬
    • _Pr 템플릿 매개변수를 이용하여 우선 순위를 결정하는 방식을 선택할 수 있습니다.
    • 내부적으로 힙(Heap) 구조를 사용하여 정렬하며, 기본적으로는 less(내림차순) 정렬 객체를 사용하고, greator(오름차순) 정렬 객체를 사용하거나 사용자가 직접 작성할 수도 있습니다.
    • 요소의 삽입 및 삭제 후 정렬까지 O(log n) 시간 복잡도를 가집니다.
  • 임의/순차적인 접근 제한
    • 단방향 구조로 구성되어 우선순위가 가장 높은 요소(top)의 데이터에만 접근할 수 있습니다.
    • 따라서 priority_queue는 iterator를 지원하지 않으며, 컨테이너 내의 모든 요소를 순회하기 어렵습니다.

 


헤더

#include <queue>

 priority_queue를 사용하기 위해서 <queue> 헤더를 포함해야 합니다.

 


선언 및 초기화

 

템플릿 매개변수

priority_queue<_Ty, _Container = vector<_Ty>, _Pred = less<_Ty>>

 priority_queue는 타입을 선언할 때, 최대 3개의 템플릿 매개변수를 받습니다.

  • _Ty은 실제 저장되는 데이터의 형식을 나타냅니다.
  • _Container는 우선 순위 큐 자료구조를 사용할 컨테이너를 나타냅니다. 지정하지 않으면 기본적으로 std::vector 컨테이너를 사용합니다.
  • _Pred는 데이터를 정렬할 비교 함수 객체를 나타냅니다. 지정하지 않으면 기본적으로 std::less 객체를 사용합니다.

 


생성자

priority_queue<_Ty> pq;

 priority_queue를 선언하면 빈 상태의 우선 순위 큐 컨테이너를 선언할 수 있습니다. 추가로 priority_queue는 중괄호를 이용해 컨테이너의 초기 요소 값을 설정할 수 없습니다.

 

컨테이너와 비교 함수 객체 지정

priority_queue<_Ty> pq(_Container, _Pred);

priority_queue의 사용할 컨테이너와 비교 함수 객체를 설정합니다. 컨테이너만 설정할 수도, 비교 함수 객체만 설정할 수도 있습니다.

  • _Container는 사용할 컨테이너를 나타냅니다.
  • _Pred는 비교 함수 객체를 나타냅니다.

 

iterator 복사

priority_queue<_Ty> pq(_First, _Last);

 다른 컨테이너의 iterator를 이용하여 요소를 복사합니다. _Last 매개 변수 뒤에 컨테이너와 비교 함수 객체를 추가로 설정할 수도 있습니다.

  • _First는 복사할 컨테이너의 첫 iterator를 나타냅니다.
  • _Last는 복사할 컨테이너의 마지막 iterator를 나타냅니다.

 

priority_queue 복사

priority_queue<_Ty> pq(_Right);

 다른 priority_queue를 복사하여 새로운 priority_queue를 생성합니다.

 


주요 함수

 

size()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
size_t s = pq.size(); // 6을 반환합니다.

 priority_queue의 크기를 반환합니다.

 


empty()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
bool is_empty = pq.empty(); // false를 반환합니다.

 priority_queue가 비어있는지 여부(크기가 0이면 true, 그렇지 않으면 false)를 반환합니다.

 


top()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
int t = pq.top(); // 6을 반환합니다.

 priority_queue에서 우선 순위가 가장 높은(가장 앞에 정렬된) 요소를 반환합니다.

 


push()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
pq.push(7); // 컨테이너는 { 7, 6, 5, 4, 3, 2, 1 } 상태입니다.

 priority_queue에 요소를 추가하고 정렬 조건에 따라 정렬합니다.

 


pop()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
pq.pop(); // 컨테이너는 { 5, 4, 3, 2, 1 } 상태입니다.

 priority_queue에서 우선 순위가 가장 높은(가장 앞에 정렬된) 요소를 제거합니다.

 


swap()

priority_queue<int> pq1; // 컨테이너는 {  6,  5,  4,  3,  2,  1 } 상태라고 가정합니다.
priority_queue<int> pq2; // 컨테이너는 { 66, 55, 44, 33, 22, 11 } 상태라고 가정합니다.
pq1.swap(pq2);
// pq1 컨테이너는 { 66, 55, 44, 33, 22, 11 } 상태입니다.
// pq2 컨테이너는 {  6,  5,  4,  3,  2,  1 } 상태입니다.

priority_queue의 모든 요소를 교환합니다.

 

반응형
'C | C++/STL' 카테고리의 다른 글
  • [C++] std::map
  • [C++] std::set
  • [C++] std::queue
  • [C++] std::stack
HYEOKJUN
HYEOKJUN
프로그래밍 관련 수업이나 웹 사이트에서 직접 얻은 정보를 공유하는 블로그입니다. (일부 잘못된 정보가 포함될 수 있습니다)
  • HYEOKJUN
    HYEOKJUN
    HYEOKJUN
  • 전체
    오늘
    어제
    • 분류 전체보기 (53)
      • UNITY (18)
        • Tool (9)
        • Script (9)
      • C | C++ (20)
        • Basic (11)
        • STL (8)
        • ETC (1)
      • C# (1)
        • Basic (0)
        • ETC (1)
      • Python (8)
        • Basic (7)
        • Library (1)
        • ETC (0)
      • WEB (2)
        • Basic (2)
      • Skill (0)
        • 자료구조 (0)
      • Workspace (0)
      • ETC (4)
  • 블로그 메뉴

    • 인기 글

    • 태그

      조건문
      C#
      C++
      컨테이너
      C
      Package
      while
      반복문
      queue
      포인터
      Python
      std
      Localization
      자료형
      변수
      vector
      red-black tree
      식별자
      stack
      Unity
    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    HYEOKJUN
    [C++] std::priority_queue
    상단으로

    티스토리툴바