ceph/src/boost/libs/intrusive/include/boost/intrusive/set.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Olaf Krzikalla 2004-2006.
   4 // (C) Copyright Ion Gaztanaga  2006-2014
   5 //
   6 // Distributed under the Boost Software License, Version 1.0.
   7 //    (See accompanying file LICENSE_1_0.txt or copy at
   8 //          http://www.boost.org/LICENSE_1_0.txt)
   9 //
  10 // See http://www.boost.org/libs/intrusive for documentation.
  11 //
  12 /////////////////////////////////////////////////////////////////////////////
  13 #ifndef BOOST_INTRUSIVE_SET_HPP
  14 #define BOOST_INTRUSIVE_SET_HPP
  15
  16 #include <boost/intrusive/detail/config_begin.hpp>
  17 #include <boost/intrusive/intrusive_fwd.hpp>
  18
  19 #include <boost/intrusive/detail/mpl.hpp>
  20 #include <boost/intrusive/rbtree.hpp>
  21 #include <boost/move/utility_core.hpp>
  22 #include <boost/static_assert.hpp>
  23
  24 #if defined(BOOST_HAS_PRAGMA_ONCE)
  25 #  pragma once
  26 #endif
  27
  28 namespace boost {
  29 namespace intrusive {
  30
  31 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  32 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  33 class multiset_impl;
  34 #endif
  35
  36 //! The class template set is an intrusive container, that mimics most of
  37 //! the interface of std::set as described in the C++ standard.
  38 //!
  39 //! The template parameter \c T is the type to be managed by the container.
  40 //! The user can specify additional options and if no options are provided
  41 //! default options are used.
  42 //!
  43 //! The container supports the following options:
  44 //! \c base_hook<>/member_hook<>/value_traits<>,
  45 //! \c constant_time_size<>, \c size_type<> and
  46 //! \c compare<>.
  47 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  48 template<class T, class ...Options>
  49 #else
  50 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  51 #endif
  52 class set_impl
  53 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  54    : public bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder>
  55 #endif
  56 {
  57    /// @cond
  58    typedef bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder> tree_type;
  59    BOOST_MOVABLE_BUT_NOT_COPYABLE(set_impl)
  60
  61    typedef tree_type implementation_defined;
  62    /// @endcond
  63
  64    public:
  65    typedef typename implementation_defined::value_type               value_type;
  66    typedef typename implementation_defined::key_type                 key_type;
  67    typedef typename implementation_defined::key_of_value             key_of_value;
  68    typedef typename implementation_defined::value_traits             value_traits;
  69    typedef typename implementation_defined::pointer                  pointer;
  70    typedef typename implementation_defined::const_pointer            const_pointer;
  71    typedef typename implementation_defined::reference                reference;
  72    typedef typename implementation_defined::const_reference          const_reference;
  73    typedef typename implementation_defined::difference_type          difference_type;
  74    typedef typename implementation_defined::size_type                size_type;
  75    typedef typename implementation_defined::value_compare            value_compare;
  76    typedef typename implementation_defined::key_compare              key_compare;
  77    typedef typename implementation_defined::iterator                 iterator;
  78    typedef typename implementation_defined::const_iterator           const_iterator;
  79    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
  80    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
  81    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
  82    typedef typename implementation_defined::node_traits              node_traits;
  83    typedef typename implementation_defined::node                     node;
  84    typedef typename implementation_defined::node_ptr                 node_ptr;
  85    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
  86    typedef typename implementation_defined::node_algorithms          node_algorithms;
  87
  88    static const bool constant_time_size = tree_type::constant_time_size;
  89
  90    public:
  91    //! @copydoc ::boost::intrusive::rbtree::rbtree()
  92    set_impl()
  93       :  tree_type()
  94    {}
  95
  96    //! @copydoc ::boost::intrusive::rbtree::rbtree(const key_compare &,const value_traits &)
  97    explicit set_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
  98       :  tree_type(cmp, v_traits)
  99    {}
 100
 101    //! @copydoc ::boost::intrusive::rbtree::rbtree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
 102    template<class Iterator>
 103    set_impl( Iterator b, Iterator e
 104            , const key_compare &cmp = key_compare()
 105            , const value_traits &v_traits = value_traits())
 106       : tree_type(true, b, e, cmp, v_traits)
 107    {}
 108
 109    //! @copydoc ::boost::intrusive::rbtree::rbtree(rbtree &&)
 110    set_impl(BOOST_RV_REF(set_impl) x)
 111       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
 112    {}
 113
 114    //! @copydoc ::boost::intrusive::rbtree::operator=(rbtree &&)
 115    set_impl& operator=(BOOST_RV_REF(set_impl) x)
 116    {  return static_cast<set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
 117
 118    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 119    //! @copydoc ::boost::intrusive::rbtree::~rbtree()
 120    ~set_impl();
 121
 122    //! @copydoc ::boost::intrusive::rbtree::begin()
 123    iterator begin();
 124
 125    //! @copydoc ::boost::intrusive::rbtree::begin()const
 126    const_iterator begin() const;
 127
 128    //! @copydoc ::boost::intrusive::rbtree::cbegin()const
 129    const_iterator cbegin() const;
 130
 131    //! @copydoc ::boost::intrusive::rbtree::end()
 132    iterator end();
 133
 134    //! @copydoc ::boost::intrusive::rbtree::end()const
 135    const_iterator end() const;
 136
 137    //! @copydoc ::boost::intrusive::rbtree::cend()const
 138    const_iterator cend() const;
 139
 140    //! @copydoc ::boost::intrusive::rbtree::rbegin()
 141    reverse_iterator rbegin();
 142
 143    //! @copydoc ::boost::intrusive::rbtree::rbegin()const
 144    const_reverse_iterator rbegin() const;
 145
 146    //! @copydoc ::boost::intrusive::rbtree::crbegin()const
 147    const_reverse_iterator crbegin() const;
 148
 149    //! @copydoc ::boost::intrusive::rbtree::rend()
 150    reverse_iterator rend();
 151
 152    //! @copydoc ::boost::intrusive::rbtree::rend()const
 153    const_reverse_iterator rend() const;
 154
 155    //! @copydoc ::boost::intrusive::rbtree::crend()const
 156    const_reverse_iterator crend() const;
 157
 158    //! @copydoc ::boost::intrusive::rbtree::root()
 159    iterator root();
 160
 161    //! @copydoc ::boost::intrusive::rbtree::root()const
 162    const_iterator root() const;
 163
 164    //! @copydoc ::boost::intrusive::rbtree::croot()const
 165    const_iterator croot() const;
 166
 167    //! @copydoc ::boost::intrusive::rbtree::container_from_end_iterator(iterator)
 168    static set_impl &container_from_end_iterator(iterator end_iterator);
 169
 170    //! @copydoc ::boost::intrusive::rbtree::container_from_end_iterator(const_iterator)
 171    static const set_impl &container_from_end_iterator(const_iterator end_iterator);
 172
 173    //! @copydoc ::boost::intrusive::rbtree::container_from_iterator(iterator)
 174    static set_impl &container_from_iterator(iterator it);
 175
 176    //! @copydoc ::boost::intrusive::rbtree::container_from_iterator(const_iterator)
 177    static const set_impl &container_from_iterator(const_iterator it);
 178
 179    //! @copydoc ::boost::intrusive::rbtree::key_comp()const
 180    key_compare key_comp() const;
 181
 182    //! @copydoc ::boost::intrusive::rbtree::value_comp()const
 183    value_compare value_comp() const;
 184
 185    //! @copydoc ::boost::intrusive::rbtree::empty()const
 186    bool empty() const;
 187
 188    //! @copydoc ::boost::intrusive::rbtree::size()const
 189    size_type size() const;
 190
 191    //! @copydoc ::boost::intrusive::rbtree::swap
 192    void swap(set_impl& other);
 193
 194    //! @copydoc ::boost::intrusive::rbtree::clone_from(const rbtree&,Cloner,Disposer)
 195    template <class Cloner, class Disposer>
 196    void clone_from(const set_impl &src, Cloner cloner, Disposer disposer);
 197
 198    #else
 199
 200    using tree_type::clone_from;
 201
 202    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 203
 204    //! @copydoc ::boost::intrusive::rbtree::clone_from(rbtree&&,Cloner,Disposer)
 205    template <class Cloner, class Disposer>
 206    void clone_from(BOOST_RV_REF(set_impl) src, Cloner cloner, Disposer disposer)
 207    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 208
 209    //! @copydoc ::boost::intrusive::rbtree::insert_unique(reference)
 210    std::pair<iterator, bool> insert(reference value)
 211    {  return tree_type::insert_unique(value);  }
 212
 213    //! @copydoc ::boost::intrusive::rbtree::insert_unique(const_iterator,reference)
 214    iterator insert(const_iterator hint, reference value)
 215    {  return tree_type::insert_unique(hint, value);  }
 216
 217    //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const key_type&,insert_commit_data&)
 218    std::pair<iterator, bool> insert_check
 219       (const key_type &key, insert_commit_data &commit_data)
 220    {  return tree_type::insert_unique_check(key, commit_data); }
 221
 222    //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
 223    std::pair<iterator, bool> insert_check
 224       (const_iterator hint, const key_type &key
 225       ,insert_commit_data &commit_data)
 226    {  return tree_type::insert_unique_check(hint, key, commit_data); }
 227
 228    //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 229    template<class KeyType, class KeyTypeKeyCompare>
 230    std::pair<iterator, bool> insert_check
 231       (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data)
 232    {  return tree_type::insert_unique_check(key, comp, commit_data); }
 233
 234    //! @copydoc ::boost::intrusive::rbtree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 235    template<class KeyType, class KeyTypeKeyCompare>
 236    std::pair<iterator, bool> insert_check
 237       (const_iterator hint, const KeyType &key
 238       ,KeyTypeKeyCompare comp, insert_commit_data &commit_data)
 239    {  return tree_type::insert_unique_check(hint, key, comp, commit_data); }
 240
 241    //! @copydoc ::boost::intrusive::rbtree::insert_unique(Iterator,Iterator)
 242    template<class Iterator>
 243    void insert(Iterator b, Iterator e)
 244    {  tree_type::insert_unique(b, e);  }
 245
 246    //! @copydoc ::boost::intrusive::rbtree::insert_unique_commit
 247    iterator insert_commit(reference value, const insert_commit_data &commit_data)
 248    {  return tree_type::insert_unique_commit(value, commit_data);  }
 249
 250    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 251    //! @copydoc ::boost::intrusive::rbtree::insert_before
 252    iterator insert_before(const_iterator pos, reference value);
 253
 254    //! @copydoc ::boost::intrusive::rbtree::push_back
 255    void push_back(reference value);
 256
 257    //! @copydoc ::boost::intrusive::rbtree::push_front
 258    void push_front(reference value);
 259
 260    //! @copydoc ::boost::intrusive::rbtree::erase(const_iterator)
 261    iterator erase(const_iterator i);
 262
 263    //! @copydoc ::boost::intrusive::rbtree::erase(const_iterator,const_iterator)
 264    iterator erase(const_iterator b, const_iterator e);
 265
 266    //! @copydoc ::boost::intrusive::rbtree::erase(const key_type &)
 267    size_type erase(const key_type &key);
 268
 269    //! @copydoc ::boost::intrusive::rbtree::erase(const KeyType&,KeyTypeKeyCompare)
 270    template<class KeyType, class KeyTypeKeyCompare>
 271    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 272
 273    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const_iterator,Disposer)
 274    template<class Disposer>
 275    iterator erase_and_dispose(const_iterator i, Disposer disposer);
 276
 277    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const_iterator,const_iterator,Disposer)
 278    template<class Disposer>
 279    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
 280
 281    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const key_type &, Disposer)
 282    template<class Disposer>
 283    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 284
 285    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 286    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 287    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 288
 289    //! @copydoc ::boost::intrusive::rbtree::clear
 290    void clear();
 291
 292    //! @copydoc ::boost::intrusive::rbtree::clear_and_dispose
 293    template<class Disposer>
 294    void clear_and_dispose(Disposer disposer);
 295
 296    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 297
 298    //! @copydoc ::boost::intrusive::rbtree::count(const key_type &)const
 299    size_type count(const key_type &key) const
 300    {  return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); }
 301
 302    //! @copydoc ::boost::intrusive::rbtree::count(const KeyType&,KeyTypeKeyCompare)const
 303    template<class KeyType, class KeyTypeKeyCompare>
 304    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const
 305    {  return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); }
 306
 307    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 308
 309    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const key_type &)
 310    iterator lower_bound(const key_type &key);
 311
 312    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const KeyType&,KeyTypeKeyCompare)
 313    template<class KeyType, class KeyTypeKeyCompare>
 314    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 315
 316    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const key_type &)const
 317    const_iterator lower_bound(const key_type &key) const;
 318
 319    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 320    template<class KeyType, class KeyTypeKeyCompare>
 321    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 322
 323    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const key_type &)
 324    iterator upper_bound(const key_type &key);
 325
 326    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const KeyType&,KeyTypeKeyCompare)
 327    template<class KeyType, class KeyTypeKeyCompare>
 328    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 329
 330    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const key_type &)const
 331    const_iterator upper_bound(const key_type &key) const;
 332
 333    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 334    template<class KeyType, class KeyTypeKeyCompare>
 335    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 336
 337    //! @copydoc ::boost::intrusive::rbtree::find(const key_type &)
 338    iterator find(const key_type &key);
 339
 340    //! @copydoc ::boost::intrusive::rbtree::find(const KeyType&,KeyTypeKeyCompare)
 341    template<class KeyType, class KeyTypeKeyCompare>
 342    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 343
 344    //! @copydoc ::boost::intrusive::rbtree::find(const key_type &)const
 345    const_iterator find(const key_type &key) const;
 346
 347    //! @copydoc ::boost::intrusive::rbtree::find(const KeyType&,KeyTypeKeyCompare)const
 348    template<class KeyType, class KeyTypeKeyCompare>
 349    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 350
 351    #endif   //   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 352
 353    //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &)
 354    std::pair<iterator,iterator> equal_range(const key_type &key)
 355    {  return this->tree_type::lower_bound_range(key); }
 356
 357    //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare)
 358    template<class KeyType, class KeyTypeKeyCompare>
 359    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp)
 360    {  return this->tree_type::equal_range(key, comp); }
 361
 362    //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &)const
 363    std::pair<const_iterator, const_iterator>
 364       equal_range(const key_type &key) const
 365    {  return this->tree_type::lower_bound_range(key); }
 366
 367    //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare)const
 368    template<class KeyType, class KeyTypeKeyCompare>
 369    std::pair<const_iterator, const_iterator>
 370       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const
 371    {  return this->tree_type::equal_range(key, comp); }
 372
 373    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 374
 375    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const key_type &,const key_type &,bool,bool)
 376    std::pair<iterator,iterator> bounded_range
 377       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
 378
 379    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 380    template<class KeyType, class KeyTypeKeyCompare>
 381    std::pair<iterator,iterator> bounded_range
 382       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 383
 384    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const key_type &,const key_type &,bool,bool)const
 385    std::pair<const_iterator, const_iterator>
 386       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 387
 388    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 389    template<class KeyType, class KeyTypeKeyCompare>
 390    std::pair<const_iterator, const_iterator> bounded_range
 391          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 392
 393    //! @copydoc ::boost::intrusive::rbtree::s_iterator_to(reference)
 394    static iterator s_iterator_to(reference value);
 395
 396    //! @copydoc ::boost::intrusive::rbtree::s_iterator_to(const_reference)
 397    static const_iterator s_iterator_to(const_reference value);
 398
 399    //! @copydoc ::boost::intrusive::rbtree::iterator_to(reference)
 400    iterator iterator_to(reference value);
 401
 402    //! @copydoc ::boost::intrusive::rbtree::iterator_to(const_reference)const
 403    const_iterator iterator_to(const_reference value) const;
 404
 405    //! @copydoc ::boost::intrusive::rbtree::init_node(reference)
 406    static void init_node(reference value);
 407
 408    //! @copydoc ::boost::intrusive::rbtree::unlink_leftmost_without_rebalance
 409    pointer unlink_leftmost_without_rebalance();
 410
 411    //! @copydoc ::boost::intrusive::rbtree::replace_node
 412    void replace_node(iterator replace_this, reference with_this);
 413
 414    //! @copydoc ::boost::intrusive::rbtree::remove_node
 415    void remove_node(reference value);
 416
 417    //! @copydoc ::boost::intrusive::rbtree::merge_unique
 418    template<class ...Options2>
 419    void merge(set<T, Options2...> &source);
 420
 421    //! @copydoc ::boost::intrusive::rbtree::merge_unique
 422    template<class ...Options2>
 423    void merge(multiset<T, Options2...> &source);
 424
 425    #else
 426
 427    template<class Compare2>
 428    void merge(set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 429    {  return tree_type::merge_unique(source);  }
 430
 431
 432    template<class Compare2>
 433    void merge(multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 434    {  return tree_type::merge_unique(source);  }
 435
 436    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 437 };
 438
 439 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 440
 441 template<class T, class ...Options>
 442 bool operator!= (const set_impl<T, Options...> &x, const set_impl<T, Options...> &y);
 443
 444 template<class T, class ...Options>
 445 bool operator>(const set_impl<T, Options...> &x, const set_impl<T, Options...> &y);
 446
 447 template<class T, class ...Options>
 448 bool operator<=(const set_impl<T, Options...> &x, const set_impl<T, Options...> &y);
 449
 450 template<class T, class ...Options>
 451 bool operator>=(const set_impl<T, Options...> &x, const set_impl<T, Options...> &y);
 452
 453 template<class T, class ...Options>
 454 void swap(set_impl<T, Options...> &x, set_impl<T, Options...> &y);
 455
 456 #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 457
 458 //! Helper metafunction to define a \c set that yields to the same type when the
 459 //! same options (either explicitly or implicitly) are used.
 460 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 461 template<class T, class ...Options>
 462 #else
 463 template<class T, class O1 = void, class O2 = void
 464                 , class O3 = void, class O4 = void
 465                 , class O5 = void, class O6 = void>
 466 #endif
 467 struct make_set
 468 {
 469    /// @cond
 470    typedef typename pack_options
 471       < rbtree_defaults,
 472       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 473       O1, O2, O3, O4, O5, O6
 474       #else
 475       Options...
 476       #endif
 477       >::type packed_options;
 478
 479    typedef typename detail::get_value_traits
 480       <T, typename packed_options::proto_value_traits>::type value_traits;
 481
 482    typedef set_impl
 483          < value_traits
 484          , typename packed_options::key_of_value
 485          , typename packed_options::compare
 486          , typename packed_options::size_type
 487          , packed_options::constant_time_size
 488          , typename packed_options::header_holder_type
 489          > implementation_defined;
 490    /// @endcond
 491    typedef implementation_defined type;
 492 };
 493
 494 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 495 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 496 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
 497 #else
 498 template<class T, class ...Options>
 499 #endif
 500 class set
 501    :  public make_set<T,
 502    #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 503    O1, O2, O3, O4, O5, O6
 504    #else
 505    Options...
 506    #endif
 507    >::type
 508 {
 509    typedef typename make_set
 510       <T,
 511       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 512       O1, O2, O3, O4, O5, O6
 513       #else
 514       Options...
 515       #endif
 516       >::type   Base;
 517
 518    BOOST_MOVABLE_BUT_NOT_COPYABLE(set)
 519    public:
 520    typedef typename Base::key_compare        key_compare;
 521    typedef typename Base::value_traits       value_traits;
 522    typedef typename Base::iterator           iterator;
 523    typedef typename Base::const_iterator     const_iterator;
 524
 525    //Assert if passed value traits are compatible with the type
 526    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 527
 528    set()
 529       :  Base()
 530    {}
 531
 532    explicit set( const key_compare &cmp, const value_traits &v_traits = value_traits())
 533       :  Base(cmp, v_traits)
 534    {}
 535
 536    template<class Iterator>
 537    set( Iterator b, Iterator e
 538       , const key_compare &cmp = key_compare()
 539       , const value_traits &v_traits = value_traits())
 540       :  Base(b, e, cmp, v_traits)
 541    {}
 542
 543    set(BOOST_RV_REF(set) x)
 544       :  Base(BOOST_MOVE_BASE(Base, x))
 545    {}
 546
 547    set& operator=(BOOST_RV_REF(set) x)
 548    {  return static_cast<set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
 549
 550    template <class Cloner, class Disposer>
 551    void clone_from(const set &src, Cloner cloner, Disposer disposer)
 552    {  Base::clone_from(src, cloner, disposer);  }
 553
 554    template <class Cloner, class Disposer>
 555    void clone_from(BOOST_RV_REF(set) src, Cloner cloner, Disposer disposer)
 556    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
 557
 558    static set &container_from_end_iterator(iterator end_iterator)
 559    {  return static_cast<set &>(Base::container_from_end_iterator(end_iterator));   }
 560
 561    static const set &container_from_end_iterator(const_iterator end_iterator)
 562    {  return static_cast<const set &>(Base::container_from_end_iterator(end_iterator));   }
 563
 564    static set &container_from_iterator(iterator it)
 565    {  return static_cast<set &>(Base::container_from_iterator(it));   }
 566
 567    static const set &container_from_iterator(const_iterator it)
 568    {  return static_cast<const set &>(Base::container_from_iterator(it));   }
 569 };
 570
 571 #endif
 572
 573 //! The class template multiset is an intrusive container, that mimics most of
 574 //! the interface of std::multiset as described in the C++ standard.
 575 //!
 576 //! The template parameter \c T is the type to be managed by the container.
 577 //! The user can specify additional options and if no options are provided
 578 //! default options are used.
 579 //!
 580 //! The container supports the following options:
 581 //! \c base_hook<>/member_hook<>/value_traits<>,
 582 //! \c constant_time_size<>, \c size_type<> and
 583 //! \c compare<>.
 584 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 585 template<class T, class ...Options>
 586 #else
 587 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
 588 #endif
 589 class multiset_impl
 590 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 591    : public bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder>
 592 #endif
 593 {
 594    /// @cond
 595    typedef bstree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder> tree_type;
 596
 597    BOOST_MOVABLE_BUT_NOT_COPYABLE(multiset_impl)
 598    typedef tree_type implementation_defined;
 599    /// @endcond
 600
 601    public:
 602    typedef typename implementation_defined::value_type               value_type;
 603    typedef typename implementation_defined::key_type                 key_type;
 604    typedef typename implementation_defined::key_of_value             key_of_value;
 605    typedef typename implementation_defined::value_traits             value_traits;
 606    typedef typename implementation_defined::pointer                  pointer;
 607    typedef typename implementation_defined::const_pointer            const_pointer;
 608    typedef typename implementation_defined::reference                reference;
 609    typedef typename implementation_defined::const_reference          const_reference;
 610    typedef typename implementation_defined::difference_type          difference_type;
 611    typedef typename implementation_defined::size_type                size_type;
 612    typedef typename implementation_defined::value_compare            value_compare;
 613    typedef typename implementation_defined::key_compare              key_compare;
 614    typedef typename implementation_defined::iterator                 iterator;
 615    typedef typename implementation_defined::const_iterator           const_iterator;
 616    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 617    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 618    typedef typename implementation_defined::insert_commit_data       insert_commit_data;
 619    typedef typename implementation_defined::node_traits              node_traits;
 620    typedef typename implementation_defined::node                     node;
 621    typedef typename implementation_defined::node_ptr                 node_ptr;
 622    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 623    typedef typename implementation_defined::node_algorithms          node_algorithms;
 624
 625    static const bool constant_time_size = tree_type::constant_time_size;
 626
 627    public:
 628    //! @copydoc ::boost::intrusive::rbtree::rbtree()
 629    multiset_impl()
 630       :  tree_type()
 631    {}
 632
 633    //! @copydoc ::boost::intrusive::rbtree::rbtree(const key_compare &,const value_traits &)
 634    explicit multiset_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
 635       :  tree_type(cmp, v_traits)
 636    {}
 637
 638    //! @copydoc ::boost::intrusive::rbtree::rbtree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
 639    template<class Iterator>
 640    multiset_impl( Iterator b, Iterator e
 641                 , const key_compare &cmp = key_compare()
 642                 , const value_traits &v_traits = value_traits())
 643       : tree_type(false, b, e, cmp, v_traits)
 644    {}
 645
 646    //! @copydoc ::boost::intrusive::rbtree::rbtree(rbtree &&)
 647    multiset_impl(BOOST_RV_REF(multiset_impl) x)
 648       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
 649    {}
 650
 651    //! @copydoc ::boost::intrusive::rbtree::operator=(rbtree &&)
 652    multiset_impl& operator=(BOOST_RV_REF(multiset_impl) x)
 653    {  return static_cast<multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
 654
 655    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 656    //! @copydoc ::boost::intrusive::rbtree::~rbtree()
 657    ~multiset_impl();
 658
 659    //! @copydoc ::boost::intrusive::rbtree::begin()
 660    iterator begin();
 661
 662    //! @copydoc ::boost::intrusive::rbtree::begin()const
 663    const_iterator begin() const;
 664
 665    //! @copydoc ::boost::intrusive::rbtree::cbegin()const
 666    const_iterator cbegin() const;
 667
 668    //! @copydoc ::boost::intrusive::rbtree::end()
 669    iterator end();
 670
 671    //! @copydoc ::boost::intrusive::rbtree::end()const
 672    const_iterator end() const;
 673
 674    //! @copydoc ::boost::intrusive::rbtree::cend()const
 675    const_iterator cend() const;
 676
 677    //! @copydoc ::boost::intrusive::rbtree::rbegin()
 678    reverse_iterator rbegin();
 679
 680    //! @copydoc ::boost::intrusive::rbtree::rbegin()const
 681    const_reverse_iterator rbegin() const;
 682
 683    //! @copydoc ::boost::intrusive::rbtree::crbegin()const
 684    const_reverse_iterator crbegin() const;
 685
 686    //! @copydoc ::boost::intrusive::rbtree::rend()
 687    reverse_iterator rend();
 688
 689    //! @copydoc ::boost::intrusive::rbtree::rend()const
 690    const_reverse_iterator rend() const;
 691
 692    //! @copydoc ::boost::intrusive::rbtree::crend()const
 693    const_reverse_iterator crend() const;
 694
 695    //! @copydoc ::boost::intrusive::rbtree::root()
 696    iterator root();
 697
 698    //! @copydoc ::boost::intrusive::rbtree::root()const
 699    const_iterator root() const;
 700
 701    //! @copydoc ::boost::intrusive::rbtree::croot()const
 702    const_iterator croot() const;
 703
 704    //! @copydoc ::boost::intrusive::rbtree::container_from_end_iterator(iterator)
 705    static multiset_impl &container_from_end_iterator(iterator end_iterator);
 706
 707    //! @copydoc ::boost::intrusive::rbtree::container_from_end_iterator(const_iterator)
 708    static const multiset_impl &container_from_end_iterator(const_iterator end_iterator);
 709
 710    //! @copydoc ::boost::intrusive::rbtree::container_from_iterator(iterator)
 711    static multiset_impl &container_from_iterator(iterator it);
 712
 713    //! @copydoc ::boost::intrusive::rbtree::container_from_iterator(const_iterator)
 714    static const multiset_impl &container_from_iterator(const_iterator it);
 715
 716    //! @copydoc ::boost::intrusive::rbtree::key_comp()const
 717    key_compare key_comp() const;
 718
 719    //! @copydoc ::boost::intrusive::rbtree::value_comp()const
 720    value_compare value_comp() const;
 721
 722    //! @copydoc ::boost::intrusive::rbtree::empty()const
 723    bool empty() const;
 724
 725    //! @copydoc ::boost::intrusive::rbtree::size()const
 726    size_type size() const;
 727
 728    //! @copydoc ::boost::intrusive::rbtree::swap
 729    void swap(multiset_impl& other);
 730
 731    //! @copydoc ::boost::intrusive::rbtree::clone_from(const rbtree&,Cloner,Disposer)
 732    template <class Cloner, class Disposer>
 733    void clone_from(const multiset_impl &src, Cloner cloner, Disposer disposer);
 734
 735    #else
 736
 737    using tree_type::clone_from;
 738
 739    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 740
 741    //! @copydoc ::boost::intrusive::rbtree::clone_from(rbtree&&,Cloner,Disposer)
 742    template <class Cloner, class Disposer>
 743    void clone_from(BOOST_RV_REF(multiset_impl) src, Cloner cloner, Disposer disposer)
 744    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 745
 746    //! @copydoc ::boost::intrusive::rbtree::insert_equal(reference)
 747    iterator insert(reference value)
 748    {  return tree_type::insert_equal(value);  }
 749
 750    //! @copydoc ::boost::intrusive::rbtree::insert_equal(const_iterator,reference)
 751    iterator insert(const_iterator hint, reference value)
 752    {  return tree_type::insert_equal(hint, value);  }
 753
 754    //! @copydoc ::boost::intrusive::rbtree::insert_equal(Iterator,Iterator)
 755    template<class Iterator>
 756    void insert(Iterator b, Iterator e)
 757    {  tree_type::insert_equal(b, e);  }
 758
 759    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 760    //! @copydoc ::boost::intrusive::rbtree::insert_before
 761    iterator insert_before(const_iterator pos, reference value);
 762
 763    //! @copydoc ::boost::intrusive::rbtree::push_back
 764    void push_back(reference value);
 765
 766    //! @copydoc ::boost::intrusive::rbtree::push_front
 767    void push_front(reference value);
 768
 769    //! @copydoc ::boost::intrusive::rbtree::erase(const_iterator)
 770    iterator erase(const_iterator i);
 771
 772    //! @copydoc ::boost::intrusive::rbtree::erase(const_iterator,const_iterator)
 773    iterator erase(const_iterator b, const_iterator e);
 774
 775    //! @copydoc ::boost::intrusive::rbtree::erase(const key_type &)
 776    size_type erase(const key_type &key);
 777
 778    //! @copydoc ::boost::intrusive::rbtree::erase(const KeyType&,KeyTypeKeyCompare)
 779    template<class KeyType, class KeyTypeKeyCompare>
 780    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 781
 782    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const_iterator,Disposer)
 783    template<class Disposer>
 784    iterator erase_and_dispose(const_iterator i, Disposer disposer);
 785
 786    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const_iterator,const_iterator,Disposer)
 787    template<class Disposer>
 788    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
 789
 790    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const key_type &, Disposer)
 791    template<class Disposer>
 792    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 793
 794    //! @copydoc ::boost::intrusive::rbtree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 795    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 796    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 797
 798    //! @copydoc ::boost::intrusive::rbtree::clear
 799    void clear();
 800
 801    //! @copydoc ::boost::intrusive::rbtree::clear_and_dispose
 802    template<class Disposer>
 803    void clear_and_dispose(Disposer disposer);
 804
 805    //! @copydoc ::boost::intrusive::rbtree::count(const key_type &)const
 806    size_type count(const key_type &key) const;
 807
 808    //! @copydoc ::boost::intrusive::rbtree::count(const KeyType&,KeyTypeKeyCompare)const
 809    template<class KeyType, class KeyTypeKeyCompare>
 810    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
 811
 812    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const key_type &)
 813    iterator lower_bound(const key_type &key);
 814
 815    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const KeyType&,KeyTypeKeyCompare)
 816    template<class KeyType, class KeyTypeKeyCompare>
 817    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 818
 819    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const key_type &)const
 820    const_iterator lower_bound(const key_type &key) const;
 821
 822    //! @copydoc ::boost::intrusive::rbtree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 823    template<class KeyType, class KeyTypeKeyCompare>
 824    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 825
 826    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const key_type &)
 827    iterator upper_bound(const key_type &key);
 828
 829    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const KeyType&,KeyTypeKeyCompare)
 830    template<class KeyType, class KeyTypeKeyCompare>
 831    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 832
 833    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const key_type &)const
 834    const_iterator upper_bound(const key_type &key) const;
 835
 836    //! @copydoc ::boost::intrusive::rbtree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 837    template<class KeyType, class KeyTypeKeyCompare>
 838    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 839
 840    //! @copydoc ::boost::intrusive::rbtree::find(const key_type &)
 841    iterator find(const key_type &key);
 842
 843    //! @copydoc ::boost::intrusive::rbtree::find(const KeyType&,KeyTypeKeyCompare)
 844    template<class KeyType, class KeyTypeKeyCompare>
 845    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 846
 847    //! @copydoc ::boost::intrusive::rbtree::find(const key_type &)const
 848    const_iterator find(const key_type &key) const;
 849
 850    //! @copydoc ::boost::intrusive::rbtree::find(const KeyType&,KeyTypeKeyCompare)const
 851    template<class KeyType, class KeyTypeKeyCompare>
 852    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 853
 854    //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &)
 855    std::pair<iterator,iterator> equal_range(const key_type &key);
 856
 857    //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare)
 858    template<class KeyType, class KeyTypeKeyCompare>
 859    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
 860
 861    //! @copydoc ::boost::intrusive::rbtree::equal_range(const key_type &)const
 862    std::pair<const_iterator, const_iterator>
 863       equal_range(const key_type &key) const;
 864
 865    //! @copydoc ::boost::intrusive::rbtree::equal_range(const KeyType&,KeyTypeKeyCompare)const
 866    template<class KeyType, class KeyTypeKeyCompare>
 867    std::pair<const_iterator, const_iterator>
 868       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
 869
 870    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const key_type &,const key_type &,bool,bool)
 871    std::pair<iterator,iterator> bounded_range
 872       (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
 873
 874    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 875    template<class KeyType, class KeyTypeKeyCompare>
 876    std::pair<iterator,iterator> bounded_range
 877       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 878
 879    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const key_type &,const key_type &,bool,bool)const
 880    std::pair<const_iterator, const_iterator>
 881       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 882
 883    //! @copydoc ::boost::intrusive::rbtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 884    template<class KeyType, class KeyTypeKeyCompare>
 885    std::pair<const_iterator, const_iterator> bounded_range
 886          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 887
 888    //! @copydoc ::boost::intrusive::rbtree::s_iterator_to(reference)
 889    static iterator s_iterator_to(reference value);
 890
 891    //! @copydoc ::boost::intrusive::rbtree::s_iterator_to(const_reference)
 892    static const_iterator s_iterator_to(const_reference value);
 893
 894    //! @copydoc ::boost::intrusive::rbtree::iterator_to(reference)
 895    iterator iterator_to(reference value);
 896
 897    //! @copydoc ::boost::intrusive::rbtree::iterator_to(const_reference)const
 898    const_iterator iterator_to(const_reference value) const;
 899
 900    //! @copydoc ::boost::intrusive::rbtree::init_node(reference)
 901    static void init_node(reference value);
 902
 903    //! @copydoc ::boost::intrusive::rbtree::unlink_leftmost_without_rebalance
 904    pointer unlink_leftmost_without_rebalance();
 905
 906    //! @copydoc ::boost::intrusive::rbtree::replace_node
 907    void replace_node(iterator replace_this, reference with_this);
 908
 909    //! @copydoc ::boost::intrusive::rbtree::remove_node
 910    void remove_node(reference value);
 911
 912    //! @copydoc ::boost::intrusive::rbtree::merge_equal
 913    template<class ...Options2>
 914    void merge(multiset<T, Options2...> &source);
 915
 916    //! @copydoc ::boost::intrusive::rbtree::merge_equal
 917    template<class ...Options2>
 918    void merge(set<T, Options2...> &source);
 919
 920    #else
 921
 922    template<class Compare2>
 923    void merge(multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 924    {  return tree_type::merge_equal(source);  }
 925
 926    template<class Compare2>
 927    void merge(set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, HeaderHolder> &source)
 928    {  return tree_type::merge_equal(source);  }
 929
 930    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 931 };
 932
 933 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 934
 935 template<class T, class ...Options>
 936 bool operator!= (const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y);
 937
 938 template<class T, class ...Options>
 939 bool operator>(const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y);
 940
 941 template<class T, class ...Options>
 942 bool operator<=(const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y);
 943
 944 template<class T, class ...Options>
 945 bool operator>=(const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y);
 946
 947 template<class T, class ...Options>
 948 void swap(multiset_impl<T, Options...> &x, multiset_impl<T, Options...> &y);
 949
 950 #endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
 951
 952 //! Helper metafunction to define a \c multiset that yields to the same type when the
 953 //! same options (either explicitly or implicitly) are used.
 954 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 955 template<class T, class ...Options>
 956 #else
 957 template<class T, class O1 = void, class O2 = void
 958                 , class O3 = void, class O4 = void
 959                 , class O5 = void, class O6 = void>
 960 #endif
 961 struct make_multiset
 962 {
 963    /// @cond
 964    typedef typename pack_options
 965       < rbtree_defaults,
 966       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 967       O1, O2, O3, O4, O5, O6
 968       #else
 969       Options...
 970       #endif
 971       >::type packed_options;
 972
 973    typedef typename detail::get_value_traits
 974       <T, typename packed_options::proto_value_traits>::type value_traits;
 975
 976    typedef multiset_impl
 977          < value_traits
 978          , typename packed_options::key_of_value
 979          , typename packed_options::compare
 980          , typename packed_options::size_type
 981          , packed_options::constant_time_size
 982          , typename packed_options::header_holder_type
 983          > implementation_defined;
 984    /// @endcond
 985    typedef implementation_defined type;
 986 };
 987
 988 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 989
 990 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 991 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
 992 #else
 993 template<class T, class ...Options>
 994 #endif
 995 class multiset
 996    :  public make_multiset<T,
 997       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 998       O1, O2, O3, O4, O5, O6
 999       #else
