Namespaces
Variants
Views
Actions

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

From cppreference.com
(Fixed unmatched par)
m (fmt, @-@ -> @,@)
 
(31 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
{{cpp/container/priority_queue/title | priority_queue}}
+
{{cpp/container/priority_queue/title|priority_queue}}
 
{{cpp/container/priority_queue/navbar}}
 
{{cpp/container/priority_queue/navbar}}
 
{{dcl begin}}
 
{{dcl begin}}
−
{{dcl rev begin | num=1}}
+
{{dcl|num=1|since=c++11|
−
{{dcl | until=c++11 | 1=
+
priority_queue() : priority_queue(Compare(), Container()) {}
 +
}}
 +
{{dcl|num=2|since=c++11|
 +
explicit priority_queue( const Compare& compare )
 +
    : priority_queue(compare, Container()) {}
 +
}}
 +
{{dcl rev multi|num=3
 +
|dcl1=
 
explicit priority_queue( const Compare& compare = Compare(),
 
explicit priority_queue( const Compare& compare = Compare(),
 
                         const Container& cont = Container() );
 
                         const Container& cont = Container() );
−
}}
+
|since2=c++11|dcl2=
−
{{dcl | since=c++11 | 1=
+
 
priority_queue( const Compare& compare, const Container& cont );
 
priority_queue( const Compare& compare, const Container& cont );
 
}}
 
}}
−
{{dcl rev end}}
+
{{dcl|num=4|since=c++11|
−
{{dcl | num=2 | since=c++11 | 1=
+
priority_queue( const Compare& compare, Container&& cont );
−
explicit priority_queue( const Compare& compare = Compare(),
+
−
                        Container&& cont = Container() );
+
 
}}
 
}}
−
{{dcl | num=3 |1=
+
{{dcl|num=5|
 
priority_queue( const priority_queue& other );
 
priority_queue( const priority_queue& other );
 
}}
 
}}
−
{{dcl | num=4 | since=c++11 |1=
+
{{dcl|num=6|since=c++11|
 
priority_queue( priority_queue&& other );
 
priority_queue( priority_queue&& other );
 
}}
 
}}
−
{{dcl | num=5 | since=c++11 |1=
+
{{dcl|num=7|since=c++11|1=
−
template< class Alloc >  
+
template< class InputIt >
 +
priority_queue( InputIt first, InputIt last,
 +
                const Compare& compare = Compare() );
 +
}}
 +
{{dcl rev multi|num=8
 +
|dcl1=
 +
template< class InputIt >
 +
priority_queue( InputIt first, InputIt last,
 +
                const Compare& compare = Compare(),
 +
                const Container& cont = Container() );
 +
|since2=c++11|dcl2=
 +
template< class InputIt >
 +
priority_queue( InputIt first, InputIt last,
 +
                const Compare& compare, const Container& cont );
 +
}}
 +
{{dcl|num=9|since=c++11|
 +
template< class InputIt >
 +
priority_queue( InputIt first, InputIt last,
 +
                const Compare& compare, Container&& cont );
 +
}}
 +
{{dcl|num=10|since=c++11|
 +
template< class Alloc >
 
explicit priority_queue( const Alloc& alloc );
 
explicit priority_queue( const Alloc& alloc );
 
}}
 
}}
−
{{dcl | num=6 | since=c++11 |1=
+
{{dcl|num=11|since=c++11|
−
template< class Alloc >  
+
template< class Alloc >
 
priority_queue( const Compare& compare, const Alloc& alloc );
 
priority_queue( const Compare& compare, const Alloc& alloc );
 
}}
 
}}
−
{{dcl | num=7 | since=c++11 |1=
+
{{dcl|num=12|since=c++11|
−
template< class Alloc >  
+
template< class Alloc >
 
priority_queue( const Compare& compare, const Container& cont,
 
priority_queue( const Compare& compare, const Container& cont,
 
                 const Alloc& alloc );
 
                 const Alloc& alloc );
 
}}
 
}}
−
{{dcl | num=8 | since=c++11 |1=
+
{{dcl|num=13|since=c++11|
−
template< class Alloc >  
+
template< class Alloc >
 
priority_queue( const Compare& compare, Container&& cont,
 
priority_queue( const Compare& compare, Container&& cont,
 
                 const Alloc& alloc );
 
                 const Alloc& alloc );
 
}}
 
}}
−
{{dcl | num=9 | since=c++11 |1=
+
{{dcl|num=14|since=c++11|
−
template< class Alloc >  
+
template< class Alloc >
 
priority_queue( const priority_queue& other, const Alloc& alloc );
 
priority_queue( const priority_queue& other, const Alloc& alloc );
 
}}
 
}}
−
{{dcl | num=10 | since=c++11 |1=
+
{{dcl|num=15|since=c++11|
−
template< class Alloc >  
+
template< class Alloc >
 
priority_queue( priority_queue&& other, const Alloc& alloc );
 
priority_queue( priority_queue&& other, const Alloc& alloc );
 
}}
 
}}
−
{{dcl | num=11 | since=c++11 |1=
+
{{dcl|num=16|since=c++11|
−
template< class InputIt >
+
template< class InputIt, class Alloc >
−
priority_queue( InputIt first, InputIt last,
+
priority_queue( InputIt first, InputIt last, const Alloc& alloc );
−
                const Compare& compare, const Container& cont );
+
 
}}
 
}}
−
{{dcl | num=12 | since=c++11 |1=
+
{{dcl|num=17|since=c++11|
−
template< class InputIt >
+
template< class InputIt, class Alloc >
−
priority_queue( InputIt first, InputIt last,
+
priority_queue( InputIt first, InputIt last, const Compare& compare,
−
                 const Compare& compare = Compare(),  
+
                 const Alloc& alloc );
−
                 Container&& cont = Container() );
+
}}
 +
{{dcl|num=18|since=c++11|
 +
template< class InputIt, class Alloc >
 +
priority_queue( InputIt first, InputIt last, const Compare& compare,
 +
                const Container& cont, const Alloc& alloc );
 +
}}
 +
{{dcl|num=19|since=c++11|
 +
template< class InputIt, class Alloc >
 +
priority_queue( InputIt first, InputIt last, const Compare& compare,
 +
                 Container&& cont, const Alloc& alloc );
 +
}}
 +
{{dcla|num=20|since=c++23|1=
 +
template< container-compatible-range<T> R >
 +
priority_queue( std::from_range_t, R&& rg,
 +
                const Compare& compare = Compare() );
 +
}}
 +
{{dcl|num=21|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 );
 +
}}
 +
{{dcl|num=22|since=c++23|
 +
template< container-compatible-range<T> R, class Alloc >
 +
priority_queue( std::from_range_t, R&& rg, const Alloc& alloc );
 
}}
 
}}
 
