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