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