{{dcl end}}
 
{{dcl end}}
Line 62: Line 109:
 
Constructs new underlying container of the container adaptor from a variety of data sources.
 
Constructs new underlying container of the container adaptor from a variety of data sources.
  
−
@1@ Copy-constructs the underlying container {{tt|c}} with the contents of {{tt|cont}}. Copy-constructs the comparison functor {{tt|comp}} with the contents of {{tt|compare}}. Calls {{c|std::make_heap(c.begin(), c.end(), comp)}}.}} {{rev inl|until=c++11| This is also the default constructor.}}
+
@1@ Default constructor. Value-initializes the comparator and the underlying container.
  
−
@2@ Move-constructs the underlying container {{tt|c}} with {{c|std::move(cont)}}. Move-constructs the comparison functor {{tt|comp}} with {{c|std::move(compare)}}. Calls {{c|std::make_heap(c.begin(), c.end(), comp)}}. {{rev inl|since=c++11 | This is also the default constructor.}}
+
@2@ Copy-constructs the comparison functor {{c|comp}} with the contents of {{c|compare}}. Value-initializes the underlying container {{c|c}}.
  
−
@3@ Copy constructor. The adaptor is copy-constructed with the contents of {{c|other.c}}. The comparison functor is constructed with {{c|std::move(other.comp)}}. {{mark implicit}}
+
@3@ Copy-constructs the underlying container {{c|c}} with the contents of {{c|cont}}. Copy-constructs the comparison functor {{c|comp}} with the contents of {{c|compare}}. Calls {{c|std::make_heap(c.begin(), c.end(), comp)}}. {{rev inl|until=c++11|This is also the default constructor.}}
  
