Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:38:45 

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