Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for a snapshot of the master branch, built from commit b9ab49fc70.
PrevUpHomeNext

Class template skew_heap

boost::heap::skew_heap — skew heap

Synopsis

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

template<typename T, class ... Options> 
class skew_heap {
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;  
  typedef implementation_defined::ordered_iterator                                                     ordered_iterator;
  typedef boost::conditional< is_mutable, typename implementation_defined::handle_type, void * >::type handle_type;     

  // member classes/structs/unions
  template<typename T, typename A0 = boost::parameter::void_, 
           typename A1 = boost::parameter::void_, 
           typename A2 = boost::parameter::void_, 
           typename A3 = boost::parameter::void_, 
           typename A4 = boost::parameter::void_, 
           typename A5 = boost::parameter::void_, 
           typename A6 = boost::parameter::void_> 
  struct implementation_defined {
    // types
    typedef T                                                      value_type;         
    typedef base_maker::compare_argument                           value_compare;      
    typedef base_maker::allocator_type                             allocator_type;     
    typedef base_maker::node_type                                  node;               
    typedef boost::allocator_pointer< allocator_type >::type       node_pointer;       
    typedef boost::allocator_const_pointer< allocator_type >::type const_node_pointer; 
    typedef unspecified                                            value_extractor;    
    typedef boost::array< node_pointer, 2 >                        child_list_type;    
    typedef child_list_type::iterator                              child_list_iterator;
    typedef unspecified                                            iterator;           
    typedef iterator                                               const_iterator;     
    typedef unspecified                                            ordered_iterator;   
    typedef unspecified                                            reference;          
    typedef unspecified                                            handle_type;        
  };
  template<typename T, typename A0 = boost::parameter::void_, 
           typename A1 = boost::parameter::void_, 
           typename A2 = boost::parameter::void_, 
           typename A3 = boost::parameter::void_, 
           typename A4 = boost::parameter::void_, 
           typename A5 = boost::parameter::void_, 
           typename A6 = boost::parameter::void_> 
  struct push_handle {

    // public static functions
    static handle_type push(skew_heap *, const_reference);
    template<class... Args> 
      static handle_type emplace(skew_heap *, Args &&...);
  };
  template<typename T, typename A0 = boost::parameter::void_, 
           typename A1 = boost::parameter::void_, 
           typename A2 = boost::parameter::void_, 
           typename A3 = boost::parameter::void_, 
           typename A4 = boost::parameter::void_, 
           typename A5 = boost::parameter::void_, 
           typename A6 = boost::parameter::void_> 
  struct push_void {

    // public static functions
    static void push(skew_heap *, const_reference);
    template<class... Args> static void emplace(skew_heap *, Args &&...);
  };

  // construct/copy/destruct
  explicit skew_heap(value_compare const & = value_compare());
  skew_heap(skew_heap const &);
  skew_heap(skew_heap &&);
  skew_heap & operator=(skew_heap const &);
  skew_heap & operator=(skew_heap &&);
  ~skew_heap(void);

  // public member functions
  boost::conditional< is_mutable, handle_type, void >::type 
  push(value_type const &);
  template<typename... Args> 
    boost::conditional< is_mutable, handle_type, void >::type 
    emplace(Args &&...);
  bool empty(void) const;
  size_type size(void) const;
  size_type max_size(void) const;
  void clear(void);
  allocator_type get_allocator(void) const;
  void swap(skew_heap &);
  const_reference top(void) const;
  void pop(void);
  iterator begin(void) const;
  iterator end(void) const;
  ordered_iterator ordered_begin(void) const;
  ordered_iterator ordered_end(void) const;
  void merge(skew_heap &);
  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;
  void erase(handle_type);
  void update(handle_type, const_reference);
  void update(handle_type);
  void increase(handle_type, const_reference);
  void increase(handle_type);
  void decrease(handle_type, const_reference);
  void decrease(handle_type);

  // public static functions
  static handle_type s_handle_from_iterator(iterator const &);