−
@4@ Move constructor. The adaptor is constructed with {{c|std::move(other.c)}}.The comparison functor is constructed with {{c|std::move(other.comp)}}. {{mark implicit}}
+
@4@ Move-constructs the underlying container {{c|c}} with {{c|std::move(cont)}}. Copy-constructs the comparison functor {{c|comp}} with {{c|compare}}. Calls {{c|std::make_heap(c.begin(), c.end(), comp)}}.
  
−
@5-10@ The following constructors are only defined if {{c|1=std::uses_allocator<container_type, Alloc>::value == true}}, that is, if the underlying container is an allocator-aware container (true for all standard library containers).
+
@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}}
  
−
:@5@ Constructs the underlying container using {{tt|alloc}} as allocator. Effectively calls {{c|c(alloc)}}. {{#ifeq:priority_queue|priority_queue|{{tt|comp}} is value-initialized.}}
+
@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@ Constructs the underlying container using {{tt|alloc}} as allocator. Effectively calls {{c|c(alloc)}}. Copy-constructs {{tt|comp}} from {{tt|compare}}.
+
@7-9@ Iterator-pair constructors. {{cpp/enable_if|{{tt|InputIt}} satisfies {{named req|InputIterator}}|plural=yes}}.
  
−
:@7@ Constructs the underlying container with the contents of {{tt|cont}} and using {{tt|alloc}} as allocator. Effectively calls {{c|c(cont, alloc)}}. Copy-constructs {{tt|comp}} from {{tt|compare}}.
+
@7@ Constructs {{c|c}} as if by {{c|c(first, last)}} and {{c|comp}} from {{c|compare}}. Then calls {{c|std::make_heap(c.begin(), c.end(), comp);}}.
  
−
:@8@ Constructs the underlying container with the contents of {{tt|cont}} using move semantics while utilising {{tt|alloc}} as allocator. Effectively calls {{c|c(std::move(cont), alloc)}}. Copy-constructs {{tt|comp}} from {{tt|compare}}.
+
@8@ Copy-constructs {{c|c}} from {{c|cont}} and {{c|comp}} from {{c|compare}}. Then calls {{c|c.insert(c.end(), first, last);}}, and then calls {{c|std::make_heap(c.begin(), c.end(), comp);}}.
  
−
:@9@Constructs the adaptor with the contents of {{tt|other.c}} and using {{tt|alloc}} as allocator. Effectively calls {{c|c(athor.c, alloc)}}. Copy-constructs {{tt|comp}} from {{tt|other.comp}}.
+
@9@ Move-constructs {{c|c}} from {{c|std::move(cont)}} and copy-constructs {{c|comp}} from {{c|compare}}. Then calls {{c|c.insert(c.end(), first, last);}}, and then calls {{c|std::make_heap(c.begin(), c.end(), comp);}}.
  
−
:@10@ Constructs the adaptor with the contents of {{tt|other}} using move semantics while utilising {{tt|alloc}} as allocator. Effectively calls {{c|c(std::move(other.c), alloc)}}. Move-constructs {{tt|comp}} from {{tt|other.comp}}.
+
@10-15@ Allocator-extended constructors. {{cpp/enable_if|{{c|std::uses_allocator<container_type, Alloc>::value}} is {{c|true}}, that is, if the underlying container is an allocator-aware container (true for all standard library containers)|plural=yes}}.
  
−
@11@ Copy-constructs {{tt|c}} from {{tt|cont}} and {{tt|comp}} from {{tt|compare}}. Then calls {{c|c.insert(c.end(), first, last);}}, and then calls {{c|std::make_heap(c.begin(), c.end(), comp);}}.
+
@10@ Constructs the underlying container using {{c|alloc}} as allocator. Effectively calls {{c|c(alloc)}}. {{c|comp}} is value-initialized.
  
−
@12@ Move-constructs {{tt|c}} from {{tt|std::move(cont)}} and {{tt|comp}} from {{tt|std::move(compare)}}. Then calls {{c|c.insert(c.end(), first, last);}}, and then calls {{c|std::make_heap(c.begin(), c.end(), comp);}}.
+
@11@ Constructs the underlying container using {{c|alloc}} as allocator. Effectively calls {{c|c(alloc)}}. Copy-constructs {{c|comp}} from {{c|compare}}.
 +
 
 +
@12@ Constructs the underlying container with the contents of {{c|cont}} and using {{c|alloc}} as allocator, as if by {{c|c(cont, alloc)}}. Copy-constructs {{c|comp}} from {{c|compare}}. Then calls {{c|std::make_heap(c.begin(), c.end(), comp)}}.
 +
 
 +
@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}}.
 +
 
 +
