...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::heap::priority_queue — priority queue, based on stl heap functions
// 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 &&); priority_queue& operator=(priority_queue &&); priority_queue& operator=(priority_queue const &); // public member functions bool empty(void) const; size_type size(void) const; size_type max_size(void) const; void clear(void); 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 &); iterator begin(void) const; iterator end(void) const; 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; };
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
construct/copy/destructexplicit 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);
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);
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 functionsbool empty(void) const;
Effects: Returns true, if the priority queue contains no elements.
Complexity: Constant.
size_type size(void) const;
Effects: Returns the number of elements contained in the priority queue.
Complexity: Constant.
size_type max_size(void) const;
Effects: Returns the maximum number of elements the priority queue can contain.
Complexity: Constant.
void clear(void);
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);
Effects: Swaps two priority queues.
Complexity: Constant.
iterator begin(void) const;
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
iterator end(void) const;
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.