Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-09-17 08:34:26 

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