contrib/libc++/include/set

   1 // -*- C++ -*-
   2 //===---------------------------- set -------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_SET
  12 #define _LIBCPP_SET
  13
  14 /*
  15
  16     set synopsis
  17
  18 namespace std
  19 {
  20
  21 template <class Key, class Compare = less<Key>,
  22           class Allocator = allocator<Key>>
  23 class set
  24 {
  25 public:
  26     // types:
  27     typedef Key                                      key_type;
  28     typedef key_type                                 value_type;
  29     typedef Compare                                  key_compare;
  30     typedef key_compare                              value_compare;
  31     typedef Allocator                                allocator_type;
  32     typedef typename allocator_type::reference       reference;
  33     typedef typename allocator_type::const_reference const_reference;
  34     typedef typename allocator_type::size_type       size_type;
  35     typedef typename allocator_type::difference_type difference_type;
  36     typedef typename allocator_type::pointer         pointer;
  37     typedef typename allocator_type::const_pointer   const_pointer;
  38
  39     typedef implementation-defined                   iterator;
  40     typedef implementation-defined                   const_iterator;
  41     typedef std::reverse_iterator<iterator>          reverse_iterator;
  42     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
  43
  44     // construct/copy/destroy:
  45     set()
  46         noexcept(
  47             is_nothrow_default_constructible<allocator_type>::value &&
  48             is_nothrow_default_constructible<key_compare>::value &&
  49             is_nothrow_copy_constructible<key_compare>::value);
  50     explicit set(const value_compare& comp);
  51     set(const value_compare& comp, const allocator_type& a);
  52     template <class InputIterator>
  53         set(InputIterator first, InputIterator last,
  54             const value_compare& comp = value_compare());
  55     template <class InputIterator>
  56         set(InputIterator first, InputIterator last, const value_compare& comp,
  57             const allocator_type& a);
  58     set(const set& s);
  59     set(set&& s)
  60         noexcept(
  61             is_nothrow_move_constructible<allocator_type>::value &&
  62             is_nothrow_move_constructible<key_compare>::value);
  63     explicit set(const allocator_type& a);
  64     set(const set& s, const allocator_type& a);
  65     set(set&& s, const allocator_type& a);
  66     set(initializer_list<value_type> il, const value_compare& comp = value_compare());
  67     set(initializer_list<value_type> il, const value_compare& comp,
  68         const allocator_type& a);
  69     ~set();
  70
  71     set& operator=(const set& s);
  72     set& operator=(set&& s)
  73         noexcept(
  74             allocator_type::propagate_on_container_move_assignment::value &&
  75             is_nothrow_move_assignable<allocator_type>::value &&
  76             is_nothrow_move_assignable<key_compare>::value);
  77     set& operator=(initializer_list<value_type> il);
  78
  79     // iterators:
  80           iterator begin() noexcept;
  81     const_iterator begin() const noexcept;
  82           iterator end() noexcept;
  83     const_iterator end()   const noexcept;
  84
  85           reverse_iterator rbegin() noexcept;
  86     const_reverse_iterator rbegin() const noexcept;
  87           reverse_iterator rend() noexcept;
  88     const_reverse_iterator rend()   const noexcept;
  89
  90     const_iterator         cbegin()  const noexcept;
  91     const_iterator         cend()    const noexcept;
  92     const_reverse_iterator crbegin() const noexcept;
  93     const_reverse_iterator crend()   const noexcept;
  94
  95     // capacity:
  96     bool      empty()    const noexcept;
  97     size_type size()     const noexcept;
  98     size_type max_size() const noexcept;
  99
 100     // modifiers:
 101     template <class... Args>
 102         pair<iterator, bool> emplace(Args&&... args);
 103     template <class... Args>
 104         iterator emplace_hint(const_iterator position, Args&&... args);
 105     pair<iterator,bool> insert(const value_type& v);
 106     pair<iterator,bool> insert(value_type&& v);
 107     iterator insert(const_iterator position, const value_type& v);
 108     iterator insert(const_iterator position, value_type&& v);
 109     template <class InputIterator>
 110         void insert(InputIterator first, InputIterator last);
 111     void insert(initializer_list<value_type> il);
 112
 113     iterator  erase(const_iterator position);
 114     size_type erase(const key_type& k);
 115     iterator  erase(const_iterator first, const_iterator last);
 116     void clear() noexcept;
 117
 118     void swap(set& s)
 119         noexcept(
 120             __is_nothrow_swappable<key_compare>::value &&
 121             (!allocator_type::propagate_on_container_swap::value ||
 122              __is_nothrow_swappable<allocator_type>::value));
 123
 124     // observers:
 125     allocator_type get_allocator() const noexcept;
 126     key_compare    key_comp()      const;
 127     value_compare  value_comp()    const;
 128
 129     // set operations:
 130           iterator find(const key_type& k);
 131     const_iterator find(const key_type& k) const;
 132     size_type      count(const key_type& k) const;
 133           iterator lower_bound(const key_type& k);
 134     const_iterator lower_bound(const key_type& k) const;
 135           iterator upper_bound(const key_type& k);
 136     const_iterator upper_bound(const key_type& k) const;
 137     pair<iterator,iterator>             equal_range(const key_type& k);
 138     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
 139 };
 140
 141 template <class Key, class Compare, class Allocator>
 142 bool
 143 operator==(const set<Key, Compare, Allocator>& x,
 144            const set<Key, Compare, Allocator>& y);
 145
 146 template <class Key, class Compare, class Allocator>
 147 bool
 148 operator< (const set<Key, Compare, Allocator>& x,
 149            const set<Key, Compare, Allocator>& y);
 150
 151 template <class Key, class Compare, class Allocator>
 152 bool
 153 operator!=(const set<Key, Compare, Allocator>& x,
 154            const set<Key, Compare, Allocator>& y);
 155
 156 template <class Key, class Compare, class Allocator>
 157 bool
 158 operator> (const set<Key, Compare, Allocator>& x,
 159            const set<Key, Compare, Allocator>& y);
 160
 161 template <class Key, class Compare, class Allocator>
 162 bool
 163 operator>=(const set<Key, Compare, Allocator>& x,
 164            const set<Key, Compare, Allocator>& y);
 165
 166 template <class Key, class Compare, class Allocator>
 167 bool
 168 operator<=(const set<Key, Compare, Allocator>& x,
 169            const set<Key, Compare, Allocator>& y);
 170
 171 // specialized algorithms:
 172 template <class Key, class Compare, class Allocator>
 173 void
 174 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
 175     noexcept(noexcept(x.swap(y)));
 176
 177 template <class Key, class Compare = less<Key>,
 178           class Allocator = allocator<Key>>
 179 class multiset
 180 {
 181 public:
 182     // types:
 183     typedef Key                                      key_type;
 184     typedef key_type                                 value_type;
 185     typedef Compare                                  key_compare;
 186     typedef key_compare                              value_compare;
 187     typedef Allocator                                allocator_type;
 188     typedef typename allocator_type::reference       reference;
 189     typedef typename allocator_type::const_reference const_reference;
 190     typedef typename allocator_type::size_type       size_type;
 191     typedef typename allocator_type::difference_type difference_type;
 192     typedef typename allocator_type::pointer         pointer;
 193     typedef typename allocator_type::const_pointer   const_pointer;
 194
 195     typedef implementation-defined                   iterator;
 196     typedef implementation-defined                   const_iterator;
 197     typedef std::reverse_iterator<iterator>          reverse_iterator;
 198     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
 199
 200     // construct/copy/destroy:
 201     multiset()
 202         noexcept(
 203             is_nothrow_default_constructible<allocator_type>::value &&
 204             is_nothrow_default_constructible<key_compare>::value &&
 205             is_nothrow_copy_constructible<key_compare>::value);
 206     explicit multiset(const value_compare& comp);
 207     multiset(const value_compare& comp, const allocator_type& a);
 208     template <class InputIterator>
 209         multiset(InputIterator first, InputIterator last,
 210                  const value_compare& comp = value_compare());
 211     template <class InputIterator>
 212         multiset(InputIterator first, InputIterator last,
 213                  const value_compare& comp, const allocator_type& a);
 214     multiset(const multiset& s);
 215     multiset(multiset&& s)
 216         noexcept(
 217             is_nothrow_move_constructible<allocator_type>::value &&
 218             is_nothrow_move_constructible<key_compare>::value);
 219     explicit multiset(const allocator_type& a);
 220     multiset(const multiset& s, const allocator_type& a);
 221     multiset(multiset&& s, const allocator_type& a);
 222     multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
 223     multiset(initializer_list<value_type> il, const value_compare& comp,
 224              const allocator_type& a);
 225     ~multiset();
 226
 227     multiset& operator=(const multiset& s);
 228     multiset& operator=(multiset&& s)
 229         noexcept(
 230             allocator_type::propagate_on_container_move_assignment::value &&
 231             is_nothrow_move_assignable<allocator_type>::value &&
 232             is_nothrow_move_assignable<key_compare>::value);
 233     multiset& operator=(initializer_list<value_type> il);
 234
 235     // iterators:
 236           iterator begin() noexcept;
 237     const_iterator begin() const noexcept;
 238           iterator end() noexcept;
 239     const_iterator end()   const noexcept;
 240
 241           reverse_iterator rbegin() noexcept;
 242     const_reverse_iterator rbegin() const noexcept;
 243           reverse_iterator rend() noexcept;
 244     const_reverse_iterator rend()   const noexcept;
 245
 246     const_iterator         cbegin()  const noexcept;
 247     const_iterator         cend()    const noexcept;
 248     const_reverse_iterator crbegin() const noexcept;
 249     const_reverse_iterator crend()   const noexcept;
 250
 251     // capacity:
 252     bool      empty()    const noexcept;
 253     size_type size()     const noexcept;
 254     size_type max_size() const noexcept;
 255
 256     // modifiers:
 257     template <class... Args>
 258         iterator emplace(Args&&... args);
 259     template <class... Args>
 260         iterator emplace_hint(const_iterator position, Args&&... args);
 261     iterator insert(const value_type& v);
 262     iterator insert(value_type&& v);
 263     iterator insert(const_iterator position, const value_type& v);
 264     iterator insert(const_iterator position, value_type&& v);
 265     template <class InputIterator>
 266         void insert(InputIterator first, InputIterator last);
 267     void insert(initializer_list<value_type> il);
 268
 269     iterator  erase(const_iterator position);
 270     size_type erase(const key_type& k);
 271     iterator  erase(const_iterator first, const_iterator last);
 272     void clear() noexcept;
 273
 274     void swap(multiset& s)
 275         noexcept(
 276             __is_nothrow_swappable<key_compare>::value &&
 277             (!allocator_type::propagate_on_container_swap::value ||
 278              __is_nothrow_swappable<allocator_type>::value));
 279
 280     // observers:
 281     allocator_type get_allocator() const noexcept;
 282     key_compare    key_comp()      const;
 283     value_compare  value_comp()    const;
 284
 285     // set operations:
 286           iterator find(const key_type& k);
 287     const_iterator find(const key_type& k) const;
 288     size_type      count(const key_type& k) const;
 289           iterator lower_bound(const key_type& k);
 290     const_iterator lower_bound(const key_type& k) const;
 291           iterator upper_bound(const key_type& k);
 292     const_iterator upper_bound(const key_type& k) const;
 293     pair<iterator,iterator>             equal_range(const key_type& k);
 294     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
 295 };
 296
 297 template <class Key, class Compare, class Allocator>
 298 bool
 299 operator==(const multiset<Key, Compare, Allocator>& x,
 300            const multiset<Key, Compare, Allocator>& y);
 301
 302 template <class Key, class Compare, class Allocator>
 303 bool
 304 operator< (const multiset<Key, Compare, Allocator>& x,
 305            const multiset<Key, Compare, Allocator>& y);
 306
 307 template <class Key, class Compare, class Allocator>
 308 bool
 309 operator!=(const multiset<Key, Compare, Allocator>& x,
 310            const multiset<Key, Compare, Allocator>& y);
 311
 312 template <class Key, class Compare, class Allocator>
 313 bool
 314 operator> (const multiset<Key, Compare, Allocator>& x,
 315            const multiset<Key, Compare, Allocator>& y);
 316
 317 template <class Key, class Compare, class Allocator>
 318 bool
 319 operator>=(const multiset<Key, Compare, Allocator>& x,
 320            const multiset<Key, Compare, Allocator>& y);
 321
 322 template <class Key, class Compare, class Allocator>
 323 bool
 324 operator<=(const multiset<Key, Compare, Allocator>& x,
 325            const multiset<Key, Compare, Allocator>& y);
 326
 327 // specialized algorithms:
 328 template <class Key, class Compare, class Allocator>
 329 void
 330 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
 331     noexcept(noexcept(x.swap(y)));
 332
 333 }  // std
 334
 335 */
 336
 337 #include <__config>
 338 #include <__tree>
 339 #include <functional>
 340
 341 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 342 #pragma GCC system_header
 343 #endif
 344
 345 _LIBCPP_BEGIN_NAMESPACE_STD
 346
 347 template <class _Key, class _Compare = less<_Key>,
 348           class _Allocator = allocator<_Key> >
 349 class _LIBCPP_TYPE_VIS set
 350 {
 351 public:
 352     // types:
 353     typedef _Key                                     key_type;
 354     typedef key_type                                 value_type;
 355     typedef _Compare                                 key_compare;
 356     typedef key_compare                              value_compare;
 357     typedef _Allocator                               allocator_type;
 358     typedef value_type&                              reference;
 359     typedef const value_type&                        const_reference;
 360
 361 private:
 362     typedef __tree<value_type, value_compare, allocator_type> __base;
 363     typedef allocator_traits<allocator_type>                  __alloc_traits;
 364     typedef typename __base::__node_holder                    __node_holder;
 365
 366     __base __tree_;
 367
 368 public:
 369     typedef typename __base::pointer               pointer;
 370     typedef typename __base::const_pointer         const_pointer;
 371     typedef typename __base::size_type             size_type;
 372     typedef typename __base::difference_type       difference_type;
 373     typedef typename __base::const_iterator        iterator;
 374     typedef typename __base::const_iterator        const_iterator;
 375     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
 376     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 377
 378     _LIBCPP_INLINE_VISIBILITY
 379     explicit set(const value_compare& __comp = value_compare())
 380         _NOEXCEPT_(
 381             is_nothrow_default_constructible<allocator_type>::value &&
 382             is_nothrow_default_constructible<key_compare>::value &&
 383             is_nothrow_copy_constructible<key_compare>::value)
 384         : __tree_(__comp) {}
 385     _LIBCPP_INLINE_VISIBILITY
 386     set(const value_compare& __comp, const allocator_type& __a)
 387         : __tree_(__comp, __a) {}
 388     template <class _InputIterator>
 389         _LIBCPP_INLINE_VISIBILITY
 390         set(_InputIterator __f, _InputIterator __l,
 391             const value_compare& __comp = value_compare())
 392         : __tree_(__comp)
 393         {
 394             insert(__f, __l);
 395         }
 396
 397     template <class _InputIterator>
 398         _LIBCPP_INLINE_VISIBILITY
 399         set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
 400             const allocator_type& __a)
 401         : __tree_(__comp, __a)
 402         {
 403             insert(__f, __l);
 404         }
 405
 406     _LIBCPP_INLINE_VISIBILITY
 407     set(const set& __s)
 408         : __tree_(__s.__tree_)
 409         {
 410             insert(__s.begin(), __s.end());
 411         }
 412
 413     _LIBCPP_INLINE_VISIBILITY
 414     set& operator=(const set& __s)
 415         {
 416             __tree_ = __s.__tree_;
 417             return *this;
 418         }
 419
 420 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 421     _LIBCPP_INLINE_VISIBILITY
 422     set(set&& __s)
 423         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
 424         : __tree_(_VSTD::move(__s.__tree_)) {}
 425 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 426
 427     _LIBCPP_INLINE_VISIBILITY
 428     explicit set(const allocator_type& __a)
 429         : __tree_(__a) {}
 430
 431     _LIBCPP_INLINE_VISIBILITY
 432     set(const set& __s, const allocator_type& __a)
 433         : __tree_(__s.__tree_.value_comp(), __a)
 434         {
 435             insert(__s.begin(), __s.end());
 436         }
 437
 438 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 439     set(set&& __s, const allocator_type& __a);
 440 #endif
 441
 442 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 443     _LIBCPP_INLINE_VISIBILITY
 444     set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
 445         : __tree_(__comp)
 446         {
 447             insert(__il.begin(), __il.end());
 448         }
 449
 450     _LIBCPP_INLINE_VISIBILITY
 451     set(initializer_list<value_type> __il, const value_compare& __comp,
 452         const allocator_type& __a)
 453         : __tree_(__comp, __a)
 454         {
 455             insert(__il.begin(), __il.end());
 456         }
 457
 458     _LIBCPP_INLINE_VISIBILITY
 459     set& operator=(initializer_list<value_type> __il)
 460         {
 461             __tree_.__assign_unique(__il.begin(), __il.end());
 462             return *this;
 463         }
 464 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 465
 466 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 467     _LIBCPP_INLINE_VISIBILITY
 468     set& operator=(set&& __s)
 469         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
 470         {
 471             __tree_ = _VSTD::move(__s.__tree_);
 472             return *this;
 473         }
 474 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 475
 476     _LIBCPP_INLINE_VISIBILITY
 477           iterator begin() _NOEXCEPT       {return __tree_.begin();}
 478     _LIBCPP_INLINE_VISIBILITY
 479     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
 480     _LIBCPP_INLINE_VISIBILITY
 481           iterator end() _NOEXCEPT         {return __tree_.end();}
 482     _LIBCPP_INLINE_VISIBILITY
 483     const_iterator end()   const _NOEXCEPT {return __tree_.end();}
 484
 485     _LIBCPP_INLINE_VISIBILITY
 486           reverse_iterator rbegin() _NOEXCEPT
 487             {return reverse_iterator(end());}
 488     _LIBCPP_INLINE_VISIBILITY
 489     const_reverse_iterator rbegin() const _NOEXCEPT
 490         {return const_reverse_iterator(end());}
 491     _LIBCPP_INLINE_VISIBILITY
 492           reverse_iterator rend() _NOEXCEPT
 493             {return reverse_iterator(begin());}
 494     _LIBCPP_INLINE_VISIBILITY
 495     const_reverse_iterator rend() const _NOEXCEPT
 496         {return const_reverse_iterator(begin());}
 497
 498     _LIBCPP_INLINE_VISIBILITY
 499     const_iterator cbegin()  const _NOEXCEPT {return begin();}
 500     _LIBCPP_INLINE_VISIBILITY
 501     const_iterator cend() const _NOEXCEPT {return end();}
 502     _LIBCPP_INLINE_VISIBILITY
 503     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
 504     _LIBCPP_INLINE_VISIBILITY
 505     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
 506
 507     _LIBCPP_INLINE_VISIBILITY
 508     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
 509     _LIBCPP_INLINE_VISIBILITY
 510     size_type size() const _NOEXCEPT {return __tree_.size();}
 511     _LIBCPP_INLINE_VISIBILITY
 512     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
 513
 514     // modifiers:
 515 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 516     template <class... _Args>
 517         _LIBCPP_INLINE_VISIBILITY
 518         pair<iterator, bool> emplace(_Args&&... __args)
 519             {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 520     template <class... _Args>
 521         _LIBCPP_INLINE_VISIBILITY
 522         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 523             {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
 524 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 525     _LIBCPP_INLINE_VISIBILITY
 526     pair<iterator,bool> insert(const value_type& __v)
 527         {return __tree_.__insert_unique(__v);}
 528 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 529     _LIBCPP_INLINE_VISIBILITY
 530     pair<iterator,bool> insert(value_type&& __v)
 531         {return __tree_.__insert_unique(_VSTD::move(__v));}
 532 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 533     _LIBCPP_INLINE_VISIBILITY
 534     iterator insert(const_iterator __p, const value_type& __v)
 535         {return __tree_.__insert_unique(__p, __v);}
 536 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 537     _LIBCPP_INLINE_VISIBILITY
 538     iterator insert(const_iterator __p, value_type&& __v)
 539         {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
 540 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 541     template <class _InputIterator>
 542         _LIBCPP_INLINE_VISIBILITY
 543         void insert(_InputIterator __f, _InputIterator __l)
 544         {
 545             for (const_iterator __e = cend(); __f != __l; ++__f)
 546                 __tree_.__insert_unique(__e, *__f);
 547         }
 548
 549 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 550     _LIBCPP_INLINE_VISIBILITY
 551     void insert(initializer_list<value_type> __il)
 552         {insert(__il.begin(), __il.end());}
 553 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 554
 555     _LIBCPP_INLINE_VISIBILITY
 556     iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
 557     _LIBCPP_INLINE_VISIBILITY
 558     size_type erase(const key_type& __k)
 559         {return __tree_.__erase_unique(__k);}
 560     _LIBCPP_INLINE_VISIBILITY
 561     iterator  erase(const_iterator __f, const_iterator __l)
 562         {return __tree_.erase(__f, __l);}
 563     _LIBCPP_INLINE_VISIBILITY
 564     void clear() _NOEXCEPT {__tree_.clear();}
 565
 566     _LIBCPP_INLINE_VISIBILITY
 567     void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
 568         {__tree_.swap(__s.__tree_);}
 569
 570     _LIBCPP_INLINE_VISIBILITY
 571     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
 572     _LIBCPP_INLINE_VISIBILITY
 573     key_compare    key_comp()      const {return __tree_.value_comp();}
 574     _LIBCPP_INLINE_VISIBILITY
 575     value_compare  value_comp()    const {return __tree_.value_comp();}
 576
 577     // set operations:
 578     _LIBCPP_INLINE_VISIBILITY
 579     iterator find(const key_type& __k)             {return __tree_.find(__k);}
 580     _LIBCPP_INLINE_VISIBILITY
 581     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
 582     _LIBCPP_INLINE_VISIBILITY
 583     size_type      count(const key_type& __k) const
 584         {return __tree_.__count_unique(__k);}
 585     _LIBCPP_INLINE_VISIBILITY
 586     iterator lower_bound(const key_type& __k)
 587         {return __tree_.lower_bound(__k);}
 588     _LIBCPP_INLINE_VISIBILITY
 589     const_iterator lower_bound(const key_type& __k) const
 590         {return __tree_.lower_bound(__k);}
 591     _LIBCPP_INLINE_VISIBILITY
 592     iterator upper_bound(const key_type& __k)
 593         {return __tree_.upper_bound(__k);}
 594     _LIBCPP_INLINE_VISIBILITY
 595     const_iterator upper_bound(const key_type& __k) const
 596         {return __tree_.upper_bound(__k);}
 597     _LIBCPP_INLINE_VISIBILITY
 598     pair<iterator,iterator> equal_range(const key_type& __k)
 599         {return __tree_.__equal_range_unique(__k);}
 600     _LIBCPP_INLINE_VISIBILITY
 601     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
 602         {return __tree_.__equal_range_unique(__k);}
 603 };
 604
 605 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 606
 607 template <class _Key, class _Compare, class _Allocator>
 608 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
 609     : __tree_(_VSTD::move(__s.__tree_), __a)
 610 {
 611     if (__a != __s.get_allocator())
 612     {
 613         const_iterator __e = cend();
 614         while (!__s.empty())
 615             insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
 616     }
 617 }
 618
 619 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 620
 621 template <class _Key, class _Compare, class _Allocator>
 622 inline _LIBCPP_INLINE_VISIBILITY
 623 bool
 624 operator==(const set<_Key, _Compare, _Allocator>& __x,
 625            const set<_Key, _Compare, _Allocator>& __y)
 626 {
 627     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
 628 }
 629
 630 template <class _Key, class _Compare, class _Allocator>
 631 inline _LIBCPP_INLINE_VISIBILITY
 632 bool
 633 operator< (const set<_Key, _Compare, _Allocator>& __x,
 634            const set<_Key, _Compare, _Allocator>& __y)
 635 {
 636     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 637 }
 638
 639 template <class _Key, class _Compare, class _Allocator>
 640 inline _LIBCPP_INLINE_VISIBILITY
 641 bool
 642 operator!=(const set<_Key, _Compare, _Allocator>& __x,
 643            const set<_Key, _Compare, _Allocator>& __y)
 644 {
 645     return !(__x == __y);
 646 }
 647
 648 template <class _Key, class _Compare, class _Allocator>
 649 inline _LIBCPP_INLINE_VISIBILITY
 650 bool
 651 operator> (const set<_Key, _Compare, _Allocator>& __x,
 652            const set<_Key, _Compare, _Allocator>& __y)
 653 {
 654     return __y < __x;
 655 }
 656
 657 template <class _Key, class _Compare, class _Allocator>
 658 inline _LIBCPP_INLINE_VISIBILITY
 659 bool
 660 operator>=(const set<_Key, _Compare, _Allocator>& __x,
 661            const set<_Key, _Compare, _Allocator>& __y)
 662 {
 663     return !(__x < __y);
 664 }
 665
 666 template <class _Key, class _Compare, class _Allocator>
 667 inline _LIBCPP_INLINE_VISIBILITY
 668 bool
 669 operator<=(const set<_Key, _Compare, _Allocator>& __x,
 670            const set<_Key, _Compare, _Allocator>& __y)
 671 {
 672     return !(__y < __x);
 673 }
 674
 675 // specialized algorithms:
 676 template <class _Key, class _Compare, class _Allocator>
 677 inline _LIBCPP_INLINE_VISIBILITY
 678 void
 679 swap(set<_Key, _Compare, _Allocator>& __x,
 680      set<_Key, _Compare, _Allocator>& __y)
 681     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 682 {
 683     __x.swap(__y);
 684 }
 685
 686 template <class _Key, class _Compare = less<_Key>,
 687           class _Allocator = allocator<_Key> >
 688 class _LIBCPP_TYPE_VIS multiset
 689 {
 690 public:
 691     // types:
 692     typedef _Key                                      key_type;
 693     typedef key_type                                 value_type;
 694     typedef _Compare                                  key_compare;
 695     typedef key_compare                              value_compare;
 696     typedef _Allocator                                allocator_type;
 697     typedef value_type&                              reference;
 698     typedef const value_type&                        const_reference;
 699
 700 private:
 701     typedef __tree<value_type, value_compare, allocator_type> __base;
 702     typedef allocator_traits<allocator_type>                  __alloc_traits;
 703     typedef typename __base::__node_holder                    __node_holder;
 704
 705     __base __tree_;
 706
 707 public:
 708     typedef typename __base::pointer               pointer;
 709     typedef typename __base::const_pointer         const_pointer;
 710     typedef typename __base::size_type             size_type;
 711     typedef typename __base::difference_type       difference_type;
 712     typedef typename __base::const_iterator        iterator;
 713     typedef typename __base::const_iterator        const_iterator;
 714     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
 715     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 716
 717     // construct/copy/destroy:
 718     _LIBCPP_INLINE_VISIBILITY
 719     explicit multiset(const value_compare& __comp = value_compare())
 720         _NOEXCEPT_(
 721             is_nothrow_default_constructible<allocator_type>::value &&
 722             is_nothrow_default_constructible<key_compare>::value &&
 723             is_nothrow_copy_constructible<key_compare>::value)
 724         : __tree_(__comp) {}
 725     _LIBCPP_INLINE_VISIBILITY
 726     multiset(const value_compare& __comp, const allocator_type& __a)
 727         : __tree_(__comp, __a) {}
 728     template <class _InputIterator>
 729         _LIBCPP_INLINE_VISIBILITY
 730         multiset(_InputIterator __f, _InputIterator __l,
 731                  const value_compare& __comp = value_compare())
 732         : __tree_(__comp)
 733         {
 734             insert(__f, __l);
 735         }
 736
 737     template <class _InputIterator>
 738         _LIBCPP_INLINE_VISIBILITY
 739         multiset(_InputIterator __f, _InputIterator __l,
 740                  const value_compare& __comp, const allocator_type& __a)
 741         : __tree_(__comp, __a)
 742         {
 743             insert(__f, __l);
 744         }
 745
 746     _LIBCPP_INLINE_VISIBILITY
 747     multiset(const multiset& __s)
 748         : __tree_(__s.__tree_.value_comp(),
 749           __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
 750         {
 751             insert(__s.begin(), __s.end());
 752         }
 753
 754     _LIBCPP_INLINE_VISIBILITY
 755     multiset& operator=(const multiset& __s)
 756         {
 757             __tree_ = __s.__tree_;
 758             return *this;
 759         }
 760
 761 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 762     _LIBCPP_INLINE_VISIBILITY
 763     multiset(multiset&& __s)
 764         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
 765         : __tree_(_VSTD::move(__s.__tree_)) {}
 766 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 767     _LIBCPP_INLINE_VISIBILITY
 768     explicit multiset(const allocator_type& __a)
 769         : __tree_(__a) {}
 770     _LIBCPP_INLINE_VISIBILITY
 771     multiset(const multiset& __s, const allocator_type& __a)
 772         : __tree_(__s.__tree_.value_comp(), __a)
 773         {
 774             insert(__s.begin(), __s.end());
 775         }
 776 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 777     multiset(multiset&& __s, const allocator_type& __a);
 778 #endif
 779
 780 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 781     _LIBCPP_INLINE_VISIBILITY
 782     multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
 783         : __tree_(__comp)
 784         {
 785             insert(__il.begin(), __il.end());
 786         }
 787
 788     _LIBCPP_INLINE_VISIBILITY
 789     multiset(initializer_list<value_type> __il, const value_compare& __comp,
 790         const allocator_type& __a)
 791         : __tree_(__comp, __a)
 792         {
 793             insert(__il.begin(), __il.end());
 794         }
 795
 796     _LIBCPP_INLINE_VISIBILITY
 797     multiset& operator=(initializer_list<value_type> __il)
 798         {
 799             __tree_.__assign_multi(__il.begin(), __il.end());
 800             return *this;
 801         }
 802 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 803
 804 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 805     _LIBCPP_INLINE_VISIBILITY
 806     multiset& operator=(multiset&& __s)
 807         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
 808         {
 809             __tree_ = _VSTD::move(__s.__tree_);
 810             return *this;
 811         }
 812 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 813
 814     _LIBCPP_INLINE_VISIBILITY
 815           iterator begin() _NOEXCEPT       {return __tree_.begin();}
 816     _LIBCPP_INLINE_VISIBILITY
 817     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
 818     _LIBCPP_INLINE_VISIBILITY
 819           iterator end() _NOEXCEPT         {return __tree_.end();}
 820     _LIBCPP_INLINE_VISIBILITY
 821     const_iterator end()   const _NOEXCEPT {return __tree_.end();}
 822
 823     _LIBCPP_INLINE_VISIBILITY
 824           reverse_iterator rbegin() _NOEXCEPT
 825             {return reverse_iterator(end());}
 826     _LIBCPP_INLINE_VISIBILITY
 827     const_reverse_iterator rbegin() const _NOEXCEPT
 828         {return const_reverse_iterator(end());}
 829     _LIBCPP_INLINE_VISIBILITY
 830           reverse_iterator rend() _NOEXCEPT
 831             {return       reverse_iterator(begin());}
 832     _LIBCPP_INLINE_VISIBILITY
 833     const_reverse_iterator rend() const _NOEXCEPT
 834         {return const_reverse_iterator(begin());}
 835
 836     _LIBCPP_INLINE_VISIBILITY
 837     const_iterator cbegin()  const _NOEXCEPT {return begin();}
 838     _LIBCPP_INLINE_VISIBILITY
 839     const_iterator cend() const _NOEXCEPT {return end();}
 840     _LIBCPP_INLINE_VISIBILITY
 841     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
 842     _LIBCPP_INLINE_VISIBILITY
 843     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
 844
 845     _LIBCPP_INLINE_VISIBILITY
 846     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
 847     _LIBCPP_INLINE_VISIBILITY
 848     size_type size() const _NOEXCEPT {return __tree_.size();}
 849     _LIBCPP_INLINE_VISIBILITY
 850     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
 851
 852     // modifiers:
 853 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 854     template <class... _Args>
 855         _LIBCPP_INLINE_VISIBILITY
 856         iterator emplace(_Args&&... __args)
 857             {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
 858     template <class... _Args>
 859         _LIBCPP_INLINE_VISIBILITY
 860         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 861             {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
 862 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 863     _LIBCPP_INLINE_VISIBILITY
 864     iterator insert(const value_type& __v)
 865         {return __tree_.__insert_multi(__v);}
 866 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 867     _LIBCPP_INLINE_VISIBILITY
 868     iterator insert(value_type&& __v)
 869         {return __tree_.__insert_multi(_VSTD::move(__v));}
 870 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 871     _LIBCPP_INLINE_VISIBILITY
 872     iterator insert(const_iterator __p, const value_type& __v)
 873         {return __tree_.__insert_multi(__p, __v);}
 874 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 875     _LIBCPP_INLINE_VISIBILITY
 876     iterator insert(const_iterator __p, value_type&& __v)
 877         {return __tree_.__insert_multi(_VSTD::move(__v));}
 878 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 879     template <class _InputIterator>
 880         _LIBCPP_INLINE_VISIBILITY
 881         void insert(_InputIterator __f, _InputIterator __l)
 882         {
 883             for (const_iterator __e = cend(); __f != __l; ++__f)
 884                 __tree_.__insert_multi(__e, *__f);
 885         }
 886
 887 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 888     _LIBCPP_INLINE_VISIBILITY
 889     void insert(initializer_list<value_type> __il)
 890         {insert(__il.begin(), __il.end());}
 891 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 892
 893     _LIBCPP_INLINE_VISIBILITY
 894     iterator  erase(const_iterator __p) {return __tree_.erase(__p);}
 895     _LIBCPP_INLINE_VISIBILITY
 896     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
 897     _LIBCPP_INLINE_VISIBILITY
 898     iterator  erase(const_iterator __f, const_iterator __l)
 899         {return __tree_.erase(__f, __l);}
 900     _LIBCPP_INLINE_VISIBILITY
 901     void clear() _NOEXCEPT {__tree_.clear();}
 902
 903     _LIBCPP_INLINE_VISIBILITY
 904     void swap(multiset& __s)
 905         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
 906         {__tree_.swap(__s.__tree_);}
 907
 908     _LIBCPP_INLINE_VISIBILITY
 909     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
 910     _LIBCPP_INLINE_VISIBILITY
 911     key_compare    key_comp()      const {return __tree_.value_comp();}
 912     _LIBCPP_INLINE_VISIBILITY
 913     value_compare  value_comp()    const {return __tree_.value_comp();}
 914
 915     // set operations:
 916     _LIBCPP_INLINE_VISIBILITY
 917     iterator find(const key_type& __k)             {return __tree_.find(__k);}
 918     _LIBCPP_INLINE_VISIBILITY
 919     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
 920     _LIBCPP_INLINE_VISIBILITY
 921     size_type      count(const key_type& __k) const
 922         {return __tree_.__count_multi(__k);}
 923     _LIBCPP_INLINE_VISIBILITY
 924     iterator lower_bound(const key_type& __k)
 925         {return __tree_.lower_bound(__k);}
 926     _LIBCPP_INLINE_VISIBILITY
 927     const_iterator lower_bound(const key_type& __k) const
 928             {return __tree_.lower_bound(__k);}
 929     _LIBCPP_INLINE_VISIBILITY
 930     iterator upper_bound(const key_type& __k)
 931             {return __tree_.upper_bound(__k);}
 932     _LIBCPP_INLINE_VISIBILITY
 933     const_iterator upper_bound(const key_type& __k) const
 934             {return __tree_.upper_bound(__k);}
 935     _LIBCPP_INLINE_VISIBILITY
 936     pair<iterator,iterator>             equal_range(const key_type& __k)
 937             {return __tree_.__equal_range_multi(__k);}
 938     _LIBCPP_INLINE_VISIBILITY
 939     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
 940             {return __tree_.__equal_range_multi(__k);}
 941 };
 942
 943 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 944
 945 template <class _Key, class _Compare, class _Allocator>
 946 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
 947     : __tree_(_VSTD::move(__s.__tree_), __a)
 948 {
 949     if (__a != __s.get_allocator())
 950     {
 951         const_iterator __e = cend();
 952         while (!__s.empty())
 953             insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
 954     }
 955 }
 956
 957 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 958
 959 template <class _Key, class _Compare, class _Allocator>
 960 inline _LIBCPP_INLINE_VISIBILITY
 961 bool
 962 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
 963            const multiset<_Key, _Compare, _Allocator>& __y)
 964 {
 965     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
 966 }
 967
 968 template <class _Key, class _Compare, class _Allocator>
 969 inline _LIBCPP_INLINE_VISIBILITY
 970 bool
 971 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
 972            const multiset<_Key, _Compare, _Allocator>& __y)
 973 {
 974     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 975 }
 976
 977 template <class _Key, class _Compare, class _Allocator>
 978 inline _LIBCPP_INLINE_VISIBILITY
 979 bool
 980 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
 981            const multiset<_Key, _Compare, _Allocator>& __y)
 982 {
 983     return !(__x == __y);
 984 }
 985
 986 template <class _Key, class _Compare, class _Allocator>
 987 inline _LIBCPP_INLINE_VISIBILITY
 988 bool
 989 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
 990            const multiset<_Key, _Compare, _Allocator>& __y)
 991 {
 992     return __y < __x;
 993 }
 994
 995 template <class _Key, class _Compare, class _Allocator>
 996 inline _LIBCPP_INLINE_VISIBILITY
 997 bool
 998 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
 999            const multiset<_Key, _Compare, _Allocator>& __y)
1000 {
1001     return !(__x < __y);
1002 }
1003
1004 template <class _Key, class _Compare, class _Allocator>
1005 inline _LIBCPP_INLINE_VISIBILITY
1006 bool
1007 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1008            const multiset<_Key, _Compare, _Allocator>& __y)
1009 {
1010     return !(__y < __x);
1011 }
1012
1013 template <class _Key, class _Compare, class _Allocator>
1014 inline _LIBCPP_INLINE_VISIBILITY
1015 void
1016 swap(multiset<_Key, _Compare, _Allocator>& __x,
1017      multiset<_Key, _Compare, _Allocator>& __y)
1018     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1019 {
1020     __x.swap(__y);
1021 }
1022
1023 _LIBCPP_END_NAMESPACE_STD
1024
1025 #endif  // _LIBCPP_SET