1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_SET 11#define _LIBCPP_SET 12 13/* 14 15 set synopsis 16 17namespace std 18{ 19 20template <class Key, class Compare = less<Key>, 21 class Allocator = allocator<Key>> 22class set 23{ 24public: 25 // types: 26 typedef Key key_type; 27 typedef key_type value_type; 28 typedef Compare key_compare; 29 typedef key_compare value_compare; 30 typedef Allocator allocator_type; 31 typedef typename allocator_type::reference reference; 32 typedef typename allocator_type::const_reference const_reference; 33 typedef typename allocator_type::size_type size_type; 34 typedef typename allocator_type::difference_type difference_type; 35 typedef typename allocator_type::pointer pointer; 36 typedef typename allocator_type::const_pointer const_pointer; 37 38 typedef implementation-defined iterator; 39 typedef implementation-defined const_iterator; 40 typedef std::reverse_iterator<iterator> reverse_iterator; 41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 42 typedef unspecified node_type; // C++17 43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 44 45 // construct/copy/destroy: 46 set() 47 noexcept( 48 is_nothrow_default_constructible<allocator_type>::value && 49 is_nothrow_default_constructible<key_compare>::value && 50 is_nothrow_copy_constructible<key_compare>::value); 51 explicit set(const value_compare& comp); 52 set(const value_compare& comp, const allocator_type& a); 53 template <class InputIterator> 54 set(InputIterator first, InputIterator last, 55 const value_compare& comp = value_compare()); 56 template <class InputIterator> 57 set(InputIterator first, InputIterator last, const value_compare& comp, 58 const allocator_type& a); 59 set(const set& s); 60 set(set&& s) 61 noexcept( 62 is_nothrow_move_constructible<allocator_type>::value && 63 is_nothrow_move_constructible<key_compare>::value); 64 explicit set(const allocator_type& a); 65 set(const set& s, const allocator_type& a); 66 set(set&& s, const allocator_type& a); 67 set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 68 set(initializer_list<value_type> il, const value_compare& comp, 69 const allocator_type& a); 70 template <class InputIterator> 71 set(InputIterator first, InputIterator last, const allocator_type& a) 72 : set(first, last, Compare(), a) {} // C++14 73 set(initializer_list<value_type> il, const allocator_type& a) 74 : set(il, Compare(), a) {} // C++14 75 ~set(); 76 77 set& operator=(const set& s); 78 set& operator=(set&& s) 79 noexcept( 80 allocator_type::propagate_on_container_move_assignment::value && 81 is_nothrow_move_assignable<allocator_type>::value && 82 is_nothrow_move_assignable<key_compare>::value); 83 set& operator=(initializer_list<value_type> il); 84 85 // iterators: 86 iterator begin() noexcept; 87 const_iterator begin() const noexcept; 88 iterator end() noexcept; 89 const_iterator end() const noexcept; 90 91 reverse_iterator rbegin() noexcept; 92 const_reverse_iterator rbegin() const noexcept; 93 reverse_iterator rend() noexcept; 94 const_reverse_iterator rend() const noexcept; 95 96 const_iterator cbegin() const noexcept; 97 const_iterator cend() const noexcept; 98 const_reverse_iterator crbegin() const noexcept; 99 const_reverse_iterator crend() const noexcept; 100 101 // capacity: 102 bool empty() const noexcept; 103 size_type size() const noexcept; 104 size_type max_size() const noexcept; 105 106 // modifiers: 107 template <class... Args> 108 pair<iterator, bool> emplace(Args&&... args); 109 template <class... Args> 110 iterator emplace_hint(const_iterator position, Args&&... args); 111 pair<iterator,bool> insert(const value_type& v); 112 pair<iterator,bool> insert(value_type&& v); 113 iterator insert(const_iterator position, const value_type& v); 114 iterator insert(const_iterator position, value_type&& v); 115 template <class InputIterator> 116 void insert(InputIterator first, InputIterator last); 117 void insert(initializer_list<value_type> il); 118 119 node_type extract(const_iterator position); // C++17 120 node_type extract(const key_type& x); // C++17 121 insert_return_type insert(node_type&& nh); // C++17 122 iterator insert(const_iterator hint, node_type&& nh); // C++17 123 124 iterator erase(const_iterator position); 125 iterator erase(iterator position); // C++14 126 size_type erase(const key_type& k); 127 iterator erase(const_iterator first, const_iterator last); 128 void clear() noexcept; 129 130 template<class C2> 131 void merge(set<Key, C2, Allocator>& source); // C++17 132 template<class C2> 133 void merge(set<Key, C2, Allocator>&& source); // C++17 134 template<class C2> 135 void merge(multiset<Key, C2, Allocator>& source); // C++17 136 template<class C2> 137 void merge(multiset<Key, C2, Allocator>&& source); // C++17 138 139 void swap(set& s) 140 noexcept( 141 __is_nothrow_swappable<key_compare>::value && 142 (!allocator_type::propagate_on_container_swap::value || 143 __is_nothrow_swappable<allocator_type>::value)); 144 145 // observers: 146 allocator_type get_allocator() const noexcept; 147 key_compare key_comp() const; 148 value_compare value_comp() const; 149 150 // set operations: 151 iterator find(const key_type& k); 152 const_iterator find(const key_type& k) const; 153 template<typename K> 154 iterator find(const K& x); 155 template<typename K> 156 const_iterator find(const K& x) const; // C++14 157 158 template<typename K> 159 size_type count(const K& x) const; // C++14 160 size_type count(const key_type& k) const; 161 162 bool contains(const key_type& x) const; // C++20 163 template<class K> bool contains(const K& x) const; // C++20 164 165 iterator lower_bound(const key_type& k); 166 const_iterator lower_bound(const key_type& k) const; 167 template<typename K> 168 iterator lower_bound(const K& x); // C++14 169 template<typename K> 170 const_iterator lower_bound(const K& x) const; // C++14 171 172 iterator upper_bound(const key_type& k); 173 const_iterator upper_bound(const key_type& k) const; 174 template<typename K> 175 iterator upper_bound(const K& x); // C++14 176 template<typename K> 177 const_iterator upper_bound(const K& x) const; // C++14 178 pair<iterator,iterator> equal_range(const key_type& k); 179 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 180 template<typename K> 181 pair<iterator,iterator> equal_range(const K& x); // C++14 182 template<typename K> 183 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 184}; 185 186template <class InputIterator, 187 class Compare = less<typename iterator_traits<InputIterator>::value_type>, 188 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 189set(InputIterator, InputIterator, 190 Compare = Compare(), Allocator = Allocator()) 191 -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 192 193template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 194set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 195 -> set<Key, Compare, Allocator>; // C++17 196 197template<class InputIterator, class Allocator> 198set(InputIterator, InputIterator, Allocator) 199 -> set<typename iterator_traits<InputIterator>::value_type, 200 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 201 202template<class Key, class Allocator> 203set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17 204 205template <class Key, class Compare, class Allocator> 206bool 207operator==(const set<Key, Compare, Allocator>& x, 208 const set<Key, Compare, Allocator>& y); 209 210template <class Key, class Compare, class Allocator> 211bool 212operator< (const set<Key, Compare, Allocator>& x, 213 const set<Key, Compare, Allocator>& y); 214 215template <class Key, class Compare, class Allocator> 216bool 217operator!=(const set<Key, Compare, Allocator>& x, 218 const set<Key, Compare, Allocator>& y); 219 220template <class Key, class Compare, class Allocator> 221bool 222operator> (const set<Key, Compare, Allocator>& x, 223 const set<Key, Compare, Allocator>& y); 224 225template <class Key, class Compare, class Allocator> 226bool 227operator>=(const set<Key, Compare, Allocator>& x, 228 const set<Key, Compare, Allocator>& y); 229 230template <class Key, class Compare, class Allocator> 231bool 232operator<=(const set<Key, Compare, Allocator>& x, 233 const set<Key, Compare, Allocator>& y); 234 235// specialized algorithms: 236template <class Key, class Compare, class Allocator> 237void 238swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 239 noexcept(noexcept(x.swap(y))); 240 241template <class Key, class Compare, class Allocator, class Predicate> 242typename set<Key, Compare, Allocator>::size_type 243erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20 244 245template <class Key, class Compare = less<Key>, 246 class Allocator = allocator<Key>> 247class multiset 248{ 249public: 250 // types: 251 typedef Key key_type; 252 typedef key_type value_type; 253 typedef Compare key_compare; 254 typedef key_compare value_compare; 255 typedef Allocator allocator_type; 256 typedef typename allocator_type::reference reference; 257 typedef typename allocator_type::const_reference const_reference; 258 typedef typename allocator_type::size_type size_type; 259 typedef typename allocator_type::difference_type difference_type; 260 typedef typename allocator_type::pointer pointer; 261 typedef typename allocator_type::const_pointer const_pointer; 262 263 typedef implementation-defined iterator; 264 typedef implementation-defined const_iterator; 265 typedef std::reverse_iterator<iterator> reverse_iterator; 266 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 267 typedef unspecified node_type; // C++17 268 269 // construct/copy/destroy: 270 multiset() 271 noexcept( 272 is_nothrow_default_constructible<allocator_type>::value && 273 is_nothrow_default_constructible<key_compare>::value && 274 is_nothrow_copy_constructible<key_compare>::value); 275 explicit multiset(const value_compare& comp); 276 multiset(const value_compare& comp, const allocator_type& a); 277 template <class InputIterator> 278 multiset(InputIterator first, InputIterator last, 279 const value_compare& comp = value_compare()); 280 template <class InputIterator> 281 multiset(InputIterator first, InputIterator last, 282 const value_compare& comp, const allocator_type& a); 283 multiset(const multiset& s); 284 multiset(multiset&& s) 285 noexcept( 286 is_nothrow_move_constructible<allocator_type>::value && 287 is_nothrow_move_constructible<key_compare>::value); 288 explicit multiset(const allocator_type& a); 289 multiset(const multiset& s, const allocator_type& a); 290 multiset(multiset&& s, const allocator_type& a); 291 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 292 multiset(initializer_list<value_type> il, const value_compare& comp, 293 const allocator_type& a); 294 template <class InputIterator> 295 multiset(InputIterator first, InputIterator last, const allocator_type& a) 296 : set(first, last, Compare(), a) {} // C++14 297 multiset(initializer_list<value_type> il, const allocator_type& a) 298 : set(il, Compare(), a) {} // C++14 299 ~multiset(); 300 301 multiset& operator=(const multiset& s); 302 multiset& operator=(multiset&& s) 303 noexcept( 304 allocator_type::propagate_on_container_move_assignment::value && 305 is_nothrow_move_assignable<allocator_type>::value && 306 is_nothrow_move_assignable<key_compare>::value); 307 multiset& operator=(initializer_list<value_type> il); 308 309 // iterators: 310 iterator begin() noexcept; 311 const_iterator begin() const noexcept; 312 iterator end() noexcept; 313 const_iterator end() const noexcept; 314 315 reverse_iterator rbegin() noexcept; 316 const_reverse_iterator rbegin() const noexcept; 317 reverse_iterator rend() noexcept; 318 const_reverse_iterator rend() const noexcept; 319 320 const_iterator cbegin() const noexcept; 321 const_iterator cend() const noexcept; 322 const_reverse_iterator crbegin() const noexcept; 323 const_reverse_iterator crend() const noexcept; 324 325 // capacity: 326 bool empty() const noexcept; 327 size_type size() const noexcept; 328 size_type max_size() const noexcept; 329 330 // modifiers: 331 template <class... Args> 332 iterator emplace(Args&&... args); 333 template <class... Args> 334 iterator emplace_hint(const_iterator position, Args&&... args); 335 iterator insert(const value_type& v); 336 iterator insert(value_type&& v); 337 iterator insert(const_iterator position, const value_type& v); 338 iterator insert(const_iterator position, value_type&& v); 339 template <class InputIterator> 340 void insert(InputIterator first, InputIterator last); 341 void insert(initializer_list<value_type> il); 342 343 node_type extract(const_iterator position); // C++17 344 node_type extract(const key_type& x); // C++17 345 iterator insert(node_type&& nh); // C++17 346 iterator insert(const_iterator hint, node_type&& nh); // C++17 347 348 iterator erase(const_iterator position); 349 iterator erase(iterator position); // C++14 350 size_type erase(const key_type& k); 351 iterator erase(const_iterator first, const_iterator last); 352 void clear() noexcept; 353 354 template<class C2> 355 void merge(multiset<Key, C2, Allocator>& source); // C++17 356 template<class C2> 357 void merge(multiset<Key, C2, Allocator>&& source); // C++17 358 template<class C2> 359 void merge(set<Key, C2, Allocator>& source); // C++17 360 template<class C2> 361 void merge(set<Key, C2, Allocator>&& source); // C++17 362 363 void swap(multiset& s) 364 noexcept( 365 __is_nothrow_swappable<key_compare>::value && 366 (!allocator_type::propagate_on_container_swap::value || 367 __is_nothrow_swappable<allocator_type>::value)); 368 369 // observers: 370 allocator_type get_allocator() const noexcept; 371 key_compare key_comp() const; 372 value_compare value_comp() const; 373 374 // set operations: 375 iterator find(const key_type& k); 376 const_iterator find(const key_type& k) const; 377 template<typename K> 378 iterator find(const K& x); 379 template<typename K> 380 const_iterator find(const K& x) const; // C++14 381 382 template<typename K> 383 size_type count(const K& x) const; // C++14 384 size_type count(const key_type& k) const; 385 386 bool contains(const key_type& x) const; // C++20 387 template<class K> bool contains(const K& x) const; // C++20 388 389 iterator lower_bound(const key_type& k); 390 const_iterator lower_bound(const key_type& k) const; 391 template<typename K> 392 iterator lower_bound(const K& x); // C++14 393 template<typename K> 394 const_iterator lower_bound(const K& x) const; // C++14 395 396 iterator upper_bound(const key_type& k); 397 const_iterator upper_bound(const key_type& k) const; 398 template<typename K> 399 iterator upper_bound(const K& x); // C++14 400 template<typename K> 401 const_iterator upper_bound(const K& x) const; // C++14 402 403 pair<iterator,iterator> equal_range(const key_type& k); 404 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 405 template<typename K> 406 pair<iterator,iterator> equal_range(const K& x); // C++14 407 template<typename K> 408 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 409}; 410 411template <class InputIterator, 412 class Compare = less<typename iterator_traits<InputIterator>::value_type>, 413 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 414multiset(InputIterator, InputIterator, 415 Compare = Compare(), Allocator = Allocator()) 416 -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 417 418template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 419multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 420 -> multiset<Key, Compare, Allocator>; // C++17 421 422template<class InputIterator, class Allocator> 423multiset(InputIterator, InputIterator, Allocator) 424 -> multiset<typename iterator_traits<InputIterator>::value_type, 425 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 426 427template<class Key, class Allocator> 428multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17 429 430template <class Key, class Compare, class Allocator> 431bool 432operator==(const multiset<Key, Compare, Allocator>& x, 433 const multiset<Key, Compare, Allocator>& y); 434 435template <class Key, class Compare, class Allocator> 436bool 437operator< (const multiset<Key, Compare, Allocator>& x, 438 const multiset<Key, Compare, Allocator>& y); 439 440template <class Key, class Compare, class Allocator> 441bool 442operator!=(const multiset<Key, Compare, Allocator>& x, 443 const multiset<Key, Compare, Allocator>& y); 444 445template <class Key, class Compare, class Allocator> 446bool 447operator> (const multiset<Key, Compare, Allocator>& x, 448 const multiset<Key, Compare, Allocator>& y); 449 450template <class Key, class Compare, class Allocator> 451bool 452operator>=(const multiset<Key, Compare, Allocator>& x, 453 const multiset<Key, Compare, Allocator>& y); 454 455template <class Key, class Compare, class Allocator> 456bool 457operator<=(const multiset<Key, Compare, Allocator>& x, 458 const multiset<Key, Compare, Allocator>& y); 459 460// specialized algorithms: 461template <class Key, class Compare, class Allocator> 462void 463swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 464 noexcept(noexcept(x.swap(y))); 465 466template <class Key, class Compare, class Allocator, class Predicate> 467typename multiset<Key, Compare, Allocator>::size_type 468erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20 469 470} // std 471 472*/ 473 474#include <__algorithm/equal.h> 475#include <__algorithm/lexicographical_compare.h> 476#include <__assert> // all public C++ headers provide the assertion handler 477#include <__config> 478#include <__functional/is_transparent.h> 479#include <__functional/operations.h> 480#include <__iterator/erase_if_container.h> 481#include <__iterator/iterator_traits.h> 482#include <__iterator/reverse_iterator.h> 483#include <__node_handle> 484#include <__tree> 485#include <__utility/forward.h> 486#include <version> 487 488// standard-mandated includes 489 490// [iterator.range] 491#include <__iterator/access.h> 492#include <__iterator/data.h> 493#include <__iterator/empty.h> 494#include <__iterator/reverse_access.h> 495#include <__iterator/size.h> 496 497// [associative.set.syn] 498#include <compare> 499#include <initializer_list> 500 501#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 502# pragma GCC system_header 503#endif 504 505_LIBCPP_BEGIN_NAMESPACE_STD 506 507template <class _Key, class _Compare, class _Allocator> 508class multiset; 509 510template <class _Key, class _Compare = less<_Key>, 511 class _Allocator = allocator<_Key> > 512class _LIBCPP_TEMPLATE_VIS set 513{ 514public: 515 // types: 516 typedef _Key key_type; 517 typedef key_type value_type; 518 typedef __type_identity_t<_Compare> key_compare; 519 typedef key_compare value_compare; 520 typedef __type_identity_t<_Allocator> allocator_type; 521 typedef value_type& reference; 522 typedef const value_type& const_reference; 523 524 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 525 "Allocator::value_type must be same type as value_type"); 526 527private: 528 typedef __tree<value_type, value_compare, allocator_type> __base; 529 typedef allocator_traits<allocator_type> __alloc_traits; 530 531 __base __tree_; 532 533public: 534 typedef typename __base::pointer pointer; 535 typedef typename __base::const_pointer const_pointer; 536 typedef typename __base::size_type size_type; 537 typedef typename __base::difference_type difference_type; 538 typedef typename __base::const_iterator iterator; 539 typedef typename __base::const_iterator const_iterator; 540 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 541 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 542 543#if _LIBCPP_STD_VER > 14 544 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 545 typedef __insert_return_type<iterator, node_type> insert_return_type; 546#endif 547 548 template <class _Key2, class _Compare2, class _Alloc2> 549 friend class _LIBCPP_TEMPLATE_VIS set; 550 template <class _Key2, class _Compare2, class _Alloc2> 551 friend class _LIBCPP_TEMPLATE_VIS multiset; 552 553 _LIBCPP_INLINE_VISIBILITY 554 set() 555 _NOEXCEPT_( 556 is_nothrow_default_constructible<allocator_type>::value && 557 is_nothrow_default_constructible<key_compare>::value && 558 is_nothrow_copy_constructible<key_compare>::value) 559 : __tree_(value_compare()) {} 560 561 _LIBCPP_INLINE_VISIBILITY 562 explicit set(const value_compare& __comp) 563 _NOEXCEPT_( 564 is_nothrow_default_constructible<allocator_type>::value && 565 is_nothrow_copy_constructible<key_compare>::value) 566 : __tree_(__comp) {} 567 568 _LIBCPP_INLINE_VISIBILITY 569 explicit set(const value_compare& __comp, const allocator_type& __a) 570 : __tree_(__comp, __a) {} 571 template <class _InputIterator> 572 _LIBCPP_INLINE_VISIBILITY 573 set(_InputIterator __f, _InputIterator __l, 574 const value_compare& __comp = value_compare()) 575 : __tree_(__comp) 576 { 577 insert(__f, __l); 578 } 579 580 template <class _InputIterator> 581 _LIBCPP_INLINE_VISIBILITY 582 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 583 const allocator_type& __a) 584 : __tree_(__comp, __a) 585 { 586 insert(__f, __l); 587 } 588 589#if _LIBCPP_STD_VER > 11 590 template <class _InputIterator> 591 _LIBCPP_INLINE_VISIBILITY 592 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 593 : set(__f, __l, key_compare(), __a) {} 594#endif 595 596 _LIBCPP_INLINE_VISIBILITY 597 set(const set& __s) 598 : __tree_(__s.__tree_) 599 { 600 insert(__s.begin(), __s.end()); 601 } 602 603 _LIBCPP_INLINE_VISIBILITY 604 set& operator=(const set& __s) 605 { 606 __tree_ = __s.__tree_; 607 return *this; 608 } 609 610#ifndef _LIBCPP_CXX03_LANG 611 _LIBCPP_INLINE_VISIBILITY 612 set(set&& __s) 613 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 614 : __tree_(_VSTD::move(__s.__tree_)) {} 615#endif // _LIBCPP_CXX03_LANG 616 617 _LIBCPP_INLINE_VISIBILITY 618 explicit set(const allocator_type& __a) 619 : __tree_(__a) {} 620 621 _LIBCPP_INLINE_VISIBILITY 622 set(const set& __s, const allocator_type& __a) 623 : __tree_(__s.__tree_.value_comp(), __a) 624 { 625 insert(__s.begin(), __s.end()); 626 } 627 628#ifndef _LIBCPP_CXX03_LANG 629 set(set&& __s, const allocator_type& __a); 630 631 _LIBCPP_INLINE_VISIBILITY 632 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 633 : __tree_(__comp) 634 { 635 insert(__il.begin(), __il.end()); 636 } 637 638 _LIBCPP_INLINE_VISIBILITY 639 set(initializer_list<value_type> __il, const value_compare& __comp, 640 const allocator_type& __a) 641 : __tree_(__comp, __a) 642 { 643 insert(__il.begin(), __il.end()); 644 } 645 646#if _LIBCPP_STD_VER > 11 647 _LIBCPP_INLINE_VISIBILITY 648 set(initializer_list<value_type> __il, const allocator_type& __a) 649 : set(__il, key_compare(), __a) {} 650#endif 651 652 _LIBCPP_INLINE_VISIBILITY 653 set& operator=(initializer_list<value_type> __il) 654 { 655 __tree_.__assign_unique(__il.begin(), __il.end()); 656 return *this; 657 } 658 659 _LIBCPP_INLINE_VISIBILITY 660 set& operator=(set&& __s) 661 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 662 { 663 __tree_ = _VSTD::move(__s.__tree_); 664 return *this; 665 } 666#endif // _LIBCPP_CXX03_LANG 667 668 _LIBCPP_INLINE_VISIBILITY 669 ~set() { 670 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 671 } 672 673 _LIBCPP_INLINE_VISIBILITY 674 iterator begin() _NOEXCEPT {return __tree_.begin();} 675 _LIBCPP_INLINE_VISIBILITY 676 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 677 _LIBCPP_INLINE_VISIBILITY 678 iterator end() _NOEXCEPT {return __tree_.end();} 679 _LIBCPP_INLINE_VISIBILITY 680 const_iterator end() const _NOEXCEPT {return __tree_.end();} 681 682 _LIBCPP_INLINE_VISIBILITY 683 reverse_iterator rbegin() _NOEXCEPT 684 {return reverse_iterator(end());} 685 _LIBCPP_INLINE_VISIBILITY 686 const_reverse_iterator rbegin() const _NOEXCEPT 687 {return const_reverse_iterator(end());} 688 _LIBCPP_INLINE_VISIBILITY 689 reverse_iterator rend() _NOEXCEPT 690 {return reverse_iterator(begin());} 691 _LIBCPP_INLINE_VISIBILITY 692 const_reverse_iterator rend() const _NOEXCEPT 693 {return const_reverse_iterator(begin());} 694 695 _LIBCPP_INLINE_VISIBILITY 696 const_iterator cbegin() const _NOEXCEPT {return begin();} 697 _LIBCPP_INLINE_VISIBILITY 698 const_iterator cend() const _NOEXCEPT {return end();} 699 _LIBCPP_INLINE_VISIBILITY 700 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 701 _LIBCPP_INLINE_VISIBILITY 702 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 703 704 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 705 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 706 _LIBCPP_INLINE_VISIBILITY 707 size_type size() const _NOEXCEPT {return __tree_.size();} 708 _LIBCPP_INLINE_VISIBILITY 709 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 710 711 // modifiers: 712#ifndef _LIBCPP_CXX03_LANG 713 template <class... _Args> 714 _LIBCPP_INLINE_VISIBILITY 715 pair<iterator, bool> emplace(_Args&&... __args) 716 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 717 template <class... _Args> 718 _LIBCPP_INLINE_VISIBILITY 719 iterator emplace_hint(const_iterator __p, _Args&&... __args) 720 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 721#endif // _LIBCPP_CXX03_LANG 722 723 _LIBCPP_INLINE_VISIBILITY 724 pair<iterator,bool> insert(const value_type& __v) 725 {return __tree_.__insert_unique(__v);} 726 _LIBCPP_INLINE_VISIBILITY 727 iterator insert(const_iterator __p, const value_type& __v) 728 {return __tree_.__insert_unique(__p, __v);} 729 730 template <class _InputIterator> 731 _LIBCPP_INLINE_VISIBILITY 732 void insert(_InputIterator __f, _InputIterator __l) 733 { 734 for (const_iterator __e = cend(); __f != __l; ++__f) 735 __tree_.__insert_unique(__e, *__f); 736 } 737 738#ifndef _LIBCPP_CXX03_LANG 739 _LIBCPP_INLINE_VISIBILITY 740 pair<iterator,bool> insert(value_type&& __v) 741 {return __tree_.__insert_unique(_VSTD::move(__v));} 742 743 _LIBCPP_INLINE_VISIBILITY 744 iterator insert(const_iterator __p, value_type&& __v) 745 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 746 747 _LIBCPP_INLINE_VISIBILITY 748 void insert(initializer_list<value_type> __il) 749 {insert(__il.begin(), __il.end());} 750#endif // _LIBCPP_CXX03_LANG 751 752 _LIBCPP_INLINE_VISIBILITY 753 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 754 _LIBCPP_INLINE_VISIBILITY 755 size_type erase(const key_type& __k) 756 {return __tree_.__erase_unique(__k);} 757 _LIBCPP_INLINE_VISIBILITY 758 iterator erase(const_iterator __f, const_iterator __l) 759 {return __tree_.erase(__f, __l);} 760 _LIBCPP_INLINE_VISIBILITY 761 void clear() _NOEXCEPT {__tree_.clear();} 762 763#if _LIBCPP_STD_VER > 14 764 _LIBCPP_INLINE_VISIBILITY 765 insert_return_type insert(node_type&& __nh) 766 { 767 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 768 "node_type with incompatible allocator passed to set::insert()"); 769 return __tree_.template __node_handle_insert_unique< 770 node_type, insert_return_type>(_VSTD::move(__nh)); 771 } 772 _LIBCPP_INLINE_VISIBILITY 773 iterator insert(const_iterator __hint, node_type&& __nh) 774 { 775 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 776 "node_type with incompatible allocator passed to set::insert()"); 777 return __tree_.template __node_handle_insert_unique<node_type>( 778 __hint, _VSTD::move(__nh)); 779 } 780 _LIBCPP_INLINE_VISIBILITY 781 node_type extract(key_type const& __key) 782 { 783 return __tree_.template __node_handle_extract<node_type>(__key); 784 } 785 _LIBCPP_INLINE_VISIBILITY 786 node_type extract(const_iterator __it) 787 { 788 return __tree_.template __node_handle_extract<node_type>(__it); 789 } 790 template <class _Compare2> 791 _LIBCPP_INLINE_VISIBILITY 792 void merge(set<key_type, _Compare2, allocator_type>& __source) 793 { 794 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 795 "merging container with incompatible allocator"); 796 __tree_.__node_handle_merge_unique(__source.__tree_); 797 } 798 template <class _Compare2> 799 _LIBCPP_INLINE_VISIBILITY 800 void merge(set<key_type, _Compare2, allocator_type>&& __source) 801 { 802 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 803 "merging container with incompatible allocator"); 804 __tree_.__node_handle_merge_unique(__source.__tree_); 805 } 806 template <class _Compare2> 807 _LIBCPP_INLINE_VISIBILITY 808 void merge(multiset<key_type, _Compare2, allocator_type>& __source) 809 { 810 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 811 "merging container with incompatible allocator"); 812 __tree_.__node_handle_merge_unique(__source.__tree_); 813 } 814 template <class _Compare2> 815 _LIBCPP_INLINE_VISIBILITY 816 void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 817 { 818 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 819 "merging container with incompatible allocator"); 820 __tree_.__node_handle_merge_unique(__source.__tree_); 821 } 822#endif 823 824 _LIBCPP_INLINE_VISIBILITY 825 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 826 {__tree_.swap(__s.__tree_);} 827 828 _LIBCPP_INLINE_VISIBILITY 829 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 830 _LIBCPP_INLINE_VISIBILITY 831 key_compare key_comp() const {return __tree_.value_comp();} 832 _LIBCPP_INLINE_VISIBILITY 833 value_compare value_comp() const {return __tree_.value_comp();} 834 835 // set operations: 836 _LIBCPP_INLINE_VISIBILITY 837 iterator find(const key_type& __k) {return __tree_.find(__k);} 838 _LIBCPP_INLINE_VISIBILITY 839 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 840#if _LIBCPP_STD_VER > 11 841 template <typename _K2> 842 _LIBCPP_INLINE_VISIBILITY 843 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 844 find(const _K2& __k) {return __tree_.find(__k);} 845 template <typename _K2> 846 _LIBCPP_INLINE_VISIBILITY 847 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 848 find(const _K2& __k) const {return __tree_.find(__k);} 849#endif 850 851 _LIBCPP_INLINE_VISIBILITY 852 size_type count(const key_type& __k) const 853 {return __tree_.__count_unique(__k);} 854#if _LIBCPP_STD_VER > 11 855 template <typename _K2> 856 _LIBCPP_INLINE_VISIBILITY 857 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 858 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 859#endif 860 861#if _LIBCPP_STD_VER > 17 862 _LIBCPP_INLINE_VISIBILITY 863 bool contains(const key_type& __k) const {return find(__k) != end();} 864 template <typename _K2> 865 _LIBCPP_INLINE_VISIBILITY 866 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 867 contains(const _K2& __k) const { return find(__k) != end(); } 868#endif // _LIBCPP_STD_VER > 17 869 870 _LIBCPP_INLINE_VISIBILITY 871 iterator lower_bound(const key_type& __k) 872 {return __tree_.lower_bound(__k);} 873 _LIBCPP_INLINE_VISIBILITY 874 const_iterator lower_bound(const key_type& __k) const 875 {return __tree_.lower_bound(__k);} 876#if _LIBCPP_STD_VER > 11 877 template <typename _K2> 878 _LIBCPP_INLINE_VISIBILITY 879 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 880 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 881 882 template <typename _K2> 883 _LIBCPP_INLINE_VISIBILITY 884 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 885 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 886#endif 887 888 _LIBCPP_INLINE_VISIBILITY 889 iterator upper_bound(const key_type& __k) 890 {return __tree_.upper_bound(__k);} 891 _LIBCPP_INLINE_VISIBILITY 892 const_iterator upper_bound(const key_type& __k) const 893 {return __tree_.upper_bound(__k);} 894#if _LIBCPP_STD_VER > 11 895 template <typename _K2> 896 _LIBCPP_INLINE_VISIBILITY 897 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 898 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 899 template <typename _K2> 900 _LIBCPP_INLINE_VISIBILITY 901 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 902 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 903#endif 904 905 _LIBCPP_INLINE_VISIBILITY 906 pair<iterator,iterator> equal_range(const key_type& __k) 907 {return __tree_.__equal_range_unique(__k);} 908 _LIBCPP_INLINE_VISIBILITY 909 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 910 {return __tree_.__equal_range_unique(__k);} 911#if _LIBCPP_STD_VER > 11 912 template <typename _K2> 913 _LIBCPP_INLINE_VISIBILITY 914 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 915 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 916 template <typename _K2> 917 _LIBCPP_INLINE_VISIBILITY 918 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 919 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 920#endif 921}; 922 923#if _LIBCPP_STD_VER >= 17 924template<class _InputIterator, 925 class _Compare = less<__iter_value_type<_InputIterator>>, 926 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 927 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 928 class = enable_if_t<__is_allocator<_Allocator>::value, void>, 929 class = enable_if_t<!__is_allocator<_Compare>::value, void>> 930set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 931 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 932 933template<class _Key, class _Compare = less<_Key>, 934 class _Allocator = allocator<_Key>, 935 class = enable_if_t<!__is_allocator<_Compare>::value, void>, 936 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 937set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 938 -> set<_Key, _Compare, _Allocator>; 939 940template<class _InputIterator, class _Allocator, 941 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 942 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 943set(_InputIterator, _InputIterator, _Allocator) 944 -> set<__iter_value_type<_InputIterator>, 945 less<__iter_value_type<_InputIterator>>, _Allocator>; 946 947template<class _Key, class _Allocator, 948 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 949set(initializer_list<_Key>, _Allocator) 950 -> set<_Key, less<_Key>, _Allocator>; 951#endif 952 953#ifndef _LIBCPP_CXX03_LANG 954 955template <class _Key, class _Compare, class _Allocator> 956set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 957 : __tree_(_VSTD::move(__s.__tree_), __a) 958{ 959 if (__a != __s.get_allocator()) 960 { 961 const_iterator __e = cend(); 962 while (!__s.empty()) 963 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 964 } 965} 966 967#endif // _LIBCPP_CXX03_LANG 968 969template <class _Key, class _Compare, class _Allocator> 970inline _LIBCPP_INLINE_VISIBILITY 971bool 972operator==(const set<_Key, _Compare, _Allocator>& __x, 973 const set<_Key, _Compare, _Allocator>& __y) 974{ 975 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 976} 977 978template <class _Key, class _Compare, class _Allocator> 979inline _LIBCPP_INLINE_VISIBILITY 980bool 981operator< (const set<_Key, _Compare, _Allocator>& __x, 982 const set<_Key, _Compare, _Allocator>& __y) 983{ 984 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 985} 986 987template <class _Key, class _Compare, class _Allocator> 988inline _LIBCPP_INLINE_VISIBILITY 989bool 990operator!=(const set<_Key, _Compare, _Allocator>& __x, 991 const set<_Key, _Compare, _Allocator>& __y) 992{ 993 return !(__x == __y); 994} 995 996template <class _Key, class _Compare, class _Allocator> 997inline _LIBCPP_INLINE_VISIBILITY 998bool 999operator> (const set<_Key, _Compare, _Allocator>& __x, 1000 const set<_Key, _Compare, _Allocator>& __y) 1001{ 1002 return __y < __x; 1003} 1004 1005template <class _Key, class _Compare, class _Allocator> 1006inline _LIBCPP_INLINE_VISIBILITY 1007bool 1008operator>=(const set<_Key, _Compare, _Allocator>& __x, 1009 const set<_Key, _Compare, _Allocator>& __y) 1010{ 1011 return !(__x < __y); 1012} 1013 1014template <class _Key, class _Compare, class _Allocator> 1015inline _LIBCPP_INLINE_VISIBILITY 1016bool 1017operator<=(const set<_Key, _Compare, _Allocator>& __x, 1018 const set<_Key, _Compare, _Allocator>& __y) 1019{ 1020 return !(__y < __x); 1021} 1022 1023// specialized algorithms: 1024template <class _Key, class _Compare, class _Allocator> 1025inline _LIBCPP_INLINE_VISIBILITY 1026void 1027swap(set<_Key, _Compare, _Allocator>& __x, 1028 set<_Key, _Compare, _Allocator>& __y) 1029 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1030{ 1031 __x.swap(__y); 1032} 1033 1034#if _LIBCPP_STD_VER > 17 1035template <class _Key, class _Compare, class _Allocator, class _Predicate> 1036inline _LIBCPP_INLINE_VISIBILITY 1037 typename set<_Key, _Compare, _Allocator>::size_type 1038 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 1039 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1040} 1041#endif 1042 1043template <class _Key, class _Compare = less<_Key>, 1044 class _Allocator = allocator<_Key> > 1045class _LIBCPP_TEMPLATE_VIS multiset 1046{ 1047public: 1048 // types: 1049 typedef _Key key_type; 1050 typedef key_type value_type; 1051 typedef __type_identity_t<_Compare> key_compare; 1052 typedef key_compare value_compare; 1053 typedef __type_identity_t<_Allocator> allocator_type; 1054 typedef value_type& reference; 1055 typedef const value_type& const_reference; 1056 1057 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1058 "Allocator::value_type must be same type as value_type"); 1059 1060private: 1061 typedef __tree<value_type, value_compare, allocator_type> __base; 1062 typedef allocator_traits<allocator_type> __alloc_traits; 1063 1064 __base __tree_; 1065 1066public: 1067 typedef typename __base::pointer pointer; 1068 typedef typename __base::const_pointer const_pointer; 1069 typedef typename __base::size_type size_type; 1070 typedef typename __base::difference_type difference_type; 1071 typedef typename __base::const_iterator iterator; 1072 typedef typename __base::const_iterator const_iterator; 1073 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1074 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1075 1076#if _LIBCPP_STD_VER > 14 1077 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 1078#endif 1079 1080 template <class _Key2, class _Compare2, class _Alloc2> 1081 friend class _LIBCPP_TEMPLATE_VIS set; 1082 template <class _Key2, class _Compare2, class _Alloc2> 1083 friend class _LIBCPP_TEMPLATE_VIS multiset; 1084 1085 // construct/copy/destroy: 1086 _LIBCPP_INLINE_VISIBILITY 1087 multiset() 1088 _NOEXCEPT_( 1089 is_nothrow_default_constructible<allocator_type>::value && 1090 is_nothrow_default_constructible<key_compare>::value && 1091 is_nothrow_copy_constructible<key_compare>::value) 1092 : __tree_(value_compare()) {} 1093 1094 _LIBCPP_INLINE_VISIBILITY 1095 explicit multiset(const value_compare& __comp) 1096 _NOEXCEPT_( 1097 is_nothrow_default_constructible<allocator_type>::value && 1098 is_nothrow_copy_constructible<key_compare>::value) 1099 : __tree_(__comp) {} 1100 1101 _LIBCPP_INLINE_VISIBILITY 1102 explicit multiset(const value_compare& __comp, const allocator_type& __a) 1103 : __tree_(__comp, __a) {} 1104 template <class _InputIterator> 1105 _LIBCPP_INLINE_VISIBILITY 1106 multiset(_InputIterator __f, _InputIterator __l, 1107 const value_compare& __comp = value_compare()) 1108 : __tree_(__comp) 1109 { 1110 insert(__f, __l); 1111 } 1112 1113#if _LIBCPP_STD_VER > 11 1114 template <class _InputIterator> 1115 _LIBCPP_INLINE_VISIBILITY 1116 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1117 : multiset(__f, __l, key_compare(), __a) {} 1118#endif 1119 1120 template <class _InputIterator> 1121 _LIBCPP_INLINE_VISIBILITY 1122 multiset(_InputIterator __f, _InputIterator __l, 1123 const value_compare& __comp, const allocator_type& __a) 1124 : __tree_(__comp, __a) 1125 { 1126 insert(__f, __l); 1127 } 1128 1129 _LIBCPP_INLINE_VISIBILITY 1130 multiset(const multiset& __s) 1131 : __tree_(__s.__tree_.value_comp(), 1132 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 1133 { 1134 insert(__s.begin(), __s.end()); 1135 } 1136 1137 _LIBCPP_INLINE_VISIBILITY 1138 multiset& operator=(const multiset& __s) 1139 { 1140 __tree_ = __s.__tree_; 1141 return *this; 1142 } 1143 1144#ifndef _LIBCPP_CXX03_LANG 1145 _LIBCPP_INLINE_VISIBILITY 1146 multiset(multiset&& __s) 1147 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1148 : __tree_(_VSTD::move(__s.__tree_)) {} 1149 1150 multiset(multiset&& __s, const allocator_type& __a); 1151#endif // _LIBCPP_CXX03_LANG 1152 _LIBCPP_INLINE_VISIBILITY 1153 explicit multiset(const allocator_type& __a) 1154 : __tree_(__a) {} 1155 _LIBCPP_INLINE_VISIBILITY 1156 multiset(const multiset& __s, const allocator_type& __a) 1157 : __tree_(__s.__tree_.value_comp(), __a) 1158 { 1159 insert(__s.begin(), __s.end()); 1160 } 1161 1162#ifndef _LIBCPP_CXX03_LANG 1163 _LIBCPP_INLINE_VISIBILITY 1164 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 1165 : __tree_(__comp) 1166 { 1167 insert(__il.begin(), __il.end()); 1168 } 1169 1170 _LIBCPP_INLINE_VISIBILITY 1171 multiset(initializer_list<value_type> __il, const value_compare& __comp, 1172 const allocator_type& __a) 1173 : __tree_(__comp, __a) 1174 { 1175 insert(__il.begin(), __il.end()); 1176 } 1177 1178#if _LIBCPP_STD_VER > 11 1179 _LIBCPP_INLINE_VISIBILITY 1180 multiset(initializer_list<value_type> __il, const allocator_type& __a) 1181 : multiset(__il, key_compare(), __a) {} 1182#endif 1183 1184 _LIBCPP_INLINE_VISIBILITY 1185 multiset& operator=(initializer_list<value_type> __il) 1186 { 1187 __tree_.__assign_multi(__il.begin(), __il.end()); 1188 return *this; 1189 } 1190 1191 _LIBCPP_INLINE_VISIBILITY 1192 multiset& operator=(multiset&& __s) 1193 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1194 { 1195 __tree_ = _VSTD::move(__s.__tree_); 1196 return *this; 1197 } 1198#endif // _LIBCPP_CXX03_LANG 1199 1200 _LIBCPP_INLINE_VISIBILITY 1201 ~multiset() { 1202 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1203 } 1204 1205 _LIBCPP_INLINE_VISIBILITY 1206 iterator begin() _NOEXCEPT {return __tree_.begin();} 1207 _LIBCPP_INLINE_VISIBILITY 1208 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1209 _LIBCPP_INLINE_VISIBILITY 1210 iterator end() _NOEXCEPT {return __tree_.end();} 1211 _LIBCPP_INLINE_VISIBILITY 1212 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1213 1214 _LIBCPP_INLINE_VISIBILITY 1215 reverse_iterator rbegin() _NOEXCEPT 1216 {return reverse_iterator(end());} 1217 _LIBCPP_INLINE_VISIBILITY 1218 const_reverse_iterator rbegin() const _NOEXCEPT 1219 {return const_reverse_iterator(end());} 1220 _LIBCPP_INLINE_VISIBILITY 1221 reverse_iterator rend() _NOEXCEPT 1222 {return reverse_iterator(begin());} 1223 _LIBCPP_INLINE_VISIBILITY 1224 const_reverse_iterator rend() const _NOEXCEPT 1225 {return const_reverse_iterator(begin());} 1226 1227 _LIBCPP_INLINE_VISIBILITY 1228 const_iterator cbegin() const _NOEXCEPT {return begin();} 1229 _LIBCPP_INLINE_VISIBILITY 1230 const_iterator cend() const _NOEXCEPT {return end();} 1231 _LIBCPP_INLINE_VISIBILITY 1232 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1233 _LIBCPP_INLINE_VISIBILITY 1234 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1235 1236 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1237 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1238 _LIBCPP_INLINE_VISIBILITY 1239 size_type size() const _NOEXCEPT {return __tree_.size();} 1240 _LIBCPP_INLINE_VISIBILITY 1241 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1242 1243 // modifiers: 1244#ifndef _LIBCPP_CXX03_LANG 1245 template <class... _Args> 1246 _LIBCPP_INLINE_VISIBILITY 1247 iterator emplace(_Args&&... __args) 1248 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1249 template <class... _Args> 1250 _LIBCPP_INLINE_VISIBILITY 1251 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1252 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1253#endif // _LIBCPP_CXX03_LANG 1254 1255 _LIBCPP_INLINE_VISIBILITY 1256 iterator insert(const value_type& __v) 1257 {return __tree_.__insert_multi(__v);} 1258 _LIBCPP_INLINE_VISIBILITY 1259 iterator insert(const_iterator __p, const value_type& __v) 1260 {return __tree_.__insert_multi(__p, __v);} 1261 1262 template <class _InputIterator> 1263 _LIBCPP_INLINE_VISIBILITY 1264 void insert(_InputIterator __f, _InputIterator __l) 1265 { 1266 for (const_iterator __e = cend(); __f != __l; ++__f) 1267 __tree_.__insert_multi(__e, *__f); 1268 } 1269 1270#ifndef _LIBCPP_CXX03_LANG 1271 _LIBCPP_INLINE_VISIBILITY 1272 iterator insert(value_type&& __v) 1273 {return __tree_.__insert_multi(_VSTD::move(__v));} 1274 1275 _LIBCPP_INLINE_VISIBILITY 1276 iterator insert(const_iterator __p, value_type&& __v) 1277 {return __tree_.__insert_multi(__p, _VSTD::move(__v));} 1278 1279 _LIBCPP_INLINE_VISIBILITY 1280 void insert(initializer_list<value_type> __il) 1281 {insert(__il.begin(), __il.end());} 1282#endif // _LIBCPP_CXX03_LANG 1283 1284 _LIBCPP_INLINE_VISIBILITY 1285 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1286 _LIBCPP_INLINE_VISIBILITY 1287 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1288 _LIBCPP_INLINE_VISIBILITY 1289 iterator erase(const_iterator __f, const_iterator __l) 1290 {return __tree_.erase(__f, __l);} 1291 _LIBCPP_INLINE_VISIBILITY 1292 void clear() _NOEXCEPT {__tree_.clear();} 1293 1294#if _LIBCPP_STD_VER > 14 1295 _LIBCPP_INLINE_VISIBILITY 1296 iterator insert(node_type&& __nh) 1297 { 1298 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1299 "node_type with incompatible allocator passed to multiset::insert()"); 1300 return __tree_.template __node_handle_insert_multi<node_type>( 1301 _VSTD::move(__nh)); 1302 } 1303 _LIBCPP_INLINE_VISIBILITY 1304 iterator insert(const_iterator __hint, node_type&& __nh) 1305 { 1306 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1307 "node_type with incompatible allocator passed to multiset::insert()"); 1308 return __tree_.template __node_handle_insert_multi<node_type>( 1309 __hint, _VSTD::move(__nh)); 1310 } 1311 _LIBCPP_INLINE_VISIBILITY 1312 node_type extract(key_type const& __key) 1313 { 1314 return __tree_.template __node_handle_extract<node_type>(__key); 1315 } 1316 _LIBCPP_INLINE_VISIBILITY 1317 node_type extract(const_iterator __it) 1318 { 1319 return __tree_.template __node_handle_extract<node_type>(__it); 1320 } 1321 template <class _Compare2> 1322 _LIBCPP_INLINE_VISIBILITY 1323 void merge(multiset<key_type, _Compare2, allocator_type>& __source) 1324 { 1325 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1326 "merging container with incompatible allocator"); 1327 __tree_.__node_handle_merge_multi(__source.__tree_); 1328 } 1329 template <class _Compare2> 1330 _LIBCPP_INLINE_VISIBILITY 1331 void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 1332 { 1333 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1334 "merging container with incompatible allocator"); 1335 __tree_.__node_handle_merge_multi(__source.__tree_); 1336 } 1337 template <class _Compare2> 1338 _LIBCPP_INLINE_VISIBILITY 1339 void merge(set<key_type, _Compare2, allocator_type>& __source) 1340 { 1341 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1342 "merging container with incompatible allocator"); 1343 __tree_.__node_handle_merge_multi(__source.__tree_); 1344 } 1345 template <class _Compare2> 1346 _LIBCPP_INLINE_VISIBILITY 1347 void merge(set<key_type, _Compare2, allocator_type>&& __source) 1348 { 1349 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1350 "merging container with incompatible allocator"); 1351 __tree_.__node_handle_merge_multi(__source.__tree_); 1352 } 1353#endif 1354 1355 _LIBCPP_INLINE_VISIBILITY 1356 void swap(multiset& __s) 1357 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1358 {__tree_.swap(__s.__tree_);} 1359 1360 _LIBCPP_INLINE_VISIBILITY 1361 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1362 _LIBCPP_INLINE_VISIBILITY 1363 key_compare key_comp() const {return __tree_.value_comp();} 1364 _LIBCPP_INLINE_VISIBILITY 1365 value_compare value_comp() const {return __tree_.value_comp();} 1366 1367 // set operations: 1368 _LIBCPP_INLINE_VISIBILITY 1369 iterator find(const key_type& __k) {return __tree_.find(__k);} 1370 _LIBCPP_INLINE_VISIBILITY 1371 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1372#if _LIBCPP_STD_VER > 11 1373 template <typename _K2> 1374 _LIBCPP_INLINE_VISIBILITY 1375 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1376 find(const _K2& __k) {return __tree_.find(__k);} 1377 template <typename _K2> 1378 _LIBCPP_INLINE_VISIBILITY 1379 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1380 find(const _K2& __k) const {return __tree_.find(__k);} 1381#endif 1382 1383 _LIBCPP_INLINE_VISIBILITY 1384 size_type count(const key_type& __k) const 1385 {return __tree_.__count_multi(__k);} 1386#if _LIBCPP_STD_VER > 11 1387 template <typename _K2> 1388 _LIBCPP_INLINE_VISIBILITY 1389 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1390 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1391#endif 1392 1393#if _LIBCPP_STD_VER > 17 1394 _LIBCPP_INLINE_VISIBILITY 1395 bool contains(const key_type& __k) const {return find(__k) != end();} 1396 template <typename _K2> 1397 _LIBCPP_INLINE_VISIBILITY 1398 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 1399 contains(const _K2& __k) const { return find(__k) != end(); } 1400#endif // _LIBCPP_STD_VER > 17 1401 1402 _LIBCPP_INLINE_VISIBILITY 1403 iterator lower_bound(const key_type& __k) 1404 {return __tree_.lower_bound(__k);} 1405 _LIBCPP_INLINE_VISIBILITY 1406 const_iterator lower_bound(const key_type& __k) const 1407 {return __tree_.lower_bound(__k);} 1408#if _LIBCPP_STD_VER > 11 1409 template <typename _K2> 1410 _LIBCPP_INLINE_VISIBILITY 1411 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1412 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1413 1414 template <typename _K2> 1415 _LIBCPP_INLINE_VISIBILITY 1416 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1417 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1418#endif 1419 1420 _LIBCPP_INLINE_VISIBILITY 1421 iterator upper_bound(const key_type& __k) 1422 {return __tree_.upper_bound(__k);} 1423 _LIBCPP_INLINE_VISIBILITY 1424 const_iterator upper_bound(const key_type& __k) const 1425 {return __tree_.upper_bound(__k);} 1426#if _LIBCPP_STD_VER > 11 1427 template <typename _K2> 1428 _LIBCPP_INLINE_VISIBILITY 1429 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 1430 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1431 template <typename _K2> 1432 _LIBCPP_INLINE_VISIBILITY 1433 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 1434 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1435#endif 1436 1437 _LIBCPP_INLINE_VISIBILITY 1438 pair<iterator,iterator> equal_range(const key_type& __k) 1439 {return __tree_.__equal_range_multi(__k);} 1440 _LIBCPP_INLINE_VISIBILITY 1441 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1442 {return __tree_.__equal_range_multi(__k);} 1443#if _LIBCPP_STD_VER > 11 1444 template <typename _K2> 1445 _LIBCPP_INLINE_VISIBILITY 1446 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1447 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1448 template <typename _K2> 1449 _LIBCPP_INLINE_VISIBILITY 1450 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1451 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1452#endif 1453}; 1454 1455#if _LIBCPP_STD_VER >= 17 1456template<class _InputIterator, 1457 class _Compare = less<__iter_value_type<_InputIterator>>, 1458 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 1459 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 1460 class = enable_if_t<__is_allocator<_Allocator>::value, void>, 1461 class = enable_if_t<!__is_allocator<_Compare>::value, void>> 1462multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1463 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 1464 1465template<class _Key, class _Compare = less<_Key>, 1466 class _Allocator = allocator<_Key>, 1467 class = enable_if_t<__is_allocator<_Allocator>::value, void>, 1468 class = enable_if_t<!__is_allocator<_Compare>::value, void>> 1469multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 1470 -> multiset<_Key, _Compare, _Allocator>; 1471 1472template<class _InputIterator, class _Allocator, 1473 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 1474 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1475multiset(_InputIterator, _InputIterator, _Allocator) 1476 -> multiset<__iter_value_type<_InputIterator>, 1477 less<__iter_value_type<_InputIterator>>, _Allocator>; 1478 1479template<class _Key, class _Allocator, 1480 class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1481multiset(initializer_list<_Key>, _Allocator) 1482 -> multiset<_Key, less<_Key>, _Allocator>; 1483#endif 1484 1485#ifndef _LIBCPP_CXX03_LANG 1486 1487template <class _Key, class _Compare, class _Allocator> 1488multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1489 : __tree_(_VSTD::move(__s.__tree_), __a) 1490{ 1491 if (__a != __s.get_allocator()) 1492 { 1493 const_iterator __e = cend(); 1494 while (!__s.empty()) 1495 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1496 } 1497} 1498 1499#endif // _LIBCPP_CXX03_LANG 1500 1501template <class _Key, class _Compare, class _Allocator> 1502inline _LIBCPP_INLINE_VISIBILITY 1503bool 1504operator==(const multiset<_Key, _Compare, _Allocator>& __x, 1505 const multiset<_Key, _Compare, _Allocator>& __y) 1506{ 1507 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1508} 1509 1510template <class _Key, class _Compare, class _Allocator> 1511inline _LIBCPP_INLINE_VISIBILITY 1512bool 1513operator< (const multiset<_Key, _Compare, _Allocator>& __x, 1514 const multiset<_Key, _Compare, _Allocator>& __y) 1515{ 1516 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1517} 1518 1519template <class _Key, class _Compare, class _Allocator> 1520inline _LIBCPP_INLINE_VISIBILITY 1521bool 1522operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1523 const multiset<_Key, _Compare, _Allocator>& __y) 1524{ 1525 return !(__x == __y); 1526} 1527 1528template <class _Key, class _Compare, class _Allocator> 1529inline _LIBCPP_INLINE_VISIBILITY 1530bool 1531operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1532 const multiset<_Key, _Compare, _Allocator>& __y) 1533{ 1534 return __y < __x; 1535} 1536 1537template <class _Key, class _Compare, class _Allocator> 1538inline _LIBCPP_INLINE_VISIBILITY 1539bool 1540operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1541 const multiset<_Key, _Compare, _Allocator>& __y) 1542{ 1543 return !(__x < __y); 1544} 1545 1546template <class _Key, class _Compare, class _Allocator> 1547inline _LIBCPP_INLINE_VISIBILITY 1548bool 1549operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1550 const multiset<_Key, _Compare, _Allocator>& __y) 1551{ 1552 return !(__y < __x); 1553} 1554 1555template <class _Key, class _Compare, class _Allocator> 1556inline _LIBCPP_INLINE_VISIBILITY 1557void 1558swap(multiset<_Key, _Compare, _Allocator>& __x, 1559 multiset<_Key, _Compare, _Allocator>& __y) 1560 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1561{ 1562 __x.swap(__y); 1563} 1564 1565#if _LIBCPP_STD_VER > 17 1566template <class _Key, class _Compare, class _Allocator, class _Predicate> 1567inline _LIBCPP_INLINE_VISIBILITY 1568 typename multiset<_Key, _Compare, _Allocator>::size_type 1569 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 1570 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1571} 1572#endif 1573 1574_LIBCPP_END_NAMESPACE_STD 1575 1576#endif // _LIBCPP_SET 1577