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 an old version of boost. Click here for the latest Boost documentation.
PrevUpHomeNext

Class template splay_multiset

boost::intrusive::splay_multiset

Synopsis

// In header: <boost/intrusive/splay_set.hpp>

template<typename T, class... Options> 
class splay_multiset {
public:
  // types
  typedef implementation_defined::value_type             value_type;            
  typedef implementation_defined::value_traits           value_traits;          
  typedef implementation_defined::pointer                pointer;               
  typedef implementation_defined::const_pointer          const_pointer;         
  typedef implementation_defined::reference              reference;             
  typedef implementation_defined::const_reference        const_reference;       
  typedef implementation_defined::difference_type        difference_type;       
  typedef implementation_defined::size_type              size_type;             
  typedef implementation_defined::value_compare          value_compare;         
  typedef implementation_defined::key_compare            key_compare;           
  typedef implementation_defined::iterator               iterator;              
  typedef implementation_defined::const_iterator         const_iterator;        
  typedef implementation_defined::reverse_iterator       reverse_iterator;      
  typedef implementation_defined::const_reverse_iterator const_reverse_iterator;
  typedef implementation_defined::insert_commit_data     insert_commit_data;    
  typedef implementation_defined::node_traits            node_traits;           
  typedef implementation_defined::node                   node;                  
  typedef implementation_defined::node_ptr               node_ptr;              
  typedef implementation_defined::const_node_ptr         const_node_ptr;        
  typedef implementation_defined::node_algorithms        node_algorithms;       

  // construct/copy/destruct
  explicit splay_multiset(const value_compare & = value_compare(), 
                          const value_traits & = value_traits());
  template<typename Iterator> 
    splay_multiset(Iterator, Iterator, 
                   const value_compare & = value_compare(), 
                   const value_traits & = value_traits());
  splay_multiset(splay_multiset &&);
  splay_multiset& operator=(splay_multiset &&);
  ~splay_multiset();

