std::priority_queue<T,Container,Compare>::priority_queue
priority_queue() : priority_queue(Compare(), Container()) { } |
(1) | (since C++11) |
explicit priority_queue( const Compare& compare ) : priority_queue(compare, Container()) { } |
(2) | (since C++11) |
(3) | ||
explicit priority_queue( const Compare& compare = Compare(), const Container& cont = Container() ); |
(until C++11) | |
priority_queue( const Compare& compare, const Container& cont ); |
(since C++11) | |
priority_queue( const Compare& compare, Container&& cont ); |
(4) | (since C++11) |
priority_queue( const priority_queue& other ); |
(5) | |
priority_queue( priority_queue&& other ); |
(6) | (since C++11) |
template< class InputIt > priority_queue( InputIt first, InputIt last, const Compare& compare = Compare() ); |
(7) | (since C++11) |
(8) | ||
template< class InputIt > priority_queue( InputIt first, InputIt last, const Compare& compare = Compare(), const Container& cont = Container() ); |
(until C++11) | |
template< class InputIt > priority_queue( InputIt first, InputIt last, const Compare& compare, const Container& cont ); |
(since C++11) | |
template< class InputIt > priority_queue( InputIt first, InputIt last, const Compare& compare, Container&& cont ); |
(9) | (since C++11) |
template< class Alloc > explicit priority_queue( const Alloc& alloc ); |
(10) | (since C++11) |
template< class Alloc > priority_queue( const Compare& compare, const Alloc& alloc ); |
(11) | (since C++11) |
template< class Alloc > priority_queue( const Compare& compare, const Container& cont, const Alloc& alloc ); |
(12) | (since C++11) |
template< class Alloc > priority_queue( const Compare& compare, Container&& cont, const Alloc& alloc ); |
(13) | (since C++11) |
template< class Alloc > priority_queue( const priority_queue& other, const Alloc& alloc ); |
(14) | (since C++11) |
template< class Alloc > priority_queue( priority_queue&& other, const Alloc& alloc ); |
(15) | (since C++11) |
template< class InputIt, class Alloc > priority_queue( InputIt first, InputIt last, const Alloc& alloc ); |
(16) | (since C++11) |
template< class InputIt, class Alloc > priority_queue( InputIt first, InputIt last, const Compare& compare, const Alloc& alloc ); |
(17) | (since C++11) |
template< class InputIt, class Alloc > priority_queue( InputIt first, InputIt last, const Compare& compare, const Container& cont, const Alloc& alloc ); |
(18) | (since C++11) |
template< class InputIt, class Alloc > priority_queue( InputIt first, InputIt last, const Compare& compare, Container&& cont, const Alloc& alloc ); |
(19) | (since C++11) |
Constructs new underlying container of the container adaptor from a variety of data sources.
1) Default constructor. Value-initializes the comparator and the underlying container.
2) Copy-constructs the comparison functor
comp
with the contents of
compare
. Value-initializes the underlying container
c
.
3) Copy-constructs the underlying container
c
with the contents of
cont
. Copy-constructs the comparison functor
comp
with the contents of
compare
. Calls
std::make_heap(c.begin(), c.end(), comp)
.
This is also the default constructor. (until C++11)
4) Move-constructs the underlying container
c
with
std::move(cont)
. Copy-constructs the comparison functor
comp
with
compare
. Calls
std::make_heap(c.begin(), c.end(), comp)
.
5) Copy constructor. The underlying container is copy-constructed with
other.c
. The comparison functor is copy-constructed with
other.comp
.
(implicitly declared)
6) Move constructor. The underlying container is constructed with
std::move(other.c)
.The comparison functor is constructed with
std::move(other.comp)
.
(implicitly declared)
7-9) Iterator-pair constructors. These overloads participate in overload resolution only if
InputIt
satisfies
LegacyInputIterator.
7) Constructs
c
as if by
c(first, last)
and
comp
from
compare
. Then calls
std::make_heap(c.begin(), c.end(), comp);
.
8) Copy-constructs
c
from
cont
and
comp
from
compare
. Then calls
c.insert(c.end(), first, last);
, and then calls
std::make_heap(c.begin(), c.end(), comp);
.
9) Move-constructs
c
from
std::move(cont)
and copy-constructs
comp
from
compare
. Then calls
c.insert(c.end(), first, last);
, and then calls
std::make_heap(c.begin(), c.end(), comp);
.
10-15) Allocator-extended constructors. These overloads participate in overload resolution only if
std::uses_allocator<container_type, Alloc>::value
is
true
, that is, if the underlying container is an allocator-aware container (true for all standard library containers).
10) Constructs the underlying container using
alloc
as allocator. Effectively calls
c(alloc)
.
comp
is value-initialized.
11) Constructs the underlying container using
alloc
as allocator. Effectively calls
c(alloc)
. Copy-constructs
comp
from
compare
.
12) Constructs the underlying container with the contents of
cont
and using
alloc
as allocator, as if by
c(cont, alloc)
. Copy-constructs
comp
from
compare
. Then calls
std::make_heap(c.begin(), c.end(), comp)
.
13) Constructs the underlying container with the contents of
cont
using move semantics while using
alloc
as allocator, as if by
c(std::move(cont), alloc)
. Copy-constructs
comp
from
compare
. Then calls
std::make_heap(c.begin(), c.end(), comp)
.
14) Constructs the underlying container with the contents of
other.c
and using
alloc
as allocator. Effectively calls
c(other.c, alloc)
. Copy-constructs
comp
from
other.comp
.
15) Constructs the underlying container with the contents of
other
using move semantics while utilising
alloc
as allocator. Effectively calls
c(std::move(other.c), alloc)
. Move-constructs
comp
from
other.comp
.
16-19) Allocator-extended iterator-pair constructors. Same as
(7-9), except that
alloc
is used for constructing the underlying container. These overloads participate in overload resolution only if
std::uses_allocator<container_type, Alloc>::value
is
true
and
InputIt
satisfies
LegacyInputIterator.
Note that how an implementation checks whether a type satisfies LegacyInputIterator is unspecified, except that integral types are required to be rejected.
Parameters
alloc | - | allocator to use for all memory allocations of the underlying container |
other | - | another container adaptor to be used as source to initialize the underlying container |
cont | - | container to be used as source to initialize the underlying container |
compare | - | the comparison function object to initialize the underlying comparison functor |
first, last | - | range of elements to initialize with |
Type requirements | ||
-Alloc must meet the requirements of Allocator. |
||
-Container must meet the requirements of Container. The allocator-extended constructors are only defined if Container meets the requirements of AllocatorAwareContainer |
||
-InputIt must meet the requirements of LegacyInputIterator. |
Complexity
1-2) Constant.
3,5) \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons and \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of
value_type
, where \(\scriptsize N\)N is
cont.size()
.
4) \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons, where \(\scriptsize N\)N is
cont.size()
.
6) Constant.
7,16-17) \(\scriptsize \mathcal{O}{(M)}\)O(M) comparisons, where \(\scriptsize M\)M is
std::distance(first, last)
.
8,18) \(\scriptsize \mathcal{O}{(N+M)}\)O(N+M) comparisons and \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of
value_type
, where \(\scriptsize N\)N and \(\scriptsize M\)M are
cont.size()
and
std::distance(first, last)
respectively.
9) \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons, where \(\scriptsize N\)N is
cont.size() + std::distance(first, last)
.
10-11) Constant.
12) \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons and \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of
value_type
, where \(\scriptsize N\)N is
cont.size()
.
13) \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons, where \(\scriptsize N\)N is
cont.size()
.
14) Linear in size of
other
.
15) Constant if
Alloc
compares equal to the allocator of
other
. Linear in size of
other
otherwise.
19) \(\scriptsize \mathcal{O}{(N+M)}\)O(N+M) comparisons and possibly present \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of
value_type
(present if
Alloc
does not compare equal to the allocator of
other
), where \(\scriptsize N\)N and \(\scriptsize M\)M are
cont.size()
and
std::distance(first, last)
respectively.
Example
#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'; } }
Output:
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)
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
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 |
See also
assigns values to the container adaptor (public member function) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue