![]() |
Home | Libraries | People | FAQ | More |
boost::heap::d_ary_heap — d-ary heap class
// In header: <boost/heap/d_ary_heap.hpp> template<typename T, Options> class d_ary_heap { public: // types typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; // construct/copy/destruct ( = ); (d_ary_heap ); (d_ary_heap &&); d_ary_heap & (d_ary_heap &&); d_ary_heap & (d_ary_heap ); // public member functions () ; () ; () ; (); () ; () ; (); template< Args> (); template<typename HeapType> () ; template<typename HeapType> () ; template<typename HeapType> () ; template<typename HeapType> () ; template<typename HeapType> () ; template<typename HeapType> () ; (, ); (); (, ); (); (, ); (); (); (); (d_ary_heap &); () ; (); (); () ; () ; () ; (); () ; // public static functions (); // public data members static constant_time_size; static has_ordered_iterators; static is_mergable; static has_reserve; static is_stable; };
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<>
, required
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>
>
boost::heap::mutable_<>
, defaults to mutable_<false>
d_ary_heap
public
construct/copy/destruct( cmp = );
Effects: constructs an empty priority queue.
Complexity: Constant.
(d_ary_heap rhs);
Effects: copy-constructs priority queue from rhs.
Complexity: Linear.
(d_ary_heap && rhs);
Effects: C++11-style move constructor.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
d_ary_heap & (d_ary_heap && rhs);
Effects: C++11-style move assignment.
Complexity: Constant.
Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined
d_ary_heap & (d_ary_heap rhs);
Effects: Assigns priority queue from rhs.
Complexity: Linear.
d_ary_heap
public member functions() ;
Effects: Returns true, if the priority queue contains no elements.
Complexity: Constant.
() ;
Effects: Returns the number of elements contained in the priority queue.
Complexity: Constant.
() ;
Effects: Returns the maximum number of elements the priority queue can contain.
Complexity: Constant.
();
Effects: Removes all elements from the priority queue.
Complexity: Linear.
() ;
Effects: Returns allocator.
Complexity: Constant.
() ;
Effects: Returns a const_reference to the maximum element.
Complexity: Constant.
( v);
Effects: Adds a new element to the priority queue.
Complexity: Logarithmic (amortized). Linear (worst case).
template< Args> ( args);
Effects: Adds a new element to the priority queue. The element is directly constructed in-place.
Complexity: Logarithmic (amortized). Linear (worst case).
template<typename HeapType> ( rhs) ;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
template<typename HeapType> ( rhs) ;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
template<typename HeapType> ( rhs) ;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
template<typename HeapType> ( rhs) ;
Returns: Element-wise comparison of heap data structures
Requirement: the value_compare
object of both heaps must match.
template<typename HeapType> ( rhs) ;Equivalent comparison Returns: True, if both heap data structures are equivalent.
Requirement: the value_compare
object of both heaps must match.
template<typename HeapType> ( rhs) ;Equivalent comparison Returns: True, if both heap data structures are not equivalent.
Requirement: the value_compare
object of both heaps must match.
( handle, v);
Effects: Assigns v
to the element handled by handle
& updates the priority queue.
Complexity: Logarithmic.
Requirement: data structure must be configured as mutable
( handle);
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
( handle, v);
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
( handle);
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
( handle, v);
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
( handle);
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
( handle);
Effects: Removes the element handled by handle
from the priority_queue
.
Complexity: Logarithmic.
Requirement: data structure must be configured as mutable
();
Effects: Removes the top element from the priority queue.
Complexity: Logarithmic (amortized). Linear (worst case).
(d_ary_heap & rhs);
Effects: Swaps two priority queues.
Complexity: Constant.
() ;
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
();
Effects: Returns an iterator to the first element contained in the priority queue.
Complexity: Constant.
();
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
() ;
Effects: Returns an iterator to the end of the priority queue.
Complexity: Constant.
() ;
Effects: Returns an ordered iterator to the first element contained in the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
() ;
Effects: Returns an ordered iterator to the end of the priority queue.
Note: Ordered iterators traverse the priority queue in heap order.
( element_count);
Effects: Reserves memory for element_count elements
Complexity: Linear.
Node: Invalidates iterators
() ;
Effect: Returns the value_compare object used by the priority queue