  // public member functions
  iterator begin();
  const_iterator begin() const;
  const_iterator cbegin() const;
  iterator end();
  const_iterator end() const;
  const_iterator cend() const;
  reverse_iterator rbegin();
  const_reverse_iterator rbegin() const;
  const_reverse_iterator crbegin() const;
  reverse_iterator rend();
  const_reverse_iterator rend() const;
  const_reverse_iterator crend() const;
  key_compare key_comp() const;
  value_compare value_comp() const;
  bool empty() const;
  size_type size() const;
  void swap(splay_multiset &);
  template<typename Cloner, typename Disposer> 
    void clone_from(const splay_multiset &, Cloner, Disposer);
  iterator insert(reference);
  iterator insert(const_iterator, reference);
  template<typename Iterator> void insert(Iterator, Iterator);
  iterator insert_before(const_iterator, reference);
  void push_back(reference);
  void push_front(reference);
  iterator erase(const_iterator);
  iterator erase(const_iterator, const_iterator);
  size_type erase(const_reference);
  template<typename KeyType, typename KeyValueCompare> 
    size_type erase(const KeyType &, KeyValueCompare);
  template<typename Disposer> 
    iterator erase_and_dispose(const_iterator, Disposer);
  template<typename Disposer> 
    iterator erase_and_dispose(const_iterator, const_iterator, Disposer);
  template<typename Disposer> 
    size_type erase_and_dispose(const_reference, Disposer);
  template<typename KeyType, typename KeyValueCompare, typename Disposer> 
    size_type erase_and_dispose(const KeyType &, KeyValueCompare, Disposer);
  void clear();
  template<typename Disposer> void clear_and_dispose(Disposer);
  size_type count(const_reference);
  template<typename KeyType, typename KeyValueCompare> 
    size_type count(const KeyType &, KeyValueCompare);
  size_type count(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    size_type count(const KeyType &, KeyValueCompare) const;
  size_type count_dont_splay(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    size_type count_dont_splay(const KeyType &, KeyValueCompare) const;
  iterator lower_bound(const_reference);
  template<typename KeyType, typename KeyValueCompare> 
    iterator lower_bound(const KeyType &, KeyValueCompare);
  const_iterator lower_bound(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    const_iterator lower_bound(const KeyType &, KeyValueCompare) const;
  const_iterator lower_bound_dont_splay(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    const_iterator 
    lower_bound_dont_splay(const KeyType &, KeyValueCompare) const;
  iterator upper_bound(const_reference);
  template<typename KeyType, typename KeyValueCompare> 
    iterator upper_bound(const KeyType &, KeyValueCompare);
  const_iterator upper_bound(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    const_iterator upper_bound(const KeyType &, KeyValueCompare) const;
  const_iterator upper_bound_dont_splay(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    const_iterator 
    upper_bound_dont_splay(const KeyType &, KeyValueCompare) const;
  iterator find(const_reference);
  template<typename KeyType, typename KeyValueCompare> 
    iterator find(const KeyType &, KeyValueCompare);
  const_iterator find(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    const_iterator find(const KeyType &, KeyValueCompare) const;
  const_iterator find_dont_splay(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    const_iterator find_dont_splay(const KeyType &, KeyValueCompare) const;
  std::pair< iterator, iterator > equal_range(const_reference);
  template<typename KeyType, typename KeyValueCompare> 
    std::pair< iterator, iterator > 
    equal_range(const KeyType &, KeyValueCompare);
  std::pair< const_iterator, const_iterator > 
  equal_range(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    std::pair< const_iterator, const_iterator > 
    equal_range(const KeyType &, KeyValueCompare) const;
  std::pair< const_iterator, const_iterator > 
  equal_range_dont_splay(const_reference) const;
  template<typename KeyType, typename KeyValueCompare> 
    std::pair< const_iterator, const_iterator > 
    equal_range_dont_splay(const KeyType &, KeyValueCompare) const;
  std::pair< iterator, iterator > 
  bounded_range(const_reference, const_reference, bool, bool);
  template<typename KeyType, typename KeyValueCompare> 
    std::pair< iterator, iterator > 
    bounded_range(const KeyType &, const KeyType &, KeyValueCompare, bool, 
                  bool);
  std::pair< const_iterator, const_iterator > 
  bounded_range(const_reference, const_reference, bool, bool) const;
  template<typename KeyType, typename KeyValueCompare> 
    std::pair< const_iterator, const_iterator > 
    bounded_range(const KeyType &, const KeyType &, KeyValueCompare, bool, 
                  bool) const;
  std::pair< const_iterator, const_iterator > 
  bounded_range_dont_splay(const_reference, const_reference, bool, bool) const;
  template<typename KeyType, typename KeyValueCompare> 
    std::pair< const_iterator, const_iterator > 
    bounded_range_dont_splay(const KeyType &, const KeyType &, 
                             KeyValueCompare, bool, bool) const;
  iterator iterator_to(reference);
  const_iterator iterator_to(const_reference) const;
  pointer unlink_leftmost_without_rebalance();
  void replace_node(iterator, reference);
  void remove_node(reference);
  void splay_up(iterator);
  template<typename KeyType, typename KeyValueCompare> 
    iterator splay_down(const KeyType &, KeyValueCompare);
  iterator splay_down(const_reference);
  void rebalance();
  iterator rebalance_subtree(iterator);

  // public static functions
  static splay_multiset & container_from_end_iterator(iterator);
  static const splay_multiset & container_from_end_iterator(const_iterator);
  static splay_multiset & container_from_iterator(iterator);
  static const splay_multiset & container_from_iterator(const_iterator);
  static iterator s_iterator_to(reference);
  static const_iterator s_iterator_to(const_reference);
  static void init_node(reference);

  // public data members
  static const bool constant_time_size;
};

Description

The class template splay_multiset is an intrusive container, that mimics most of the interface of std::multiset as described in the C++ standard.

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: base_hook<>/member_hook<>/value_traits<>, constant_time_size<>, size_type<> and compare<>.

splay_multiset public construct/copy/destruct

  1. explicit splay_multiset(const value_compare & cmp = value_compare(), 
                            const value_traits & v_traits = value_traits());

    Effects: Constructs an empty container.

    Complexity: Constant.

    Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructorof the value_compare object throws. Basic guarantee.

  2. template<typename Iterator> 
      splay_multiset(Iterator b, Iterator e, 
                     const value_compare & cmp = value_compare(), 
                     const value_traits & v_traits = value_traits());

    Requires: Dereferencing iterator must yield an lvalue of type value_type. cmp must be a comparison function that induces a strict weak ordering.

    Effects: Constructs an empty container and inserts elements from [b, e).

    Complexity: Linear in N if [b, e) is already sorted using comp and otherwise N * log N, where N is the distance between first and last.

    Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the copy constructor/operator() of the value_compare object throws. Basic guarantee.

  3. splay_multiset(splay_multiset && x);

    Effects: to-do

  4. splay_multiset& operator=(splay_multiset && x);

    Effects: to-do

  5. ~splay_multiset();

    Effects: Detaches all elements from this. The objects in the set are not deleted (i.e. no destructors are called), but the nodes according to the value_traits template parameter are reinitialized and thus can be reused.

    Complexity: Linear to elements contained in *this.

    Throws: Nothing.

splay_multiset public member functions

  1. iterator begin();

    Effects: Returns an iterator pointing to the beginning of the container.

    Complexity: Constant.

    Throws: Nothing.

  2. const_iterator begin() const;

    Effects: Returns a const_iterator pointing to the beginning of the container.

    Complexity: Constant.

    Throws: Nothing.

  3. const_iterator cbegin() const;

    Effects: Returns a const_iterator pointing to the beginning of the container.

    Complexity: Constant.

    Throws: Nothing.

  4. iterator end();

    Effects: Returns an iterator pointing to the end of the container.

    Complexity: Constant.

    Throws: Nothing.

  5. const_iterator end() const;

    Effects: Returns a const_iterator pointing to the end of the container.

    Complexity: Constant.

    Throws: Nothing.

  6. const_iterator cend() const;

    Effects: Returns a const_iterator pointing to the end of the container.

    Complexity: Constant.

    Throws: Nothing.

  7. reverse_iterator rbegin();

    Effects: Returns a reverse_iterator pointing to the beginning of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  8. const_reverse_iterator rbegin() const;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  9. const_reverse_iterator crbegin() const;

    Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  10. reverse_iterator rend();

    Effects: Returns a reverse_iterator pointing to the end of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  11. const_reverse_iterator rend() const;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  12. const_reverse_iterator crend() const;

    Effects: Returns a const_reverse_iterator pointing to the end of the reversed container.

    Complexity: Constant.

    Throws: Nothing.

  13. key_compare key_comp() const;

    Effects: Returns the key_compare object used by the container.

    Complexity: Constant.

    Throws: If value_compare copy-constructor throws.

  14. value_compare value_comp() const;

    Effects: Returns the value_compare object used by the container.

    Complexity: Constant.

    Throws: If value_compare copy-constructor throws.

  15. bool empty() const;

    Effects: Returns true if the container is empty.

    Complexity: Constant.

    Throws: Nothing.

  16. size_type size() const;

    Effects: Returns the number of elements stored in the container.

    Complexity: Linear to elements contained in *this if constant-time size option is disabled. Constant time otherwise.

    Throws: Nothing.

  17. void swap(splay_multiset & other);

    Effects: Swaps the contents of two containers.

    Complexity: Constant.

    Throws: If the comparison functor's swap call throws.

  18. template<typename Cloner, typename Disposer> 
      void clone_from(const splay_multiset & src, Cloner cloner, 
                      Disposer disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.

    Effects: Erases all the elements from *this calling Disposer::operator()(pointer), clones all the elements from src calling Cloner::operator()(const_reference ) and inserts them on *this. Copies the predicate from the source container.

    If cloner throws, all cloned elements are unlinked and disposed calling Disposer::operator()(pointer).

    Complexity: Linear to erased plus inserted elements.

    Throws: If cloner throws or predicate copy assignment throws. Basic guarantee.

  19. iterator insert(reference value);

    Requires: value must be an lvalue

    Effects: Inserts value into the container before the upper bound.

    Complexity: Average complexity for insert element is at most logarithmic.

    Throws: If the internal value_compare ordering function throws. Strong guarantee.

    Note: Does not affect the validity of iterators and references. No copy-constructors are called.

  20. iterator insert(const_iterator hint, reference value);

    Requires: value must be an lvalue, and "hint" must be a valid iterator.

    Effects: Inserts x into the container, using "hint" as a hint to where it will be inserted. If "hint" is the upper_bound the insertion takes constant time (two comparisons in the worst case)

    Complexity: Logarithmic in general, but it is amortized constant time if t is inserted immediately before hint.

    Throws: If the internal value_compare ordering function throws. Strong guarantee.

    Note: Does not affect the validity of iterators and references. No copy-constructors are called.

  21. template<typename Iterator> void insert(Iterator b, Iterator e);

    Requires: Dereferencing iterator must yield an lvalue of type value_type.

    Effects: Inserts a each element of a range into the container before the upper bound of the key of each element.

    Complexity: Insert range is in general O(N * log(N)), where N is the size of the range. However, it is linear in N if the range is already sorted by value_comp().

    Throws: Nothing.

    Note: Does not affect the validity of iterators and references. No copy-constructors are called.

  22. iterator insert_before(const_iterator pos, reference value);

    Requires: value must be an lvalue, "pos" must be a valid iterator (or end) and must be the succesor of value once inserted according to the predicate

    Effects: Inserts x into the container before "pos".

    Complexity: Constant time.

    Throws: Nothing.

    Note: This function does not check preconditions so if "pos" is not the successor of "value" container ordering invariant will be broken. This is a low-level function to be used only for performance reasons by advanced users.

  23. void push_back(reference value);

    Requires: value must be an lvalue, and it must be no less than the greatest inserted key

    Effects: Inserts x into the container in the last position.

    Complexity: Constant time.

    Throws: Nothing.

    Note: This function does not check preconditions so if value is less than the greatest inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.

  24. void push_front(reference value);

    Requires: value must be an lvalue, and it must be no greater than the minimum inserted key

    Effects: Inserts x into the container in the first position.

    Complexity: Constant time.

    Throws: Nothing.

    Note: This function does not check preconditions so if value is greater than the minimum inserted key container ordering invariant will be broken. This function is slightly more efficient than using "insert_before". This is a low-level function to be used only for performance reasons by advanced users.

  25. iterator erase(const_iterator i);

    Effects: Erases the element pointed to by pos.

    Complexity: Average complexity for erase element is constant time.

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

  26. iterator erase(const_iterator b, const_iterator e);

    Effects: Erases the range pointed to by b end e.

    Complexity: Average complexity for erase range is at most O(log(size() + N)), where N is the number of elements in the range.

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

  27. size_type erase(const_reference value);

    Effects: Erases the element pointed to by pos.

    Complexity: Average complexity for erase element is constant time.

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

  28. template<typename KeyType, typename KeyValueCompare> 
      size_type erase(const KeyType & key, KeyValueCompare comp);

    Effects: Erases all the elements with the given key. according to the comparison functor "comp".

    Returns: The number of erased elements.

    Complexity: O(log(size() + N).

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

  29. template<typename Disposer> 
      iterator erase_and_dispose(const_iterator i, Disposer disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw.

    Effects: Erases the element pointed to by pos. Disposer::operator()(pointer) is called for the removed element.

    Complexity: Average complexity for erase element is constant time.

    Throws: Nothing.

    Note: Invalidates the iterators to the erased elements.

  30. template<typename Disposer> 
      iterator erase_and_dispose(const_iterator b, const_iterator e, 
                                 Disposer disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw.

    Effects: Erases the range pointed to by b end e. Disposer::operator()(pointer) is called for the removed elements.

    Complexity: Average complexity for erase range is at most O(log(size() + N)), where N is the number of elements in the range.

    Throws: Nothing.

    Note: Invalidates the iterators to the erased elements.

  31. template<typename Disposer> 
      size_type erase_and_dispose(const_reference value, Disposer disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw.

    Effects: Erases the element pointed to by pos. Disposer::operator()(pointer) is called for the removed element.

    Complexity: Average complexity for erase element is constant time.

    Throws: Nothing.

    Note: Invalidates the iterators to the erased elements.

  32. template<typename KeyType, typename KeyValueCompare, typename Disposer> 
      size_type erase_and_dispose(const KeyType & key, KeyValueCompare comp, 
                                  Disposer disposer);

    Requires: Disposer::operator()(pointer) shouldn't throw.

    Effects: Erases all the elements with the given key. according to the comparison functor "comp". Disposer::operator()(pointer) is called for the removed elements.

    Returns: The number of erased elements.

    Complexity: O(log(size() + N).

    Throws: Nothing.

    Note: Invalidates the iterators to the erased elements.

  33. void clear();

    Effects: Erases all of the elements.

    Complexity: Linear to the number of elements on the container. if it's a safe-mode or auto-unlink value_type. Constant time otherwise.

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. No destructors are called.

  34. template<typename Disposer> void clear_and_dispose(Disposer disposer);

    Effects: Erases all of the elements calling disposer(p) for each node to be erased. Complexity: Average complexity for is at most O(log(size() + N)), where N is the number of elements in the container.

    Throws: Nothing.

    Note: Invalidates the iterators (but not the references) to the erased elements. Calls N times to disposer functor.

  35. size_type count(const_reference value);

    Effects: Returns the number of contained elements with the given value

    Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given value.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "value"

  36. template<typename KeyType, typename KeyValueCompare> 
      size_type count(const KeyType & key, KeyValueCompare comp);

    Effects: Returns the number of contained elements with the given key

    Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given key.

    Throws: Nothing. Additional note: Deprecated function, use count const overload instead.

  37. size_type count(const_reference value) const;

    Effects: Returns the number of contained elements with the given value

    Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given value.

    Throws: Nothing. Additional note: Deprecated function, use count const overload instead.

  38. template<typename KeyType, typename KeyValueCompare> 
      size_type count(const KeyType & key, KeyValueCompare comp) const;

    Effects: Returns the number of contained elements with the given key

    Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given key.

    Throws: Nothing. Additional note: Deprecated function, use count const overload instead.

  39. size_type count_dont_splay(const_reference value) const;

    Effects: Returns the number of contained elements with the given value

    Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given value.

    Throws: Nothing. Additional note: Deprecated function, use count const overload instead.

  40. template<typename KeyType, typename KeyValueCompare> 
      size_type count_dont_splay(const KeyType & key, KeyValueCompare comp) const;

    Effects: Returns the number of contained elements with the given key

    Complexity: Logarithmic to the number of elements contained plus lineal to number of objects with the given key.

    Throws: Nothing. Additional note: Deprecated function, use count const overload instead.

  41. iterator lower_bound(const_reference value);

    Effects: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "value"

  42. template<typename KeyType, typename KeyValueCompare> 
      iterator lower_bound(const KeyType & key, KeyValueCompare comp);

    Effects: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "key"

  43. const_iterator lower_bound(const_reference value) const;

    Effects: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  44. template<typename KeyType, typename KeyValueCompare> 
      const_iterator lower_bound(const KeyType & key, KeyValueCompare comp) const;

    Effects: Returns a const iterator to the first element whose key is not less than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  45. const_iterator lower_bound_dont_splay(const_reference value) const;

    Effects: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use lower_bound const overload instead.

  46. template<typename KeyType, typename KeyValueCompare> 
      const_iterator 
      lower_bound_dont_splay(const KeyType & key, KeyValueCompare comp) const;

    Effects: Returns an iterator to the first element whose key is not less than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use lower_bound const overload instead.

  47. iterator upper_bound(const_reference value);

    Effects: Returns an iterator to the first element whose key is greater than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "value"

  48. template<typename KeyType, typename KeyValueCompare> 
      iterator upper_bound(const KeyType & key, KeyValueCompare comp);

    Effects: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "key"

  49. const_iterator upper_bound(const_reference value) const;

    Effects: Returns an iterator to the first element whose key is greater than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  50. template<typename KeyType, typename KeyValueCompare> 
      const_iterator upper_bound(const KeyType & key, KeyValueCompare comp) const;

    Effects: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  51. const_iterator upper_bound_dont_splay(const_reference value) const;

    Effects: Returns an iterator to the first element whose key is greater than k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use upper_bound const overload instead.

  52. template<typename KeyType, typename KeyValueCompare> 
      const_iterator 
      upper_bound_dont_splay(const KeyType & key, KeyValueCompare comp) const;

    Effects: Returns an iterator to the first element whose key is greater than k according to comp or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use upper_bound const overload instead.

  53. iterator find(const_reference value);

    Effects: Finds an iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "value"

  54. template<typename KeyType, typename KeyValueCompare> 
      iterator find(const KeyType & key, KeyValueCompare comp);

    Effects: Finds an iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "key"

  55. const_iterator find(const_reference value) const;

    Effects: Finds a const_iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  56. template<typename KeyType, typename KeyValueCompare> 
      const_iterator find(const KeyType & key, KeyValueCompare comp) const;

    Effects: Finds a const_iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  57. const_iterator find_dont_splay(const_reference value) const;

    Effects: Finds a const_iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use find const overload instead.

  58. template<typename KeyType, typename KeyValueCompare> 
      const_iterator 
      find_dont_splay(const KeyType & key, KeyValueCompare comp) const;

    Effects: Finds a const_iterator to the first element whose key is k or end() if that element does not exist.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use find const overload instead.

  59. std::pair< iterator, iterator > equal_range(const_reference value);

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "value"

  60. template<typename KeyType, typename KeyValueCompare> 
      std::pair< iterator, iterator > 
      equal_range(const KeyType & key, KeyValueCompare comp);

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: non-const function, splaying is performed for the first element of the equal range of "key"

  61. std::pair< const_iterator, const_iterator > 
    equal_range(const_reference value) const;

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  62. template<typename KeyType, typename KeyValueCompare> 
      std::pair< const_iterator, const_iterator > 
      equal_range(const KeyType & key, KeyValueCompare comp) const;

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: const function, no splaying is performed

  63. std::pair< const_iterator, const_iterator > 
    equal_range_dont_splay(const_reference value) const;

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use equal_range const overload instead.

  64. template<typename KeyType, typename KeyValueCompare> 
      std::pair< const_iterator, const_iterator > 
      equal_range_dont_splay(const KeyType & key, KeyValueCompare comp) const;

    Effects: Finds a range containing all elements whose key is k or an empty range that indicates the position where those elements would be if they there is no elements with key k.

    Complexity: Logarithmic.

    Throws: Nothing. Additional note: Deprecated function, use equal_range const overload instead.

  65. std::pair< iterator, iterator > 
    bounded_range(const_reference lower_value, const_reference upper_value, 
                  bool left_closed, bool right_closed);

    Requires: 'lower_value' must not be greater than 'upper_value'. If 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise

    second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise

    Complexity: Logarithmic.

    Throws: If the predicate throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_value and upper_value.

    Note: Experimental function, the interface might change in future releases.

  66. template<typename KeyType, typename KeyValueCompare> 
      std::pair< iterator, iterator > 
      bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                    KeyValueCompare comp, bool left_closed, bool right_closed);

    Requires: KeyValueCompare is a function object that induces a strict weak ordering compatible with the strict weak ordering used to create the the container. 'lower_key' must not be greater than 'upper_key' according to 'comp'. If 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise

    second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise

    Complexity: Logarithmic.

    Throws: If "comp" throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.

    Note: Experimental function, the interface might change in future releases.

  67. std::pair< const_iterator, const_iterator > 
    bounded_range(const_reference lower_value, const_reference upper_value, 
                  bool left_closed, bool right_closed) const;

    Requires: 'lower_value' must not be greater than 'upper_value'. If 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise

    second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise

    Complexity: Logarithmic.

    Throws: If the predicate throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_value and upper_value.

    Note: Experimental function, the interface might change in future releases.

  68. template<typename KeyType, typename KeyValueCompare> 
      std::pair< const_iterator, const_iterator > 
      bounded_range(const KeyType & lower_key, const KeyType & upper_key, 
                    KeyValueCompare comp, bool left_closed, bool right_closed) const;

    Requires: KeyValueCompare is a function object that induces a strict weak ordering compatible with the strict weak ordering used to create the the container. 'lower_key' must not be greater than 'upper_key' according to 'comp'. If 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise

    second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise

    Complexity: Logarithmic.

    Throws: If "comp" throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.

    Note: Experimental function, the interface might change in future releases.

  69. std::pair< const_iterator, const_iterator > 
    bounded_range_dont_splay(const_reference lower_value, 
                             const_reference upper_value, bool left_closed, 
                             bool right_closed) const;

    Requires: 'lower_value' must not be greater than 'upper_value'. If 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise

    second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise

    Complexity: Logarithmic.

    Throws: If the predicate throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_value and upper_value.

    Note: Experimental function, the interface might change in future releases. Additional note: Deprecated function, use bounded_range const overload instead.

  70. template<typename KeyType, typename KeyValueCompare> 
      std::pair< const_iterator, const_iterator > 
      bounded_range_dont_splay(const KeyType & lower_key, 
                               const KeyType & upper_key, KeyValueCompare comp, 
                               bool left_closed, bool right_closed) const;

    Requires: KeyValueCompare is a function object that induces a strict weak ordering compatible with the strict weak ordering used to create the the container. 'lower_key' must not be greater than 'upper_key' according to 'comp'. If 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.

    Effects: Returns an a pair with the following criteria:

    first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise

    second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise

    Complexity: Logarithmic.

    Throws: If "comp" throws.

    Note: This function can be more efficient than calling upper_bound and lower_bound for lower_key and upper_key.

    Note: Experimental function, the interface might change in future releases. Additional note: Deprecated function, use bounded_range const overload instead.

  71. iterator iterator_to(reference value);

    Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

    Effects: Returns: a valid iterator i belonging to the set that points to the value

    Complexity: Constant.

    Throws: Nothing.

  72. const_iterator iterator_to(const_reference value) const;

    Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

    Effects: Returns: a valid const_iterator i belonging to the set that points to the value

    Complexity: Constant.

    Throws: Nothing.

  73. pointer unlink_leftmost_without_rebalance();

    Effects: Unlinks the leftmost node from the container.

    Complexity: Average complexity is constant time.

    Throws: Nothing.

    Notes: This function breaks the container and the container can only be used for more unlink_leftmost_without_rebalance calls. This function is normally used to achieve a step by step controlled destruction of the container.

  74. void replace_node(iterator replace_this, reference with_this);

    Requires: replace_this must be a valid iterator of *this and with_this must not be inserted in any container.

    Effects: Replaces replace_this in its position in the container with with_this. The container does not need to be rebalanced.

    Complexity: Constant.

    Throws: Nothing.

    Note: This function will break container ordering invariants if with_this is not equivalent to *replace_this according to the ordering rules. This function is faster than erasing and inserting the node, since no rebalancing or comparison is needed.

  75. void remove_node(reference value);

    Effects: removes "value" from the container.

    Throws: Nothing.

    Complexity: Logarithmic time.

    Note: This static function is only usable with non-constant time size containers that have stateless comparison functors.

    If the user calls this function with a constant time size container or stateful comparison functor a compilation error will be issued.

  76. void splay_up(iterator i);

    Requires: i must be a valid iterator of *this.

    Effects: Rearranges the container so that the element pointed by i is placed as the root of the tree, improving future searches of this value.

    Complexity: Amortized logarithmic.

    Throws: Nothing.

  77. template<typename KeyType, typename KeyValueCompare> 
      iterator splay_down(const KeyType & key, KeyValueCompare comp);

    Effects: Rearranges the container so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree. If the element is not present returns the last node compared with the key. If the tree is empty, end() is returned.

    Complexity: Amortized logarithmic.

    Returns: An iterator to the new root of the tree, end() if the tree is empty.

    Throws: If the comparison functor throws.

  78. iterator splay_down(const_reference value);

    Effects: Rearranges the container so that if *this stores an element with a key equivalent to value the element is placed as the root of the tree.

    Complexity: Amortized logarithmic.

    Returns: An iterator to the new root of the tree, end() if the tree is empty.

    Throws: If the predicate throws.

  79. void rebalance();

    Effects: Rebalances the tree.

    Throws: Nothing.

    Complexity: Linear.

  80. iterator rebalance_subtree(iterator root);

    Requires: old_root is a node of a tree.

    Effects: Rebalances the subtree rooted at old_root.

    Returns: The new root of the subtree.

    Throws: Nothing.

    Complexity: Linear to the elements in the subtree.

splay_multiset public static functions

  1. static splay_multiset & container_from_end_iterator(iterator end_iterator);

    Precondition: end_iterator must be a valid end iterator of the container.

    Effects: Returns a const reference to the container associated to the end iterator

    Throws: Nothing.

    Complexity: Constant.

  2. static const splay_multiset & 
    container_from_end_iterator(const_iterator end_iterator);

    Precondition: end_iterator must be a valid end iterator of the container.

    Effects: Returns a const reference to the container associated to the end iterator

    Throws: Nothing.

    Complexity: Constant.

  3. static splay_multiset & container_from_iterator(iterator it);

    Precondition: it must be a valid iterator of the container.

    Effects: Returns a const reference to the container associated to the iterator

    Throws: Nothing.

    Complexity: Logarithmic.

  4. static const splay_multiset & container_from_iterator(const_iterator it);

    Precondition: it must be a valid iterator of the container.

    Effects: Returns a const reference to the container associated to the iterator

    Throws: Nothing.

    Complexity: Logarithmic.

  5. static iterator s_iterator_to(reference value);

    Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

    Effects: Returns: a valid iterator i belonging to the set that points to the value

    Complexity: Constant.

    Throws: Nothing.

    Note: This static function is available only if the value traits is stateless.

  6. static const_iterator s_iterator_to(const_reference value);

    Requires: value must be an lvalue and shall be in a set of appropriate type. Otherwise the behavior is undefined.

    Effects: Returns: a valid iterator i belonging to the set that points to the value

    Complexity: Constant.

    Throws: Nothing.

    Note: This static function is available only if the value traits is stateless.

  7. static void init_node(reference value);

    Requires: value shall not be in a container.

    Effects: init_node puts the hook of a value in a well-known default state.

    Throws: Nothing.

    Complexity: Constant time.

    Note: This function puts the hook in the well-known default state used by auto_unlink and safe hooks.


PrevUpHomeNext