Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-07-01 08:18:21 

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

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!