priority_queue 클래스

가장 큰(또는 가장 높은 우선 순위) 요소가 항상 맨 위에서 액세스할 수 있는 요소 컬렉션을 유지하는 컨테이너 어댑터입니다. 새 요소를 추가하고 상위 요소를 제거하거나 검사할 수 있지만 컬렉션 중간에 있는 요소에 직접 액세스할 수는 없습니다.

구문

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

매개 변수

Type
에 저장할 요소 데이터 형식입니다 priority_queue.

Container
에 대한 요소를 저장하는 기본 컨테이너의 형식입니다 priority_queue.

Compare
두 요소 값을 정렬 키로 비교하여 상대적 순서 priority_queue를 결정하는 함수 개체를 제공하는 형식입니다. 이 인수는 선택 사항입니다. 이진 조건자가 less<typename Container::value_type> 기본값입니다.

설명

개체의 첫 번째 템플릿 매개 변수에 지정된 클래스 Type 의 요소는 동일 value_type 하며 두 번째 템플릿 매개 변수로 지정된 기본 컨테이너 클래스 Container 의 요소 형식과 priority_queue 일치해야 합니다. Type 할당 가능해야 합니다. 즉, 해당 형식의 개체를 복사하고 해당 형식의 변수에 값을 할당할 수 있습니다.

priority_queue 비교 함수를 사용하여 우선 순위가 더 높은 요소를 결정합니다. 이 비교 함수는 클래스 Traits의 함수 개체입니다. 작업을 priority_queue수행하려면 요소가 순서대로 정렬할 수 있도록 보다 작음 연산자(<)를 사용하여 비교만 지원하면 됩니다.

에서 사용하는 priority_queue기본 컨테이너 유형을 변경할 수 있습니다. 성능상의 이유로 이 작업을 수행할 수 있습니다. 기본값 vector은 일반적으로 캐시 지역성에 가장 적합합니다. 요소는 연속 스토리지에 저장되고 증가함에 따라 할당이 줄어들기 때문입니다. 그러나 매우 크거나 바인딩되지 않은 큐가 있고 요소를 이동하는 데 비용이 많이 드는 경우를 고려할 deque 수 있습니다. 적합한 기본 컨테이너 클래스에 대한 자세한 내용은 container_type 참조하세요.

둘 다에서 priority_queue 요소를 추가하고 제거하면 로그 복잡성이 있습니다. priority_queue에서 요소에 액세스하는 과정은 복잡한 상수 작업입니다.

C++ 표준 라이브러리는 다음과 같이 요소를 저장하는 데 사용할 수 있는 priority_queuestackqueuepriority_queue다른 컨테이너 어댑터를 정의합니다.

• 클래스stack LIFO(Last-in, first-out) 데이터 구조를 지원합니다. 플레이트 스택을 고려합니다. 기본 컨테이너의 끝에 있는 마지막 요소인 스택의 맨 위에서만 요소(판)를 삽입, 검사 또는 제거할 수 있습니다.
• 클래스queue FIFO(선점) 데이터 구조를 지원합니다. 한 줄에 있는 사람들을 고려해 보세요. 선의 뒷면에 요소(사람)를 추가하고 선의 맨 앞에서 제거합니다. 선의 앞면과 뒷면을 모두 검사할 수 있습니다.
• 클래스는 priority_queue 가장 큰 요소가 항상 맨 위에 있도록 해당 요소를 정렬합니다. 이 클래스는 요소의 삽입과 최상위 요소의 검사 및 제거를 지원합니다.

예시

• 비어 priority_queue 있는지 확인
• 요소 팝 및 큐 크기 확인
• 사용자 지정 컨테이너 및 비교자 사용
• 요소 푸시 및 위쪽 읽기
• 요소 수 가져오기
• 최상위 요소에 액세스
• priority_queue value_type 별칭 사용
• 사용자 정의 데이터 형식 사용

생성자

생성자	Description
priority_queue	비어 있거나 기본 컨테이너 개체 또는 다른 priority_queue 범위의 복사본인 priority_queue를 생성합니다.

Typedef

형식 이름	Description
container_type	적응하는 기본 컨테이너를 priority_queue 제공하는 형식입니다.
size_type	priority_queue에서 요소 수를 표현할 수 있는 부호 없는 정수 형식입니다.
value_type	priority_queue에 있는 요소로 저장된 개체의 형식을 나타내는 형식입니다.

멤버 함수

멤버 함수	Description
empty	priority_queue이 비어 있는지를 테스트합니다.
pop	priority_queue의 가장 큰 요소를 최상위 위치에서 제거합니다.
push	에서 요소의 우선 순위에 따라 우선 순위 큐에 요소를 operator<추가합니다.
size	priority_queue에 있는 요소 수를 반환합니다.
top	priority_queue의 최상위 위치에 있는 가장 큰 요소에 대한 const 참조를 반환합니다.

요구 사항

머리글:<queue>

네임스페이스:std

priority_queue::container_type

조정할 기본 컨테이너를 제공하는 형식입니다.

typedef Container container_type;

설명

이 형식은 템플릿 매개 변수 Container의 동의어입니다.

포함 deque 클래스, 기본 vector 클래스 또는 , push_back및 pop_back 임의 front액세스 반복기의 작업을 지원하는 다른 시퀀스 컨테이너에 적합한 기본 컨테이너 클래스 priority_queue 입니다. 컨테이너 어댑터에서는 기본 컨테이너 클래스를 캡슐화하고 제한된 시퀀스 컨테이너 멤버 함수 집합만 공용 인터페이스로 노출합니다.

선언 및 사용 container_type방법의 예는 사용자 지정 컨테이너 및 비교자 사용을 참조하세요.

priority_queue::empty

priority_queue가 비어 있는지 여부를 테스트합니다.

bool empty() const;

반환 값

true비어 priority_queue 있으면 이고, false 비어 있지 않으면 priority_queue

예: 비어 있는지 priority_queue 확인

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue <int> q1, s2;

   q1.push(1);

   if (q1.empty())
      cout << "The priority_queue q1 is empty." << endl;
   else
      cout << "The priority_queue q1 is not empty." << endl;

   if (s2.empty())
      cout << "The priority_queue s2 is empty." << endl;
   else
      cout << "The priority_queue s2 is not empty." << endl;
}

The priority_queue q1 is not empty.
The priority_queue s2 is empty.

priority_queue::pop

priority_queue의 가장 큰 요소를 최상위 위치에서 제거합니다.

void pop();

설명

이 priority_queue 멤버 함수를 사용하려면 비어 있지 않아야 합니다. 위쪽 priority_queue 은 항상 컨테이너에서 가장 큰 요소를 보유합니다.

예: 팝 요소 및 확인 크기

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, s2;

   q1.push(10);
   q1.push(20);
   q1.push(30);

   priority_queue <int>::size_type i, iii;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;

   q1.pop();

   iii = q1.size();
   cout << "After a pop, the priority_queue length is " << iii << "." << endl;

   const int& iv = q1.top();
   cout << "After a pop, the element at the top of the " << "priority_queue is " << iv << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.
After a pop, the priority_queue length is 2.
After a pop, the element at the top of the priority_queue is 20.

priority_queue::priority_queue

priority_queue 비어 있거나 기본 컨테이너 개체 또는 다른 priority_queue컨테이너 개체에서 범위를 복사하는 개체를 만듭니다.

priority_queue();

explicit priority_queue(const Traits& _comp);

priority_queue(const Traits& _comp, const container_type& _Cont);

priority_queue(const priority_queue& right);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp, const container_type& _Cont);

매개 변수

_comp
기본 컨테이너의 함수를 비교하는 기본값인 요소constTraits의 순서를 지정하는 데 사용되는 형식 priority_queue 의 비교 함수입니다.

_Cont
생성된 priority_queue 기본 컨테이너는 복사본이 됩니다.

