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    BOOST_INTRUSIVE_NO_DANGLING
0578    inline 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_NO_DANGLING
0582    inline static const treap_set &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
0583    {  return static_cast<const treap_set &>(Base::container_from_end_iterator(end_iterator));   }
0584
0585    BOOST_INTRUSIVE_NO_DANGLING
0586    inline static treap_set &container_from_iterator(iterator it) BOOST_NOEXCEPT
0587    {  return static_cast<treap_set &>(Base::container_from_iterator(it));   }
0588
0589    BOOST_INTRUSIVE_NO_DANGLING
0590    inline static const treap_set &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
0591    {  return static_cast<const treap_set &>(Base::container_from_iterator(it));   }
0592 };
0593
0594 #endif
0595
0596 //! The class template treap_multiset is an intrusive container, that mimics most of
0597 //! the interface of std::treap_multiset as described in the C++ standard.
0598 //!
0599 //! The template parameter \c T is the type to be managed by the container.
0600 //! The user can specify additional options and if no options are provided
0601 //! default options are used.
0602 //!
0603 //! The container supports the following options:
0604 //! \c base_hook<>/member_hook<>/value_traits<>,
0605 //! \c constant_time_size<>, \c size_type<>,
0606 //! \c compare<>, \c priority<> and \c priority_of_value<>
0607 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0608 template<class T, class ...Options>
0609 #else
0610 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioOfValue, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
0611 #endif
0612 class treap_multiset_impl
0613 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0614    : public treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder>
0615 #endif
0616 {
0617    /// @cond
0618    typedef treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
0619    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset_impl)
0620
0621    typedef tree_type implementation_defined;
0622    /// @endcond
0623
0624    public:
0625    typedef typename implementation_defined::value_type               value_type;
0626    typedef typename implementation_defined::value_traits             value_traits;
0627    typedef typename implementation_defined::key_type                 key_type;
0628    typedef typename implementation_defined::key_of_value             key_of_value;
0629    typedef typename implementation_defined::pointer                  pointer;
0630    typedef typename implementation_defined::const_pointer            const_pointer;
0631    typedef typename implementation_defined::reference                reference;
0632    typedef typename implementation_defined::const_reference          const_reference;
0633    typedef typename implementation_defined::difference_type          difference_type;
0634    typedef typename implementation_defined::size_type                size_type;
0635    typedef typename implementation_defined::value_compare            value_compare;
0636    typedef typename implementation_defined::key_compare              key_compare;
0637    typedef typename implementation_defined::priority_type            priority_type;
0638    typedef typename implementation_defined::priority_compare         priority_compare;
0639    typedef typename implementation_defined::iterator                 iterator;
0640    typedef typename implementation_defined::const_iterator           const_iterator;
0641    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
0642    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
0643    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
0644    typedef typename implementation_defined::node_traits              node_traits;
0645    typedef typename implementation_defined::node                     node;
0646    typedef typename implementation_defined::node_ptr                 node_ptr;
0647    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
0648    typedef typename implementation_defined::node_algorithms          node_algorithms;
0649
0650    static const bool constant_time_size = implementation_defined::constant_time_size;
0651
0652    public:
0653
0654    //! @copydoc ::boost::intrusive::treap::treap()
0655    treap_multiset_impl()
0656       :  tree_type()
0657    {}
0658
0659    //! @copydoc ::boost::intrusive::treap::treap(const key_compare &,const priority_compare &,const value_traits &)
0660    explicit treap_multiset_impl( const key_compare &cmp
0661                           , const priority_compare &pcmp  = priority_compare()
0662                           , const value_traits &v_traits  = value_traits())
0663       :  tree_type(cmp, pcmp, v_traits)
0664    {}
0665
0666    //! @copydoc ::boost::intrusive::treap::treap(bool,Iterator,Iterator,const key_compare &,const priority_compare &,const value_traits &)
0667    template<class Iterator>
0668    treap_multiset_impl( Iterator b, Iterator e
0669            , const key_compare &cmp = key_compare()
0670            , const priority_compare &pcmp  = priority_compare()
0671            , const value_traits &v_traits = value_traits())
0672       : tree_type(false, b, e, cmp, pcmp, v_traits)
0673    {}
0674
0675    //! <b>Effects</b>: to-do
0676    //!
0677    treap_multiset_impl(BOOST_RV_REF(treap_multiset_impl) x)
0678       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
0679    {}
0680
0681    //! <b>Effects</b>: to-do
0682    //!
0683    treap_multiset_impl& operator=(BOOST_RV_REF(treap_multiset_impl) x)
0684    {  return static_cast<treap_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x)));  }
0685
0686    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0687    //! @copydoc ::boost::intrusive::treap::~treap()
0688    ~treap_multiset_impl();
0689
0690    //! @copydoc ::boost::intrusive::treap::begin()
0691    iterator begin() BOOST_NOEXCEPT;
0692
0693    //! @copydoc ::boost::intrusive::treap::begin()const
0694    const_iterator begin() const BOOST_NOEXCEPT;
0695
0696    //! @copydoc ::boost::intrusive::treap::cbegin()const
0697    const_iterator cbegin() const BOOST_NOEXCEPT;
0698
0699    //! @copydoc ::boost::intrusive::treap::end()
0700    iterator end() BOOST_NOEXCEPT;
0701
0702    //! @copydoc ::boost::intrusive::treap::end()const
0703    const_iterator end() const BOOST_NOEXCEPT;
0704
0705    //! @copydoc ::boost::intrusive::treap::cend()const
0706    const_iterator cend() const BOOST_NOEXCEPT;
0707
0708    //! @copydoc ::boost::intrusive::treap::rbegin()
0709    reverse_iterator rbegin() BOOST_NOEXCEPT;
0710
0711    //! @copydoc ::boost::intrusive::treap::rbegin()const
0712    const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
0713
0714    //! @copydoc ::boost::intrusive::treap::crbegin()const
0715    const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
0716
0717    //! @copydoc ::boost::intrusive::treap::rend()
0718    reverse_iterator rend() BOOST_NOEXCEPT;
0719
0720    //! @copydoc ::boost::intrusive::treap::rend()const
0721    const_reverse_iterator rend() const BOOST_NOEXCEPT;
0722
0723    //! @copydoc ::boost::intrusive::treap::crend()const
0724    const_reverse_iterator crend() const BOOST_NOEXCEPT;
0725
0726    //! @copydoc ::boost::intrusive::treap::root()
0727    iterator root() BOOST_NOEXCEPT;
0728
0729    //! @copydoc ::boost::intrusive::treap::root()const
0730    const_iterator root() const BOOST_NOEXCEPT;
0731
0732    //! @copydoc ::boost::intrusive::treap::croot()const
0733    const_iterator croot() const BOOST_NOEXCEPT;
0734
0735    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
0736    static treap_multiset_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
0737
0738    //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(const_iterator)
0739    static const treap_multiset_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
0740
0741    //! @copydoc ::boost::intrusive::treap::container_from_iterator(iterator)
0742    static treap_multiset_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
0743
0744    //! @copydoc ::boost::intrusive::treap::container_from_iterator(const_iterator)
0745    static const treap_multiset_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
0746
0747    //! @copydoc ::boost::intrusive::treap::key_comp()const
0748    key_compare key_comp() const;
0749
0750    //! @copydoc ::boost::intrusive::treap::value_comp()const
0751    value_compare value_comp() const;
0752
0753    //! @copydoc ::boost::intrusive::treap::empty()const
0754    bool empty() const BOOST_NOEXCEPT;
0755
0756    //! @copydoc ::boost::intrusive::treap::size()const
0757    size_type size() const BOOST_NOEXCEPT;
0758
0759    //! @copydoc ::boost::intrusive::treap::swap
0760    void swap(treap_multiset_impl& other);
0761
0762    //! @copydoc ::boost::intrusive::treap::clone_from(const treap&,Cloner,Disposer)
0763    template <class Cloner, class Disposer>
0764    void clone_from(const treap_multiset_impl &src, Cloner cloner, Disposer disposer);
0765
0766    #else
0767
0768    using tree_type::clone_from;
0769
0770    #endif
0771
0772    //! @copydoc ::boost::intrusive::treap::clone_from(treap&&,Cloner,Disposer)
0773    template <class Cloner, class Disposer>
0774    void clone_from(BOOST_RV_REF(treap_multiset_impl) src, Cloner cloner, Disposer disposer)
0775    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
0776
0777    #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
0778
0779    //! @copydoc ::boost::intrusive::treap::top()
0780    inline iterator top() BOOST_NOEXCEPT;
0781
0782    //! @copydoc ::boost::intrusive::treap::top()const
0783    inline const_iterator top() const BOOST_NOEXCEPT;
0784
0785    //! @copydoc ::boost::intrusive::treap::ctop()const
0786    inline const_iterator ctop() const BOOST_NOEXCEPT;
0787
0788    //! @copydoc ::boost::intrusive::treap::rtop()
0789    inline reverse_iterator rtop() BOOST_NOEXCEPT;
0790
0791    //! @copydoc ::boost::intrusive::treap::rtop()const
0792    inline const_reverse_iterator rtop() const BOOST_NOEXCEPT;
0793
0794    //! @copydoc ::boost::intrusive::treap::crtop()const
0795    inline const_reverse_iterator crtop() const BOOST_NOEXCEPT;
0796
0797    //! @copydoc ::boost::intrusive::treap::crtop() const
0798    priority_compare priority_comp() const;
0799    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0800
0801    //! @copydoc ::boost::intrusive::treap::insert_equal(reference)
0802    iterator insert(reference value)
0803    {  return tree_type::insert_equal(value);  }
0804
0805    //! @copydoc ::boost::intrusive::treap::insert_equal(const_iterator,reference)
0806    iterator insert(const_iterator hint, reference value)
0807    {  return tree_type::insert_equal(hint, value);  }
0808
0809    //! @copydoc ::boost::intrusive::treap::insert_equal(Iterator,Iterator)
0810    template<class Iterator>
0811    void insert(Iterator b, Iterator e)
0812    {  tree_type::insert_equal(b, e);  }
0813
0814    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0815    //! @copydoc ::boost::intrusive::treap::insert_before
0816    iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
0817
0818    //! @copydoc ::boost::intrusive::treap::push_back
0819    void push_back(reference value) BOOST_NOEXCEPT;
0820
0821    //! @copydoc ::boost::intrusive::treap::push_front
0822    void push_front(reference value) BOOST_NOEXCEPT;
0823
0824    //! @copydoc ::boost::intrusive::treap::erase(const_iterator)
0825    iterator erase(const_iterator i) BOOST_NOEXCEPT;
0826
0827    //! @copydoc ::boost::intrusive::treap::erase(const_iterator,const_iterator)
0828    iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
0829
0830    //! @copydoc ::boost::intrusive::treap::erase(const key_type &)
0831    size_type erase(const key_type &key);
0832
0833    //! @copydoc ::boost::intrusive::treap::erase(const KeyType&,KeyTypeKeyCompare)
0834    template<class KeyType, class KeyTypeKeyCompare>
0835    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
0836
0837    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,Disposer)
0838    template<class Disposer>
0839    iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
0840
0841    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,const_iterator,Disposer)
0842    template<class Disposer>
0843    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
0844
0845    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const key_type &, Disposer)
0846    template<class Disposer>
0847    size_type erase_and_dispose(const key_type &key, Disposer disposer);
0848
0849    //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
0850    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
0851    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
0852
0853    //! @copydoc ::boost::intrusive::treap::clear
0854    void clear() BOOST_NOEXCEPT;
0855
0856    //! @copydoc ::boost::intrusive::treap::clear_and_dispose
0857    template<class Disposer>
0858    void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
0859
0860    //! @copydoc ::boost::intrusive::treap::count(const key_type &)const
0861    size_type count(const key_type &key) const;
0862
0863    //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyTypeKeyCompare)const
0864    template<class KeyType, class KeyTypeKeyCompare>
0865    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
0866
0867    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)
0868    iterator lower_bound(const key_type &key);
0869
0870    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)
0871    template<class KeyType, class KeyTypeKeyCompare>
0872    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
0873
0874    //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)const
0875    const_iterator lower_bound(const key_type &key) const;
0876
0877    //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)const
0878    template<class KeyType, class KeyTypeKeyCompare>
0879    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0880
0881    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)
0882    iterator upper_bound(const key_type &key);
0883
0884    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)
0885    template<class KeyType, class KeyTypeKeyCompare>
0886    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
0887
0888    //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)const
0889    const_iterator upper_bound(const key_type &key) const;
0890
0891    //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)const
0892    template<class KeyType, class KeyTypeKeyCompare>
0893    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
0894
0895    //! @copydoc ::boost::intrusive::treap::find(const key_type &)
0896    iterator find(const key_type &key);
0897
0898    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)
0899    template<class KeyType, class KeyTypeKeyCompare>
0900    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
0901
0902    //! @copydoc ::boost::intrusive::treap::find(const key_type &)const
0903    const_iterator find(const key_type &key) const;
0904
0905    //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)const
0906    template<class KeyType, class KeyTypeKeyCompare>
0907    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
0908
0909    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)
0910    std::pair<iterator,iterator> equal_range(const key_type &key);
0911
0912    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)
0913    template<class KeyType, class KeyTypeKeyCompare>
0914    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
0915
0916    //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)const
0917    std::pair<const_iterator, const_iterator>
0918       equal_range(const key_type &key) const;
0919
0920    //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)const
0921    template<class KeyType, class KeyTypeKeyCompare>
0922    std::pair<const_iterator, const_iterator>
0923       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
0924
0925    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)
0926    std::pair<iterator,iterator> bounded_range
0927       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
0928
0929    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
0930    template<class KeyType, class KeyTypeKeyCompare>
0931    std::pair<iterator,iterator> bounded_range
0932       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
0933
0934    //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)const
0935    std::pair<const_iterator, const_iterator>
0936       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
0937
0938    //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
0939    template<class KeyType, class KeyTypeKeyCompare>
0940    std::pair<const_iterator, const_iterator> bounded_range
0941          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
0942
0943    //! @copydoc ::boost::intrusive::treap::s_iterator_to(reference)
0944    static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
0945
0946    //! @copydoc ::boost::intrusive::treap::s_iterator_to(const_reference)
0947    static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
0948
0949    //! @copydoc ::boost::intrusive::treap::iterator_to(reference)
0950    iterator iterator_to(reference value) BOOST_NOEXCEPT;
0951
0952    //! @copydoc ::boost::intrusive::treap::iterator_to(const_reference)const
0953    const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
0954
0955    //! @copydoc ::boost::intrusive::treap::init_node(reference)
0956    static void init_node(reference value) BOOST_NOEXCEPT;
0957
0958    //! @copydoc ::boost::intrusive::treap::unlink_leftmost_without_rebalance
0959    pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
0960
0961    //! @copydoc ::boost::intrusive::treap::replace_node
0962    void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
0963
0964    //! @copydoc ::boost::intrusive::treap::remove_node
0965    void remove_node(reference value) BOOST_NOEXCEPT;
0966
0967    //! @copydoc ::boost::intrusive::treap::merge_unique
0968    template<class ...Options2>
0969    void merge(treap_multiset<T, Options2...> &source);
0970
0971    //! @copydoc ::boost::intrusive::treap::merge_unique
0972    template<class ...Options2>
0973    void merge(treap_set<T, Options2...> &source);
0974
0975    #else
0976
0977    template<class Compare2>
0978    void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
0979    {  return tree_type::merge_equal(source);  }
0980
0981    template<class Compare2>
0982    void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
0983    {  return tree_type::merge_equal(source);  }
0984
0985    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0986 };
0987
0988
0989 //! Helper metafunction to define a \c treap_multiset that yields to the same type when the
0990 //! same options (either explicitly or implicitly) are used.
0991 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
0992 template<class T, class ...Options>
0993 #else
0994 template<class T, class O1 = void, class O2 = void
0995                 , class O3 = void, class O4 = void
0996                 , class O5 = void, class O6 = void
0997                 , class O7 = void>
0998 #endif
0999 struct make_treap_multiset
1000 {
1001    typedef typename pack_options
1002       < treap_defaults,
1003       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1004       O1, O2, O3, O4, O5, O6, O7
1005       #else
1006       Options...
1007       #endif
1008       >::type packed_options;
1009
1010    typedef typename detail::get_value_traits
1011       <T, typename packed_options::proto_value_traits>::type value_traits;
1012
1013    typedef treap_multiset_impl
1014          < value_traits
1015          , typename packed_options::key_of_value
1016          , typename packed_options::compare
1017          , typename packed_options::priority_of_value
1018          , typename packed_options::priority
1019          , typename packed_options::size_type
1020          , packed_options::constant_time_size
1021          , typename packed_options::header_holder_type
1022          > implementation_defined;
1023    /// @endcond
1024    typedef implementation_defined type;
1025 };
1026
1027 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1028
1029 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1030 template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7>
1031 #else
1032 template<class T, class ...Options>
1033 #endif
1034 class treap_multiset
1035    :  public make_treap_multiset<T,
1036       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1037       O1, O2, O3, O4, O5, O6, O7
1038       #else
1039       Options...
1040       #endif
1041       >::type
1042 {
1043    typedef typename make_treap_multiset
1044       <T,
1045       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1046       O1, O2, O3, O4, O5, O6, O7
1047       #else
1048       Options...
1049       #endif
1050       >::type   Base;
1051    BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset)
1052
1053    public:
1054    typedef typename Base::key_compare        key_compare;
1055    typedef typename Base::priority_compare   priority_compare;
1056    typedef typename Base::value_traits       value_traits;
1057    typedef typename Base::iterator           iterator;
1058    typedef typename Base::const_iterator     const_iterator;
1059
1060    //Assert if passed value traits are compatible with the type
1061    BOOST_INTRUSIVE_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1062
1063    inline treap_multiset()
1064       :  Base()
1065    {}
1066
1067    inline explicit treap_multiset( const key_compare &cmp
1068                           , const priority_compare &pcmp = priority_compare()
1069                           , const value_traits &v_traits = value_traits())
1070       :  Base(cmp, pcmp, v_traits)
1071    {}
1072
1073    template<class Iterator>
1074    inline treap_multiset( Iterator b, Iterator e
1075       , const key_compare &cmp = key_compare()
1076       , const priority_compare &pcmp = priority_compare()
1077       , const value_traits &v_traits = value_traits())
1078       :  Base(b, e, cmp, pcmp, v_traits)
1079    {}
1080
1081    inline treap_multiset(BOOST_RV_REF(treap_multiset) x)
1082       :  Base(BOOST_MOVE_BASE(Base, x))
1083    {}
1084
1085    inline treap_multiset& operator=(BOOST_RV_REF(treap_multiset) x)
1086    {  return static_cast<treap_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
1087
1088    template <class Cloner, class Disposer>
1089    inline void clone_from(const treap_multiset &src, Cloner cloner, Disposer disposer)
1090    {  Base::clone_from(src, cloner, disposer);  }
1091
1092    template <class Cloner, class Disposer>
1093    inline void clone_from(BOOST_RV_REF(treap_multiset) src, Cloner cloner, Disposer disposer)
1094    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
1095
1096    BOOST_INTRUSIVE_NO_DANGLING
1097    inline static treap_multiset &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
1098    {  return static_cast<treap_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1099
1100    BOOST_INTRUSIVE_NO_DANGLING
1101    inline static const treap_multiset &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
1102    {  return static_cast<const treap_multiset &>(Base::container_from_end_iterator(end_iterator));   }
1103
1104    BOOST_INTRUSIVE_NO_DANGLING
1105    inline static treap_multiset &container_from_iterator(iterator it) BOOST_NOEXCEPT
1106    {  return static_cast<treap_multiset &>(Base::container_from_iterator(it));   }
1107
1108    BOOST_INTRUSIVE_NO_DANGLING
1109    inline static const treap_multiset &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
1110    {  return static_cast<const treap_multiset &>(Base::container_from_iterator(it));   }
1111 };
1112
1113 #endif
1114
1115 } //namespace intrusive
1116 } //namespace boost
1117
1118 #include <boost/intrusive/detail/config_end.hpp>
1119
1120 #endif //BOOST_INTRUSIVE_TREAP_SET_HPP