boost/container/set.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/container for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_CONTAINER_SET_HPP
  12 #define BOOST_CONTAINER_SET_HPP
  13
  14 #if defined(_MSC_VER)
  15 #  pragma once
  16 #endif
  17
  18 #include <boost/container/detail/config_begin.hpp>
  19 #include <boost/container/detail/workaround.hpp>
  20 #include <boost/container/container_fwd.hpp>
  21
  22 #include <utility>
  23 #include <functional>
  24 #include <memory>
  25
  26 #include <boost/move/utility_core.hpp>
  27 #include <boost/move/detail/move_helpers.hpp>
  28 #include <boost/move/traits.hpp>
  29 #include <boost/container/detail/mpl.hpp>
  30 #include <boost/container/detail/tree.hpp>
  31 #include <boost/move/utility_core.hpp>
  32 #ifndef BOOST_CONTAINER_PERFECT_FORWARDING
  33 #include <boost/container/detail/preprocessor.hpp>
  34 #endif
  35 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  36 #include <initializer_list>
  37 #endif
  38
  39 namespace boost {
  40 namespace container {
  41
  42 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
  43
  44 //! A set is a kind of associative container that supports unique keys (contains at
  45 //! most one of each key value) and provides for fast retrieval of the keys themselves.
  46 //! Class set supports bidirectional iterators.
  47 //!
  48 //! A set satisfies all of the requirements of a container and of a reversible container
  49 //! , and of an associative container. A set also provides most operations described in
  50 //! for unique keys.
  51 //!
  52 //! \tparam Key is the type to be inserted in the set, which is also the key_type
  53 //! \tparam Compare is the comparison functor used to order keys
  54 //! \tparam Allocator is the allocator to be used to allocate memory for this container
  55 //! \tparam SetOptions is an packed option type generated using using boost::container::tree_assoc_options.
  56 template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>, class SetOptions = tree_assoc_defaults >
  57 #else
  58 template <class Key, class Compare, class Allocator, class SetOptions>
  59 #endif
  60 class set
  61    ///@cond
  62    : public container_detail::tree
  63       < Key, Key, container_detail::identity<Key>, Compare, Allocator, SetOptions>
  64    ///@endcond
  65 {
  66    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  67    private:
  68    BOOST_COPYABLE_AND_MOVABLE(set)
  69    typedef container_detail::tree
  70       < Key, Key, container_detail::identity<Key>, Compare, Allocator, SetOptions> base_t;
  71    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  72
  73    public:
  74    //////////////////////////////////////////////
  75    //
  76    //                    types
  77    //
  78    //////////////////////////////////////////////
  79    typedef Key                                                                         key_type;
  80    typedef Key                                                                         value_type;
  81    typedef Compare                                                                     key_compare;
  82    typedef Compare                                                                     value_compare;
  83    typedef ::boost::container::allocator_traits<Allocator>                             allocator_traits_type;
  84    typedef typename ::boost::container::allocator_traits<Allocator>::pointer           pointer;
  85    typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer     const_pointer;
  86    typedef typename ::boost::container::allocator_traits<Allocator>::reference         reference;
  87    typedef typename ::boost::container::allocator_traits<Allocator>::const_reference   const_reference;
  88    typedef typename ::boost::container::allocator_traits<Allocator>::size_type         size_type;
  89    typedef typename ::boost::container::allocator_traits<Allocator>::difference_type   difference_type;
  90    typedef Allocator                                                                   allocator_type;
  91    typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type)              stored_allocator_type;
  92    typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator)                           iterator;
  93    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator)                     const_iterator;
  94    typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator)                   reverse_iterator;
  95    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator)             const_reverse_iterator;
  96
  97    //////////////////////////////////////////////
  98    //
  99    //          construct/copy/destroy
 100    //
 101    //////////////////////////////////////////////
 102
 103    //! <b>Effects</b>: Default constructs an empty set.
 104    //!
 105    //! <b>Complexity</b>: Constant.
 106    set()
 107       : base_t()
 108    {}
 109
 110    //! <b>Effects</b>: Constructs an empty set using the specified comparison object
 111    //! and allocator.
 112    //!
 113    //! <b>Complexity</b>: Constant.
 114    explicit set(const Compare& comp,
 115                 const allocator_type& a = allocator_type())
 116       : base_t(comp, a)
 117    {}
 118
 119    //! <b>Effects</b>: Constructs an empty set using the specified allocator object.
 120    //!
 121    //! <b>Complexity</b>: Constant.
 122    explicit set(const allocator_type& a)
 123       : base_t(a)
 124    {}
 125
 126    //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
 127    //! allocator, and inserts elements from the range [first ,last ).
 128    //!
 129    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
 130    //! comp and otherwise N logN, where N is last - first.
 131    template <class InputIterator>
 132    set(InputIterator first, InputIterator last, const Compare& comp = Compare(),
 133          const allocator_type& a = allocator_type())
 134       : base_t(true, first, last, comp, a)
 135    {}
 136
 137    //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
 138    //! allocator, and inserts elements from the ordered unique range [first ,last). This function
 139    //! is more efficient than the normal range creation for ordered ranges.
 140    //!
 141    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
 142    //! unique values.
 143    //!
 144    //! <b>Complexity</b>: Linear in N.
 145    //!
 146    //! <b>Note</b>: Non-standard extension.
 147    template <class InputIterator>
 148    set( ordered_unique_range_t, InputIterator first, InputIterator last
 149       , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
 150       : base_t(ordered_range, first, last, comp, a)
 151    {}
 152
 153 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 154    //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
 155    //! allocator, and inserts elements from the range [il.begin(), il.end()).
 156    //!
 157    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
 158    //! comp and otherwise N logN, where N is il.begin() - il.end().
 159    set(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
 160       : base_t(true, il.begin(), il.end(), comp, a)
 161    {}
 162
 163    //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
 164    //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
 165    //! is more efficient than the normal range creation for ordered ranges.
 166    //!
 167    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
 168    //! unique values.
 169    //!
 170    //! <b>Complexity</b>: Linear in N.
 171    //!
 172    //! <b>Note</b>: Non-standard extension.
 173    set(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
 174       : base_t(ordered_range, il.begin(), il.end(), comp, a)
 175    {}
 176 #endif
 177
 178    //! <b>Effects</b>: Copy constructs a set.
 179    //!
 180    //! <b>Complexity</b>: Linear in x.size().
 181    set(const set& x)
 182       : base_t(static_cast<const base_t&>(x))
 183    {}
 184
 185    //! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources.
 186    //!
 187    //! <b>Complexity</b>: Constant.
 188    //!
 189    //! <b>Postcondition</b>: x is emptied.
 190    set(BOOST_RV_REF(set) x)
 191       : base_t(boost::move(static_cast<base_t&>(x)))
 192    {}
 193
 194    //! <b>Effects</b>: Copy constructs a set using the specified allocator.
 195    //!
 196    //! <b>Complexity</b>: Linear in x.size().
 197    set(const set& x, const allocator_type &a)
 198       : base_t(static_cast<const base_t&>(x), a)
 199    {}
 200
 201    //! <b>Effects</b>: Move constructs a set using the specified allocator.
 202    //!                 Constructs *this using x's resources.
 203    //!
 204    //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
 205    set(BOOST_RV_REF(set) x, const allocator_type &a)
 206       : base_t(boost::move(static_cast<base_t&>(x)), a)
 207    {}
 208
 209    //! <b>Effects</b>: Makes *this a copy of x.
 210    //!
 211    //! <b>Complexity</b>: Linear in x.size().
 212    set& operator=(BOOST_COPY_ASSIGN_REF(set) x)
 213    {  return static_cast<set&>(this->base_t::operator=(static_cast<const base_t&>(x)));  }
 214
 215    //! <b>Effects</b>: this->swap(x.get()).
 216    //!
 217    //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
 218    //!   is false and (allocation throws or value_type's move constructor throws)
 219    //!
 220    //! <b>Complexity</b>: Constant if allocator_traits_type::
 221    //!   propagate_on_container_move_assignment is true or
 222    //!   this->get>allocator() == x.get_allocator(). Linear otherwise.
 223    set& operator=(BOOST_RV_REF(set) x)
 224       BOOST_CONTAINER_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value)
 225    {  return static_cast<set&>(this->base_t::operator=(boost::move(static_cast<base_t&>(x))));  }
 226
 227 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 228    set& operator=(std::initializer_list<value_type> il)
 229    {
 230       this->clear();
 231       insert(il.begin(), il.end());
 232       return *this;
 233    }
 234 #endif
 235
 236    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 237
 238    //! <b>Effects</b>: Returns a copy of the Allocator that
 239    //!   was passed to the object's constructor.
 240    //!
 241    //! <b>Complexity</b>: Constant.
 242    allocator_type get_allocator() const;
 243
 244    //! <b>Effects</b>: Returns a reference to the internal allocator.
 245    //!
 246    //! <b>Throws</b>: Nothing
 247    //!
 248    //! <b>Complexity</b>: Constant.
 249    //!
 250    //! <b>Note</b>: Non-standard extension.
 251    stored_allocator_type &get_stored_allocator();
 252
 253    //! <b>Effects</b>: Returns a reference to the internal allocator.
 254    //!
 255    //! <b>Throws</b>: Nothing
 256    //!
 257    //! <b>Complexity</b>: Constant.
 258    //!
 259    //! <b>Note</b>: Non-standard extension.
 260    const stored_allocator_type &get_stored_allocator() const;
 261
 262    //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
 263    //!
 264    //! <b>Throws</b>: Nothing.
 265    //!
 266    //! <b>Complexity</b>: Constant
 267    iterator begin();
 268
 269    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
 270    //!
 271    //! <b>Throws</b>: Nothing.
 272    //!
 273    //! <b>Complexity</b>: Constant.
 274    const_iterator begin() const;
 275
 276    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
 277    //!
 278    //! <b>Throws</b>: Nothing.
 279    //!
 280    //! <b>Complexity</b>: Constant.
 281    const_iterator cbegin() const;
 282
 283    //! <b>Effects</b>: Returns an iterator to the end of the container.
 284    //!
 285    //! <b>Throws</b>: Nothing.
 286    //!
 287    //! <b>Complexity</b>: Constant.
 288    iterator end();
 289
 290    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
 291    //!
 292    //! <b>Throws</b>: Nothing.
 293    //!
 294    //! <b>Complexity</b>: Constant.
 295    const_iterator end() const;
 296
 297    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
 298    //!
 299    //! <b>Throws</b>: Nothing.
 300    //!
 301    //! <b>Complexity</b>: Constant.
 302    const_iterator cend() const;
 303
 304    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
 305    //! of the reversed container.
 306    //!
 307    //! <b>Throws</b>: Nothing.
 308    //!
 309    //! <b>Complexity</b>: Constant.
 310    reverse_iterator rbegin();
 311
 312    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 313    //! of the reversed container.
 314    //!
 315    //! <b>Throws</b>: Nothing.
 316    //!
 317    //! <b>Complexity</b>: Constant.
 318    const_reverse_iterator rbegin() const;
 319
 320    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 321    //! of the reversed container.
 322    //!
 323    //! <b>Throws</b>: Nothing.
 324    //!
 325    //! <b>Complexity</b>: Constant.
 326    const_reverse_iterator crbegin() const;
 327
 328    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
 329    //! of the reversed container.
 330    //!
 331    //! <b>Throws</b>: Nothing.
 332    //!
 333    //! <b>Complexity</b>: Constant.
 334    reverse_iterator rend();
 335
 336    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 337    //! of the reversed container.
 338    //!
 339    //! <b>Throws</b>: Nothing.
 340    //!
 341    //! <b>Complexity</b>: Constant.
 342    const_reverse_iterator rend() const;
 343
 344    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 345    //! of the reversed container.
 346    //!
 347    //! <b>Throws</b>: Nothing.
 348    //!
 349    //! <b>Complexity</b>: Constant.
 350    const_reverse_iterator crend() const;
 351
 352    //! <b>Effects</b>: Returns true if the container contains no elements.
 353    //!
 354    //! <b>Throws</b>: Nothing.
 355    //!
 356    //! <b>Complexity</b>: Constant.
 357    bool empty() const;
 358
 359    //! <b>Effects</b>: Returns the number of the elements contained in the container.
 360    //!
 361    //! <b>Throws</b>: Nothing.
 362    //!
 363    //! <b>Complexity</b>: Constant.
 364    size_type size() const;
 365
 366    //! <b>Effects</b>: Returns the largest possible size of the container.
 367    //!
 368    //! <b>Throws</b>: Nothing.
 369    //!
 370    //! <b>Complexity</b>: Constant.
 371    size_type max_size() const;
 372    #endif   //   #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 373
 374    #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 375
 376    //! <b>Effects</b>:  Inserts an object x of type Key constructed with
 377    //!   std::forward<Args>(args)... if and only if there is
 378    //!   no element in the container with equivalent value.
 379    //!   and returns the iterator pointing to the
 380    //!   newly inserted element.
 381    //!
 382    //! <b>Returns</b>: The bool component of the returned pair is true if and only
 383    //!   if the insertion takes place, and the iterator component of the pair
 384    //!   points to the element with key equivalent to the key of x.
 385    //!
 386    //! <b>Throws</b>: If memory allocation throws or
 387    //!   Key's in-place constructor throws.
 388    //!
 389    //! <b>Complexity</b>: Logarithmic.
 390    template <class... Args>
 391    std::pair<iterator,bool> emplace(Args&&... args)
 392    {  return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
 393
 394    //! <b>Effects</b>:  Inserts an object of type Key constructed with
 395    //!   std::forward<Args>(args)... if and only if there is
 396    //!   no element in the container with equivalent value.
 397    //!   p is a hint pointing to where the insert
 398    //!   should start to search.
 399    //!
 400    //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
 401    //!
 402    //! <b>Complexity</b>: Logarithmic.
 403    template <class... Args>
 404    iterator emplace_hint(const_iterator p, Args&&... args)
 405    {  return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
 406
 407    #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
 408
 409    #define BOOST_PP_LOCAL_MACRO(n)                                                                 \
 410    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
 411    std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _))            \
 412    {  return this->base_t::emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); }\
 413                                                                                                    \
 414    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
 415    iterator emplace_hint(const_iterator p                                                          \
 416                          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _))              \
 417    {  return this->base_t::emplace_hint_unique(p                                                   \
 418                                BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));}   \
 419    //!
 420    #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
 421    #include BOOST_PP_LOCAL_ITERATE()
 422
 423    #endif   //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
 424
 425    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 426    //! <b>Effects</b>: Inserts x if and only if there is no element in the container
 427    //!   with key equivalent to the key of x.
 428    //!
 429    //! <b>Returns</b>: The bool component of the returned pair is true if and only
 430    //!   if the insertion takes place, and the iterator component of the pair
 431    //!   points to the element with key equivalent to the key of x.
 432    //!
 433    //! <b>Complexity</b>: Logarithmic.
 434    std::pair<iterator, bool> insert(const value_type &x);
 435
 436    //! <b>Effects</b>: Move constructs a new value from x if and only if there is
 437    //!   no element in the container with key equivalent to the key of x.
 438    //!
 439    //! <b>Returns</b>: The bool component of the returned pair is true if and only
 440    //!   if the insertion takes place, and the iterator component of the pair
 441    //!   points to the element with key equivalent to the key of x.
 442    //!
 443    //! <b>Complexity</b>: Logarithmic.
 444    std::pair<iterator, bool> insert(value_type &&x);
 445    #else
 446    private:
 447    typedef std::pair<iterator, bool> insert_return_pair;
 448    public:
 449    BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert)
 450    #endif
 451
 452    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 453    //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
 454    //!   no element in the container with key equivalent to the key of x.
 455    //!   p is a hint pointing to where the insert should start to search.
 456    //!
 457    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
 458    //!   to the key of x.
 459    //!
 460    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
 461    //!   is inserted right before p.
 462    iterator insert(const_iterator p, const value_type &x);
 463
 464    //! <b>Effects</b>: Inserts an element move constructed from x in the container.
 465    //!   p is a hint pointing to where the insert should start to search.
 466    //!
 467    //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
 468    //!
 469    //! <b>Complexity</b>: Logarithmic.
 470    iterator insert(const_iterator p, value_type &&x);
 471    #else
 472    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
 473    #endif
 474
 475    //! <b>Requires</b>: first, last are not iterators into *this.
 476    //!
 477    //! <b>Effects</b>: inserts each element from the range [first,last) if and only
 478    //!   if there is no element with key equivalent to the key of that element.
 479    //!
 480    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
 481    template <class InputIterator>
 482    void insert(InputIterator first, InputIterator last)
 483    {  this->base_t::insert_unique(first, last);  }
 484
 485 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 486    //! <b>Effects</b>: inserts each element from the range [il.begin(),il.end()) if and only
 487    //!   if there is no element with key equivalent to the key of that element.
 488    //!
 489    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
 490    void insert(std::initializer_list<value_type> il)
 491    {  this->base_t::insert_unique(il.begin(), il.end()); }
 492 #endif
 493
 494    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 495
 496    //! <b>Effects</b>: Erases the element pointed to by p.
 497    //!
 498    //! <b>Returns</b>: Returns an iterator pointing to the element immediately
 499    //!   following q prior to the element being erased. If no such element exists,
 500    //!   returns end().
 501    //!
 502    //! <b>Complexity</b>: Amortized constant time
 503    iterator erase(const_iterator p);
 504
 505    //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
 506    //!
 507    //! <b>Returns</b>: Returns the number of erased elements.
 508    //!
 509    //! <b>Complexity</b>: log(size()) + count(k)
 510    size_type erase(const key_type& x);
 511
 512    //! <b>Effects</b>: Erases all the elements in the range [first, last).
 513    //!
 514    //! <b>Returns</b>: Returns last.
 515    //!
 516    //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
 517    iterator erase(const_iterator first, const_iterator last);
 518
 519    //! <b>Effects</b>: Swaps the contents of *this and x.
 520    //!
 521    //! <b>Throws</b>: Nothing.
 522    //!
 523    //! <b>Complexity</b>: Constant.
 524    void swap(set& x);
 525
 526    //! <b>Effects</b>: erase(a.begin(),a.end()).
 527    //!
 528    //! <b>Postcondition</b>: size() == 0.
 529    //!
 530    //! <b>Complexity</b>: linear in size().
 531    void clear();
 532
 533    //! <b>Effects</b>: Returns the comparison object out
 534    //!   of which a was constructed.
 535    //!
 536    //! <b>Complexity</b>: Constant.
 537    key_compare key_comp() const;
 538
 539    //! <b>Effects</b>: Returns an object of value_compare constructed out
 540    //!   of the comparison object.
 541    //!
 542    //! <b>Complexity</b>: Constant.
 543    value_compare value_comp() const;
 544
 545    //! <b>Returns</b>: An iterator pointing to an element with the key
 546    //!   equivalent to x, or end() if such an element is not found.
 547    //!
 548    //! <b>Complexity</b>: Logarithmic.
 549    iterator find(const key_type& x);
 550
 551    //! <b>Returns</b>: Allocator const_iterator pointing to an element with the key
 552    //!   equivalent to x, or end() if such an element is not found.
 553    //!
 554    //! <b>Complexity</b>: Logarithmic.
 555    const_iterator find(const key_type& x) const;
 556
 557    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 558
 559    //! <b>Returns</b>: The number of elements with key equivalent to x.
 560    //!
 561    //! <b>Complexity</b>: log(size())+count(k)
 562    size_type count(const key_type& x) const
 563    {  return static_cast<size_type>(this->base_t::find(x) != this->base_t::cend());  }
 564
 565    //! <b>Returns</b>: The number of elements with key equivalent to x.
 566    //!
 567    //! <b>Complexity</b>: log(size())+count(k)
 568    size_type count(const key_type& x)
 569    {  return static_cast<size_type>(this->base_t::find(x) != this->base_t::end());  }
 570
 571    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 572
 573    //! <b>Returns</b>: An iterator pointing to the first element with key not less
 574    //!   than k, or a.end() if such an element is not found.
 575    //!
 576    //! <b>Complexity</b>: Logarithmic
 577    iterator lower_bound(const key_type& x);
 578
 579    //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
 580    //!   less than k, or a.end() if such an element is not found.
 581    //!
 582    //! <b>Complexity</b>: Logarithmic
 583    const_iterator lower_bound(const key_type& x) const;
 584
 585    //! <b>Returns</b>: An iterator pointing to the first element with key not less
 586    //!   than x, or end() if such an element is not found.
 587    //!
 588    //! <b>Complexity</b>: Logarithmic
 589    iterator upper_bound(const key_type& x);
 590
 591    //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
 592    //!   less than x, or end() if such an element is not found.
 593    //!
 594    //! <b>Complexity</b>: Logarithmic
 595    const_iterator upper_bound(const key_type& x) const;
 596
 597    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 598
 599    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
 600    //!
 601    //! <b>Complexity</b>: Logarithmic
 602    std::pair<iterator,iterator> equal_range(const key_type& x)
 603    {  return this->base_t::lower_bound_range(x);  }
 604
 605    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
 606    //!
 607    //! <b>Complexity</b>: Logarithmic
 608    std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
 609    {  return this->base_t::lower_bound_range(x);  }
 610
 611    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 612
 613    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
 614    //!
 615    //! <b>Complexity</b>: Logarithmic
 616    std::pair<iterator,iterator> equal_range(const key_type& x);
 617
 618    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
 619    //!
 620    //! <b>Complexity</b>: Logarithmic
 621    std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
 622
 623    //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
 624    //!
 625    //! <b>Complexity</b>: Linear
 626    void rebalance();
 627
 628    //! <b>Effects</b>: Returns true if x and y are equal
 629    //!
 630    //! <b>Complexity</b>: Linear to the number of elements in the container.
 631    friend bool operator==(const set& x, const set& y);
 632
 633    //! <b>Effects</b>: Returns true if x and y are unequal
 634    //!
 635    //! <b>Complexity</b>: Linear to the number of elements in the container.
 636    friend bool operator!=(const set& x, const set& y);
 637
 638    //! <b>Effects</b>: Returns true if x is less than y
 639    //!
 640    //! <b>Complexity</b>: Linear to the number of elements in the container.
 641    friend bool operator<(const set& x, const set& y);
 642
 643    //! <b>Effects</b>: Returns true if x is greater than y
 644    //!
 645    //! <b>Complexity</b>: Linear to the number of elements in the container.
 646    friend bool operator>(const set& x, const set& y);
 647
 648    //! <b>Effects</b>: Returns true if x is equal or less than y
 649    //!
 650    //! <b>Complexity</b>: Linear to the number of elements in the container.
 651    friend bool operator<=(const set& x, const set& y);
 652
 653    //! <b>Effects</b>: Returns true if x is equal or greater than y
 654    //!
 655    //! <b>Complexity</b>: Linear to the number of elements in the container.
 656    friend bool operator>=(const set& x, const set& y);
 657
 658    //! <b>Effects</b>: x.swap(y)
 659    //!
 660    //! <b>Complexity</b>: Constant.
 661    friend void swap(set& x, set& y);
 662
 663    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 664
 665    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 666    private:
 667    template <class KeyType>
 668    std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x)
 669    {  return this->base_t::insert_unique(::boost::forward<KeyType>(x));  }
 670
 671    template <class KeyType>
 672    iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
 673    {  return this->base_t::insert_unique(p, ::boost::forward<KeyType>(x)); }
 674    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 675 };
 676
 677 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 678
 679 }  //namespace container {
 680
 681 //!has_trivial_destructor_after_move<> == true_type
 682 //!specialization for optimizations
 683 template <class Key, class C, class SetOptions, class Allocator>
 684 struct has_trivial_destructor_after_move<boost::container::set<Key, C, Allocator, SetOptions> >
 685 {
 686    static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
 687 };
 688
 689 namespace container {
 690
 691 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 692
 693 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
 694
 695 //! A multiset is a kind of associative container that supports equivalent keys
 696 //! (possibly contains multiple copies of the same key value) and provides for
 697 //! fast retrieval of the keys themselves. Class multiset supports bidirectional iterators.
 698 //!
 699 //! A multiset satisfies all of the requirements of a container and of a reversible
 700 //! container, and of an associative container). multiset also provides most operations
 701 //! described for duplicate keys.
 702 //!
 703 //! \tparam Key is the type to be inserted in the set, which is also the key_type
 704 //! \tparam Compare is the comparison functor used to order keys
 705 //! \tparam Allocator is the allocator to be used to allocate memory for this container
 706 //! \tparam MultiSetOptions is an packed option type generated using using boost::container::tree_assoc_options.
 707 template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>, class MultiSetOptions = tree_assoc_defaults >
 708 #else
 709 template <class Key, class Compare, class Allocator, class MultiSetOptions>
 710 #endif
 711 class multiset
 712    /// @cond
 713    : public container_detail::tree
 714       <Key, Key,container_detail::identity<Key>, Compare, Allocator, MultiSetOptions>
 715    /// @endcond
 716 {
 717    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 718    private:
 719    BOOST_COPYABLE_AND_MOVABLE(multiset)
 720    typedef container_detail::tree
 721       <Key, Key,container_detail::identity<Key>, Compare, Allocator, MultiSetOptions> base_t;
 722    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 723
 724    public:
 725
 726    //////////////////////////////////////////////
 727    //
 728    //                    types
 729    //
 730    //////////////////////////////////////////////
 731    typedef Key                                                                         key_type;
 732    typedef Key                                                                         value_type;
 733    typedef Compare                                                                     key_compare;
 734    typedef Compare                                                                     value_compare;
 735    typedef ::boost::container::allocator_traits<Allocator>                             allocator_traits_type;
 736    typedef typename ::boost::container::allocator_traits<Allocator>::pointer           pointer;
 737    typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer     const_pointer;
 738    typedef typename ::boost::container::allocator_traits<Allocator>::reference         reference;
 739    typedef typename ::boost::container::allocator_traits<Allocator>::const_reference   const_reference;
 740    typedef typename ::boost::container::allocator_traits<Allocator>::size_type         size_type;
 741    typedef typename ::boost::container::allocator_traits<Allocator>::difference_type   difference_type;
 742    typedef Allocator                                                                   allocator_type;
 743    typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type)              stored_allocator_type;
 744    typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator)                           iterator;
 745    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator)                     const_iterator;
 746    typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator)                   reverse_iterator;
 747    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator)             const_reverse_iterator;
 748
 749    //////////////////////////////////////////////
 750    //
 751    //          construct/copy/destroy
 752    //
 753    //////////////////////////////////////////////
 754
 755    //! @copydoc ::boost::container::set::set()
 756    multiset()
 757       : base_t()
 758    {}
 759
 760    //! @copydoc ::boost::container::set::set(const Compare&, const allocator_type&)
 761    explicit multiset(const Compare& comp,
 762                      const allocator_type& a = allocator_type())
 763       : base_t(comp, a)
 764    {}
 765
 766    //! @copydoc ::boost::container::set::set(const allocator_type&)
 767    explicit multiset(const allocator_type& a)
 768       : base_t(a)
 769    {}
 770
 771    //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const Compare& comp, const allocator_type&)
 772    template <class InputIterator>
 773    multiset(InputIterator first, InputIterator last,
 774             const Compare& comp = Compare(),
 775             const allocator_type& a = allocator_type())
 776       : base_t(false, first, last, comp, a)
 777    {}
 778
 779    //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and
 780    //! allocator, and inserts elements from the ordered range [first ,last ). This function
 781    //! is more efficient than the normal range creation for ordered ranges.
 782    //!
 783    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
 784    //!
 785    //! <b>Complexity</b>: Linear in N.
 786    //!
 787    //! <b>Note</b>: Non-standard extension.
 788    template <class InputIterator>
 789    multiset( ordered_range_t, InputIterator first, InputIterator last
 790            , const Compare& comp = Compare()
 791            , const allocator_type& a = allocator_type())
 792       : base_t(ordered_range, first, last, comp, a)
 793    {}
 794
 795 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 796    //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
 797    multiset(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
 798       : base_t(false, il.begin(), il.end(), comp, a)
 799    {}
 800
 801    //! @copydoc ::boost::container::set::set(ordered_unique_range_t, std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
 802    multiset(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
 803       : base_t(ordered_range, il.begin(), il.end(), comp, a)
 804    {}
 805 #endif
 806
 807
 808    //! @copydoc ::boost::container::set::set(const set &)
 809    multiset(const multiset& x)
 810       : base_t(static_cast<const base_t&>(x))
 811    {}
 812
 813    //! @copydoc ::boost::container::set(set &&)
 814    multiset(BOOST_RV_REF(multiset) x)
 815       : base_t(boost::move(static_cast<base_t&>(x)))
 816    {}
 817
 818    //! @copydoc ::boost::container::set(const set &, const allocator_type &)
 819    multiset(const multiset& x, const allocator_type &a)
 820       : base_t(static_cast<const base_t&>(x), a)
 821    {}
 822
 823    //! @copydoc ::boost::container::set(set &&, const allocator_type &)
 824    multiset(BOOST_RV_REF(multiset) x, const allocator_type &a)
 825       : base_t(boost::move(static_cast<base_t&>(x)), a)
 826    {}
 827
 828    //! @copydoc ::boost::container::set::operator=(const set &)
 829    multiset& operator=(BOOST_COPY_ASSIGN_REF(multiset) x)
 830    {  return static_cast<multiset&>(this->base_t::operator=(static_cast<const base_t&>(x)));  }
 831
 832    //! @copydoc ::boost::container::set::operator=(set &&)
 833    multiset& operator=(BOOST_RV_REF(multiset) x)
 834    {  return static_cast<multiset&>(this->base_t::operator=(boost::move(static_cast<base_t&>(x))));  }
 835
 836 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 837    //! @copydoc ::boost::container::set::operator=(std::initializer_list<value_type>)
 838    multiset& operator=(std::initializer_list<value_type> il)
 839    {
 840        this->clear();
 841        insert(il.begin(), il.end());
 842        return *this;
 843    }
 844 #endif
 845    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 846
 847    //! @copydoc ::boost::container::set::get_allocator()
 848    allocator_type get_allocator() const;
 849
 850    //! @copydoc ::boost::container::set::get_stored_allocator()
 851    stored_allocator_type &get_stored_allocator();
 852
 853    //! @copydoc ::boost::container::set::get_stored_allocator() const
 854    const stored_allocator_type &get_stored_allocator() const;
 855
 856    //! @copydoc ::boost::container::set::begin()
 857    iterator begin();
 858
 859    //! @copydoc ::boost::container::set::begin() const
 860    const_iterator begin() const;
 861
 862    //! @copydoc ::boost::container::set::cbegin() const
 863    const_iterator cbegin() const;
 864
 865    //! @copydoc ::boost::container::set::end()
 866    iterator end() BOOST_CONTAINER_NOEXCEPT;
 867
 868    //! @copydoc ::boost::container::set::end() const
 869    const_iterator end() const BOOST_CONTAINER_NOEXCEPT;
 870
 871    //! @copydoc ::boost::container::set::cend() const
 872    const_iterator cend() const BOOST_CONTAINER_NOEXCEPT;
 873
 874    //! @copydoc ::boost::container::set::rbegin()
 875    reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT;
 876
 877    //! @copydoc ::boost::container::set::rbegin() const
 878    const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT;
 879
 880    //! @copydoc ::boost::container::set::crbegin() const
 881    const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT;
 882
 883    //! @copydoc ::boost::container::set::rend()
 884    reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT;
 885
 886    //! @copydoc ::boost::container::set::rend() const
 887    const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT;
 888
 889    //! @copydoc ::boost::container::set::crend() const
 890    const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT;
 891
 892    //! @copydoc ::boost::container::set::empty() const
 893    bool empty() const;
 894
 895    //! @copydoc ::boost::container::set::size() const
 896    size_type size() const;
 897
 898    //! @copydoc ::boost::container::set::max_size() const
 899    size_type max_size() const;
 900
 901    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 902
 903    #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 904
 905    //! <b>Effects</b>: Inserts an object of type Key constructed with
 906    //!   std::forward<Args>(args)... and returns the iterator pointing to the
 907    //!   newly inserted element.
 908    //!
 909    //! <b>Complexity</b>: Logarithmic.
 910    template <class... Args>
 911    iterator emplace(Args&&... args)
 912    {  return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
 913
 914    //! <b>Effects</b>: Inserts an object of type Key constructed with
 915    //!   std::forward<Args>(args)...
 916    //!
 917    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
 918    //!   to the key of x.
 919    //!
 920    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
 921    //!   is inserted right before p.
 922    template <class... Args>
 923    iterator emplace_hint(const_iterator p, Args&&... args)
 924    {  return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
 925
 926    #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
 927
 928    #define BOOST_PP_LOCAL_MACRO(n)                                                                 \
 929    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
 930    iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _))                            \
 931    {  return this->base_t::emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
 932                                                                                                    \
 933    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
 934    iterator emplace_hint(const_iterator p                                                          \
 935                          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _))              \
 936    {  return this->base_t::emplace_hint_equal(p                                                    \
 937                                BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));}   \
 938    //!
 939    #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
 940    #include BOOST_PP_LOCAL_ITERATE()
 941
 942    #endif   //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
 943
 944    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 945    //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
 946    //!   newly inserted element.
 947    //!
 948    //! <b>Complexity</b>: Logarithmic.
 949    iterator insert(const value_type &x);
 950
 951    //! <b>Effects</b>: Inserts a copy of x in the container.
 952    //!
 953    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
 954    //!   to the key of x.
 955    //!
 956    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
 957    //!   is inserted right before p.
 958    iterator insert(value_type &&x);
 959    #else
 960    BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert)
 961    #endif
 962
 963    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
 964    //! <b>Effects</b>: Inserts a copy of x in the container.
 965    //!   p is a hint pointing to where the insert should start to search.
 966    //!
 967    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
 968    //!   to the key of x.
 969    //!
 970    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
 971    //!   is inserted right before p.
 972    iterator insert(const_iterator p, const value_type &x);
 973
 974    //! <b>Effects</b>: Inserts a value move constructed from x in the container.
 975    //!   p is a hint pointing to where the insert should start to search.
 976    //!
 977    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
 978    //!   to the key of x.
 979    //!
 980    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
 981    //!   is inserted right before p.
 982    iterator insert(const_iterator p, value_type &&x);
 983    #else
 984    BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
 985    #endif
 986
 987    //! <b>Requires</b>: first, last are not iterators into *this.
 988    //!
 989    //! <b>Effects</b>: inserts each element from the range [first,last) .
 990    //!
 991    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
 992    template <class InputIterator>
 993    void insert(InputIterator first, InputIterator last)
 994    {  this->base_t::insert_equal(first, last);  }
 995
 996 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 997    //! @copydoc ::boost::container::set::insert(std::initializer_list<value_type>)
 998    void insert(std::initializer_list<value_type> il)
 999    {  this->base_t::insert_unique(il.begin(), il.end()); }
1000 #endif
1001
1002    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1003
1004    //! @copydoc ::boost::container::set::erase(const_iterator)
1005    iterator erase(const_iterator p);
1006
1007    //! @copydoc ::boost::container::set::erase(const key_type&)
1008    size_type erase(const key_type& x);
1009
1010    //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator)
1011    iterator erase(const_iterator first, const_iterator last);
1012
1013    //! @copydoc ::boost::container::set::swap
1014    void swap(flat_multiset& x);
1015
1016    //! @copydoc ::boost::container::set::clear
1017    void clear() BOOST_CONTAINER_NOEXCEPT;
1018
1019    //! @copydoc ::boost::container::set::key_comp
1020    key_compare key_comp() const;
1021
1022    //! @copydoc ::boost::container::set::value_comp
1023    value_compare value_comp() const;
1024
1025    //! @copydoc ::boost::container::set::find(const key_type& )
1026    iterator find(const key_type& x);
1027
1028    //! @copydoc ::boost::container::set::find(const key_type& ) const
1029    const_iterator find(const key_type& x) const;
1030
1031    //! @copydoc ::boost::container::set::count(const key_type& ) const
1032    size_type count(const key_type& x) const;
1033
1034    //! @copydoc ::boost::container::set::lower_bound(const key_type& )
1035    iterator lower_bound(const key_type& x);
1036
1037    //! @copydoc ::boost::container::set::lower_bound(const key_type& ) const
1038    const_iterator lower_bound(const key_type& x) const;
1039
1040    //! @copydoc ::boost::container::set::upper_bound(const key_type& )
1041    iterator upper_bound(const key_type& x);
1042
1043    //! @copydoc ::boost::container::set::upper_bound(const key_type& ) const
1044    const_iterator upper_bound(const key_type& x) const;
1045
1046    //! @copydoc ::boost::container::set::equal_range(const key_type& ) const
1047    std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1048
1049    //! @copydoc ::boost::container::set::equal_range(const key_type& )
1050    std::pair<iterator,iterator> equal_range(const key_type& x);
1051
1052    //! @copydoc ::boost::container::set::rebalance()
1053    void rebalance();
1054
1055    //! <b>Effects</b>: Returns true if x and y are equal
1056    //!
1057    //! <b>Complexity</b>: Linear to the number of elements in the container.
1058    friend bool operator==(const multiset& x, const multiset& y);
1059
1060    //! <b>Effects</b>: Returns true if x and y are unequal
1061    //!
1062    //! <b>Complexity</b>: Linear to the number of elements in the container.
1063    friend bool operator!=(const multiset& x, const multiset& y);
1064
1065    //! <b>Effects</b>: Returns true if x is less than y
1066    //!
1067    //! <b>Complexity</b>: Linear to the number of elements in the container.
1068    friend bool operator<(const multiset& x, const multiset& y);
1069
1070    //! <b>Effects</b>: Returns true if x is greater than y
1071    //!
1072    //! <b>Complexity</b>: Linear to the number of elements in the container.
1073    friend bool operator>(const multiset& x, const multiset& y);
1074
1075    //! <b>Effects</b>: Returns true if x is equal or less than y
1076    //!
1077    //! <b>Complexity</b>: Linear to the number of elements in the container.
1078    friend bool operator<=(const multiset& x, const multiset& y);
1079
1080    //! <b>Effects</b>: Returns true if x is equal or greater than y
1081    //!
1082    //! <b>Complexity</b>: Linear to the number of elements in the container.
1083    friend bool operator>=(const multiset& x, const multiset& y);
1084
1085    //! <b>Effects</b>: x.swap(y)
1086    //!
1087    //! <b>Complexity</b>: Constant.
1088    friend void swap(multiset& x, multiset& y);
1089
1090    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1091
1092    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1093    private:
1094    template <class KeyType>
1095    iterator priv_insert(BOOST_FWD_REF(KeyType) x)
1096    {  return this->base_t::insert_equal(::boost::forward<KeyType>(x));  }
1097
1098    template <class KeyType>
1099    iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
1100    {  return this->base_t::insert_equal(p, ::boost::forward<KeyType>(x)); }
1101
1102    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1103 };
1104
1105 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1106
1107 }  //namespace container {
1108
1109 //!has_trivial_destructor_after_move<> == true_type
1110 //!specialization for optimizations
1111 template <class Key, class C, class Allocator, class MultiSetOptions>
1112 struct has_trivial_destructor_after_move<boost::container::multiset<Key, C, Allocator, MultiSetOptions> >
1113 {
1114    static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
1115 };
1116
1117 namespace container {
1118
1119 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1120
1121 }}
1122
1123 #include <boost/container/detail/config_end.hpp>
1124
1125 #endif /* BOOST_CONTAINER_SET_HPP */
1126