std::priority_queue<T,Container,Compare>::priority_queue (3) - Linux Manuals

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

NAME

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

Synopsis

priority_queue() : priority_queue(Compare(), Container()) { } (1) (since C++11)
explicit priority_queue(const Compare& compare) (2) (since C++11)
: priority_queue(compare, Container()) { }
explicit priority_queue( const Compare& compare = Compare(), (until C++11)
const Container& cont = Container() );
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 Alloc > (7) (since C++11)
explicit priority_queue( const Alloc& alloc );
template< class Alloc > (8) (since C++11)
priority_queue( const Compare& compare, const Alloc& alloc );
template< class Alloc >
priority_queue( const Compare& compare, const Container& cont, (9) (since C++11)
const Alloc& alloc );
template< class Alloc > (3)
priority_queue( const Compare& compare, Container&& cont, (10) (since C++11)
const Alloc& alloc );
template< class Alloc > (11) (since C++11)
priority_queue( const priority_queue& other, const Alloc& alloc );
template< class Alloc > (12) (since C++11)
priority_queue( priority_queue&& other, const Alloc& alloc );
template< class InputIt >
priority_queue( InputIt first, InputIt last, (13) (since C++11)
const Compare& compare, const Container& cont );
template< class InputIt >
priority_queue( InputIt first, InputIt last, (14) (since C++11)
const Compare& compare = Compare(),
Container&& cont = Container() );

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 the contents of compare. Calls std::make_heap(c.begin(), c.end(), comp).
5) Copy constructor. The adaptor is copy-constructed with the contents of other.c. The comparison functor is constructed with std::move(other.comp). (implicitly declared)
6) Move constructor. The adaptor is constructed with std::move(other.c).The comparison functor is constructed with std::move(other.comp). (implicitly declared)
7-12) The following constructors are only defined if 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).
7) Constructs the underlying container using alloc as allocator. Effectively calls c(alloc). comp is value-initialized.
8) Constructs the underlying container using alloc as allocator. Effectively calls c(alloc). Copy-constructs comp from compare.
9) 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).
10) 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).
11) Constructs the adaptor with the contents of other.c and using alloc as allocator. Effectively calls c(other.c, alloc). Copy-constructs comp from other.comp.
12) Constructs the adaptor 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.
13) 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);.
14) Move-constructs c from std::move(cont) and comp from std::move(compare). Then calls c.insert(c.end(), first, last);, and then calls std::make_heap(c.begin(), c.end(), comp);.

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 constructors (5-10) are only defined if Container meets the requirements of AllocatorAwareContainer
-
InputIt must meet the requirements of LegacyInputIterator.

Complexity

1-2) Constant.
3,5) O(N) comparisons, where N is cont.size().
Additionally, O(N) calls to the constructor of value_type, where N is cont.size().
4) O(N) comparisons, where N is cont.size().
6-8) Constant.
9) O(N) comparisons, where N is cont.size().
Additionally, O(N) calls to the constructor of value_type, where N is cont.size().
10) O(N) comparisons, where N is cont.size().
11) Linear in size of other.
12) Constant.
13) O(N) comparisons, where N is cont.size() + std::distance(first, last).
Additionally, O(N) calls to the constructor of value_type, where N is cont.size().
14) O(N) comparisons, where N is cont.size() + std::distance(first, last).

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

Example

// Run this code

  #include <queue>
  #include <vector>
  #include <iostream>
  #include <functional>

  int main()
  {
      std::priority_queue<int> c1;
      c1.push(5);
      std::cout << c1.size() << '\n';

      std::priority_queue<int> c2(c1);
      std::cout << c2.size() << '\n';

      std::vector<int> vec={3, 1, 4, 1, 5};
      std::priority_queue<int> c3(std::less<int>(), vec);
      std::cout << c3.size() << '\n';
  }

Output:

  1
  1
  5

Example With Custom Comparator

// Run this code

  #include <iostream>
  #include <queue>
  #include <vector>
  #include <utility>

  using my_pair_t = std::pair<size_t,bool>;

  using my_container_t = std::vector<my_pair_t>;

  int main()
  {
      auto my_comp =
          [](const my_pair_t& e1, const my_pair_t& e2)
          { return e1.first > e2.first; };
      std::priority_queue<my_pair_t,
                          my_container_t,
                          decltype(my_comp)> queue(my_comp);
      queue.push(std::make_pair(5, true));
      queue.push(std::make_pair(3, false));
      queue.push(std::make_pair(7, true));
      std::cout << std::boolalpha;
      while(!queue.empty())
      {
          const auto& p = queue.top();
          std::cout << p.first << " " << p.second << "\n";
          queue.pop();
      }
  }

Output:

  3 false
  5 true
  7 true