Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-09-16 08:37:13 

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