@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}}.
 +
 
 +
@16-19@ Allocator-extended iterator-pair constructors. Same as {{v|7-9}}, except that {{c|alloc}} is used for constructing the underlying container. {{cpp/enable_if|{{c|std::uses_allocator<container_type, Alloc>::value}} is {{c|true}} and {{c|InputIt}} satisfies {{named req|InputIterator}}|plural=yes}}.
 +
 
 +
@20@ Initializes {{c|comp}} with {{c|compare}} and {{c|c}} with {{c|ranges::to<Container>(std::forward<R>(rg))}}. Then calls {{c|std::make_heap(c.begin(), c.end(), comp)}}.
 +
@21@ Initializes {{c|comp}} with {{c|compare}} and {{c|c}} with {{c|ranges::to<Container>(std::forward<R>(rg), alloc)}}. Then calls {{c|std::make_heap(c.begin(), c.end(), comp)}}.
 +
@22@ Initializes {{c|c}} with {{c|ranges::to<Container>(std::forward<R>(rg), alloc)}}. Then calls {{c|std::make_heap(c.begin(), c.end(), comp)}}.
 +
 
 +
Note that how an implementation checks whether a type satisfies {{named req|InputIterator}} is unspecified, except that integral types are required to be rejected.
  
 
===Parameters===
 
===Parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | alloc | allocator to use for all memory allocations of the underlying container}}
+
{{par|alloc|allocator to use for all memory allocations of the underlying container}}
−
{{par | other | another container adaptor to be used as source to initialize the underlying container}}
+
{{par|other|another container adaptor to be used as source to initialize the underlying container}}
−
{{par | cont | container to be used as source to initialize the underlying container}}
+
{{par|cont|container to be used as source to initialize the underlying container}}
−
{{par | compare | the comparison function object to initialize the underlying comparison functor}}
+
{{par|compare|the comparison function object to initialize the underlying comparison functor}}
−
{{par | first, last | range of elements to initialize with}}
+
{{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 hreq}}
 
{{par hreq}}
−
{{par req concept | Alloc | Allocator}}
+
{{par req named|Alloc|Allocator}}
−
{{par req concept | Container | Container | notes=The constructors (5-10) are only defined if {{tt|Container}} meets the requirements of {{concept|AllocatorAwareContainer}}}}
+
{{par req named|Compare|Compare}}
−
{{par req concept | InputIt | InputIterator}}
+
{{par req named|Container|Container|notes=The allocator-extended constructors are only defined if {{tt|Container}} meets the requirements of {{named req|AllocatorAwareContainer}}.}}
−
{{par end}}  
+
{{par req named|InputIt|InputIterator}}
 +
{{par end}}
  
 
===Complexity===
 
===Complexity===
−
@1,3@ {{math|O(N log(N)}} comparisons, where {{math|N}} is {{c|cont.size()}}.
+
@1,2@ Constant.
  
−
@@ Additionally, {{math|O(N)}} calls to the constructor of {{tt|value_type}}, where {{math|N}} is {{c|cont.size()}}.
+
@3,5,12@ {{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|cont.size()}}.
  
−
@2@ {{math|O(N log(N)}} comparisons, where {{math|N}} is {{c|cont.size()}}.
+
@4@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} comparisons, where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}}.
  
−
@4-6@ Constant.
+
@6@ Constant.
  