  // private member functions
  node_pointer push_internal(const_reference);
  template<class... Args> node_pointer emplace_internal(Args &&...);
  void unlink_node(node_pointer);
  void clone_tree(skew_heap const &);
  void merge_node(node_pointer);
  node_pointer merge_nodes(node_pointer, node_pointer, node_pointer);
  node_pointer merge_children(node_pointer);
  node_pointer merge_nodes_recursive(node_pointer, node_pointer, node_pointer);
  void sanity_check(void);

  // 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;
  static const bool 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 implementation_defined::iterator iterator;

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

skew_heap public construct/copy/destruct

  1. explicit skew_heap(value_compare const & cmp = value_compare());

    Effects: constructs an empty priority queue.

    Complexity: Constant.

  2. skew_heap(skew_heap const & rhs);

    Effects: copy-constructs priority queue from rhs.

    Complexity: Linear.

  3. skew_heap(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 & operator=(skew_heap const & rhs);

    Effects: Assigns priority queue from rhs.

    Complexity: Linear.

  5. skew_heap & operator=(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(void);

skew_heap public member functions

  1. boost::conditional< is_mutable, handle_type, void >::type 
    push(value_type const & v);

    Effects: Adds a new element to the priority queue.

    Complexity: Logarithmic (amortized).

  2. template<typename... Args> 
      boost::conditional< is_mutable, handle_type, void >::type 
      emplace(Args &&... args);

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

    Complexity: Logarithmic (amortized).

  3. bool empty(void) const;

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

    Complexity: Constant.

  4. size_type size(void) const;

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

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

  5. size_type max_size(void) const;

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

    Complexity: Constant.

  6. void clear(void);

    Effects: Removes all elements from the priority queue.

    Complexity: Linear.

  7. allocator_type get_allocator(void) const;

    Effects: Returns allocator.

    Complexity: Constant.

  8. void swap(skew_heap & rhs);

    Effects: Swaps two priority queues.

    Complexity: Constant.

  9. const_reference top(void) const;

    Effects: Returns a const_reference to the maximum element.

    Complexity: Constant.

  10. void pop(void);

    Effects: Removes the top element from the priority queue.

    Complexity: Logarithmic (amortized).

  11. iterator begin(void) const;

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

    Complexity: Constant.

  12. iterator end(void) const;

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

    Complexity: Constant.

  13. ordered_iterator ordered_begin(void) const;

    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. ordered_iterator ordered_end(void) const;

    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. void merge(skew_heap & rhs);

    Effects: Merge all elements from rhs into this

    Complexity: Logarithmic (amortized).

  16. value_compare const  & value_comp(void) const;

    Effect: Returns the value_compare object used by the priority queue

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

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

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

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

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

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

  23. void erase(handle_type object);

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

    Complexity: Logarithmic (amortized).

  24. void update(handle_type handle, const_reference v);

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

    Complexity: Logarithmic (amortized).

  25. void update(handle_type 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. void increase(handle_type handle, const_reference 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. void increase(handle_type 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. void decrease(handle_type handle, const_reference 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. void decrease(handle_type 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. static handle_type s_handle_from_iterator(iterator const & it);

    Effects: Casts an iterator to a node handle.

    Complexity: Constant.

    Requirement: data structure must be configured as mutable

skew_heap private member functions

  1. node_pointer push_internal(const_reference v);
  2. template<class... Args> node_pointer emplace_internal(Args &&... args);
  3. void unlink_node(node_pointer node);
  4. void clone_tree(skew_heap const & rhs);
  5. void merge_node(node_pointer other);
  6. node_pointer 
    merge_nodes(node_pointer node1, node_pointer node2, node_pointer new_parent);
  7. node_pointer merge_children(node_pointer node);
  8. node_pointer 
    merge_nodes_recursive(node_pointer node1, node_pointer node2, 
                          node_pointer new_parent);
  9. void sanity_check(void);

PrevUpHomeNext