Namespaces
Variants

std::priority_queue<T,Container,Compare>:: priority_queue

From cppreference.net
C++
Containers library
std::priority_queue
priority_queue ( ) : priority_queue ( Compare ( ) , Container ( ) ) { }
(1) (начиная с C++11)
explicit priority_queue ( const Compare & compare )
: priority_queue ( compare, Container ( ) ) { }
(2) (начиная с C++11)
(3)
explicit priority_queue ( const Compare & compare = Compare ( ) ,
const Container & cont = Container ( ) ) ;
(до C++11)
priority_queue ( const Compare & compare, const Container & cont ) ;
(начиная с C++11)
priority_queue ( const Compare & compare, Container && cont ) ;
(4) (начиная с C++11)
priority_queue ( const priority_queue & other ) ;
(5)
priority_queue ( priority_queue && other ) ;
(6) (начиная с C++11)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,

const Compare & compare = Compare ( ) ) ;
(7) (начиная с C++11)
(8)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,
const Compare & compare = Compare ( ) ,

const Container & cont = Container ( ) ) ;
(до C++11)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,

const Compare & compare, const Container & cont ) ;
(начиная с C++11)
template < class InputIt >

priority_queue ( InputIt first, InputIt last,

const Compare & compare, Container && cont ) ;
(9) (начиная с C++11)
template < class Alloc >
explicit priority_queue ( const Alloc & alloc ) ;
(10) (начиная с C++11)
template < class Alloc >
priority_queue ( const Compare & compare, const Alloc & alloc ) ;
(11) (начиная с C++11)
template < class Alloc >

priority_queue ( const Compare & compare, const Container & cont,

const Alloc & alloc ) ;
(12) (начиная с C++11)
template < class Alloc >

priority_queue ( const Compare & compare, Container && cont,

const Alloc & alloc ) ;
(13) (начиная с C++11)
template < class Alloc >
priority_queue ( const priority_queue & other, const Alloc & alloc ) ;
(14) (начиная с C++11)
template < class Alloc >
priority_queue ( priority_queue && other, const Alloc & alloc ) ;
(15) (начиная с C++11)
template < class InputIt, class Alloc >
priority_queue ( InputIt first, InputIt last, const Alloc & alloc ) ;
(16) (начиная с C++11)
template < class InputIt, class Alloc >

priority_queue ( InputIt first, InputIt last, const Compare & compare,

const Alloc & alloc ) ;
(17) (начиная с C++11)
template < class InputIt, class Alloc >

priority_queue ( InputIt first, InputIt last, const Compare & compare,

const Container & cont, const Alloc & alloc ) ;
(18) (начиная с C++11)
template < class InputIt, class Alloc >

priority_queue ( InputIt first, InputIt last, const Compare & compare,

Container && cont, const Alloc & alloc ) ;
(19) (начиная с C++11)
template < container-compatible-range < T > R >

priority_queue ( std:: from_range_t , R && rg,

const Compare & compare = Compare ( ) ) ;
(20) (начиная с C++23)
template < container-compatible-range < T > R, class Alloc >

priority_queue ( std:: from_range_t , R && rg,

const Compare & compare, const Alloc & alloc ) ;
(21) (начиная с C++23)
template < container-compatible-range < T > R, class Alloc >
priority_queue ( std:: from_range_t , R && rg, const Alloc & alloc ) ;
(22) (начиная с C++23)

Создает новый базовый контейнер адаптера контейнера из различных источников данных.

