Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Class template skew_heap

boost::heap::skew_heap — skew heap

Synopsis

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

template<typename T,  Options> 
class skew_heap {
public:
  // types
  typedef                                                                                            ;      
  typedef                                                            ;       
  typedef                                                      ; 
  typedef                                                        ;   
  typedef                                                       ;  
  typedef                                                            ;       
  typedef                                                      ; 
  typedef                                                              ;         
  typedef                                                        ;   
  typedef                                                             ;        
  typedef                                                       ;  
  typedef                                                     ;
  typedef  ;     

  // member classes/structs/unions

  struct implementation_defined {
    // types
    typedef                                                       ;         
    typedef                            ;      
    typedef                              ;     
    typedef                                   ;               
    typedef        ;       
    typedef  ; 
    typedef                                             ;    
    typedef                         ;    
    typedef                               ;
    typedef                                             ;           
    typedef                                                ;     
    typedef                                             ;   
    typedef                                             ;          
    typedef                                             ;        
  };

  // construct/copy/destruct
  ( = );
  (skew_heap );
  (skew_heap &&);
  skew_heap & (skew_heap );
  skew_heap & (skew_heap &&);
  ~();

  // public member functions
   
  ();
  template< Args> 
     
    ();
   () ;
   () ;
   () ;
   ();
   () ;
   (skew_heap &);
   () ;
   ();
   () ;
   () ;
   () ;
   () ;
   (skew_heap &);
   () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
  template<typename HeapType>  () ;
   ();
   (, );
   ();
   (, );
   ();
   (, );
   ();

  // public static functions
   ();

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

Description

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> >

  • boost::heap::constant_time_size<>, defaults to constant_time_size<true>

  • boost::heap::store_parent_pointer<>, defaults to store_parent_pointer<true>. Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient.

  • boost::heap::mutable<>, defaults to mutable<false>.

skew_heap public types

  1. typedef ;

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

skew_heap public construct/copy/destruct

  1. ( cmp = );
  2. (skew_heap  rhs);

    Effects: copy-constructs priority queue from rhs.

    Complexity: Linear.

  3. (skew_heap && rhs);

    Effects: C++11-style move constructor.

    Complexity: Constant.

    Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined

  4. skew_heap & (skew_heap  rhs);

    Effects: Assigns priority queue from rhs.

    Complexity: Linear.

  5. skew_heap & (skew_heap && rhs);

    Effects: C++11-style move assignment.

    Complexity: Constant.

    Note: Only available, if BOOST_NO_CXX11_RVALUE_REFERENCES is not defined

  6. ~();

skew_heap public member functions

  1.  
    ( v);

    Effects: Adds a new element to the priority queue.

    Complexity: Logarithmic (amortized).

  2. template< Args> 
       
      ( args);

    Effects: Adds a new element to the priority queue. The element is directly constructed in-place.

    Complexity: Logarithmic (amortized).

  3.  () ;

    Effects: Returns true, if the priority queue contains no elements.

    Complexity: Constant.

  4.  () ;

    Effects: Returns the number of elements contained in the priority queue.

    Complexity: Constant, if configured with constant_time_size<true>, otherwise linear.

  5.  () ;

    Effects: Returns the maximum number of elements the priority queue can contain.

    Complexity: Constant.

  6.  ();

    Effects: Removes all elements from the priority queue.

    Complexity: Linear.

  7.  () ;

    Effects: Returns allocator.

    Complexity: Constant.

  8.  (skew_heap & rhs);

    Effects: Swaps two priority queues.

    Complexity: Constant.

  9.  () ;

    Effects: Returns a const_reference to the maximum element.

    Complexity: Constant.

  10.  ();

    Effects: Removes the top element from the priority queue.

    Complexity: Logarithmic (amortized).

  11.  () ;

    Effects: Returns an iterator to the first element contained in the priority queue.

    Complexity: Constant.

  12.  () ;

    Effects: Returns an iterator to the end of the priority queue.

    Complexity: Constant.

  13.  () ;

    Effects: Returns an ordered iterator to the first element contained in the priority queue.

    Note: Ordered iterators traverse the priority queue in heap order.

  14.  () ;

    Effects: Returns an ordered iterator to the first element contained in the priority queue.

    Note: Ordered iterators traverse the priority queue in heap order.

  15.  (skew_heap & rhs);

    Effects: Merge all elements from rhs into this

    Complexity: Logarithmic (amortized).

  16.  () ;

    Effect: Returns the value_compare object used by the priority queue

  17. template<typename HeapType>  ( rhs) ;

    Returns: Element-wise comparison of heap data structures

    Requirement: the value_compare object of both heaps must match.

  18. template<typename HeapType>  ( rhs) ;

    Returns: Element-wise comparison of heap data structures

    Requirement: the value_compare object of both heaps must match.

  19. template<typename HeapType>  ( rhs) ;

    Returns: Element-wise comparison of heap data structures

    Requirement: the value_compare object of both heaps must match.

  20. template<typename HeapType>  ( rhs) ;

    Returns: Element-wise comparison of heap data structures

    Requirement: the value_compare object of both heaps must match.

  21. 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.

  22. 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.

  23.  ( object);

    Effects: Removes the element handled by handle from the priority_queue.

    Complexity: Logarithmic (amortized).

  24.  ( handle,  v);

    Effects: Assigns v to the element handled by handle & updates the priority queue.

    Complexity: Logarithmic (amortized).

  25.  ( handle);

    Effects: Updates the heap after the element handled by handle has been changed.

    Complexity: Logarithmic (amortized).

    Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!

  26.  ( handle,  v);

    Effects: Assigns v to the element handled by handle & updates the priority queue.

    Complexity: Logarithmic (amortized).

    Note: The new value is expected to be greater than the current one

  27.  ( handle);

    Effects: Updates the heap after the element handled by handle has been changed.

    Complexity: Logarithmic (amortized).

    Note: If this is not called, after a handle has been updated, the behavior of the data structure is undefined!

  28.  ( handle,  v);

    Effects: Assigns v to the element handled by handle & updates the priority queue.

    Complexity: Logarithmic (amortized).

    Note: The new value is expected to be less than the current one

  29.  ( handle);

    Effects: Updates the heap after the element handled by handle has been changed.

    Complexity: Logarithmic (amortized).

    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!

skew_heap public static functions

  1.  ( it);

    Effects: Casts an iterator to a node handle.

    Complexity: Constant.

    Requirement: data structure must be configured as mutable


PrevUpHomeNext