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

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

Можно изменить базовый тип контейнера, используемый параметром priority_queue. Вы можете сделать это по соображениям производительности. Значение по умолчанию лучше всего подходит для локализации кэша, vectorтак как элементы хранятся в непрерывном хранилище и делают меньше выделений по мере роста. Но, возможно, вы рассмотрите deque , если у вас есть очень большие или несвязанные очереди и перемещение элементов дорого. Дополнительные сведения о подходящих базовых классах контейнеров см. в container_type.

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

Стандартная библиотека C++ определяет другие адаптеры контейнеров, которые можно использовать для хранения элементов в : priority_queuestack, queueи priority_queue:

• Класс stack поддерживает структуру данных последней и первой версии (LIFO). Рассмотрим стек плит: можно вставлять, проверять или удалять элементы (пластины) только из верхней части стека, который является последним элементом в конце базового контейнера.
• Класс queue поддерживает структуру данных fiFO. Рассмотрим людей в строке. Вы добавляете элементы (люди) в задней части линии и удаляете их из передней части линии. Можно проверить как передний, так и задней части линии.
• Класс priority_queue упорядочивает его элементы таким образом, чтобы самый большой элемент всегда был в верхней части. Он поддерживает вставку элемента, а также проверку и удаление верхнего элемента.

Примеры

• Проверьте, является ли пустой priority_queue
• Всплывающие элементы и проверка размера очереди
• Использование пользовательских контейнеров и сравнения
• Отправка элементов и чтение верхней части
• Получение количества элементов
• Доступ к верхнему элементу
• Использование псевдонима priority_queue value_type
• Использование определяемого пользователем типа данных

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

Конструктор	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.

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

Пример объявления и использования 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;

Замечания

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

Пример. Доступ к верхнему элементу

Пример объявления и использования size_typeсм. в разделе "Получение количества элементов"

priority_queue::top

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

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;

Замечания

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

Пример. Использование псевдонима 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< тип или указать объект пользовательской функции сравнения.

В следующем примере показано priority_queue , как хранить Task объекты, упорядоченные по уровню приоритета. Задачи с более высоким приоритетом находятся в верхней части очереди.

// 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++