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