boost/intrusive/treap_set.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2007-2014
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012 #ifndef BOOST_INTRUSIVE_TREAP_SET_HPP
0013 #define BOOST_INTRUSIVE_TREAP_SET_HPP
0014
0015 #include <boost/intrusive/detail/config_begin.hpp>
0016 #include <boost/intrusive/intrusive_fwd.hpp>
0017 #include <boost/intrusive/treap.hpp>
0018 #include <boost/intrusive/detail/mpl.hpp>
0019 #include <boost/move/utility_core.hpp>
0020 #include <boost/static_assert.hpp>
0021
0022 #if defined(BOOST_HAS_PRAGMA_ONCE)
0023 #  pragma once
0024 #endif
0025
0026 namespace boost {
0027 namespace intrusive {
0028
0029 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0030 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioOfValue, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0031 class treap_multiset_impl;
0032 #endif
0033
0034 //! The class template treap_set is an intrusive container, that mimics most of
0035 //! the interface of std::set as described in the C++ standard.
0036 //!
0037 //! The template parameter \c T is the type to be managed by the container.
0038 //! The user can specify additional options and if no options are provided
0039 //! default options are used.
0040 //!
0041 //! The container supports the following options:
0042 //! \c base_hook<>/member_hook<>/value_traits<>,
0043 //! \c constant_time_size<>, \c size_type<>,
0044 //! \c compare<>, \c priority<> and \c priority_of_value<>
0045 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0046 template<class T, class ...Options>
0047 #else
0048 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioOfValue, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0049 #endif
0050 class treap_set_impl
0051 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0052    : public treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder>
0053 #endif
0054 {
0055    /// @cond
0056    public:
0057    typedef treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
0058    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set_impl)
0059
0060    typedef tree_type implementation_defined;
0061    /// @endcond
0062
0063    public:
0064    typedef typename implementation_defined::value_type               value_type;
0065    typedef typename implementation_defined::value_traits             value_traits;
0066    typedef typename implementation_defined::key_type                 key_type;
0067    typedef typename implementation_defined::key_of_value             key_of_value;
0068    typedef typename implementation_defined::pointer                  pointer;
0069    typedef typename implementation_defined::const_pointer            const_pointer;
0070    typedef typename implementation_defined::reference                reference;
0071    typedef typename implementation_defined::const_reference          const_reference;
0072    typedef typename implementation_defined::difference_type          difference_type;
0073    typedef typename implementation_defined::size_type                size_type;
0074    typedef typename implementation_defined::value_compare            value_compare;
0075    typedef typename implementation_defined::key_compare              key_compare;
0076    typedef typename implementation_defined::priority_type            priority_type;
0077    typedef typename implementation_defined::priority_compare         priority_compare;
0078    typedef typename implementation_defined::iterator                 iterator;
0079    typedef typename implementation_defined::const_iterator           const_iterator;
0080    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
0081    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
0082    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
0083    typedef typename implementation_defined::node_traits              node_traits;
0084    typedef typename implementation_defined::node                     node;
0085    typedef typename implementation_defined::node_ptr                 node_ptr;
0086    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
0087    typedef typename implementation_defined::node_algorithms          node_algorithms;
0088
0089    static const bool constant_time_size = implementation_defined::constant_time_size;
0090
0091    public:
0092    //! @copydoc ::boost::intrusive::treap::treap()
0093    treap_set_impl()
0094       :  tree_type()
0095    {}
0096
0097    //! @copydoc ::boost::intrusive::treap::treap(const key_compare &,const priority_compare &,const value_traits &)
0098    explicit treap_set_impl( const key_compare &cmp
0099                           , const priority_compare &pcmp  = priority_compare()
0100                           , const value_traits &v_traits  = value_traits())
0101       :  tree_type(cmp, pcmp, v_traits)
0102    {}
0103
0104    //! @copydoc ::boost::intrusive::treap::treap(bool,Iterator,Iterator,const key_compare &,const priority_compare &,const value_traits &)
0105    template<class Iterator>
0106    treap_set_impl( Iterator b, Iterator e
0107            , const key_compare &cmp = key_compare()
0108            , const priority_compare &pcmp  = priority_compare()
0109            , const value_traits &v_traits = value_traits())
0110       : tree_type(true, b, e, cmp, pcmp, v_traits)
0111    {}
0112
0113    //! <b>Effects</b>: to-do
0114    //!
0115    treap_set_impl(BOOST_RV_REF(treap_set_impl) x)
0116       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
0117    {}
0118
0119    //! <b>Effects</b>: to-do
0120    //!
0121    treap_set_impl& operator=(BOOST_RV_REF(treap_set_impl) x)
0122    {  return static_cast<treap_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));  }
0123
0124    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0125    //! @copydoc ::boost::intrusive::treap::~treap()
0126    ~treap_set_impl();
0127
0128    //! @copydoc ::boost::intrusive::treap::begin()
0129    iterator begin() BOOST_NOEXCEPT;
0130
0131    //! @copydoc ::boost::intrusive::treap::begin()const
0132    const_iterator begin() const BOOST_NOEXCEPT;
0133
0134    //! @copydoc ::boost::intrusive::treap::cbegin()const
0135    const_iterator cbegin() const BOOST_NOEXCEPT;
0136
0137    //! @copydoc ::boost::intrusive::treap::end()
0138    iterator end() BOOST_NOEXCEPT;
0139
0140    //! @copydoc ::boost::intrusive::treap::end()const
0141    const_iterator end() const BOOST_NOEXCEPT;
0142
0143    //! @copydoc ::boost::intrusive::treap::cend()const
0144    const_iterator cend() const BOOST_NOEXCEPT;
0145
0146    //! @copydoc ::boost::intrusive::treap::rbegin()
0147    reverse_iterator rbegin() BOOST_NOEXCEPT;
0148
0149    //! @copydoc ::boost::intrusive::treap::rbegin()const
0150    const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
0151
0152    //! @copydoc ::boost::intrusive::treap::crbegin()const
0153    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
0154
0155    //! @copydoc ::boost::intrusive::treap::rend()
0156    reverse_iterator rend() BOOST_NOEXCEPT;
0157
0158    //! @copydoc ::boost::intrusive::treap::rend()const
0159    const_reverse_iterator rend() const BOOST_NOEXCEPT;
0160
0161    //! @copydoc ::boost::intrusive::treap::crend()const
0162    const_reverse_iterator crend() const BOOST_NOEXCEPT;
0163
0164    //! @copydoc ::boost::intrusive::treap::root()
0165    iterator root() BOOST_NOEXCEPT;
0166
0167    //! @copydoc ::boost::intrusive::treap::root()const
0168    const_iterator root() const BOOST_NOEXCEPT;
0169
0170    //! @copydoc ::boost::intrusive::treap::croot()const
0171    const_iterator croot() const BOOST_NOEXCEPT;
0172
0173    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
0174    static treap_set_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
0175
0176    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(const_iterator)
0177    static const treap_set_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
0178
0179    //! @copydoc ::boost::intrusive::treap::container_from_iterator(iterator)
0180    static treap_set_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
0181
0182    //! @copydoc ::boost::intrusive::treap::container_from_iterator(const_iterator)
0183    static const treap_set_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
0184
0185    //! @copydoc ::boost::intrusive::treap::key_comp()const
0186    key_compare key_comp() const;
0187
0188    //! @copydoc ::boost::intrusive::treap::value_comp()const
0189    value_compare value_comp() const;
0190
0191    //! @copydoc ::boost::intrusive::treap::empty()const
0192    bool empty() const BOOST_NOEXCEPT;
0193
0194    //! @copydoc ::boost::intrusive::treap::size()const
0195    size_type size() const BOOST_NOEXCEPT;
0196
0197    //! @copydoc ::boost::intrusive::treap::swap
0198    void swap(treap_set_impl& other);
0199
0200    //! @copydoc ::boost::intrusive::treap::clone_from(const treap&,Cloner,Disposer)
0201    template <class Cloner, class Disposer>
0202    void clone_from(const treap_set_impl &src, Cloner cloner, Disposer disposer);
0203
0204    #else
0205
0206    using tree_type::clone_from;
0207
0208    #endif
0209
0210    //! @copydoc ::boost::intrusive::treap::clone_from(treap&&,Cloner,Disposer)
0211    template <class Cloner, class Disposer>
0212    void clone_from(BOOST_RV_REF(treap_set_impl) src, Cloner cloner, Disposer disposer)
0213    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
0214
0215    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0216
0217    //! @copydoc ::boost::intrusive::treap::top()
0218    BOOST_INTRUSIVE_FORCEINLINE iterator top() BOOST_NOEXCEPT;
0219
0220    //! @copydoc ::boost::intrusive::treap::top()const
0221    BOOST_INTRUSIVE_FORCEINLINE const_iterator top() const BOOST_NOEXCEPT;
0222
0223    //! @copydoc ::boost::intrusive::treap::ctop()const
0224    BOOST_INTRUSIVE_FORCEINLINE const_iterator ctop() const BOOST_NOEXCEPT;
0225
0226    //! @copydoc ::boost::intrusive::treap::rtop()
0227    BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rtop() BOOST_NOEXCEPT;
0228
0229    //! @copydoc ::boost::intrusive::treap::rtop()const
0230    BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rtop() const BOOST_NOEXCEPT;
0231
0232    //! @copydoc ::boost::intrusive::treap::crtop()const
0233    BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crtop() const BOOST_NOEXCEPT;
0234
0235    //! @copydoc ::boost::intrusive::treap::crtop() const
0236    priority_compare priority_comp() const;
0237    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0238
0239    //! @copydoc ::boost::intrusive::treap::insert_unique(reference)
0240    std::pair<iterator, bool> insert(reference value)
0241    {  return tree_type::insert_unique(value);  }
0242
0243    //! @copydoc ::boost::intrusive::treap::insert_unique(const_iterator,reference)
0244    iterator insert(const_iterator hint, reference value)
0245    {  return tree_type::insert_unique(hint, value);  }
0246
0247    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const key_type&,const priority_type &,insert_commit_data&)
0248    std::pair<iterator, bool> insert_check( const key_type &key, const priority_type &prio, insert_commit_data &commit_data)
0249    {  return tree_type::insert_unique_check(key, prio, commit_data); }
0250
0251    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const_iterator,const key_type&,const priority_type &,insert_commit_data&)
0252    std::pair<iterator, bool> insert_check
0253       ( const_iterator hint, const key_type &key, const priority_type &prio, insert_commit_data &commit_data)
0254    {  return tree_type::insert_unique_check(hint, key, prio, commit_data); }
0255
0256    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const KeyType&,KeyTypeKeyCompare,PrioValuePrioCompare,insert_commit_data&)
0257    template<class KeyType, class KeyTypeKeyCompare, class PrioType, class PrioValuePrioCompare>
0258    std::pair<iterator, bool> insert_check
0259       ( const KeyType &key, KeyTypeKeyCompare comp, const PrioType &prio, PrioValuePrioCompare pcomp
0260       , insert_commit_data &commit_data)
0261    {  return tree_type::insert_unique_check(key, comp, prio, pcomp, commit_data); }
0262
0263    //! @copydoc ::boost::intrusive::treap::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,PrioValuePrioCompare,insert_commit_data&)
0264    template<class KeyType, class KeyTypeKeyCompare, class PrioType, class PrioValuePrioCompare>
0265    std::pair<iterator, bool> insert_check
0266       ( const_iterator hint
0267       , const KeyType &key, KeyTypeKeyCompare comp
0268       , const PrioType &prio, PrioValuePrioCompare pcomp
0269       , insert_commit_data &commit_data)
0270    {  return tree_type::insert_unique_check(hint, key, comp, prio, pcomp, commit_data); }
0271
0272    //! @copydoc ::boost::intrusive::treap::insert_unique(Iterator,Iterator)
0273    template<class Iterator>
0274    void insert(Iterator b, Iterator e)
0275    {  tree_type::insert_unique(b, e);  }
0276
0277    //! @copydoc ::boost::intrusive::treap::insert_unique_commit
0278    iterator insert_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT
0279    {  return tree_type::insert_unique_commit(value, commit_data);  }
0280
0281    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0282    //! @copydoc ::boost::intrusive::treap::insert_before
0283    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
0284
0285    //! @copydoc ::boost::intrusive::treap::push_back
0286    void push_back(reference value) BOOST_NOEXCEPT;
0287
0288    //! @copydoc ::boost::intrusive::treap::push_front
0289    void push_front(reference value) BOOST_NOEXCEPT;
0290
0291    //! @copydoc ::boost::intrusive::treap::erase(const_iterator)
0292    iterator erase(const_iterator i) BOOST_NOEXCEPT;
0293
0294    //! @copydoc ::boost::intrusive::treap::erase(const_iterator,const_iterator)
0295    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
0296
0297    //! @copydoc ::boost::intrusive::treap::erase(const key_type &)
0298    size_type erase(const key_type &key);
0299
0300    //! @copydoc ::boost::intrusive::treap::erase(const KeyType&,KeyTypeKeyCompare)
0301    template<class KeyType, class KeyTypeKeyCompare>
0302    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
0303
0304    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,Disposer)
0305    template<class Disposer>
0306    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
0307
0308    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,const_iterator,Disposer)
0309    template<class Disposer>
0310    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
0311
0312    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const key_type &, Disposer)
0313    template<class Disposer>
0314    size_type erase_and_dispose(const key_type &key, Disposer disposer);
0315
0316    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
0317    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
0318    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
0319
0320    //! @copydoc ::boost::intrusive::treap::clear
0321    void clear() BOOST_NOEXCEPT;
0322
0323    //! @copydoc ::boost::intrusive::treap::clear_and_dispose
0324    template<class Disposer>
0325    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
0326
0327    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0328
0329    //! @copydoc ::boost::intrusive::treap::count(const key_type &)const
0330    size_type count(const key_type &key) const
0331    {  return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); }
0332
0333    //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyTypeKeyCompare)const
0334    template<class KeyType, class KeyTypeKeyCompare>
0335    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const
0336    {  return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); }
0337
0338    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0339
0340    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)
0341    iterator lower_bound(const key_type &key);
0342
0343    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)
0344    template<class KeyType, class KeyTypeKeyCompare>
0345    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
0346
0347    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)const
0348    const_iterator lower_bound(const key_type &key) const;
0349
0350    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)const
0351    template<class KeyType, class KeyTypeKeyCompare>
0352    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0353
0354    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)
0355    iterator upper_bound(const key_type &key);
0356
0357    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)
0358    template<class KeyType, class KeyTypeKeyCompare>
0359    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
0360
0361    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)const
0362    const_iterator upper_bound(const key_type &key) const;
0363
0364    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)const
0365    template<class KeyType, class KeyTypeKeyCompare>
0366    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0367
0368    //! @copydoc ::boost::intrusive::treap::find(const key_type &)
0369    iterator find(const key_type &key);
0370
0371    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)
0372    template<class KeyType, class KeyTypeKeyCompare>
0373    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
0374
0375    //! @copydoc ::boost::intrusive::treap::find(const key_type &)const
0376    const_iterator find(const key_type &key) const;
0377
0378    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)const
0379    template<class KeyType, class KeyTypeKeyCompare>
0380    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
0381
0382    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0383
0384    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)
0385    std::pair<iterator,iterator> equal_range(const key_type &key)
0386    {  return this->tree_type::lower_bound_range(key); }
0387
0388    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)
0389    template<class KeyType, class KeyTypeKeyCompare>
0390    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp)
0391    {  return this->tree_type::equal_range(key, comp); }
0392
0393    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)const
0394    std::pair<const_iterator, const_iterator>
0395       equal_range(const key_type &key) const
0396    {  return this->tree_type::lower_bound_range(key); }
0397
0398    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)const
0399    template<class KeyType, class KeyTypeKeyCompare>
0400    std::pair<const_iterator, const_iterator>
0401       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const
0402    {  return this->tree_type::equal_range(key, comp); }
0403
0404    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0405
0406    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)
0407    std::pair<iterator,iterator> bounded_range
0408       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
0409
0410    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
0411    template<class KeyType, class KeyTypeKeyCompare>
0412    std::pair<iterator,iterator> bounded_range
0413       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
0414
0415    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)const
0416    std::pair<const_iterator, const_iterator>
0417       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
0418
0419    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
0420    template<class KeyType, class KeyTypeKeyCompare>
0421    std::pair<const_iterator, const_iterator> bounded_range
0422          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
0423
0424    //! @copydoc ::boost::intrusive::treap::s_iterator_to(reference)
0425    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
0426
0427    //! @copydoc ::boost::intrusive::treap::s_iterator_to(const_reference)
0428    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
0429
0430    //! @copydoc ::boost::intrusive::treap::iterator_to(reference)
0431    iterator iterator_to(reference value) BOOST_NOEXCEPT;
0432
0433    //! @copydoc ::boost::intrusive::treap::iterator_to(const_reference)const
0434    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
0435
0436    //! @copydoc ::boost::intrusive::treap::init_node(reference)
0437    static void init_node(reference value) BOOST_NOEXCEPT;
0438
0439    //! @copydoc ::boost::intrusive::treap::unlink_leftmost_without_rebalance
0440    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
0441
0442    //! @copydoc ::boost::intrusive::treap::replace_node
0443    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
0444
0445    //! @copydoc ::boost::intrusive::treap::remove_node
0446    void remove_node(reference value) BOOST_NOEXCEPT;
0447
0448
0449    //! @copydoc ::boost::intrusive::treap::merge_unique
0450    template<class ...Options2>
0451    void merge(treap_set<T, Options2...> &source);
0452
0453    //! @copydoc ::boost::intrusive::treap::merge_unique
0454    template<class ...Options2>
0455    void merge(treap_multiset<T, Options2...> &source);
0456
0457    #else
0458
0459    template<class Compare2>
0460    void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
0461    {  return tree_type::merge_unique(source);  }
0462
0463    template<class Compare2>
0464    void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
0465    {  return tree_type::merge_unique(source);  }
0466
0467    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0468 };
0469
0470
0471 //! Helper metafunction to define a \c treap_set that yields to the same type when the
0472 //! same options (either explicitly or implicitly) are used.
0473 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0474 template<class T, class ...Options>
0475 #else
0476 template<class T, class O1 = void, class O2 = void
0477                 , class O3 = void, class O4 = void
0478                 , class O5 = void, class O6 = void
0479                 , class O7 = void>
0480 #endif
0481 struct make_treap_set
0482 {
0483    typedef typename pack_options
0484       < treap_defaults,
0485       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0486       O1, O2, O3, O4, O5, O6, O7
0487       #else
0488       Options...
0489       #endif
0490       >::type packed_options;
0491
0492    typedef typename detail::get_value_traits
0493       <T, typename packed_options::proto_value_traits>::type value_traits;
0494
0495    typedef treap_set_impl
0496          < value_traits
0497          , typename packed_options::key_of_value
0498          , typename packed_options::compare
0499          , typename packed_options::priority_of_value
0500          , typename packed_options::priority
0501          , typename packed_options::size_type
0502          , packed_options::constant_time_size
0503          , typename packed_options::header_holder_type
0504          > implementation_defined;
0505    /// @endcond
0506    typedef implementation_defined type;
0507 };
0508
0509 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0510
0511 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0512 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7>
0513 #else
0514 template<class T, class ...Options>
0515 #endif
0516 class treap_set
0517    :  public make_treap_set<T,
0518       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0519       O1, O2, O3, O4, O5, O6, O7
0520       #else
0521       Options...
0522       #endif
0523       >::type
0524 {
0525    typedef typename make_treap_set
0526       <T,
0527       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0528       O1, O2, O3, O4, O5, O6, O7
0529       #else
0530       Options...
0531       #endif
0532       >::type   Base;
0533    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set)
0534
0535    public:
0536    typedef typename Base::key_compare        key_compare;
0537    typedef typename Base::priority_compare   priority_compare;
0538    typedef typename Base::value_traits       value_traits;
0539    typedef typename Base::iterator           iterator;
0540    typedef typename Base::const_iterator     const_iterator;
0541
0542    //Assert if passed value traits are compatible with the type
0543    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
0544
0545    BOOST_INTRUSIVE_FORCEINLINE treap_set()
0546       :  Base()
0547    {}
0548
0549    BOOST_INTRUSIVE_FORCEINLINE explicit treap_set( const key_compare &cmp
0550                      , const priority_compare &pcmp = priority_compare()
0551                      , const value_traits &v_traits = value_traits())
0552       :  Base(cmp, pcmp, v_traits)
0553    {}
0554
0555    template<class Iterator>
0556    BOOST_INTRUSIVE_FORCEINLINE treap_set( Iterator b, Iterator e
0557       , const key_compare &cmp = key_compare()
0558       , const priority_compare &pcmp = priority_compare()
0559       , const value_traits &v_traits = value_traits())
0560       :  Base(b, e, cmp, pcmp, v_traits)
0561    {}
0562
0563    BOOST_INTRUSIVE_FORCEINLINE treap_set(BOOST_RV_REF(treap_set) x)
0564       :  Base(BOOST_MOVE_BASE(Base, x))
0565    {}
0566
0567    BOOST_INTRUSIVE_FORCEINLINE treap_set& operator=(BOOST_RV_REF(treap_set) x)
0568    {  return static_cast<treap_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
0569
0570    template <class Cloner, class Disposer>
0571    BOOST_INTRUSIVE_FORCEINLINE void clone_from(const treap_set &src, Cloner cloner, Disposer disposer)
0572    {  Base::clone_from(src, cloner, disposer);  }
0573
0574    template <class Cloner, class Disposer>
0575    BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(treap_set) src, Cloner cloner, Disposer disposer)
0576    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
0577
0578    BOOST_INTRUSIVE_FORCEINLINE static treap_set &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
0579    {  return static_cast<treap_set &>(Base::container_from_end_iterator(end_iterator));   }
0580
0581    BOOST_INTRUSIVE_FORCEINLINE static const treap_set &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
0582    {  return static_cast<const treap_set &>(Base::container_from_end_iterator(end_iterator));   }
0583
0584    BOOST_INTRUSIVE_FORCEINLINE static treap_set &container_from_iterator(iterator it) BOOST_NOEXCEPT
0585    {  return static_cast<treap_set &>(Base::container_from_iterator(it));   }
0586
0587    BOOST_INTRUSIVE_FORCEINLINE static const treap_set &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
0588    {  return static_cast<const treap_set &>(Base::container_from_iterator(it));   }
0589 };
0590
0591 #endif
0592
0593 //! The class template treap_multiset is an intrusive container, that mimics most of
0594 //! the interface of std::treap_multiset as described in the C++ standard.
0595 //!
0596 //! The template parameter \c T is the type to be managed by the container.
0597 //! The user can specify additional options and if no options are provided
0598 //! default options are used.
0599 //!
0600 //! The container supports the following options:
0601 //! \c base_hook<>/member_hook<>/value_traits<>,
0602 //! \c constant_time_size<>, \c size_type<>,
0603 //! \c compare<>, \c priority<> and \c priority_of_value<>
0604 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0605 template<class T, class ...Options>
0606 #else
0607 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioOfValue, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0608 #endif
0609 class treap_multiset_impl
0610 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0611    : public treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder>
0612 #endif
0613 {
0614    /// @cond
0615    typedef treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
0616    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset_impl)
0617
0618    typedef tree_type implementation_defined;
0619    /// @endcond
0620
0621    public:
0622    typedef typename implementation_defined::value_type               value_type;
0623    typedef typename implementation_defined::value_traits             value_traits;
0624    typedef typename implementation_defined::key_type                 key_type;
0625    typedef typename implementation_defined::key_of_value             key_of_value;
0626    typedef typename implementation_defined::pointer                  pointer;
0627    typedef typename implementation_defined::const_pointer            const_pointer;
0628    typedef typename implementation_defined::reference                reference;
0629    typedef typename implementation_defined::const_reference          const_reference;
0630    typedef typename implementation_defined::difference_type          difference_type;
0631    typedef typename implementation_defined::size_type                size_type;
0632    typedef typename implementation_defined::value_compare            value_compare;
0633    typedef typename implementation_defined::key_compare              key_compare;
0634    typedef typename implementation_defined::priority_type            priority_type;
0635    typedef typename implementation_defined::priority_compare         priority_compare;
0636    typedef typename implementation_defined::iterator                 iterator;
0637    typedef typename implementation_defined::const_iterator           const_iterator;
0638    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
0639    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
0640    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
0641    typedef typename implementation_defined::node_traits              node_traits;
0642    typedef typename implementation_defined::node                     node;
0643    typedef typename implementation_defined::node_ptr                 node_ptr;
0644    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
0645    typedef typename implementation_defined::node_algorithms          node_algorithms;
0646
0647    static const bool constant_time_size = implementation_defined::constant_time_size;
0648
0649    public:
0650
0651    //! @copydoc ::boost::intrusive::treap::treap()
0652    treap_multiset_impl()
0653       :  tree_type()
0654    {}
0655
0656    //! @copydoc ::boost::intrusive::treap::treap(const key_compare &,const priority_compare &,const value_traits &)
0657    explicit treap_multiset_impl( const key_compare &cmp
0658                           , const priority_compare &pcmp  = priority_compare()
0659                           , const value_traits &v_traits  = value_traits())
0660       :  tree_type(cmp, pcmp, v_traits)
0661    {}
0662
0663    //! @copydoc ::boost::intrusive::treap::treap(bool,Iterator,Iterator,const key_compare &,const priority_compare &,const value_traits &)
0664    template<class Iterator>
0665    treap_multiset_impl( Iterator b, Iterator e
0666            , const key_compare &cmp = key_compare()
0667            , const priority_compare &pcmp  = priority_compare()
0668            , const value_traits &v_traits = value_traits())
0669       : tree_type(false, b, e, cmp, pcmp, v_traits)
0670    {}
0671
0672    //! <b>Effects</b>: to-do
0673    //!
0674    treap_multiset_impl(BOOST_RV_REF(treap_multiset_impl) x)
0675       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
0676    {}
0677
0678    //! <b>Effects</b>: to-do
0679    //!
0680    treap_multiset_impl& operator=(BOOST_RV_REF(treap_multiset_impl) x)
0681    {  return static_cast<treap_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));  }
0682
0683    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0684    //! @copydoc ::boost::intrusive::treap::~treap()
0685    ~treap_multiset_impl();
0686
0687    //! @copydoc ::boost::intrusive::treap::begin()
0688    iterator begin() BOOST_NOEXCEPT;
0689
0690    //! @copydoc ::boost::intrusive::treap::begin()const
0691    const_iterator begin() const BOOST_NOEXCEPT;
0692
0693    //! @copydoc ::boost::intrusive::treap::cbegin()const
0694    const_iterator cbegin() const BOOST_NOEXCEPT;
0695
0696    //! @copydoc ::boost::intrusive::treap::end()
0697    iterator end() BOOST_NOEXCEPT;
0698
0699    //! @copydoc ::boost::intrusive::treap::end()const
0700    const_iterator end() const BOOST_NOEXCEPT;
0701
0702    //! @copydoc ::boost::intrusive::treap::cend()const
0703    const_iterator cend() const BOOST_NOEXCEPT;
0704
0705    //! @copydoc ::boost::intrusive::treap::rbegin()
0706    reverse_iterator rbegin() BOOST_NOEXCEPT;
0707
0708    //! @copydoc ::boost::intrusive::treap::rbegin()const
0709    const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
0710
0711    //! @copydoc ::boost::intrusive::treap::crbegin()const
0712    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
0713
0714    //! @copydoc ::boost::intrusive::treap::rend()
0715    reverse_iterator rend() BOOST_NOEXCEPT;
0716
0717    //! @copydoc ::boost::intrusive::treap::rend()const
0718    const_reverse_iterator rend() const BOOST_NOEXCEPT;
0719
0720    //! @copydoc ::boost::intrusive::treap::crend()const
0721    const_reverse_iterator crend() const BOOST_NOEXCEPT;
0722
0723    //! @copydoc ::boost::intrusive::treap::root()
0724    iterator root() BOOST_NOEXCEPT;
0725
0726    //! @copydoc ::boost::intrusive::treap::root()const
0727    const_iterator root() const BOOST_NOEXCEPT;
0728
0729    //! @copydoc ::boost::intrusive::treap::croot()const
0730    const_iterator croot() const BOOST_NOEXCEPT;
0731
0732    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
0733    static treap_multiset_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
0734
0735    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(const_iterator)
0736    static const treap_multiset_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
0737
0738    //! @copydoc ::boost::intrusive::treap::container_from_iterator(iterator)
0739    static treap_multiset_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
0740
0741    //! @copydoc ::boost::intrusive::treap::container_from_iterator(const_iterator)
0742    static const treap_multiset_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
0743
0744    //! @copydoc ::boost::intrusive::treap::key_comp()const
0745    key_compare key_comp() const;
0746
0747    //! @copydoc ::boost::intrusive::treap::value_comp()const
0748    value_compare value_comp() const;
0749
0750    //! @copydoc ::boost::intrusive::treap::empty()const
0751    bool empty() const BOOST_NOEXCEPT;
0752
0753    //! @copydoc ::boost::intrusive::treap::size()const
0754    size_type size() const BOOST_NOEXCEPT;
0755
0756    //! @copydoc ::boost::intrusive::treap::swap
0757    void swap(treap_multiset_impl& other);
0758
0759    //! @copydoc ::boost::intrusive::treap::clone_from(const treap&,Cloner,Disposer)
0760    template <class Cloner, class Disposer>
0761    void clone_from(const treap_multiset_impl &src, Cloner cloner, Disposer disposer);
0762
0763    #else
0764
0765    using tree_type::clone_from;
0766
0767    #endif
0768
0769    //! @copydoc ::boost::intrusive::treap::clone_from(treap&&,Cloner,Disposer)
0770    template <class Cloner, class Disposer>
0771    void clone_from(BOOST_RV_REF(treap_multiset_impl) src, Cloner cloner, Disposer disposer)
0772    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
0773
0774    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0775
0776    //! @copydoc ::boost::intrusive::treap::top()
0777    BOOST_INTRUSIVE_FORCEINLINE iterator top() BOOST_NOEXCEPT;
0778
0779    //! @copydoc ::boost::intrusive::treap::top()const
0780    BOOST_INTRUSIVE_FORCEINLINE const_iterator top() const BOOST_NOEXCEPT;
0781
0782    //! @copydoc ::boost::intrusive::treap::ctop()const
0783    BOOST_INTRUSIVE_FORCEINLINE const_iterator ctop() const BOOST_NOEXCEPT;
0784
0785    //! @copydoc ::boost::intrusive::treap::rtop()
0786    BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rtop() BOOST_NOEXCEPT;
0787
0788    //! @copydoc ::boost::intrusive::treap::rtop()const
0789    BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rtop() const BOOST_NOEXCEPT;
0790
0791    //! @copydoc ::boost::intrusive::treap::crtop()const
0792    BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crtop() const BOOST_NOEXCEPT;
0793
0794    //! @copydoc ::boost::intrusive::treap::crtop() const
0795    priority_compare priority_comp() const;
0796    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0797
0798    //! @copydoc ::boost::intrusive::treap::insert_equal(reference)
0799    iterator insert(reference value)
0800    {  return tree_type::insert_equal(value);  }
0801
0802    //! @copydoc ::boost::intrusive::treap::insert_equal(const_iterator,reference)
0803    iterator insert(const_iterator hint, reference value)
0804    {  return tree_type::insert_equal(hint, value);  }
0805
0806    //! @copydoc ::boost::intrusive::treap::insert_equal(Iterator,Iterator)
0807    template<class Iterator>
0808    void insert(Iterator b, Iterator e)
0809    {  tree_type::insert_equal(b, e);  }
0810
0811    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0812    //! @copydoc ::boost::intrusive::treap::insert_before
0813    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
0814
0815    //! @copydoc ::boost::intrusive::treap::push_back
0816    void push_back(reference value) BOOST_NOEXCEPT;
0817
0818    //! @copydoc ::boost::intrusive::treap::push_front
0819    void push_front(reference value) BOOST_NOEXCEPT;
0820
0821    //! @copydoc ::boost::intrusive::treap::erase(const_iterator)
0822    iterator erase(const_iterator i) BOOST_NOEXCEPT;
0823
0824    //! @copydoc ::boost::intrusive::treap::erase(const_iterator,const_iterator)
0825    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
0826
0827    //! @copydoc ::boost::intrusive::treap::erase(const key_type &)
0828    size_type erase(const key_type &key);
0829
0830    //! @copydoc ::boost::intrusive::treap::erase(const KeyType&,KeyTypeKeyCompare)
0831    template<class KeyType, class KeyTypeKeyCompare>
0832    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
0833
0834    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,Disposer)
0835    template<class Disposer>
0836    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
0837
0838    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,const_iterator,Disposer)
0839    template<class Disposer>
0840    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
0841
0842    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const key_type &, Disposer)
0843    template<class Disposer>
0844    size_type erase_and_dispose(const key_type &key, Disposer disposer);
0845
0846    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
0847    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
0848    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
0849
0850    //! @copydoc ::boost::intrusive::treap::clear
0851    void clear() BOOST_NOEXCEPT;
0852
0853    //! @copydoc ::boost::intrusive::treap::clear_and_dispose
0854    template<class Disposer>
0855    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
0856
0857    //! @copydoc ::boost::intrusive::treap::count(const key_type &)const
0858    size_type count(const key_type &key) const;
0859
0860    //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyTypeKeyCompare)const
0861    template<class KeyType, class KeyTypeKeyCompare>
0862    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
0863
0864    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)
0865    iterator lower_bound(const key_type &key);
0866
0867    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)
0868    template<class KeyType, class KeyTypeKeyCompare>
0869    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
0870
0871    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)const
0872    const_iterator lower_bound(const key_type &key) const;
0873
0874    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)const
0875    template<class KeyType, class KeyTypeKeyCompare>
0876    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0877
0878    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)
0879    iterator upper_bound(const key_type &key);
0880
0881    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)
0882    template<class KeyType, class KeyTypeKeyCompare>
0883    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
0884
0885    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)const
0886    const_iterator upper_bound(const key_type &key) const;
0887
0888    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)const
0889    template<class KeyType, class KeyTypeKeyCompare>
0890    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0891
0892    //! @copydoc ::boost::intrusive::treap::find(const key_type &)
0893    iterator find(const key_type &key);
0894
0895    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)
0896    template<class KeyType, class KeyTypeKeyCompare>
0897    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
0898
0899    //! @copydoc ::boost::intrusive::treap::find(const key_type &)const
0900    const_iterator find(const key_type &key) const;
0901
0902    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)const
0903    template<class KeyType, class KeyTypeKeyCompare>
0904    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
0905
0906    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)
0907    std::pair<iterator,iterator> equal_range(const key_type &key);
0908
0909    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)
0910    template<class KeyType, class KeyTypeKeyCompare>
0911    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
0912
0913    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)const
0914    std::pair<const_iterator, const_iterator>
0915       equal_range(const key_type &key) const;
0916
0917    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)const
0918    template<class KeyType, class KeyTypeKeyCompare>
0919    std::pair<const_iterator, const_iterator>
0920       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
0921
0922    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)
0923    std::pair<iterator,iterator> bounded_range
0924       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
0925
0926    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
0927    template<class KeyType, class KeyTypeKeyCompare>
0928    std::pair<iterator,iterator> bounded_range
0929       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
0930
0931    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)const
0932    std::pair<const_iterator, const_iterator>
0933       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
0934
0935    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
0936    template<class KeyType, class KeyTypeKeyCompare>
0937    std::pair<const_iterator, const_iterator> bounded_range
0938          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
0939
0940    //! @copydoc ::boost::intrusive::treap::s_iterator_to(reference)
0941    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
0942
0943    //! @copydoc ::boost::intrusive::treap::s_iterator_to(const_reference)
0944    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
0945
0946    //! @copydoc ::boost::intrusive::treap::iterator_to(reference)
0947    iterator iterator_to(reference value) BOOST_NOEXCEPT;
0948
0949    //! @copydoc ::boost::intrusive::treap::iterator_to(const_reference)const
0950    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
0951
0952    //! @copydoc ::boost::intrusive::treap::init_node(reference)
0953    static void init_node(reference value) BOOST_NOEXCEPT;
0954
0955    //! @copydoc ::boost::intrusive::treap::unlink_leftmost_without_rebalance
0956    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
0957
0958    //! @copydoc ::boost::intrusive::treap::replace_node
0959    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
0960
0961    //! @copydoc ::boost::intrusive::treap::remove_node
0962    void remove_node(reference value) BOOST_NOEXCEPT;
0963
0964    //! @copydoc ::boost::intrusive::treap::merge_unique
0965    template<class ...Options2>
0966    void merge(treap_multiset<T, Options2...> &source);
0967
0968    //! @copydoc ::boost::intrusive::treap::merge_unique
0969    template<class ...Options2>
0970    void merge(treap_set<T, Options2...> &source);
0971
0972    #else
0973
0974    template<class Compare2>
0975    void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
0976    {  return tree_type::merge_equal(source);  }
0977
0978    template<class Compare2>
0979    void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
0980    {  return tree_type::merge_equal(source);  }
0981
0982    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0983 };
0984
0985
0986 //! Helper metafunction to define a \c treap_multiset that yields to the same type when the
0987 //! same options (either explicitly or implicitly) are used.
0988 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0989 template<class T, class ...Options>
0990 #else
0991 template<class T, class O1 = void, class O2 = void
0992                 , class O3 = void, class O4 = void
0993                 , class O5 = void, class O6 = void
0994                 , class O7 = void>
0995 #endif
0996 struct make_treap_multiset
0997 {
0998    typedef typename pack_options
0999       < 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