1) Конструктор по умолчанию. Выполняет инициализацию значениями компаратора и базового контейнера.
2) Копирует функтор сравнения comp с содержимым compare . Инициализирует значением по умолчанию базовый контейнер c .
3) Копирует базовый контейнер c с содержимым cont . Копирует функтор сравнения comp с содержимым compare . Вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) . Это также конструктор по умолчанию. (до C++11)
4) Перемещающий конструктор инициализирует базовый контейнер c с помощью std :: move ( cont ) . Копирующий конструктор инициализирует функтор сравнения comp с помощью compare . Вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .
5) Конструктор копирования . Базовый контейнер копируется с помощью other. c . Функтор сравнения копируется с помощью other. comp . (неявно объявлен)
6) Конструктор перемещения . Базовый контейнер создается с помощью std :: move ( other. c ) . Функтор сравнения создается с помощью std :: move ( other. comp ) . (неявно объявлен)
7-9) Конструкторы с парой итераторов. Эти перегрузки участвуют в разрешении перегрузки только если InputIt удовлетворяет требованиям LegacyInputIterator .
7) Конструирует c как если бы через c ( first, last ) и comp из compare . Затем вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; .
8) Копирующий конструктор создаёт c из cont и comp из compare . Затем вызывает c. insert ( c. end ( ) , first, last ) ; , после чего вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; .
9) Перемещающее конструирование c из std :: move ( cont ) и копирующее конструирование comp из compare . Затем вызывается c. insert ( c. end ( ) , first, last ) ; , после чего вызывается std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; .
10-15) Конструкторы с расширенным аллокатором. Эти перегрузки участвуют в разрешении перегрузки только если std:: uses_allocator < container_type, Alloc > :: value равно true , то есть если базовый контейнер является контейнером с поддержкой аллокатора (верно для всех контейнеров стандартной библиотеки).
10) Конструирует базовый контейнер, используя alloc в качестве аллокатора. Фактически вызывает c ( alloc ) . comp инициализируется значением по умолчанию.
11) Создает базовый контейнер, используя alloc в качестве аллокатора. Фактически вызывает c ( alloc ) . Копирует comp из compare .
12) Создает базовый контейнер с содержимым cont и использует alloc в качестве аллокатора, как если бы было выполнено c ( cont, alloc ) . Копирует comp из compare . Затем вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .
13) Конструирует базовый контейнер с содержимым cont с использованием семантики перемещения, используя alloc в качестве аллокатора, как если бы c ( std :: move ( cont ) , alloc ) . Копирующе конструирует comp из compare . Затем вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .
14) Создает базовый контейнер с содержимым other. c и использует alloc в качестве аллокатора. Фактически вызывает c ( other. c , alloc ) . Копирует comp из other. comp .
15) Конструирует базовый контейнер с содержимым other с использованием семантики перемещения, используя alloc в качестве аллокатора. Фактически вызывает c ( std :: move ( other. c ) , alloc ) . Перемещающее конструирование comp из other. comp .
16-19) Конструкторы с аллокатором и парой итераторов. Аналогичны (7-9) , за исключением того, что alloc используется для конструирования базового контейнера. Эти перегрузки участвуют в разрешении перегрузки только если std:: uses_allocator < container_type, Alloc > :: value равно true и InputIt удовлетворяет требованиям LegacyInputIterator .
20) Инициализирует comp с помощью compare и c с помощью ranges:: to < Container > ( std:: forward < R > ( rg ) ) . Затем вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .
21) Инициализирует comp с помощью compare и c с помощью ranges:: to < Container > ( std:: forward < R > ( rg ) , alloc ) . Затем вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .
22) Инициализирует c с помощью ranges:: to < Container > ( std:: forward < R > ( rg ) , alloc ) . Затем вызывает std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .

Обратите внимание, что способ, которым реализация проверяет, удовлетворяет ли тип требованиям LegacyInputIterator , не специфицирован, за исключением того, что целочисленные типы должны быть отклонены.

Содержание

Параметры

alloc - аллокатор для использования во всех выделениях памяти базового контейнера
other - другой адаптер контейнера, используемый в качестве источника для инициализации базового контейнера
cont - контейнер, используемый в качестве источника для инициализации базового контейнера
compare - функциональный объект сравнения для инициализации базового функтора сравнения
first, last - пара итераторов, определяющая диапазон элементов для инициализации
rg - диапазон, совместимый с контейнером, то есть input_range , элементы которого конвертируются в T
Требования к типам
-
Alloc должен удовлетворять требованиям Allocator .
-
Compare должен удовлетворять требованиям Compare .
-
Container должен удовлетворять требованиям Container . Конструкторы с расширенным аллокатором определены только если Container удовлетворяет требованиям AllocatorAwareContainer .
-
InputIt должен удовлетворять требованиям LegacyInputIterator .

