Back to home page

EIC code displayed by LXR
 
 

    

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

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