d-ary heap class More...
#include <d_ary_heap.hpp>
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 |
Note: The iterator does not traverse the priority queue in order of the priorities. More... | |
typedef implementation_defined::const_iterator | const_iterator |
typedef implementation_defined::ordered_iterator | ordered_iterator |
typedef implementation_defined::handle_type | handle_type |
typedef T | type |
Public Member Functions | |
d_ary_heap (value_compare const &cmp=value_compare()) | |
Effects: constructs an empty priority queue. More... | |
d_ary_heap (d_ary_heap const &rhs) | |
Effects: copy-constructs priority queue from rhs. More... | |
d_ary_heap (d_ary_heap &&rhs) | |
Effects: C++11-style move constructor. More... | |
d_ary_heap & | operator= (d_ary_heap &&rhs) |
Effects: C++11-style move assignment. More... | |
d_ary_heap & | operator= (d_ary_heap const &rhs) |
Effects: Assigns priority queue from rhs. More... | |
bool | empty (void) const |
Effects: Returns true, if the priority queue contains no elements. More... | |
size_type | size (void) const |
Effects: Returns the number of elements contained in the priority queue. More... | |
size_type | max_size (void) const |
Effects: Returns the maximum number of elements the priority queue can contain. More... | |
void | clear (void) |
Effects: Removes all elements from the priority queue. More... | |
allocator_type | get_allocator (void) const |
Effects: Returns allocator. More... | |
value_type const & | top (void) const |
Effects: Returns a const_reference to the maximum element. More... | |
mpl::if_c< is_mutable, handle_type, void >::type | push (value_type const &v) |
Effects: Adds a new element to the priority queue. More... | |
template<class... Args> | |
mpl::if_c< is_mutable, handle_type, void >::type | emplace (Args &&...args) |
Effects: Adds a new element to the priority queue. More... | |
template<typename HeapType > | |
bool | operator< (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator> (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator>= (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator<= (HeapType const &rhs) const |
Returns: Element-wise comparison of heap data structures More... | |
template<typename HeapType > | |
bool | operator== (HeapType const &rhs) const |
Equivalent comparison Returns: True, if both heap data structures are equivalent. More... | |
template<typename HeapType > | |
bool | operator!= (HeapType const &rhs) const |
Equivalent comparison Returns: True, if both heap data structures are not equivalent. More... | |
void | update (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | update (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | increase (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | increase (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | decrease (handle_type handle, const_reference v) |
Effects: Assigns v to the element handled by handle & updates the priority queue. More... | |
void | decrease (handle_type handle) |
Effects: Updates the heap after the element handled by handle has been changed. More... | |
void | erase (handle_type handle) |
Effects: Removes the element handled by handle from the priority_queue. More... | |
void | pop (void) |
Effects: Removes the top element from the priority queue. More... | |
void | swap (d_ary_heap &rhs) |
Effects: Swaps two priority queues. More... | |
const_iterator | begin (void) const |
Effects: Returns an iterator to the first element contained in the priority queue. More... | |
iterator | begin (void) |
Effects: Returns an iterator to the first element contained in the priority queue. More... | |
iterator | end (void) |
Effects: Returns an iterator to the end of the priority queue. More... | |
const_iterator | end (void) const |
Effects: Returns an iterator to the end of the priority queue. More... | |
ordered_iterator | ordered_begin (void) const |
Effects: Returns an ordered iterator to the first element contained in the priority queue. More... | |
ordered_iterator | ordered_end (void) const |
Effects: Returns an ordered iterator to the end of the priority queue. More... | |
void | reserve (size_type element_count) |
Effects: Reserves memory for element_count elements More... | |
value_compare const & | value_comp (void) const |
Effect: Returns the value_compare object used by the priority queue More... | |
Static Public Member Functions | |
static handle_type | s_handle_from_iterator (iterator const &it) |
Effects: Casts an iterator to a node handle. More... | |
Static Public Attributes | |
static const bool | constant_time_size = true |
static const bool | has_ordered_iterators = true |
static const bool | is_mergable = false |
static const bool | has_reserve = true |
static const bool | is_stable = super_t::is_stable |
Friends | |
template<typename Heap1 , typename Heap2 > | |
struct | heap_merge_emulate |
d-ary heap class
This class implements an immutable priority queue. Internally, the d-ary heap is represented as dynamically sized array (std::vector), that directly stores the values.
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::arity<>
, requiredboost::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>
>boost::heap::mutable_<>
, defaults to mutable_<false>
typedef implementation_defined::allocator_type boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::allocator_type |
typedef implementation_defined::const_iterator boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::const_iterator |
typedef implementation_defined::const_pointer boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::const_pointer |
typedef implementation_defined::const_reference boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::const_reference |
typedef implementation_defined::difference_type boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::difference_type |
typedef implementation_defined::handle_type boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::handle_type |
typedef implementation_defined::iterator boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::iterator |
Note: The iterator does not traverse the priority queue in order of the priorities.
typedef implementation_defined::ordered_iterator boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::ordered_iterator |
typedef implementation_defined::pointer boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::pointer |
typedef implementation_defined::reference boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::reference |
typedef implementation_defined::size_type boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::size_type |
|
inherited |
typedef implementation_defined::value_compare boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::value_compare |
typedef T boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::value_type |
|
inlineexplicit |
Effects: constructs an empty priority queue.
Complexity: Constant.
|
inline |
Effects: copy-constructs priority queue from rhs.
Complexity: Linear.
|
inline |
Effects: C++11-style move constructor.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
|
inline |
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
References boost::asio::begin.
|
inline |
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
References boost::asio::begin.
|
inline |
Effects: Removes all elements from the priority queue.
Complexity: Linear.
References boost::fusion::clear().
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic.
Note: The new value is expected to be less than the current one
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic.
Note: The new value is expected to be less than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Adds a new element to the priority queue.
The element is directly constructed in-place.
Complexity: Logarithmic (amortized). Linear (worst case).
References boost::python::args().
|
inline |
Effects: Returns true, if the priority queue contains no elements.
Complexity: Constant.
References empty().
|
inline |
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
References boost::asio::end.
|
inline |
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
References boost::asio::end.
|
inline |
Effects: Removes the element handled by handle
from the priority_queue.
Complexity: Logarithmic.
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT(), and boost::fusion::erase().
|
inline |
Effects: Returns allocator.
Complexity: Constant.
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic.
Note: The new value is expected to be greater than the current one
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic.
Note: The new value is expected to be greater than the current one. If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Returns the maximum number of elements the priority queue can contain.
Complexity: Constant.
|
inline |
Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare
object of both heaps must match.
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
Referenced by boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::operator>=().
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
References boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::operator>().
|
inline |
Effects: C++11-style move assignment.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
References boost::fusion::move(), and boost::multiprecision::backends::operator=().
|
inline |
Effects: Assigns priority queue from rhs.
Complexity: Linear.
References boost::multiprecision::backends::operator=().
|
inline |
Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare
object of both heaps must match.
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
Referenced by boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::operator<=().
|
inline |
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
References boost::heap::d_ary_heap< T, A0, A1, A2, A3, A4, A5 >::operator<().
|
inline |
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
|
inline |
Effects: Returns an ordered iterator to the end of the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
|
inline |
Effects: Removes the top element from the priority queue.
Complexity: Logarithmic (amortized). Linear (worst case).
References boost::xpressive::pop.
|
inline |
Effects: Adds a new element to the priority queue.
Complexity: Logarithmic (amortized). Linear (worst case).
References boost::xpressive::push.
|
inline |
Effects: Reserves memory for element_count elements
Complexity: Linear.
Node: Invalidates iterators
|
inlinestatic |
Effects: Casts an iterator to a node handle.
Complexity: Constant.
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Returns the number of elements contained in the priority queue.
Complexity: Constant.
References boost::fusion::size().
|
inline |
|
inline |
Effects: Returns a const_reference to the maximum element.
Complexity: Constant.
References boost::xpressive::top.
|
inline |
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic.
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effects: Updates the heap after the element handled by handle
has been changed.
Complexity: Logarithmic.
Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!
Requirement: data structure must be configured as mutable
References boost::BOOST_STATIC_ASSERT().
|
inline |
Effect: Returns the value_compare object used by the priority queue
|
friend |
|
static |
|
static |
|
static |
|
static |
|
static |