Difference between revisions of "cpp/container/priority queue/priority queue"

Latest revision as of 01:28, 4 November 2023

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)
template< container-compatible-range<T> R > priority_queue( std::from_range_t, R&& rg, const Compare& compare = Compare() );			(20)	(since 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)	(since C++23)
template< container-compatible-range<T> R, class Alloc > priority_queue( std::from_range_t, R&& rg, const Alloc& alloc );			(22)	(since C++23)

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 utilizing 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.

20) Initializes comp with compare and c with ranges::to<Container>(std::forward<R>(rg)). Then calls std::make_heap(c.begin(), c.end(), comp).

21) Initializes comp with compare and c with ranges::to<Container>(std::forward<R>(rg), alloc). Then calls std::make_heap(c.begin(), c.end(), comp).

22) Initializes c with ranges::to<Container>(std::forward<R>(rg), alloc). Then calls std::make_heap(c.begin(), c.end(), comp).

Note that how an implementation checks whether a type satisfies LegacyInputIterator is unspecified, except that integral types are required to be rejected.

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	-	a range `[`first`,` last`)` of elements to initialize with
rg	-	a container compatible range, that is, an `input_range` whose elements are convertible to `T`
Type requirements
- `Alloc` must meet the requirements of Allocator.
- `Compare` must meet the requirements of Compare.
- `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.

[edit] Complexity

1,2) Constant.

3,5,12)

O(N)

comparisons and

O(N)

calls to the constructor of value_type, where

N

is cont.size().

4)

O(N)

comparisons, where

N

is cont.size().

6) Constant.

7,16,17)

O(M)

comparisons, where

M

is std::distance(first, last).

8,18)

O(N + M)

comparisons and

O(N)

calls to the constructor of value_type, where

N

is cont.size() and

M

is std::distance(first, last).

9)

O(N + M)

comparisons, where

N

is cont.size() and

M

is std::distance(first, last).

10,11) Constant.

13)

O(N)

comparisons, where

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)

O(N + M)

comparisons and possibly

O(N)

calls to the constructor of value_type (present if Alloc does not compare equal to the allocator of other), where

N

is cont.size() and

M

is std::distance(first, last).

20)

O(N)

comparisons and

O(N)

calls to the constructor of value_type, where

N

is ranges::distance(rg).

21,22)

[edit] Notes

Feature-test macro	Value	Std	Feature
`__cpp_lib_containers_ranges`	202202L	(C++23)	Ranges-aware construction and insertion; overloads (20-22)

[edit] Example

Run this code

#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
}

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)

[edit] 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

[edit] See also

operator=

assigns values to the container adaptor
(public member function) [edit]

@@ Line 3: / Line 3: @@
 {{dcl begin}}
 {{dcl|num=1|since=c++11|
-priority_queue() : priority_queue(Compare(), Container()) { }
+priority_queue() : priority_queue(Compare(), Container()) {}
 }}
 {{dcl|num=2|since=c++11|
 explicit priority_queue( const Compare& compare )
-     : priority_queue(compare, Container()) { }
+     : priority_queue(compare, Container()) {}
 }}
 {{dcl rev multi|num=3
@@ Line 119: / Line 119: @@
 @5@ [[cpp/language/copy constructor|Copy constructor]]. The underlying container is copy-constructed with {{c|other.c}}. The comparison functor is copy-constructed with {{c|other.comp}}. {{mark implicit}}
-@6@ [[cpp/language/move constructor|Move constructor]]. The underlying container is constructed with {{c|std::move(other.c)}}.The comparison functor is constructed with {{c|std::move(other.comp)}}. {{mark implicit}}
+@6@ [[cpp/language/move constructor|Move constructor]]. The underlying container is constructed with {{c|std::move(other.c)}}. The comparison functor is constructed with {{c|std::move(other.comp)}}. {{mark implicit}}
 @7-9@ Iterator-pair constructors. {{cpp/enable_if|{{tt|InputIt}} satisfies {{named req|InputIterator}}|plural=yes}}.
@@ Line 139: / Line 139: @@
 @13@ Constructs the underlying container with the contents of {{c|cont}} using move semantics while using {{c|alloc}} as allocator, as if by {{c|c(std::move(cont), alloc)}}. Copy-constructs {{c|comp}} from {{c|compare}}. Then calls {{c|std::make_heap(c.begin(), c.end(), comp)}}.
-@14@Constructs the underlying container with the contents of {{c|other.c}} and using {{c|alloc}} as allocator. Effectively calls {{c|c(other.c, alloc)}}. Copy-constructs {{c|comp}} from {{c|other.comp}}.
+@14@ Constructs the underlying container with the contents of {{c|other.c}} and using {{c|alloc}} as allocator. Effectively calls {{c|c(other.c, alloc)}}. Copy-constructs {{c|comp}} from {{c|other.comp}}.
 @15@ Constructs the underlying container with the contents of {{c|other}} using move semantics while utilizing {{c|alloc}} as allocator. Effectively calls {{c|c(std::move(other.c), alloc)}}. Move-constructs {{c|comp}} from {{c|other.comp}}.
@@ Line 158: / Line 158: @@
 {{par|compare|the comparison function object to initialize the underlying comparison functor}}
 {{par|first, last|a range {{range|first|last}} of elements to initialize with}}
-{{par|rg|a {{ls|cpp/ranges/to|container compatible range}}, that is, an {{lconcept|input_range}} whose elements are convertible to {{tt|T}}}}
+{{par|rg|a {{ls|cpp/ranges/to#container compatible range}}, that is, an {{lconcept|input_range}} whose elements are convertible to {{tt|T}}}}
 {{par hreq}}
 {{par req named|Alloc|Allocator}}
@@ Line 177: / Line 177: @@
 @7,16,17@ {{mathjax-or|\(\scriptsize \mathcal{O}{(M)}\)|O(M)}} comparisons, where {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
-@8,18@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N+M)}\)|O(N+M)}} comparisons and {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} calls to the constructor of {{tt|value_type}}, where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}} and {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
+@8,18@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N + M)}\)|O(N + M)}} comparisons and {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} calls to the constructor of {{tt|value_type}}, where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}} and {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
-@9@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N+M)}\)|O(N+M)}} comparisons, where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}} and {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
+@9@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N + M)}\)|O(N + M)}} comparisons, where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}} and {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
 @10,11@ Constant.
@@ Line 189: / Line 189: @@
 @15@ Constant if {{tt|Alloc}} compares equal to the allocator of {{c|other}}. Linear in size of {{c|other}} otherwise.
-@19@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N+M)}\)|O(N+M)}} comparisons and possibly {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} calls to the constructor of {{tt|value_type}} (present if {{tt|Alloc}} does not compare equal to the allocator of {{c|other}}), where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}} and {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
+@19@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N + M)}\)|O(N + M)}} comparisons and possibly {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} calls to the constructor of {{tt|value_type}} (present if {{tt|Alloc}} does not compare equal to the allocator of {{c|other}}), where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}} and {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
 @20@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} comparisons and {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} calls to the constructor of {{tt|value_type}}, where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|ranges::distance(rg)}}.
-@21-22@ {{todo}}
+@21,22@ {{todo}}
 ===Notes===
@@ Line 223: / Line 223: @@
          std::cout << pq3.top() << ' ';
      std::cout << '\n';
      // Demo With Custom Comparator:
@@ Line 237: / Line 236: @@
      std::priority_queue<my_value_t,
                          my_container_t,
-                         decltype(my_comp)> pq4 {my_comp};
+                         decltype(my_comp)> pq4{my_comp};
      using namespace std::complex_literals;

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

Sequence
array (C++11)
vector
vector<bool>
inplace_vector (C++26)
deque
forward_list (C++11)
list
Associative
set
multiset
map
multimap
Unordered associative
unordered_set (C++11)
unordered_multiset (C++11)
unordered_map (C++11)
unordered_multimap (C++11)
Adaptors
stack
queue
priority_queue
flat_set (C++23)
flat_multiset (C++23)
flat_map (C++23)
flat_multimap (C++23)
Views
span (C++20)
mdspan (C++23)
Tables
Iterator invalidation
Member function table
Non-member function table

Member functions
priority_queue::priority_queue
priority_queue::~priority_queue
priority_queue::operator=
Element access
priority_queue::top
Capacity
priority_queue::empty
priority_queue::size
Modifiers
priority_queue::push
priority_queue::push_range (C++23)
priority_queue::emplace (C++11)
priority_queue::pop
priority_queue::swap (C++11)
Non-member functions
swap(std::priority_queue) (C++11)
Helper classes
uses_allocator<std::priority_queue> (C++11)
formatter<std::priority_queue> (C++23)
Deduction guides(C++17)

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/container/priority queue/priority queue"

Latest revision as of 01:28, 4 November 2023

Contents

[edit] Parameters

[edit] Complexity

[edit] Notes

[edit] Example

[edit] Defect reports

[edit] See also

Navigation

Toolbox