right
priority_queue 생성된 집합이 복사본이 될 것입니다.

first
복사할 요소의 범위에서 첫 번째 요소의 위치입니다.

last
복사할 요소의 범위를 벗어나는 첫 번째 요소의 위치입니다.

설명

처음 세 개의 생성자는 각각 빈 이니셜priority_queue을 지정하고, 두 번째 생성자는 요소의 순서를 설정하는 데 사용할 비교 함수(comp)의 형식을 지정하고, 세 번째 생성자는 사용할 (container_type)를 명시적으로 지정합니다 _Cont . explicit 키워드를 사용하는 경우 특정 종류의 자동 형식 변환이 수행되지 않습니다.

네 번째 생성자는 .의 복사본을 priority_queue right지정합니다.

마지막 세 생성자는 일부 컨테이너의 범위를 [first, last) 복사하고 값을 사용하여 클래스 priority_queue 의 비교 함수 형식을 지정할 때 명시성이 증가하는 값을 초기화 Traits 합니다container_type.

예: 사용자 지정 컨테이너 및 비교자 사용

// compile with: /EHsc
#include <queue>
#include <vector>
#include <deque>
#include <list>
#include <iostream>

int main()
{
   using namespace std;

   // Declares a priority_queue with a default vector base container
   priority_queue <int> q1;
   cout << "q1 = ( ";
   while (!q1.empty())
   {
      cout << q1.top() << " ";
      q1.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue with nondefault deque base container
   priority_queue <int, deque <int>> q2;
   q2.push(5);
   q2.push(15);
   q2.push(10);
   cout << "q2 = ( ";
   while (!q2.empty())
   {
      cout << q2.top() << " ";
      q2.pop();
   }
   cout << ")" << endl;
   cout << "After printing, q2 has " << q2.size() << " elements." << endl;

   // Declares a priority_queue with a vector base container and specifies that
   // the comparison function greater is to be used for ordering elements
   priority_queue <int, vector<int>, greater<int>> q3;
   q3.push(2);
   q3.push(1);
   q3.push(3);
   cout << "q3 = ( ";
   
   while (!q3.empty())
   {
      cout << q3.top() << " ";
      q3.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue and initializes it with elements copied from another
   // container by first inserting elements into q1 and then copying q1 elements into q4
   q1.push(100);
   q1.push(200);
   priority_queue <int> q4(q1);
   cout << "q4 = ( ";
   while (!q4.empty())
   {
      cout << q4.top() << " ";
      q4.pop();
   }
   cout << ")" << endl;

   // Creates an auxiliary vector object v5 to be used to initialize q5
   vector <int> v5;
   vector <int>::iterator v5_Iter;
   v5.push_back(10);
   v5.push_back(30);
   v5.push_back(20);
   cout << "v5 = ( " ;
   for (v5_Iter = v5.begin() ; v5_Iter != v5.end() ; v5_Iter++)
   {
      cout << *v5_Iter << " ";
   }
   cout << ")" << endl;

   // Declares and initializes a priority_queue q5 by copying the
   // range v5[ first,  last) from vector v5
   priority_queue <int> q5(v5.begin(), v5.begin() + 2);
   cout << "q5 = ( ";
   while (!q5.empty())
   {
      cout << q5.top() << " ";
      q5.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue q6 with a comparison function greater and
   // initializes q6 by copying the range v5[ first,  last) from vector v5
   priority_queue <int, vector<int>, greater<int>> q6(v5.begin(), v5.begin() + 2);
   cout << "q6 = ( ";
   while (!q6.empty())
   {
      cout << q6.top() << " ";
      q6.pop();
   }
   cout << ")" << endl;
}

priority_queue::push

에서 요소의 우선 순위에 따라 우선 순위 큐에 요소를 operator<추가합니다.

void push(const Type& val);

매개 변수

val
의 맨 위에 추가할 요소입니다 priority_queue.

설명

위쪽에는 priority_queue 컨테이너에서 가장 큰 요소가 포함됩니다.

예: 요소 푸시 및 위쪽 읽기

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::size

priority_queue에 있는 요소 수를 반환합니다.

size_type size() const;

반환 값

의 현재 길이입니다 priority_queue.

예: 다음의 요소 수를 가져옵니다. priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, q2;
   priority_queue <int>::size_type i;

   q1.push(1);
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   q1.push(2);
   i = q1.size();
   cout << "The priority_queue length is now " << i << "." << endl;
}

The priority_queue length is 1.
The priority_queue length is now 2.

priority_queue::size_type

에 있는 요소 수를 나타내는 부호 없는 정수 형식입니다 priority_queue.

typedef typename Container::size_type size_type;

설명

이 형식은 적응하는 기본 컨테이너 priority_queue 의 동의어 size_type 입니다.

예: 상위 요소에 액세스

선언하고 사용하는 size_type방법의 예는 요소 수 가져오기를 참조하세요.

priority_queue::top

priority_queue의 최상위 위치에 있는 가장 큰 요소에 대한 const 참조를 반환합니다.

const_reference top() const;

반환 값

함수, 개체에 의해 Traits 결정되는 가장 큰 요소에 대한 참조입니다 priority_queue.

설명

이 priority_queue 멤버 함수를 사용하려면 비어 있지 않아야 합니다.

예: 의 상위 요소 가져오기 priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::value_type

priority_queue에 있는 요소로 저장된 개체의 형식을 나타내는 형식입니다.

typedef typename Container::value_type value_type;

설명

이 형식은 적응하는 기본 컨테이너 priority_queue 의 동의어 value_type 입니다.

예: priority_queue value_type 별칭 사용

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue<int>::value_type AnInt;

   AnInt = 69;
   cout << "The value_type is AnInt = " << AnInt << endl;

   priority_queue<int> q1;
   q1.push(AnInt);
   cout << "The element at the top of the priority_queue is " << q1.top() << "." << endl;
}

The value_type is AnInt = 69
The element at the top of the priority_queue is 69.

예: 사용자 정의 데이터 형식 사용

사용자 정의 형식 요소와 함께 사용 priority_queue 하려면 요소를 비교하는 방법을 제공해야 합니다. 형식을 정의 operator< 하거나 사용자 지정 비교 함수 개체를 제공할 수 있습니다.

다음 예제에서는 우선 순위 수준별로 정렬된 개체를 저장하는 Task 방법을 보여 priority_queue 줍니다. 우선 순위 값이 높은 작업은 큐의 맨 위에 있습니다.

// compile with: /EHsc
#include <queue>
#include <iostream>
#include <string>

struct Task
{
    int priority;
    std::string name;

    // Define operator< for priority_queue ordering
    // Returns true if this task has LOWER priority than other
    // (priority_queue puts the "largest" element at the top)
    bool operator<(const Task& other) const
    {
        return priority < other.priority;
    }
};

int main()
{
    std::priority_queue<Task> tasks;

    tasks.push({3, "Low priority task"});
    tasks.push({10, "High priority task"});
    tasks.push({5, "Medium priority task"});

    std::cout << "Processing tasks by priority:\n";
    while (!tasks.empty())
    {
        const Task& t = tasks.top();
        std::cout << "  Priority " << t.priority << ": " << t.name << "\n";
        tasks.pop();
    }
}

Processing tasks by priority:
  Priority 10: High priority task
  Priority 5: Medium priority task
  Priority 3: Low priority task

설명

다른 순서 지정을 원하는 경우(예: 낮은 값 먼저) 사용자 지정 비교자를 제공합니다.

struct ComparePriority
{
    bool operator()(const Task& a, const Task& b)
    {
        return a.priority > b.priority; // Lower priority value means higher priority
    }
};

std::priority_queue<Task, std::vector<Task>, ComparePriority> minQueue;

참고 항목

C++ 표준 라이브러리의 스레드 보안
C++ 표준 라이브러리 참조