Class template priority_queue

boost::heap::priority_queue — priority queue, based on stl heap functions

Synopsis

// In header: <boost/heap/priority_queue.hpp>

template<typename T, class ... Options> 
class priority_queue {
public:
  // types
  typedef T                                       value_type;     
  typedef implementation_defined::size_type       size_type;      
  typedef implementation_defined::difference_type difference_type;
  typedef implementation_defined::value_compare   value_compare;  
  typedef implementation_defined::allocator_type  allocator_type; 
  typedef implementation_defined::reference       reference;      
  typedef implementation_defined::const_reference const_reference;
  typedef implementation_defined::pointer         pointer;        
  typedef implementation_defined::const_pointer   const_pointer;  
  typedef implementation_defined::iterator        iterator;       
  typedef implementation_defined::const_iterator  const_iterator; 

  // construct/copy/destruct
  explicit priority_queue(value_compare const & = value_compare());
  priority_queue(priority_queue const &);
  priority_queue(priority_queue &&) noexcept(boost::is_nothrow_move_constructible< super_t >::value));
  priority_queue & 
  operator=(priority_queue &&) noexcept(boost::is_nothrow_move_assignable< super_t >::value));
  priority_queue & operator=(priority_queue const &);

  // public member functions
  bool empty(void) const noexcept;
  size_type size(void) const noexcept;
  size_type max_size(void) const noexcept;
  void clear(void) noexcept;
  allocator_type get_allocator(void) const;
  const_reference top(void) const;
  void push(value_type const &);
  template<class... Args> void emplace(Args &&...);
  void pop(void);
  void swap(priority_queue &) noexcept(boost::is_nothrow_move_constructible< super_t >::value &&boost::is_nothrow_move_assignable< super_t >::value));
  iterator begin(void) const noexcept;
  iterator end(void) const noexcept;
  void reserve(size_type);
  value_compare const  & value_comp(void) const;
  template<typename HeapType> bool operator<(HeapType const &) const;
  template<typename HeapType> bool operator>(HeapType const &) const;
  template<typename HeapType> bool operator>=(HeapType const &) const;
  template<typename HeapType> bool operator<=(HeapType const &) const;
  template<typename HeapType> bool operator==(HeapType const &) const;
  template<typename HeapType> bool operator!=(HeapType const &) const;

  // public data members
  static const bool constant_time_size;
  static const bool has_ordered_iterators;
  static const bool is_mergable;
  static const bool is_stable;
  static const bool has_reserve;
};

Description

The priority_queue class is a wrapper for the stl heap functions.
The template parameter T is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.

The container supports the following options:

boost::heap::compare<>, defaults to compare<std::less<T> >
boost::heap::stable<>, defaults to stable<false>
boost::heap::stability_counter_type<>, defaults to stability_counter_type<boost::uintmax_t>
boost::heap::allocator<>, defaults to allocator<std::allocator<T> >

`priority_queue` public types

typedef implementation_defined::iterator iterator;

Note: The iterator does not traverse the priority queue in order of the priorities.

`priority_queue` public construct/copy/destruct

explicit priority_queue(value_compare const & cmp = value_compare());

Effects: constructs an empty priority queue.

Complexity: Constant.

```
priority_queue(priority_queue const & rhs);
```
Effects: copy-constructs priority queue from rhs.

Complexity: Linear.
```
priority_queue(priority_queue && rhs) noexcept(boost::is_nothrow_move_constructible< super_t >::value));
```
Effects: C++11-style move constructor.

Complexity: Constant.

Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
```
priority_queue & 
operator=(priority_queue && rhs) noexcept(boost::is_nothrow_move_assignable< super_t >::value));
```
Effects: C++11-style move assignment.

Complexity: Constant.

Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined

priority_queue & operator=(priority_queue const & rhs);

Effects: Assigns priority queue from rhs.

Complexity: Linear.

`priority_queue` public member functions

```
bool empty(void) const noexcept;
```
Effects: Returns true, if the priority queue contains no elements.

Complexity: Constant.
```
size_type size(void) const noexcept;
```
Effects: Returns the number of elements contained in the priority queue.

Complexity: Constant.
```
size_type max_size(void) const noexcept;
```
Effects: Returns the maximum number of elements the priority queue can contain.

Complexity: Constant.
```
void clear(void) noexcept;
```
Effects: Removes all elements from the priority queue.

Complexity: Linear.
```
allocator_type get_allocator(void) const;
```
Effects: Returns allocator.

Complexity: Constant.
```
const_reference top(void) const;
```
Effects: Returns a const_reference to the maximum element.

Complexity: Constant.
```
void push(value_type const & v);
```
Effects: Adds a new element to the priority queue.

Complexity: Logarithmic (amortized). Linear (worst case).
```
template<class... Args> void emplace(Args &&... args);
```
Effects: Adds a new element to the priority queue. The element is directly constructed in-place.

Complexity: Logarithmic (amortized). Linear (worst case).
```
void pop(void);
```
Effects: Removes the top element from the priority queue.

Complexity: Logarithmic (amortized). Linear (worst case).

void swap(priority_queue & rhs) noexcept(boost::is_nothrow_move_constructible< super_t >::value &&boost::is_nothrow_move_assignable< super_t >::value));

Effects: Swaps two priority queues.

Complexity: Constant.

```
iterator begin(void) const noexcept;
```
Effects: Returns an iterator to the first element contained in the priority queue.

Complexity: Constant.
```
iterator end(void) const noexcept;
```
Effects: Returns an iterator to the end of the priority queue.

Complexity: Constant.
```
void reserve(size_type element_count);
```
Effects: Reserves memory for element_count elements

Complexity: Linear.

Node: Invalidates iterators
```
value_compare const  & value_comp(void) const;
```
Effect: Returns the value_compare object used by the priority queue
```
template<typename HeapType> bool operator<(HeapType const & rhs) const;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType> bool operator>(HeapType const & rhs) const;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType> bool operator>=(HeapType const & rhs) const;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType> bool operator<=(HeapType const & rhs) const;
```
Returns: Element-wise comparison of heap data structures

Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType> bool operator==(HeapType const & rhs) const;
```
Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare object of both heaps must match.
```
template<typename HeapType> bool operator!=(HeapType const & rhs) const;
```
Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare object of both heaps must match.

Boost C++ Libraries