Сложность

1,2) Константа.
3,5,12) O(N) сравнений и O(N) вызовов конструктора value_type , где N равно cont. size ( ) .
4) O(N) сравнений, где N это cont. size ( ) .
6) Константа.
7,16,17) O(M) сравнений, где M равно std:: distance ( first, last ) .
8,18) O(N + M) сравнений и O(N) вызовов конструктора value_type , где N равно cont. size ( ) , а M равно std:: distance ( first, last ) .
9) O(N + M) сравнений, где N это cont. size ( ) и M это std:: distance ( first, last ) .
10,11) Константа.
13) O(N) сравнений, где N равно cont. size ( ) .
14) Линейно по размеру other .
15) Константное время, если Alloc сравнивается с аллокатором other . Линейное от размера other в противном случае.
19) O(N + M) сравнений и возможно O(N) вызовов конструктора value_type (присутствует, если Alloc не равен аллокатору other ), где N это cont. size ( ) и M это std:: distance ( first, last ) .
20) O(N) сравнений и O(N) вызовов конструктора value_type , где N равно ranges:: distance ( rg ) .
21,22)
Этот раздел не завершен

Примечания

Макрос тестирования функций Значение Стандарт Функция
__cpp_lib_containers_ranges 202202L (C++23) Ориентированная на диапазоны конструкция и вставка; перегрузки ( 20-22 )

Пример

Запустить этот код 
#include <complex>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main()
{
    std::priority_queue<int> pq1;
    pq1.push(5);
    std::cout << "pq1.size() = " << pq1.size() << '\n';
    std::priority_queue<int> pq2 {pq1};
    std::cout << "pq2.size() = " << pq2.size() << '\n';
    std::vector<int> vec {3, 1, 4, 1, 5};
    std::priority_queue<int> pq3 {std::less<int>(), vec};
    std::cout << "pq3.size() = " << pq3.size() << '\n';
    for (std::cout << "pq3 : "; !pq3.empty(); pq3.pop())
        std::cout << pq3.top() << ' ';
    std::cout << '\n';
    // Demo With Custom Comparator:
    using my_value_t = std::complex<double>;
    using my_container_t = std::vector<my_value_t>;
    auto my_comp = [](const my_value_t& z1, const my_value_t& z2)
    {
        return z2.real() < z1.real();
    };
    std::priority_queue<my_value_t,
                        my_container_t,
                        decltype(my_comp)> pq4{my_comp};
    using namespace std::complex_literals;
    pq4.push(5.0 + 1i);
    pq4.push(3.0 + 2i);
    pq4.push(7.0 + 3i);
    for (; !pq4.empty(); pq4.pop())
    {
        const auto& z = pq4.top();
        std::cout << "pq4.top() = " << z << '\n';
    }
    // TODO: C++23 range-aware ctors
}

Вывод: 

pq1.size() = 1
pq2.size() = 1
pq3.size() = 5
pq3 : 5 4 3 1 1
pq4.top() = (3,2)
pq4.top() = (5,1)
pq4.top() = (7,3)

Отчеты о дефектах

Следующие отчеты об изменениях поведения, влияющие на дефекты, были применены ретроактивно к ранее опубликованным стандартам C++.

DR Applied to Behavior as published Correct behavior
P0935R0 C++11 default constructor and constructor (4) were explicit made implicit
LWG 3506 C++11 allocator-extended iterator-pair constructors were missing added
LWG 3522 C++11 constraints on iterator-pair constructors were missing added
LWG 3529 C++11 construction from a pair of iterators called insert constructs the container from them

Смотрите также

присваивает значения адаптеру контейнера
(public member function)