Класс priority_queue

Класс-шаблон адаптера контейнера, который предоставляет ограничение функциональности, ограничивая доступ к верхнему элементу некоторого базового типа контейнера, который всегда является самым большим или имеет высший приоритет. Новые элементы можно добавить в priority_queue верхний элемент 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 контейнера, заданном вторым параметром шаблона. Необходимо Type назначить его, чтобы можно было копировать объекты этого типа и назначать значения переменным этого типа.

Порядок priority_queue последовательности, которую он управляет, путем вызова объекта хранимой функции класса Traits. Как правило, элементы должны быть просто меньше, чем сравнимые для установления этого порядка: чтобы, учитывая два элемента, можно определить, что они эквивалентны (в том смысле, что ни меньше другого), либо что один меньше другого. Это приводит к упорядочению неравнозначных элементов. С более технической точки зрения, функция сравнения является бинарным предикатом, который вызывает строгого слабое упорядочение в стандартном математически смысле.

Подходящие базовые классы контейнеров для включения класса и класса по умолчаниюvectorили любого другого frontконтейнера последовательности, поддерживающего операции, push_backитератор pop_back случайного доступа.dequepriority_queue Класс базового контейнера инкапсулирован в адаптер контейнера, который предоставляет только ограниченный набор функций-членов контейнера последовательностей в виде открытого интерфейса.

Добавление элементов в priority_queue и удаление элементов из него имеют логарифмическую сложность. Доступ к элементам в priority_queue имеет постоянную сложность.

Существует три типа адаптеров контейнеров, определенных стандартной библиотекой C++: stack, queueи priority_queue. Каждый ограничивает функциональность некоторого базового класса контейнеров для обеспечения точно управляемого интерфейса к стандартной структуре данных.

• Класс stack поддерживает структуру данных последней и первой версии (LIFO). Хороший аналог такого подхода — стопка тарелок. Элементы (тарелки) можно вставлять, проверять или удалять только из верхней части стека, которая является последним элементом в конце базового контейнера. Ограничение доступа только к верхнему элементу является причиной использования stack класса.

• Класс queue поддерживает структуру данных fiFO. Хороший аналог такого подхода — очередь из людей к банковскому служащему. Элементы (люди) можно добавлять в конец очереди и удалять из начала очереди. Проверять можно как начало, так и конец очереди. Ограничение доступа только к внешним и задним элементам таким образом является причиной использования queue класса.

• Класс priority_queue упорядочивает его элементы таким образом, чтобы самый большой элемент всегда был в верхней позиции. Он поддерживает вставку элемента, а также проверку и удаление верхнего элемента. Хорошим аналогом следует помнить, что люди выстраиваются, где они упорядочены по возрасту, высоте или другому критерию.

Конструкторы

Конструктор	Description
priority_queue	Создает priority_queue, который является пустым или копией диапазона объекта базового контейнера или другого priority_queue.

Определения типов

Введите имя	Description
container_type	Тип, предоставляющий базовый контейнер для принятия priority_queue.
size_type	Целочисленный Typedef без знака, который может представлять число элементов в priority_queue.
value_type	Тип, представляющий тип объекта, который хранится в виде элемента в priority_queue.

Функции элементов

Функция-член	Description
empty	Проверяет, является ли priority_queue пустым.
pop	Удаляет самый большой элемент priority_queue с верхней позиции.
push	Добавляет элемент в очередь приоритета на основе приоритета элемента из operator<.
size	Возвращает количество элементов в контейнере priority_queue.
top	Возвращает константную ссылку на наибольший элемент в верхней части priority_queue.

Требования

Заголовок.<queue>

Пространство именstd:

priority_queue::container_type

Тип, предоставляющий базовый контейнер для изменения.

typedef Container container_type;

Замечания

Этот тип является синонимом для параметра шаблона Container. Класс контейнера последовательности стандартной библиотеки C++ и класс dequevector по умолчанию соответствуют требованиям, которые необходимо использовать в качестве базового контейнера для priority_queue объекта. Также можно использовать пользовательские типы, удовлетворяющие требованиям.

Дополнительные сведения см. в разделе "Примечания Container" раздела priority_queue "Класс ".

Пример

Пример объявления и использования container_typeсм. в примереpriority_queue.

priority_queue::empty

Проверяет, пуст ли priority_queue.

bool empty() const;

Возвращаемое значение

truepriority_queue Значение , если priority_queue значение не false является пустым.

Пример

// pqueue_empty.cpp
// 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 часть всегда занята крупнейшим элементом в контейнере.

Пример

// pqueue_pop.cpp
// 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.

Пример

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

int main( )
{
   using namespace std;

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

   // Explicitly 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;

   // This method of printing out the elements of a priority_queue
   // removes the elements from the priority queue, leaving it empty
   cout << "After printing, q2 has " << q2.size( ) << " elements." << endl;

   // The third member function 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;

   // The fourth member function declares a priority_queue and
   // initializes it with elements copied from another container:
   // first, inserting elements into q1, 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;

   // The fifth member function 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;

   // The sixth member function 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 часть — это позиция, занятая крупнейшим элементом в контейнере.

Пример

// pqueue_push.cpp
// 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.

Пример

// pqueue_size.cpp
// 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

Целочисленный Typedef без знака, который может представлять число элементов в priority_queue.

typedef typename Container::size_type size_type;

Замечания

Тип является синонимом базового size_type контейнера, адаптированного с помощью .priority_queue

Пример

Пример объявления и использования size_typeсм. в примереsize.

priority_queue::top

Возвращает константную ссылку на наибольший элемент в верхней части priority_queue.

const_reference top() const;

Возвращаемое значение

Ссылка на самый большой элемент, определяемый Traits функцией, объектом priority_queueобъекта .

Замечания

Для priority_queue применения функции-члена должна быть непустимая.

Пример

// pqueue_top.cpp
// 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;

Замечания

Тип является синонимом базового value_type контейнера, адаптированного с помощью .priority_queue

Пример

// pqueue_value_type.cpp
// 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.

См. также

Потокобезопасность в стандартной библиотеке C++
Справочник по стандартной библиотеке C++