Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-07-11 08:14:03 

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