Back to home page

EIC code displayed by LXR
 
 

    

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