−
@7@ {{math|O(N log(N)}} comparisons, where {{math|N}} is {{c|cont.size()}}.
+
@7,16,17@ {{mathjax-or|\(\scriptsize \mathcal{O}{(M)}\)|O(M)}} comparisons, where {{mathjax-or|\(\scriptsize M\)|M}} is {{c|std::distance(first, last)}}.
  
−
@@ Additionally, {{math|O(N)}} calls to the constructor of {{tt|value_type}}, where {{math|N}} is {{c|cont.size()}}.
+
@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@ {{math|O(N log(N)}} comparisons, where {{math|N}} is {{c|cont.size()}}.
+
@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@ Linear in size of {{tt|other}}.
+
@10,11@ Constant.
  
−
@10@ Constant.
+
@13@ {{mathjax-or|\(\scriptsize \mathcal{O}{(N)}\)|O(N)}} comparisons, where {{mathjax-or|\(\scriptsize N\)|N}} is {{c|cont.size()}}.
  
−
@11@ {{math|O(N log(N))}} comparisons, where {{math|N}} is {{c|cont.size() + std::distance(first, last)}}.
+
@14@ Linear in size of {{c|other}}.
  
−
@@ Additionally, {{math|O(N)}} calls to the constructor of {{tt|value_type}}, where {{math|N}} is {{c|cont.size()}}.
+
@15@ Constant if {{tt|Alloc}} compares equal to the allocator of {{c|other}}. Linear in size of {{c|other}} otherwise.
  
−
@12@ {{math|O(N log(N))}} comparisons, where {{math|N}} is {{c|cont.size() + 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}}
 +
 
 +
===Notes===
 +
{{feature test macro|__cpp_lib_containers_ranges|[[cpp/ranges/to#container compatible range|Ranges-aware]] construction and insertion; overloads {{vl|20-22}}|value=202202L|std=C++23}}
  
 
===Example===
 
===Example===
 
{{example
 
{{example
−
| code=
+
|code=
 +
#include <complex>
 +
#include <functional>
 +
#include <iostream>
 
#include <queue>
 
#include <queue>
 
#include <vector>
 
#include <vector>
−
#include <iostream>
 
−
#include <functional>
 
  
 
int main()
 
int main()
 
{
 
{
−
     std::priority_queue<int> c1;
+
     std::priority_queue<int> pq1;
−
     c1.push(5);
+
     pq1.push(5);
−
     std::cout << c1.size() << '\n';
+
     std::cout << "pq1.size() = " << pq1.size() << '\n';
  
−
     std::priority_queue<int> c2(c1);
+
     std::priority_queue<int> pq2 {pq1};
−
     std::cout << c2.size() << '\n';
+
     std::cout << "pq2.size() = " << pq2.size() << '\n';
−
+
 
−
     std::vector<int> vec={3, 1, 4, 1, 5};
+
     std::vector<int> vec {3, 1, 4, 1, 5};
−
     std::priority_queue<int> c3(std::less<int>(), vec);
+
     std::priority_queue<int> pq3 {std::less<int>(), vec};
−
     std::cout << c3.size() << '\n';
+
     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=
+
|output=
−
1
+
pq1.size() = 1
−
1
+
pq2.size() = 1
−
5
+
pq3.size() = 5
 +
pq3 : 5 4 3 1 1
 +
pq4.top() = (3,2)
 +
pq4.top() = (5,1)
 +
pq4.top() = (7,3)
 
}}
 
}}
 +
 +
===Defect reports===
 +
{{dr list begin}}
 +
{{dr list item|paper=P0935R0|std=C++11|before=default constructor and constructor {{v|4}} were explicit|after=made implicit}}
 +
{{dr list item|wg=lwg|dr=3506|std=C++11|before=allocator-extended iterator-pair constructors were missing|after=added}}
 +
{{dr list item|wg=lwg|dr=3522|std=C++11|before=constraints on iterator-pair constructors were missing|after=added}}
 +
{{dr list item|wg=lwg|dr=3529|std=C++11|before=construction from a pair of iterators called {{tt|insert}}|after=constructs the container from them}}
 +
{{dr list end}}
  
 
===See also===
 
===See also===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/container/dsc operator{{=}} | priority_queue}}
+
{{dsc inc|cpp/container/dsc operator{{=}}|priority_queue}}
 
{{dsc end}}
 
{{dsc end}}
  
−
[[de:cpp/container/priority queue/priority queue]]
+
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
−
[[es:cpp/container/priority queue/priority queue]]
+
−
[[fr:cpp/container/priority queue/priority queue]]
+
−
[[it:cpp/container/priority queue/priority queue]]
+
−
[[ja:cpp/container/priority queue/priority queue]]
+
−
[[pt:cpp/container/priority queue/priority queue]]
+
−
[[ru:cpp/container/priority queue/priority queue]]
+
−
[[zh:cpp/container/priority queue/priority queue]]
+

Latest revision as of 01:28, 4 November 2023

 
C++
 
Containers library
 
std::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)
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.

Contents

[edit] 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 - 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)
This section is incomplete

[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

 assigns values to the container adaptor
(public member function) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/priority_queue/priority_queue&oldid=161969"