1000       Options...
1001       #endif
1002       >::type
1003 {
1004    typedef typename make_multiset<T,
1005       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1006       O1, O2, O3, O4, O5, O6
1007       #else
1008       Options...
1009       #endif
1010       >::type   Base;
1011
1012    BOOST_MOVABLE_BUT_NOT_COPYABLE(multiset)
1013
1014    public:
1015    typedef typename Base::key_compare        key_compare;
1016    typedef typename Base::value_traits       value_traits;
1017    typedef typename Base::iterator           iterator;
1018    typedef typename Base::const_iterator     const_iterator;
1019
1020    //Assert if passed value traits are compatible with the type
1021    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1022
1023    multiset()
1024       :  Base()
1025    {}
1026
1027    explicit multiset( const key_compare &cmp, const value_traits &v_traits = value_traits())
1028       :  Base(cmp, v_traits)
1029    {}
1030
1031    template<class Iterator>
1032    multiset( Iterator b, Iterator e
1033            , const key_compare &cmp = key_compare()
1034            , const value_traits &v_traits = value_traits())
1035       :  Base(b, e, cmp, v_traits)
1036    {}
1037
1038    multiset(BOOST_RV_REF(multiset) x)
1039       :  Base(BOOST_MOVE_BASE(Base, x))
1040    {}
1041
1042    multiset& operator=(BOOST_RV_REF(multiset) x)
1043    {  return static_cast<multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
1044
1045    template <class Cloner, class Disposer>
1046    void clone_from(const multiset &src, Cloner cloner, Disposer disposer)
1047    {  Base::clone_from(src, cloner, disposer);  }
1048
1049    template <class Cloner, class Disposer>
1050    void clone_from(BOOST_RV_REF(multiset) src, Cloner cloner, Disposer disposer)
1051    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
1052
1053    static multiset &container_from_end_iterator(iterator end_iterator)
1054    {  return static_cast<multiset &>(Base::container_from_end_iterator(end_iterator));   }
1055
1056    static const multiset &container_from_end_iterator(const_iterator end_iterator)
1057    {  return static_cast<const multiset &>(Base::container_from_end_iterator(end_iterator));   }
1058
1059    static multiset &container_from_iterator(iterator it)
1060    {  return static_cast<multiset &>(Base::container_from_iterator(it));   }
1061
1062    static const multiset &container_from_iterator(const_iterator it)
1063    {  return static_cast<const multiset &>(Base::container_from_iterator(it));   }
1064 };
1065
1066 #endif
1067
1068 } //namespace intrusive
1069 } //namespace boost
1070
1071 #include <boost/intrusive/detail/config_end.hpp>
1072
1073 #endif //BOOST_INTRUSIVE_SET_HPP