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