ceph/src/boost/boost/intrusive/splay_set.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 #ifndef BOOST_INTRUSIVE_SPLAY_SET_HPP
  13 #define BOOST_INTRUSIVE_SPLAY_SET_HPP
  14
  15 #include <boost/intrusive/detail/config_begin.hpp>
  16 #include <boost/intrusive/intrusive_fwd.hpp>
  17 #include <boost/intrusive/splaytree.hpp>
  18 #include <boost/intrusive/detail/mpl.hpp>
  19 #include <boost/move/utility_core.hpp>
  20 #include <boost/static_assert.hpp>
  21
  22 #if defined(BOOST_HAS_PRAGMA_ONCE)
  23 #  pragma once
  24 #endif
  25
  26 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  27 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  28 class splay_multiset_impl;
  29 #endif
  30
  31 namespace boost {
  32 namespace intrusive {
  33
  34 //! The class template splay_set is an intrusive container, that mimics most of
  35 //! the interface of std::set as described in the C++ standard.
  36 //!
  37 //! The template parameter \c T is the type to be managed by the container.
  38 //! The user can specify additional options and if no options are provided
  39 //! default options are used.
  40 //!
  41 //! The container supports the following options:
  42 //! \c base_hook<>/member_hook<>/value_traits<>,
  43 //! \c constant_time_size<>, \c size_type<> and
  44 //! \c compare<>.
  45 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  46 template<class T, class ...Options>
  47 #else
  48 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  49 #endif
  50 class splay_set_impl
  51 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  52    : public splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder>
  53 #endif
  54 {
  55    /// @cond
  56    typedef splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
  57    BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_set_impl)
  58
  59    typedef tree_type implementation_defined;
  60    /// @endcond
  61
  62    public:
  63    typedef typename implementation_defined::value_type               value_type;
  64    typedef typename implementation_defined::key_type                 key_type;
  65    typedef typename implementation_defined::key_of_value             key_of_value;
  66    typedef typename implementation_defined::value_traits             value_traits;
  67    typedef typename implementation_defined::pointer                  pointer;
  68    typedef typename implementation_defined::const_pointer            const_pointer;
  69    typedef typename implementation_defined::reference                reference;
  70    typedef typename implementation_defined::const_reference          const_reference;
  71    typedef typename implementation_defined::difference_type          difference_type;
  72    typedef typename implementation_defined::size_type                size_type;
  73    typedef typename implementation_defined::value_compare            value_compare;
  74    typedef typename implementation_defined::key_compare              key_compare;
  75    typedef typename implementation_defined::iterator                 iterator;
  76    typedef typename implementation_defined::const_iterator           const_iterator;
  77    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
  78    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
  79    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
  80    typedef typename implementation_defined::node_traits              node_traits;
  81    typedef typename implementation_defined::node                     node;
  82    typedef typename implementation_defined::node_ptr                 node_ptr;
  83    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
  84    typedef typename implementation_defined::node_algorithms          node_algorithms;
  85
  86    static const bool constant_time_size = tree_type::constant_time_size;
  87
  88    public:
  89    //! @copydoc ::boost::intrusive::splaytree::splaytree()
  90    splay_set_impl()
  91       :  tree_type()
  92    {}
  93
  94    //! @copydoc ::boost::intrusive::splaytree::splaytree(const key_compare &,const value_traits &)
  95    explicit splay_set_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
  96       :  tree_type(cmp, v_traits)
  97    {}
  98
  99    //! @copydoc ::boost::intrusive::splaytree::splaytree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
 100    template<class Iterator>
 101    splay_set_impl( Iterator b, Iterator e
 102            , const key_compare &cmp = key_compare()
 103            , const value_traits &v_traits = value_traits())
 104       : tree_type(true, b, e, cmp, v_traits)
 105    {}
 106
 107    //! @copydoc ::boost::intrusive::splaytree::splaytree(splaytree &&)
 108    splay_set_impl(BOOST_RV_REF(splay_set_impl) x)
 109       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
 110    {}
 111
 112    //! @copydoc ::boost::intrusive::splaytree::operator=(splaytree &&)
 113    splay_set_impl& operator=(BOOST_RV_REF(splay_set_impl) x)
 114    {  return static_cast<splay_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
 115
 116    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 117    //! @copydoc ::boost::intrusive::splaytree::~splaytree()
 118    ~splay_set_impl();
 119
 120    //! @copydoc ::boost::intrusive::splaytree::begin()
 121    iterator begin() BOOST_NOEXCEPT;
 122
 123    //! @copydoc ::boost::intrusive::splaytree::begin()const
 124    const_iterator begin() const BOOST_NOEXCEPT;
 125
 126    //! @copydoc ::boost::intrusive::splaytree::cbegin()const
 127    const_iterator cbegin() const BOOST_NOEXCEPT;
 128
 129    //! @copydoc ::boost::intrusive::splaytree::end()
 130    iterator end() BOOST_NOEXCEPT;
 131
 132    //! @copydoc ::boost::intrusive::splaytree::end()const
 133    const_iterator end() const BOOST_NOEXCEPT;
 134
 135    //! @copydoc ::boost::intrusive::splaytree::cend()const
 136    const_iterator cend() const BOOST_NOEXCEPT;
 137
 138    //! @copydoc ::boost::intrusive::splaytree::rbegin()
 139    reverse_iterator rbegin() BOOST_NOEXCEPT;
 140
 141    //! @copydoc ::boost::intrusive::splaytree::rbegin()const
 142    const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
 143
 144    //! @copydoc ::boost::intrusive::splaytree::crbegin()const
 145    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
 146
 147    //! @copydoc ::boost::intrusive::splaytree::rend()
 148    reverse_iterator rend() BOOST_NOEXCEPT;
 149
 150    //! @copydoc ::boost::intrusive::splaytree::rend()const
 151    const_reverse_iterator rend() const BOOST_NOEXCEPT;
 152
 153    //! @copydoc ::boost::intrusive::splaytree::crend()const
 154    const_reverse_iterator crend() const BOOST_NOEXCEPT;
 155
 156    //! @copydoc ::boost::intrusive::splaytree::root()
 157    iterator root() BOOST_NOEXCEPT;
 158
 159    //! @copydoc ::boost::intrusive::splaytree::root()const
 160    const_iterator root() const BOOST_NOEXCEPT;
 161
 162    //! @copydoc ::boost::intrusive::splaytree::croot()const
 163    const_iterator croot() const BOOST_NOEXCEPT;
 164
 165    //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(iterator)
 166    static splay_set_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
 167
 168    //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(const_iterator)
 169    static const splay_set_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
 170
 171    //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(iterator)
 172    static splay_set_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
 173
 174    //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(const_iterator)
 175    static const splay_set_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
 176
 177    //! @copydoc ::boost::intrusive::splaytree::key_comp()const
 178    key_compare key_comp() const;
 179
 180    //! @copydoc ::boost::intrusive::splaytree::value_comp()const
 181    value_compare value_comp() const;
 182
 183    //! @copydoc ::boost::intrusive::splaytree::empty()const
 184    bool empty() const BOOST_NOEXCEPT;
 185
 186    //! @copydoc ::boost::intrusive::splaytree::size()const
 187    size_type size() const BOOST_NOEXCEPT;
 188
 189    //! @copydoc ::boost::intrusive::splaytree::swap
 190    void swap(splay_set_impl& other);
 191
 192    //! @copydoc ::boost::intrusive::splaytree::clone_from(const splaytree&,Cloner,Disposer)
 193    template <class Cloner, class Disposer>
 194    void clone_from(const splay_set_impl &src, Cloner cloner, Disposer disposer);
 195
 196    #else
 197
 198    using tree_type::clone_from;
 199
 200    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 201
 202    //! @copydoc ::boost::intrusive::splaytree::clone_from(splaytree&&,Cloner,Disposer)
 203    template <class Cloner, class Disposer>
 204    void clone_from(BOOST_RV_REF(splay_set_impl) src, Cloner cloner, Disposer disposer)
 205    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 206
 207    //! @copydoc ::boost::intrusive::splaytree::insert_unique(reference)
 208    std::pair<iterator, bool> insert(reference value)
 209    {  return tree_type::insert_unique(value);  }
 210
 211    //! @copydoc ::boost::intrusive::splaytree::insert_unique(const_iterator,reference)
 212    iterator insert(const_iterator hint, reference value)
 213    {  return tree_type::insert_unique(hint, value);  }
 214
 215    //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const key_type&,insert_commit_data&)
 216    std::pair<iterator, bool> insert_check
 217       (const key_type &key, insert_commit_data &commit_data)
 218    {  return tree_type::insert_unique_check(key, commit_data); }
 219
 220    //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
 221    std::pair<iterator, bool> insert_check
 222       (const_iterator hint, const key_type &key
 223       ,insert_commit_data &commit_data)
 224    {  return tree_type::insert_unique_check(hint, key, commit_data); }
 225
 226    //! @copydoc ::boost::intrusive::splaytree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 227    template<class KeyType, class KeyTypeKeyCompare>
 228    std::pair<iterator, bool> insert_check
 229       (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data)
 230    {  return tree_type::insert_unique_check(key, comp, commit_data); }
 231
 232    //! @copydoc ::boost::intrusive::splaytree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 233    template<class KeyType, class KeyTypeKeyCompare>
 234    std::pair<iterator, bool> insert_check
 235       (const_iterator hint, const KeyType &key
 236       ,KeyTypeKeyCompare comp, insert_commit_data &commit_data)
 237    {  return tree_type::insert_unique_check(hint, key, comp, commit_data); }
 238
 239    //! @copydoc ::boost::intrusive::splaytree::insert_unique(Iterator,Iterator)
 240    template<class Iterator>
 241    void insert(Iterator b, Iterator e)
 242    {  tree_type::insert_unique(b, e);  }
 243
 244    //! @copydoc ::boost::intrusive::splaytree::insert_unique_commit
 245    iterator insert_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT
 246    {  return tree_type::insert_unique_commit(value, commit_data);  }
 247
 248    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 249    //! @copydoc ::boost::intrusive::splaytree::insert_before
 250    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
 251
 252    //! @copydoc ::boost::intrusive::splaytree::push_back
 253    void push_back(reference value) BOOST_NOEXCEPT;
 254
 255    //! @copydoc ::boost::intrusive::splaytree::push_front
 256    void push_front(reference value) BOOST_NOEXCEPT;
 257
 258    //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator)
 259    iterator erase(const_iterator i) BOOST_NOEXCEPT;
 260
 261    //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator,const_iterator)
 262    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
 263
 264    //! @copydoc ::boost::intrusive::splaytree::erase(const key_type &)
 265    size_type erase(const key_type &key);
 266
 267    //! @copydoc ::boost::intrusive::splaytree::erase(const KeyType&,KeyTypeKeyCompare)
 268    template<class KeyType, class KeyTypeKeyCompare>
 269    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 270
 271    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,Disposer)
 272    template<class Disposer>
 273    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
 274
 275    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,const_iterator,Disposer)
 276    template<class Disposer>
 277    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
 278
 279    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const key_type &, Disposer)
 280    template<class Disposer>
 281    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 282
 283    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 284    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 285    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 286
 287    //! @copydoc ::boost::intrusive::splaytree::clear
 288    void clear() BOOST_NOEXCEPT;
 289
 290    //! @copydoc ::boost::intrusive::splaytree::clear_and_dispose
 291    template<class Disposer>
 292    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
 293
 294    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 295
 296    //! @copydoc ::boost::intrusive::splaytree::count(const key_type &)const
 297    size_type count(const key_type &key) const
 298    {  return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); }
 299
 300    //! @copydoc ::boost::intrusive::splaytree::count(const KeyType&,KeyTypeKeyCompare)const
 301    template<class KeyType, class KeyTypeKeyCompare>
 302    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const
 303    {  return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); }
 304
 305    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 306
 307    //! @copydoc ::boost::intrusive::splaytree::count(const key_type &)const
 308    size_type count(const key_type &key) const;
 309
 310    //! @copydoc ::boost::intrusive::splaytree::count(const KeyType&,KeyTypeKeyCompare)const
 311    template<class KeyType, class KeyTypeKeyCompare>
 312    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
 313
 314    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type &)
 315    iterator lower_bound(const key_type &key);
 316
 317    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare)
 318    template<class KeyType, class KeyTypeKeyCompare>
 319    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 320
 321    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type &)const
 322    const_iterator lower_bound(const key_type &key) const;
 323
 324    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 325    template<class KeyType, class KeyTypeKeyCompare>
 326    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 327
 328    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type &)
 329    iterator upper_bound(const key_type &key);
 330
 331    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare)
 332    template<class KeyType, class KeyTypeKeyCompare>
 333    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 334
 335    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type &)const
 336    const_iterator upper_bound(const key_type &key) const;
 337
 338    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 339    template<class KeyType, class KeyTypeKeyCompare>
 340    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 341
 342    //! @copydoc ::boost::intrusive::splaytree::find(const key_type &)
 343    iterator find(const key_type &key);
 344
 345    //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare)
 346    template<class KeyType, class KeyTypeKeyCompare>
 347    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 348
 349    //! @copydoc ::boost::intrusive::splaytree::find(const key_type &)const
 350    const_iterator find(const key_type &key) const;
 351
 352    //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare)const
 353    template<class KeyType, class KeyTypeKeyCompare>
 354    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 355
 356    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 357
 358    //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &)
 359    std::pair<iterator,iterator> equal_range(const key_type &key)
 360    {  return this->tree_type::lower_bound_range(key); }
 361
 362    //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare)
 363    template<class KeyType, class KeyTypeKeyCompare>
 364    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp)
 365    {  return this->tree_type::equal_range(key, comp); }
 366
 367    //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &)const
 368    std::pair<const_iterator, const_iterator>
 369       equal_range(const key_type &key) const
 370    {  return this->tree_type::lower_bound_range(key); }
 371
 372    //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare)const
 373    template<class KeyType, class KeyTypeKeyCompare>
 374    std::pair<const_iterator, const_iterator>
 375       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const
 376    {  return this->tree_type::equal_range(key, comp); }
 377
 378    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 379
 380    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&,const key_type&,bool,bool)
 381    std::pair<iterator,iterator> bounded_range
 382       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
 383
 384    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 385    template<class KeyType, class KeyTypeKeyCompare>
 386    std::pair<iterator,iterator> bounded_range
 387       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 388
 389    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&,const key_type&,bool,bool)const
 390    std::pair<const_iterator, const_iterator> bounded_range
 391       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 392
 393    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 394    template<class KeyType, class KeyTypeKeyCompare>
 395    std::pair<const_iterator, const_iterator> bounded_range
 396       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 397
 398    //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(reference)
 399    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
 400
 401    //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(const_reference)
 402    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
 403
 404    //! @copydoc ::boost::intrusive::splaytree::iterator_to(reference)
 405    iterator iterator_to(reference value) BOOST_NOEXCEPT;
 406
 407    //! @copydoc ::boost::intrusive::splaytree::iterator_to(const_reference)const
 408    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
 409
 410    //! @copydoc ::boost::intrusive::splaytree::init_node(reference)
 411    static void init_node(reference value) BOOST_NOEXCEPT;
 412
 413    //! @copydoc ::boost::intrusive::splaytree::unlink_leftmost_without_rebalance
 414    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
 415
 416    //! @copydoc ::boost::intrusive::splaytree::replace_node
 417    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
 418
 419    //! @copydoc ::boost::intrusive::splaytree::remove_node
 420    void remove_node(reference value) BOOST_NOEXCEPT;
 421
 422    //! @copydoc ::boost::intrusive::splaytree::splay_up(iterator)
 423    void splay_up(iterator i) BOOST_NOEXCEPT;
 424
 425    //! @copydoc ::boost::intrusive::splaytree::splay_down(const KeyType&,KeyTypeKeyCompare)
 426    template<class KeyType, class KeyTypeKeyCompare>
 427    iterator splay_down(const KeyType &key, KeyTypeKeyCompare comp);
 428
 429    //! @copydoc ::boost::intrusive::splaytree::splay_down(const key_type &key)
 430    iterator splay_down(const key_type &key);
 431
 432    //! @copydoc ::boost::intrusive::splaytree::rebalance
 433    void rebalance() BOOST_NOEXCEPT;
 434
 435    //! @copydoc ::boost::intrusive::splaytree::rebalance_subtree
 436    iterator rebalance_subtree(iterator root) BOOST_NOEXCEPT;
 437
 438    //! @copydoc ::boost::intrusive::splaytree::merge_unique
 439    template<class ...Options2>
 440    void merge(splay_set<T, Options2...> &source);
 441
 442    //! @copydoc ::boost::intrusive::splaytree::merge_unique
 443    template<class ...Options2>
 444    void merge(splay_multiset<T, Options2...> &source);
 445
 446    #else
 447
 448    template<class Compare2>
 449    void merge(splay_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 450    {  return tree_type::merge_unique(source);  }
 451
 452
 453    template<class Compare2>
 454    void merge(splay_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 455    {  return tree_type::merge_unique(source);  }
 456
 457    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 458 };
 459
 460 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 461
 462 template<class T, class ...Options>
 463 bool operator!= (const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y);
 464
 465 template<class T, class ...Options>
 466 bool operator>(const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y);
 467
 468 template<class T, class ...Options>
 469 bool operator<=(const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y);
 470
 471 template<class T, class ...Options>
 472 bool operator>=(const splay_set_impl<T, Options...> &x, const splay_set_impl<T, Options...> &y);
 473
 474 template<class T, class ...Options>
 475 void swap(splay_set_impl<T, Options...> &x, splay_set_impl<T, Options...> &y);
 476
 477 #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 478
 479 //! Helper metafunction to define a \c splay_set that yields to the same type when the
 480 //! same options (either explicitly or implicitly) are used.
 481 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 482 template<class T, class ...Options>
 483 #else
 484 template<class T, class O1 = void, class O2 = void
 485                 , class O3 = void, class O4 = void
 486                 , class O5 = void, class O6 = void>
 487 #endif
 488 struct make_splay_set
 489 {
 490    /// @cond
 491    typedef typename pack_options
 492       < splaytree_defaults,
 493       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 494       O1, O2, O3, O4, O5, O6
 495       #else
 496       Options...
 497       #endif
 498       >::type packed_options;
 499
 500    typedef typename detail::get_value_traits
 501       <T, typename packed_options::proto_value_traits>::type value_traits;
 502
 503    typedef splay_set_impl
 504          < value_traits
 505          , typename packed_options::key_of_value
 506          , typename packed_options::compare
 507          , typename packed_options::size_type
 508          , packed_options::constant_time_size
 509          , typename packed_options::header_holder_type
 510          > implementation_defined;
 511    /// @endcond
 512    typedef implementation_defined type;
 513 };
 514
 515 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 516 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 517 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
 518 #else
 519 template<class T, class ...Options>
 520 #endif
 521 class splay_set
 522    :  public make_splay_set<T,
 523    #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 524    O1, O2, O3, O4, O5, O6
 525    #else
 526    Options...
 527    #endif
 528    >::type
 529 {
 530    typedef typename make_splay_set
 531       <T,
 532       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 533       O1, O2, O3, O4, O5, O6
 534       #else
 535       Options...
 536       #endif
 537       >::type   Base;
 538
 539    BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_set)
 540    public:
 541    typedef typename Base::key_compare        key_compare;
 542    typedef typename Base::value_traits       value_traits;
 543    typedef typename Base::iterator           iterator;
 544    typedef typename Base::const_iterator     const_iterator;
 545
 546    //Assert if passed value traits are compatible with the type
 547    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 548
 549    BOOST_INTRUSIVE_FORCEINLINE splay_set()
 550       :  Base()
 551    {}
 552
 553    BOOST_INTRUSIVE_FORCEINLINE explicit splay_set( const key_compare &cmp, const value_traits &v_traits = value_traits())
 554       :  Base(cmp, v_traits)
 555    {}
 556
 557    template<class Iterator>
 558    BOOST_INTRUSIVE_FORCEINLINE splay_set( Iterator b, Iterator e
 559       , const key_compare &cmp = key_compare()
 560       , const value_traits &v_traits = value_traits())
 561       :  Base(b, e, cmp, v_traits)
 562    {}
 563
 564    BOOST_INTRUSIVE_FORCEINLINE splay_set(BOOST_RV_REF(splay_set) x)
 565       :  Base(::boost::move(static_cast<Base&>(x)))
 566    {}
 567
 568    BOOST_INTRUSIVE_FORCEINLINE splay_set& operator=(BOOST_RV_REF(splay_set) x)
 569    {  return static_cast<splay_set &>(this->Base::operator=(::boost::move(static_cast<Base&>(x))));  }
 570
 571    template <class Cloner, class Disposer>
 572    BOOST_INTRUSIVE_FORCEINLINE void clone_from(const splay_set &src, Cloner cloner, Disposer disposer)
 573    {  Base::clone_from(src, cloner, disposer);  }
 574
 575    template <class Cloner, class Disposer>
 576    BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(splay_set) src, Cloner cloner, Disposer disposer)
 577    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
 578
 579    BOOST_INTRUSIVE_FORCEINLINE static splay_set &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
 580    {  return static_cast<splay_set &>(Base::container_from_end_iterator(end_iterator));   }
 581
 582    BOOST_INTRUSIVE_FORCEINLINE static const splay_set &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
 583    {  return static_cast<const splay_set &>(Base::container_from_end_iterator(end_iterator));   }
 584
 585    BOOST_INTRUSIVE_FORCEINLINE static splay_set &container_from_iterator(iterator it) BOOST_NOEXCEPT
 586    {  return static_cast<splay_set &>(Base::container_from_iterator(it));   }
 587
 588    BOOST_INTRUSIVE_FORCEINLINE static const splay_set &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
 589    {  return static_cast<const splay_set &>(Base::container_from_iterator(it));   }
 590 };
 591
 592 #endif
 593
 594 //! The class template splay_multiset is an intrusive container, that mimics most of
 595 //! the interface of std::multiset as described in the C++ standard.
 596 //!
 597 //! The template parameter \c T is the type to be managed by the container.
 598 //! The user can specify additional options and if no options are provided
 599 //! default options are used.
 600 //!
 601 //! The container supports the following options:
 602 //! \c base_hook<>/member_hook<>/value_traits<>,
 603 //! \c constant_time_size<>, \c size_type<> and
 604 //! \c compare<>.
 605 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 606 template<class T, class ...Options>
 607 #else
 608 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
 609 #endif
 610 class splay_multiset_impl
 611 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 612    : public splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder>
 613 #endif
 614 {
 615    /// @cond
 616    typedef splaytree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
 617
 618    BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_multiset_impl)
 619    typedef tree_type implementation_defined;
 620    /// @endcond
 621
 622    public:
 623    typedef typename implementation_defined::value_type               value_type;
 624    typedef typename implementation_defined::key_type                 key_type;
 625    typedef typename implementation_defined::key_of_value             key_of_value;
 626    typedef typename implementation_defined::value_traits             value_traits;
 627    typedef typename implementation_defined::pointer                  pointer;
 628    typedef typename implementation_defined::const_pointer            const_pointer;
 629    typedef typename implementation_defined::reference                reference;
 630    typedef typename implementation_defined::const_reference          const_reference;
 631    typedef typename implementation_defined::difference_type          difference_type;
 632    typedef typename implementation_defined::size_type                size_type;
 633    typedef typename implementation_defined::value_compare            value_compare;
 634    typedef typename implementation_defined::key_compare              key_compare;
 635    typedef typename implementation_defined::iterator                 iterator;
 636    typedef typename implementation_defined::const_iterator           const_iterator;
 637    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 638    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 639    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
 640    typedef typename implementation_defined::node_traits              node_traits;
 641    typedef typename implementation_defined::node                     node;
 642    typedef typename implementation_defined::node_ptr                 node_ptr;
 643    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 644    typedef typename implementation_defined::node_algorithms          node_algorithms;
 645
 646    static const bool constant_time_size = tree_type::constant_time_size;
 647
 648    public:
 649    //! @copydoc ::boost::intrusive::splaytree::splaytree()
 650    splay_multiset_impl()
 651       :  tree_type()
 652    {}
 653
 654    //! @copydoc ::boost::intrusive::splaytree::splaytree(const key_compare &,const value_traits &)
 655    explicit splay_multiset_impl(const key_compare &cmp, const value_traits &v_traits = value_traits())
 656       :  tree_type(cmp, v_traits)
 657    {}
 658
 659    //! @copydoc ::boost::intrusive::splaytree::splaytree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
 660    template<class Iterator>
 661    splay_multiset_impl( Iterator b, Iterator e
 662                 , const key_compare &cmp = key_compare()
 663                 , const value_traits &v_traits = value_traits())
 664       : tree_type(false, b, e, cmp, v_traits)
 665    {}
 666
 667    //! @copydoc ::boost::intrusive::splaytree::splaytree(splaytree &&)
 668    splay_multiset_impl(BOOST_RV_REF(splay_multiset_impl) x)
 669       :  tree_type(::boost::move(static_cast<tree_type&>(x)))
 670    {}
 671
 672    //! @copydoc ::boost::intrusive::splaytree::operator=(splaytree &&)
 673    splay_multiset_impl& operator=(BOOST_RV_REF(splay_multiset_impl) x)
 674    {  return static_cast<splay_multiset_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); }
 675
 676    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 677    //! @copydoc ::boost::intrusive::splaytree::~splaytree()
 678    ~splay_multiset_impl();
 679
 680    //! @copydoc ::boost::intrusive::splaytree::begin()
 681    iterator begin() BOOST_NOEXCEPT;
 682
 683    //! @copydoc ::boost::intrusive::splaytree::begin()const
 684    const_iterator begin() const BOOST_NOEXCEPT;
 685
 686    //! @copydoc ::boost::intrusive::splaytree::cbegin()const
 687    const_iterator cbegin() const BOOST_NOEXCEPT;
 688
 689    //! @copydoc ::boost::intrusive::splaytree::end()
 690    iterator end() BOOST_NOEXCEPT;
 691
 692    //! @copydoc ::boost::intrusive::splaytree::end()const
 693    const_iterator end() const BOOST_NOEXCEPT;
 694
 695    //! @copydoc ::boost::intrusive::splaytree::cend()const
 696    const_iterator cend() const BOOST_NOEXCEPT;
 697
 698    //! @copydoc ::boost::intrusive::splaytree::rbegin()
 699    reverse_iterator rbegin() BOOST_NOEXCEPT;
 700
 701    //! @copydoc ::boost::intrusive::splaytree::rbegin()const
 702    const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
 703
 704    //! @copydoc ::boost::intrusive::splaytree::crbegin()const
 705    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
 706
 707    //! @copydoc ::boost::intrusive::splaytree::rend()
 708    reverse_iterator rend() BOOST_NOEXCEPT;
 709
 710    //! @copydoc ::boost::intrusive::splaytree::rend()const
 711    const_reverse_iterator rend() const BOOST_NOEXCEPT;
 712
 713    //! @copydoc ::boost::intrusive::splaytree::crend()const
 714    const_reverse_iterator crend() const BOOST_NOEXCEPT;
 715
 716    //! @copydoc ::boost::intrusive::splaytree::root()
 717    iterator root() BOOST_NOEXCEPT;
 718
 719    //! @copydoc ::boost::intrusive::splaytree::root()const
 720    const_iterator root() const BOOST_NOEXCEPT;
 721
 722    //! @copydoc ::boost::intrusive::splaytree::croot()const
 723    const_iterator croot() const BOOST_NOEXCEPT;
 724
 725    //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(iterator)
 726    static splay_multiset_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
 727
 728    //! @copydoc ::boost::intrusive::splaytree::container_from_end_iterator(const_iterator)
 729    static const splay_multiset_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
 730
 731    //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(iterator)
 732    static splay_multiset_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
 733
 734    //! @copydoc ::boost::intrusive::splaytree::container_from_iterator(const_iterator)
 735    static const splay_multiset_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
 736
 737    //! @copydoc ::boost::intrusive::splaytree::key_comp()const
 738    key_compare key_comp() const;
 739
 740    //! @copydoc ::boost::intrusive::splaytree::value_comp()const
 741    value_compare value_comp() const;
 742
 743    //! @copydoc ::boost::intrusive::splaytree::empty()const
 744    bool empty() const BOOST_NOEXCEPT;
 745
 746    //! @copydoc ::boost::intrusive::splaytree::size()const
 747    size_type size() const BOOST_NOEXCEPT;
 748
 749    //! @copydoc ::boost::intrusive::splaytree::swap
 750    void swap(splay_multiset_impl& other);
 751
 752    //! @copydoc ::boost::intrusive::splaytree::clone_from(const splaytree&,Cloner,Disposer)
 753    template <class Cloner, class Disposer>
 754    void clone_from(const splay_multiset_impl &src, Cloner cloner, Disposer disposer);
 755
 756    #else
 757
 758    using tree_type::clone_from;
 759
 760    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 761
 762    //! @copydoc ::boost::intrusive::splaytree::clone_from(splaytree&&,Cloner,Disposer)
 763    template <class Cloner, class Disposer>
 764    void clone_from(BOOST_RV_REF(splay_multiset_impl) src, Cloner cloner, Disposer disposer)
 765    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 766
 767    //! @copydoc ::boost::intrusive::splaytree::insert_equal(reference)
 768    iterator insert(reference value)
 769    {  return tree_type::insert_equal(value);  }
 770
 771    //! @copydoc ::boost::intrusive::splaytree::insert_equal(const_iterator,reference)
 772    iterator insert(const_iterator hint, reference value)
 773    {  return tree_type::insert_equal(hint, value);  }
 774
 775    //! @copydoc ::boost::intrusive::splaytree::insert_equal(Iterator,Iterator)
 776    template<class Iterator>
 777    void insert(Iterator b, Iterator e)
 778    {  tree_type::insert_equal(b, e);  }
 779
 780    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 781    //! @copydoc ::boost::intrusive::splaytree::insert_before
 782    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
 783
 784    //! @copydoc ::boost::intrusive::splaytree::push_back
 785    void push_back(reference value) BOOST_NOEXCEPT;
 786
 787    //! @copydoc ::boost::intrusive::splaytree::push_front
 788    void push_front(reference value) BOOST_NOEXCEPT;
 789
 790    //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator)
 791    iterator erase(const_iterator i) BOOST_NOEXCEPT;
 792
 793    //! @copydoc ::boost::intrusive::splaytree::erase(const_iterator,const_iterator)
 794    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
 795
 796    //! @copydoc ::boost::intrusive::splaytree::erase(const key_type&)
 797    size_type erase(const key_type &key);
 798
 799    //! @copydoc ::boost::intrusive::splaytree::erase(const KeyType&,KeyTypeKeyCompare)
 800    template<class KeyType, class KeyTypeKeyCompare>
 801    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 802
 803    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,Disposer)
 804    template<class Disposer>
 805    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
 806
 807    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const_iterator,const_iterator,Disposer)
 808    template<class Disposer>
 809    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
 810
 811    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const key_type&, Disposer)
 812    template<class Disposer>
 813    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 814
 815    //! @copydoc ::boost::intrusive::splaytree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 816    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 817    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 818
 819    //! @copydoc ::boost::intrusive::splaytree::clear
 820    void clear() BOOST_NOEXCEPT;
 821
 822    //! @copydoc ::boost::intrusive::splaytree::clear_and_dispose
 823    template<class Disposer>
 824    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
 825
 826    //! @copydoc ::boost::intrusive::splaytree::count(const key_type&)
 827    size_type count(const key_type&);
 828
 829    //! @copydoc ::boost::intrusive::splaytree::count(const KeyType&,KeyTypeKeyCompare)const
 830    template<class KeyType, class KeyTypeKeyCompare>
 831    size_type count(const KeyType& key, KeyTypeKeyCompare comp);
 832
 833    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type&)
 834    iterator lower_bound(const key_type &key);
 835
 836    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare)
 837    template<class KeyType, class KeyTypeKeyCompare>
 838    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 839
 840    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const key_type&)const
 841    const_iterator lower_bound(const key_type &key) const;
 842
 843    //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 844    template<class KeyType, class KeyTypeKeyCompare>
 845    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 846
 847    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type&)
 848    iterator upper_bound(const key_type &key);
 849
 850    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare)
 851    template<class KeyType, class KeyTypeKeyCompare>
 852    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 853
 854    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const key_type&)const
 855    const_iterator upper_bound(const key_type &key) const;
 856
 857    //! @copydoc ::boost::intrusive::splaytree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 858    template<class KeyType, class KeyTypeKeyCompare>
 859    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 860
 861    //! @copydoc ::boost::intrusive::splaytree::find(const key_type&)
 862    iterator find(const key_type &key);
 863
 864    //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare)
 865    template<class KeyType, class KeyTypeKeyCompare>
 866    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 867
 868    //! @copydoc ::boost::intrusive::splaytree::find(const key_type&)const
 869    const_iterator find(const key_type &key) const;
 870
 871    //! @copydoc ::boost::intrusive::splaytree::find(const KeyType&,KeyTypeKeyCompare)const
 872    template<class KeyType, class KeyTypeKeyCompare>
 873    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 874
 875    //! @copydoc ::boost::intrusive::splaytree::equal_range(const key_type&)
 876    std::pair<iterator,iterator> equal_range(const key_type &key);
 877
 878    //! @copydoc ::boost::intrusive::splaytree::equal_range(const KeyType&,KeyTypeKeyCompare)
 879    template<class KeyType, class KeyTypeKeyCompare>
 880    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
 881
 882    //! @copydoc ::boost::intrusive::splaytree::equal_range(const key_type&)const
 883    std::pair<const_iterator, const_iterator>
 884       equal_range(const key_type &key) const;
 885
 886    //! @copydoc ::boost::intrusive::splaytree::equal_range(const KeyType&,KeyTypeKeyCompare)const
 887    template<class KeyType, class KeyTypeKeyCompare>
 888    std::pair<const_iterator, const_iterator>
 889       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
 890
 891    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&, const key_type&,bool,bool)
 892    std::pair<iterator,iterator> bounded_range
 893       (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed);
 894
 895    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 896    template<class KeyType, class KeyTypeKeyCompare>
 897    std::pair<iterator,iterator> bounded_range
 898       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 899
 900    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const key_type&, const key_type&,bool,bool)const
 901    std::pair<const_iterator, const_iterator> bounded_range
 902       (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const;
 903
 904    //! @copydoc ::boost::intrusive::splaytree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 905    template<class KeyType, class KeyTypeKeyCompare>
 906    std::pair<const_iterator, const_iterator> bounded_range
 907       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 908
 909    //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(reference)
 910    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
 911
 912    //! @copydoc ::boost::intrusive::splaytree::s_iterator_to(const_reference)
 913    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
 914
 915    //! @copydoc ::boost::intrusive::splaytree::iterator_to(reference)
 916    iterator iterator_to(reference value) BOOST_NOEXCEPT;
 917
 918    //! @copydoc ::boost::intrusive::splaytree::iterator_to(const_reference)const
 919    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
 920
 921    //! @copydoc ::boost::intrusive::splaytree::init_node(reference)
 922    static void init_node(reference value) BOOST_NOEXCEPT;
 923
 924    //! @copydoc ::boost::intrusive::splaytree::unlink_leftmost_without_rebalance
 925    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
 926
 927    //! @copydoc ::boost::intrusive::splaytree::replace_node
 928    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
 929
 930    //! @copydoc ::boost::intrusive::splaytree::remove_node
 931    void remove_node(reference value) BOOST_NOEXCEPT;
 932
 933    //! @copydoc ::boost::intrusive::splaytree::splay_up(iterator)
 934    void splay_up(iterator i) BOOST_NOEXCEPT;
 935
 936    //! @copydoc ::boost::intrusive::splaytree::splay_down(const KeyType&,KeyTypeKeyCompare)
 937    template<class KeyType, class KeyTypeKeyCompare>
 938    iterator splay_down(const KeyType &key, KeyTypeKeyCompare comp);
 939
 940    //! @copydoc ::boost::intrusive::splaytree::splay_down(const key_type &key)
 941    iterator splay_down(const key_type &key);
 942
 943    //! @copydoc ::boost::intrusive::splaytree::rebalance
 944    void rebalance() BOOST_NOEXCEPT;
 945
 946    //! @copydoc ::boost::intrusive::splaytree::rebalance_subtree
 947    iterator rebalance_subtree(iterator root) BOOST_NOEXCEPT;
 948
 949    //! @copydoc ::boost::intrusive::splaytree::merge_equal
 950    template<class ...Options2>
 951    void merge(splay_multiset<T, Options2...> &source);
 952
 953    //! @copydoc ::boost::intrusive::splaytree::merge_equal
 954    template<class ...Options2>
 955    void merge(splay_set<T, Options2...> &source);
 956
 957    #else
 958
 959    template<class Compare2>
 960    void merge(splay_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 961    {  return tree_type::merge_equal(source);  }
 962
 963    template<class Compare2>
 964    void merge(splay_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 965    {  return tree_type::merge_equal(source);  }
 966
 967    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 968 };
 969
 970 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 971
 972 template<class T, class ...Options>
 973 bool operator!= (const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y);
 974
 975 template<class T, class ...Options>
 976 bool operator>(const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y);
 977
 978 template<class T, class ...Options>
 979 bool operator<=(const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y);
 980
 981 template<class T, class ...Options>
 982 bool operator>=(const splay_multiset_impl<T, Options...> &x, const splay_multiset_impl<T, Options...> &y);
 983
 984 template<class T, class ...Options>
 985 void swap(splay_multiset_impl<T, Options...> &x, splay_multiset_impl<T, Options...> &y);
 986
 987 #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 988
 989 //! Helper metafunction to define a \c splay_multiset that yields to the same type when the
 990 //! same options (either explicitly or implicitly) are used.
 991 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 992 template<class T, class ...Options>
 993 #else
 994 template<class T, class O1 = void, class O2 = void
 995                 , class O3 = void, class O4 = void
 996                 , class O5 = void, class O6 = void>
 997 #endif
 998 struct make_splay_multiset
 999 {
1000    /// @cond
1001    typedef typename pack_options
1002       < splaytree_defaults,
1003       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1004       O1, O2, O3, O4, O5, O6
1005       #else
1006       Options...
1007       #endif
1008       >::type packed_options;
1009
1010    typedef typename detail::get_value_traits
1011       <T, typename packed_options::proto_value_traits>::type value_traits;
1012
1013    typedef splay_multiset_impl
1014          < value_traits
1015          , typename packed_options::key_of_value
1016          , typename packed_options::compare
1017          , typename packed_options::size_type
1018          , packed_options::constant_time_size
1019          , typename packed_options::header_holder_type
1020          > implementation_defined;
1021    /// @endcond
1022    typedef implementation_defined type;
1023 };
1024
1025 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1026
1027 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1028 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
1029 #else
1030 template<class T, class ...Options>
1031 #endif
1032 class splay_multiset
1033    :  public make_splay_multiset<T,
1034       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1035       O1, O2, O3, O4, O5, O6
1036       #else
1037       Options...
1038       #endif
1039       >::type
1040 {
1041    typedef typename make_splay_multiset<T,
1042       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1043       O1, O2, O3, O4, O5, O6
1044       #else
1045       Options...
1046       #endif
1047       >::type   Base;
1048
1049    BOOST_MOVABLE_BUT_NOT_COPYABLE(splay_multiset)
1050
1051    public:
1052    typedef typename Base::key_compare        key_compare;
1053    typedef typename Base::value_traits       value_traits;
1054    typedef typename Base::iterator           iterator;
1055    typedef typename Base::const_iterator     const_iterator;
1056
1057    //Assert if passed value traits are compatible with the type
1058    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1059
1060    BOOST_INTRUSIVE_FORCEINLINE splay_multiset()
1061       :  Base()
1062    {}
1063
1064    BOOST_INTRUSIVE_FORCEINLINE explicit splay_multiset( const key_compare &cmp, const value_traits &v_traits = value_traits())
1065       :  Base(cmp, v_traits)
1066    {}
1067
1068    template<class Iterator>
1069    BOOST_INTRUSIVE_FORCEINLINE splay_multiset( Iterator b, Iterator e
1070            , const key_compare &cmp = key_compare()
1071            , const value_traits &v_traits = value_traits())
1072       :  Base(b, e, cmp, v_traits)
1073    {}
1074
1075    BOOST_INTRUSIVE_FORCEINLINE splay_multiset(BOOST_RV_REF(splay_multiset) x)
1076       :  Base(::boost::move(static_cast<Base&>(x)))
1077    {}
1078
1079    BOOST_INTRUSIVE_FORCEINLINE splay_multiset& operator=(BOOST_RV_REF(splay_multiset) x)
1080    {  return static_cast<splay_multiset &>(this->Base::operator=(::boost::move(static_cast<Base&>(x))));  }
1081
1082    template <class Cloner, class Disposer>
1083    BOOST_INTRUSIVE_FORCEINLINE void clone_from(const splay_multiset &src, Cloner cloner, Disposer disposer)
1084    {  Base::clone_from(src, cloner, disposer);  }
1085
1086    template <class Cloner, class Disposer>
1087    BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(splay_multiset) src, Cloner cloner, Disposer disposer)
1088    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
1089
1090    BOOST_INTRUSIVE_FORCEINLINE static splay_multiset &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
1091    {  return static_cast<splay_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1092
1093    BOOST_INTRUSIVE_FORCEINLINE static const splay_multiset &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
1094    {  return static_cast<const splay_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1095
1096    BOOST_INTRUSIVE_FORCEINLINE static splay_multiset &container_from_iterator(iterator it) BOOST_NOEXCEPT
1097    {  return static_cast<splay_multiset &>(Base::container_from_iterator(it));   }
1098
1099    BOOST_INTRUSIVE_FORCEINLINE static const splay_multiset &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
1100    {  return static_cast<const splay_multiset &>(Base::container_from_iterator(it));   }
1101 };
1102
1103 #endif
1104
1105 } //namespace intrusive
1106 } //namespace boost
1107
1108 #include <boost/intrusive/detail/config_end.hpp>
1109
1110 #endif //BOOST_INTRUSIVE_SPLAY_SET_HPP