set revision 360784
113547Sjulian// -*- C++ -*- 213547Sjulian//===---------------------------- set -------------------------------------===// 313547Sjulian// 413547Sjulian// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 513547Sjulian// See https://llvm.org/LICENSE.txt for license information. 613547Sjulian// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 713547Sjulian// 813547Sjulian//===----------------------------------------------------------------------===// 913547Sjulian 1013547Sjulian#ifndef _LIBCPP_SET 1113547Sjulian#define _LIBCPP_SET 1213547Sjulian 1313547Sjulian/* 1413547Sjulian 1513547Sjulian set synopsis 1613547Sjulian 1713547Sjuliannamespace std 1813547Sjulian{ 1913547Sjulian 2013547Sjuliantemplate <class Key, class Compare = less<Key>, 2113547Sjulian class Allocator = allocator<Key>> 2213547Sjulianclass set 2313547Sjulian{ 2413547Sjulianpublic: 2513547Sjulian // types: 2613547Sjulian typedef Key key_type; 2713547Sjulian typedef key_type value_type; 2813547Sjulian typedef Compare key_compare; 2913547Sjulian typedef key_compare value_compare; 3013547Sjulian typedef Allocator allocator_type; 3113547Sjulian typedef typename allocator_type::reference reference; 3213547Sjulian typedef typename allocator_type::const_reference const_reference; 3313547Sjulian typedef typename allocator_type::size_type size_type; 3413547Sjulian typedef typename allocator_type::difference_type difference_type; 3513547Sjulian typedef typename allocator_type::pointer pointer; 3613547Sjulian typedef typename allocator_type::const_pointer const_pointer; 3713547Sjulian 3813547Sjulian typedef implementation-defined iterator; 3913547Sjulian typedef implementation-defined const_iterator; 4013547Sjulian typedef std::reverse_iterator<iterator> reverse_iterator; 4113547Sjulian typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 4213547Sjulian typedef unspecified node_type; // C++17 4317706Sjulian typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 4417706Sjulian 4513547Sjulian // construct/copy/destroy: 4613547Sjulian set() 4717706Sjulian noexcept( 4813547Sjulian is_nothrow_default_constructible<allocator_type>::value && 4917706Sjulian is_nothrow_default_constructible<key_compare>::value && 5017706Sjulian is_nothrow_copy_constructible<key_compare>::value); 5117706Sjulian explicit set(const value_compare& comp); 5217706Sjulian set(const value_compare& comp, const allocator_type& a); 5313547Sjulian template <class InputIterator> 5413547Sjulian set(InputIterator first, InputIterator last, 5517706Sjulian const value_compare& comp = value_compare()); 5617706Sjulian template <class InputIterator> 5717706Sjulian set(InputIterator first, InputIterator last, const value_compare& comp, 5817706Sjulian const allocator_type& a); 5913547Sjulian set(const set& s); 6017706Sjulian set(set&& s) 6117706Sjulian noexcept( 6217706Sjulian is_nothrow_move_constructible<allocator_type>::value && 6317706Sjulian is_nothrow_move_constructible<key_compare>::value); 6417706Sjulian explicit set(const allocator_type& a); 6517706Sjulian set(const set& s, const allocator_type& a); 6617706Sjulian set(set&& s, const allocator_type& a); 6717706Sjulian set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 6813547Sjulian set(initializer_list<value_type> il, const value_compare& comp, 6913547Sjulian const allocator_type& a); 7022315Sjulian template <class InputIterator> 7122315Sjulian set(InputIterator first, InputIterator last, const allocator_type& a) 7222315Sjulian : set(first, last, Compare(), a) {} // C++14 7322315Sjulian set(initializer_list<value_type> il, const allocator_type& a) 7422315Sjulian : set(il, Compare(), a) {} // C++14 7522315Sjulian ~set(); 7622315Sjulian 7722315Sjulian set& operator=(const set& s); 7822315Sjulian set& operator=(set&& s) 7922315Sjulian noexcept( 8022315Sjulian allocator_type::propagate_on_container_move_assignment::value && 8122315Sjulian is_nothrow_move_assignable<allocator_type>::value && 8222315Sjulian is_nothrow_move_assignable<key_compare>::value); 8317706Sjulian set& operator=(initializer_list<value_type> il); 8417706Sjulian 8517706Sjulian // iterators: 8613547Sjulian iterator begin() noexcept; 8717706Sjulian const_iterator begin() const noexcept; 8817706Sjulian iterator end() noexcept; 8917706Sjulian const_iterator end() const noexcept; 9017706Sjulian 9117706Sjulian reverse_iterator rbegin() noexcept; 9217706Sjulian const_reverse_iterator rbegin() const noexcept; 9317706Sjulian reverse_iterator rend() noexcept; 9417706Sjulian const_reverse_iterator rend() const noexcept; 9513547Sjulian 9613547Sjulian const_iterator cbegin() const noexcept; 9717706Sjulian const_iterator cend() const noexcept; 9817706Sjulian const_reverse_iterator crbegin() const noexcept; 9917706Sjulian const_reverse_iterator crend() const noexcept; 10017706Sjulian 10117706Sjulian // capacity: 10213547Sjulian bool empty() const noexcept; 10317706Sjulian size_type size() const noexcept; 10417706Sjulian size_type max_size() const noexcept; 10517706Sjulian 10617706Sjulian // modifiers: 10717706Sjulian template <class... Args> 10817706Sjulian pair<iterator, bool> emplace(Args&&... args); 10917706Sjulian template <class... Args> 11017706Sjulian iterator emplace_hint(const_iterator position, Args&&... args); 11113547Sjulian pair<iterator,bool> insert(const value_type& v); 11213547Sjulian pair<iterator,bool> insert(value_type&& v); 11317706Sjulian iterator insert(const_iterator position, const value_type& v); 11417706Sjulian iterator insert(const_iterator position, value_type&& v); 11517706Sjulian template <class InputIterator> 11617706Sjulian void insert(InputIterator first, InputIterator last); 11713547Sjulian void insert(initializer_list<value_type> il); 11817706Sjulian 11917706Sjulian node_type extract(const_iterator position); // C++17 12013547Sjulian node_type extract(const key_type& x); // C++17 12113547Sjulian insert_return_type insert(node_type&& nh); // C++17 12213547Sjulian iterator insert(const_iterator hint, node_type&& nh); // C++17 12313547Sjulian 12413547Sjulian iterator erase(const_iterator position); 12517706Sjulian iterator erase(iterator position); // C++14 12617706Sjulian size_type erase(const key_type& k); 12713547Sjulian iterator erase(const_iterator first, const_iterator last); 12813547Sjulian void clear() noexcept; 12913547Sjulian 13013547Sjulian template<class C2> 13113547Sjulian void merge(set<Key, C2, Allocator>& source); // C++17 13213547Sjulian template<class C2> 13313547Sjulian void merge(set<Key, C2, Allocator>&& source); // C++17 13413547Sjulian template<class C2> 13513547Sjulian void merge(multiset<Key, C2, Allocator>& source); // C++17 13613547Sjulian template<class C2> 13713547Sjulian void merge(multiset<Key, C2, Allocator>&& source); // C++17 13817706Sjulian 13913547Sjulian void swap(set& s) 14013547Sjulian noexcept( 14113547Sjulian __is_nothrow_swappable<key_compare>::value && 14213547Sjulian (!allocator_type::propagate_on_container_swap::value || 14322315Sjulian __is_nothrow_swappable<allocator_type>::value)); 14413547Sjulian 14513547Sjulian // observers: 14613547Sjulian allocator_type get_allocator() const noexcept; 14713547Sjulian key_compare key_comp() const; 14813547Sjulian value_compare value_comp() const; 14919637Shsu 15019637Shsu // set operations: 15119637Shsu iterator find(const key_type& k); 15219637Shsu const_iterator find(const key_type& k) const; 15319637Shsu template<typename K> 15419637Shsu iterator find(const K& x); 15513547Sjulian template<typename K> 15613547Sjulian const_iterator find(const K& x) const; // C++14 15713547Sjulian template<typename K> 15813547Sjulian size_type count(const K& x) const; // C++14 15917706Sjulian size_type count(const key_type& k) const; 16017706Sjulian bool contains(const key_type& x) const; // C++20 16117706Sjulian iterator lower_bound(const key_type& k); 16217706Sjulian const_iterator lower_bound(const key_type& k) const; 16317706Sjulian template<typename K> 16417706Sjulian iterator lower_bound(const K& x); // C++14 16517706Sjulian template<typename K> 16617706Sjulian const_iterator lower_bound(const K& x) const; // C++14 16717706Sjulian 16817706Sjulian iterator upper_bound(const key_type& k); 16917706Sjulian const_iterator upper_bound(const key_type& k) const; 17017706Sjulian template<typename K> 17117706Sjulian iterator upper_bound(const K& x); // C++14 17217706Sjulian template<typename K> 17317706Sjulian const_iterator upper_bound(const K& x) const; // C++14 17417706Sjulian pair<iterator,iterator> equal_range(const key_type& k); 17517706Sjulian pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 17617706Sjulian template<typename K> 17717706Sjulian pair<iterator,iterator> equal_range(const K& x); // C++14 17822315Sjulian template<typename K> 17917706Sjulian pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 18017706Sjulian}; 18117706Sjulian 18217706Sjuliantemplate <class Key, class Compare, class Allocator> 18317706Sjulianbool 18417706Sjulianoperator==(const set<Key, Compare, Allocator>& x, 18517706Sjulian const set<Key, Compare, Allocator>& y); 18617706Sjulian 18717706Sjuliantemplate <class Key, class Compare, class Allocator> 18817706Sjulianbool 18917706Sjulianoperator< (const set<Key, Compare, Allocator>& x, 19017706Sjulian const set<Key, Compare, Allocator>& y); 19117706Sjulian 19217706Sjuliantemplate <class Key, class Compare, class Allocator> 19317706Sjulianbool 19417706Sjulianoperator!=(const set<Key, Compare, Allocator>& x, 19517706Sjulian const set<Key, Compare, Allocator>& y); 19617706Sjulian 19717706Sjuliantemplate <class Key, class Compare, class Allocator> 19817706Sjulianbool 19919637Shsuoperator> (const set<Key, Compare, Allocator>& x, 20017706Sjulian const set<Key, Compare, Allocator>& y); 20117706Sjulian 20217706Sjuliantemplate <class Key, class Compare, class Allocator> 20317706Sjulianbool 20417706Sjulianoperator>=(const set<Key, Compare, Allocator>& x, 20517706Sjulian const set<Key, Compare, Allocator>& y); 20617706Sjulian 20717706Sjuliantemplate <class Key, class Compare, class Allocator> 20817706Sjulianbool 20917706Sjulianoperator<=(const set<Key, Compare, Allocator>& x, 21017706Sjulian const set<Key, Compare, Allocator>& y); 21117706Sjulian 21217706Sjulian// specialized algorithms: 21317706Sjuliantemplate <class Key, class Compare, class Allocator> 21417706Sjulianvoid 21517706Sjulianswap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 21617706Sjulian noexcept(noexcept(x.swap(y))); 21717706Sjulian 21817706Sjuliantemplate <class Key, class Compare, class Allocator, class Predicate> 21917706Sjulian void erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20 22017706Sjulian 22117706Sjuliantemplate <class Key, class Compare = less<Key>, 22217706Sjulian class Allocator = allocator<Key>> 22317706Sjulianclass multiset 22417706Sjulian{ 22517706Sjulianpublic: 22617706Sjulian // types: 22717706Sjulian typedef Key key_type; 22817706Sjulian typedef key_type value_type; 22917706Sjulian typedef Compare key_compare; 23017706Sjulian typedef key_compare value_compare; 23117706Sjulian typedef Allocator allocator_type; 23217706Sjulian typedef typename allocator_type::reference reference; 23317706Sjulian typedef typename allocator_type::const_reference const_reference; 23417706Sjulian typedef typename allocator_type::size_type size_type; 23517706Sjulian typedef typename allocator_type::difference_type difference_type; 23617706Sjulian typedef typename allocator_type::pointer pointer; 23717706Sjulian typedef typename allocator_type::const_pointer const_pointer; 23817706Sjulian 23917706Sjulian typedef implementation-defined iterator; 24017706Sjulian typedef implementation-defined const_iterator; 24117706Sjulian typedef std::reverse_iterator<iterator> reverse_iterator; 24217706Sjulian typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 24317706Sjulian typedef unspecified node_type; // C++17 24417706Sjulian 24517706Sjulian // construct/copy/destroy: 24617706Sjulian multiset() 24717706Sjulian noexcept( 24813547Sjulian is_nothrow_default_constructible<allocator_type>::value && 24913547Sjulian is_nothrow_default_constructible<key_compare>::value && 25013547Sjulian 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 template<typename K> 358 size_type count(const K& x) const; // C++14 359 size_type count(const key_type& k) const; 360 bool contains(const key_type& x) const; // C++20 361 iterator lower_bound(const key_type& k); 362 const_iterator lower_bound(const key_type& k) const; 363 template<typename K> 364 iterator lower_bound(const K& x); // C++14 365 template<typename K> 366 const_iterator lower_bound(const K& x) const; // C++14 367 368 iterator upper_bound(const key_type& k); 369 const_iterator upper_bound(const key_type& k) const; 370 template<typename K> 371 iterator upper_bound(const K& x); // C++14 372 template<typename K> 373 const_iterator upper_bound(const K& x) const; // C++14 374 375 pair<iterator,iterator> equal_range(const key_type& k); 376 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 377 template<typename K> 378 pair<iterator,iterator> equal_range(const K& x); // C++14 379 template<typename K> 380 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 381}; 382 383template <class Key, class Compare, class Allocator> 384bool 385operator==(const multiset<Key, Compare, Allocator>& x, 386 const multiset<Key, Compare, Allocator>& y); 387 388template <class Key, class Compare, class Allocator> 389bool 390operator< (const multiset<Key, Compare, Allocator>& x, 391 const multiset<Key, Compare, Allocator>& y); 392 393template <class Key, class Compare, class Allocator> 394bool 395operator!=(const multiset<Key, Compare, Allocator>& x, 396 const multiset<Key, Compare, Allocator>& y); 397 398template <class Key, class Compare, class Allocator> 399bool 400operator> (const multiset<Key, Compare, Allocator>& x, 401 const multiset<Key, Compare, Allocator>& y); 402 403template <class Key, class Compare, class Allocator> 404bool 405operator>=(const multiset<Key, Compare, Allocator>& x, 406 const multiset<Key, Compare, Allocator>& y); 407 408template <class Key, class Compare, class Allocator> 409bool 410operator<=(const multiset<Key, Compare, Allocator>& x, 411 const multiset<Key, Compare, Allocator>& y); 412 413// specialized algorithms: 414template <class Key, class Compare, class Allocator> 415void 416swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 417 noexcept(noexcept(x.swap(y))); 418 419template <class Key, class Compare, class Allocator, class Predicate> 420 void erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20 421 422} // std 423 424*/ 425 426#include <__config> 427#include <__tree> 428#include <__node_handle> 429#include <functional> 430#include <version> 431 432#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 433#pragma GCC system_header 434#endif 435 436_LIBCPP_BEGIN_NAMESPACE_STD 437 438template <class _Key, class _Compare, class _Allocator> 439class multiset; 440 441template <class _Key, class _Compare = less<_Key>, 442 class _Allocator = allocator<_Key> > 443class _LIBCPP_TEMPLATE_VIS set 444{ 445public: 446 // types: 447 typedef _Key key_type; 448 typedef key_type value_type; 449 typedef _Compare key_compare; 450 typedef key_compare value_compare; 451 typedef typename __identity<_Allocator>::type allocator_type; 452 typedef value_type& reference; 453 typedef const value_type& const_reference; 454 455 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 456 "Allocator::value_type must be same type as value_type"); 457 458private: 459 typedef __tree<value_type, value_compare, allocator_type> __base; 460 typedef allocator_traits<allocator_type> __alloc_traits; 461 typedef typename __base::__node_holder __node_holder; 462 463 __base __tree_; 464 465public: 466 typedef typename __base::pointer pointer; 467 typedef typename __base::const_pointer const_pointer; 468 typedef typename __base::size_type size_type; 469 typedef typename __base::difference_type difference_type; 470 typedef typename __base::const_iterator iterator; 471 typedef typename __base::const_iterator const_iterator; 472 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 473 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 474 475#if _LIBCPP_STD_VER > 14 476 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 477 typedef __insert_return_type<iterator, node_type> insert_return_type; 478#endif 479 480 template <class _Key2, class _Compare2, class _Alloc2> 481 friend class _LIBCPP_TEMPLATE_VIS set; 482 template <class _Key2, class _Compare2, class _Alloc2> 483 friend class _LIBCPP_TEMPLATE_VIS multiset; 484 485 _LIBCPP_INLINE_VISIBILITY 486 set() 487 _NOEXCEPT_( 488 is_nothrow_default_constructible<allocator_type>::value && 489 is_nothrow_default_constructible<key_compare>::value && 490 is_nothrow_copy_constructible<key_compare>::value) 491 : __tree_(value_compare()) {} 492 493 _LIBCPP_INLINE_VISIBILITY 494 explicit set(const value_compare& __comp) 495 _NOEXCEPT_( 496 is_nothrow_default_constructible<allocator_type>::value && 497 is_nothrow_copy_constructible<key_compare>::value) 498 : __tree_(__comp) {} 499 500 _LIBCPP_INLINE_VISIBILITY 501 explicit set(const value_compare& __comp, const allocator_type& __a) 502 : __tree_(__comp, __a) {} 503 template <class _InputIterator> 504 _LIBCPP_INLINE_VISIBILITY 505 set(_InputIterator __f, _InputIterator __l, 506 const value_compare& __comp = value_compare()) 507 : __tree_(__comp) 508 { 509 insert(__f, __l); 510 } 511 512 template <class _InputIterator> 513 _LIBCPP_INLINE_VISIBILITY 514 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 515 const allocator_type& __a) 516 : __tree_(__comp, __a) 517 { 518 insert(__f, __l); 519 } 520 521#if _LIBCPP_STD_VER > 11 522 template <class _InputIterator> 523 _LIBCPP_INLINE_VISIBILITY 524 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 525 : set(__f, __l, key_compare(), __a) {} 526#endif 527 528 _LIBCPP_INLINE_VISIBILITY 529 set(const set& __s) 530 : __tree_(__s.__tree_) 531 { 532 insert(__s.begin(), __s.end()); 533 } 534 535 _LIBCPP_INLINE_VISIBILITY 536 set& operator=(const set& __s) 537 { 538 __tree_ = __s.__tree_; 539 return *this; 540 } 541 542#ifndef _LIBCPP_CXX03_LANG 543 _LIBCPP_INLINE_VISIBILITY 544 set(set&& __s) 545 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 546 : __tree_(_VSTD::move(__s.__tree_)) {} 547#endif // _LIBCPP_CXX03_LANG 548 549 _LIBCPP_INLINE_VISIBILITY 550 explicit set(const allocator_type& __a) 551 : __tree_(__a) {} 552 553 _LIBCPP_INLINE_VISIBILITY 554 set(const set& __s, const allocator_type& __a) 555 : __tree_(__s.__tree_.value_comp(), __a) 556 { 557 insert(__s.begin(), __s.end()); 558 } 559 560#ifndef _LIBCPP_CXX03_LANG 561 set(set&& __s, const allocator_type& __a); 562 563 _LIBCPP_INLINE_VISIBILITY 564 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 565 : __tree_(__comp) 566 { 567 insert(__il.begin(), __il.end()); 568 } 569 570 _LIBCPP_INLINE_VISIBILITY 571 set(initializer_list<value_type> __il, const value_compare& __comp, 572 const allocator_type& __a) 573 : __tree_(__comp, __a) 574 { 575 insert(__il.begin(), __il.end()); 576 } 577 578#if _LIBCPP_STD_VER > 11 579 _LIBCPP_INLINE_VISIBILITY 580 set(initializer_list<value_type> __il, const allocator_type& __a) 581 : set(__il, key_compare(), __a) {} 582#endif 583 584 _LIBCPP_INLINE_VISIBILITY 585 set& operator=(initializer_list<value_type> __il) 586 { 587 __tree_.__assign_unique(__il.begin(), __il.end()); 588 return *this; 589 } 590 591 _LIBCPP_INLINE_VISIBILITY 592 set& operator=(set&& __s) 593 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 594 { 595 __tree_ = _VSTD::move(__s.__tree_); 596 return *this; 597 } 598#endif // _LIBCPP_CXX03_LANG 599 600 _LIBCPP_INLINE_VISIBILITY 601 ~set() { 602 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 603 } 604 605 _LIBCPP_INLINE_VISIBILITY 606 iterator begin() _NOEXCEPT {return __tree_.begin();} 607 _LIBCPP_INLINE_VISIBILITY 608 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 609 _LIBCPP_INLINE_VISIBILITY 610 iterator end() _NOEXCEPT {return __tree_.end();} 611 _LIBCPP_INLINE_VISIBILITY 612 const_iterator end() const _NOEXCEPT {return __tree_.end();} 613 614 _LIBCPP_INLINE_VISIBILITY 615 reverse_iterator rbegin() _NOEXCEPT 616 {return reverse_iterator(end());} 617 _LIBCPP_INLINE_VISIBILITY 618 const_reverse_iterator rbegin() const _NOEXCEPT 619 {return const_reverse_iterator(end());} 620 _LIBCPP_INLINE_VISIBILITY 621 reverse_iterator rend() _NOEXCEPT 622 {return reverse_iterator(begin());} 623 _LIBCPP_INLINE_VISIBILITY 624 const_reverse_iterator rend() const _NOEXCEPT 625 {return const_reverse_iterator(begin());} 626 627 _LIBCPP_INLINE_VISIBILITY 628 const_iterator cbegin() const _NOEXCEPT {return begin();} 629 _LIBCPP_INLINE_VISIBILITY 630 const_iterator cend() const _NOEXCEPT {return end();} 631 _LIBCPP_INLINE_VISIBILITY 632 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 633 _LIBCPP_INLINE_VISIBILITY 634 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 635 636 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 637 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 638 _LIBCPP_INLINE_VISIBILITY 639 size_type size() const _NOEXCEPT {return __tree_.size();} 640 _LIBCPP_INLINE_VISIBILITY 641 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 642 643 // modifiers: 644#ifndef _LIBCPP_CXX03_LANG 645 template <class... _Args> 646 _LIBCPP_INLINE_VISIBILITY 647 pair<iterator, bool> emplace(_Args&&... __args) 648 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 649 template <class... _Args> 650 _LIBCPP_INLINE_VISIBILITY 651 iterator emplace_hint(const_iterator __p, _Args&&... __args) 652 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 653#endif // _LIBCPP_CXX03_LANG 654 655 _LIBCPP_INLINE_VISIBILITY 656 pair<iterator,bool> insert(const value_type& __v) 657 {return __tree_.__insert_unique(__v);} 658 _LIBCPP_INLINE_VISIBILITY 659 iterator insert(const_iterator __p, const value_type& __v) 660 {return __tree_.__insert_unique(__p, __v);} 661 662 template <class _InputIterator> 663 _LIBCPP_INLINE_VISIBILITY 664 void insert(_InputIterator __f, _InputIterator __l) 665 { 666 for (const_iterator __e = cend(); __f != __l; ++__f) 667 __tree_.__insert_unique(__e, *__f); 668 } 669 670#ifndef _LIBCPP_CXX03_LANG 671 _LIBCPP_INLINE_VISIBILITY 672 pair<iterator,bool> insert(value_type&& __v) 673 {return __tree_.__insert_unique(_VSTD::move(__v));} 674 675 _LIBCPP_INLINE_VISIBILITY 676 iterator insert(const_iterator __p, value_type&& __v) 677 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 678 679 _LIBCPP_INLINE_VISIBILITY 680 void insert(initializer_list<value_type> __il) 681 {insert(__il.begin(), __il.end());} 682#endif // _LIBCPP_CXX03_LANG 683 684 _LIBCPP_INLINE_VISIBILITY 685 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 686 _LIBCPP_INLINE_VISIBILITY 687 size_type erase(const key_type& __k) 688 {return __tree_.__erase_unique(__k);} 689 _LIBCPP_INLINE_VISIBILITY 690 iterator erase(const_iterator __f, const_iterator __l) 691 {return __tree_.erase(__f, __l);} 692 _LIBCPP_INLINE_VISIBILITY 693 void clear() _NOEXCEPT {__tree_.clear();} 694 695#if _LIBCPP_STD_VER > 14 696 _LIBCPP_INLINE_VISIBILITY 697 insert_return_type insert(node_type&& __nh) 698 { 699 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 700 "node_type with incompatible allocator passed to set::insert()"); 701 return __tree_.template __node_handle_insert_unique< 702 node_type, insert_return_type>(_VSTD::move(__nh)); 703 } 704 _LIBCPP_INLINE_VISIBILITY 705 iterator insert(const_iterator __hint, node_type&& __nh) 706 { 707 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 708 "node_type with incompatible allocator passed to set::insert()"); 709 return __tree_.template __node_handle_insert_unique<node_type>( 710 __hint, _VSTD::move(__nh)); 711 } 712 _LIBCPP_INLINE_VISIBILITY 713 node_type extract(key_type const& __key) 714 { 715 return __tree_.template __node_handle_extract<node_type>(__key); 716 } 717 _LIBCPP_INLINE_VISIBILITY 718 node_type extract(const_iterator __it) 719 { 720 return __tree_.template __node_handle_extract<node_type>(__it); 721 } 722 template <class _Compare2> 723 _LIBCPP_INLINE_VISIBILITY 724 void merge(set<key_type, _Compare2, allocator_type>& __source) 725 { 726 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 727 "merging container with incompatible allocator"); 728 __tree_.__node_handle_merge_unique(__source.__tree_); 729 } 730 template <class _Compare2> 731 _LIBCPP_INLINE_VISIBILITY 732 void merge(set<key_type, _Compare2, allocator_type>&& __source) 733 { 734 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 735 "merging container with incompatible allocator"); 736 __tree_.__node_handle_merge_unique(__source.__tree_); 737 } 738 template <class _Compare2> 739 _LIBCPP_INLINE_VISIBILITY 740 void merge(multiset<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(multiset<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#endif 755 756 _LIBCPP_INLINE_VISIBILITY 757 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 758 {__tree_.swap(__s.__tree_);} 759 760 _LIBCPP_INLINE_VISIBILITY 761 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 762 _LIBCPP_INLINE_VISIBILITY 763 key_compare key_comp() const {return __tree_.value_comp();} 764 _LIBCPP_INLINE_VISIBILITY 765 value_compare value_comp() const {return __tree_.value_comp();} 766 767 // set operations: 768 _LIBCPP_INLINE_VISIBILITY 769 iterator find(const key_type& __k) {return __tree_.find(__k);} 770 _LIBCPP_INLINE_VISIBILITY 771 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 772#if _LIBCPP_STD_VER > 11 773 template <typename _K2> 774 _LIBCPP_INLINE_VISIBILITY 775 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 776 find(const _K2& __k) {return __tree_.find(__k);} 777 template <typename _K2> 778 _LIBCPP_INLINE_VISIBILITY 779 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 780 find(const _K2& __k) const {return __tree_.find(__k);} 781#endif 782 783 _LIBCPP_INLINE_VISIBILITY 784 size_type count(const key_type& __k) const 785 {return __tree_.__count_unique(__k);} 786#if _LIBCPP_STD_VER > 11 787 template <typename _K2> 788 _LIBCPP_INLINE_VISIBILITY 789 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 790 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 791#endif 792 793#if _LIBCPP_STD_VER > 17 794 _LIBCPP_INLINE_VISIBILITY 795 bool contains(const key_type& __k) const {return find(__k) != end();} 796#endif // _LIBCPP_STD_VER > 17 797 798 _LIBCPP_INLINE_VISIBILITY 799 iterator lower_bound(const key_type& __k) 800 {return __tree_.lower_bound(__k);} 801 _LIBCPP_INLINE_VISIBILITY 802 const_iterator lower_bound(const key_type& __k) const 803 {return __tree_.lower_bound(__k);} 804#if _LIBCPP_STD_VER > 11 805 template <typename _K2> 806 _LIBCPP_INLINE_VISIBILITY 807 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 808 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 809 810 template <typename _K2> 811 _LIBCPP_INLINE_VISIBILITY 812 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 813 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 814#endif 815 816 _LIBCPP_INLINE_VISIBILITY 817 iterator upper_bound(const key_type& __k) 818 {return __tree_.upper_bound(__k);} 819 _LIBCPP_INLINE_VISIBILITY 820 const_iterator upper_bound(const key_type& __k) const 821 {return __tree_.upper_bound(__k);} 822#if _LIBCPP_STD_VER > 11 823 template <typename _K2> 824 _LIBCPP_INLINE_VISIBILITY 825 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 826 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 827 template <typename _K2> 828 _LIBCPP_INLINE_VISIBILITY 829 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 830 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 831#endif 832 833 _LIBCPP_INLINE_VISIBILITY 834 pair<iterator,iterator> equal_range(const key_type& __k) 835 {return __tree_.__equal_range_unique(__k);} 836 _LIBCPP_INLINE_VISIBILITY 837 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 838 {return __tree_.__equal_range_unique(__k);} 839#if _LIBCPP_STD_VER > 11 840 template <typename _K2> 841 _LIBCPP_INLINE_VISIBILITY 842 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 843 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 844 template <typename _K2> 845 _LIBCPP_INLINE_VISIBILITY 846 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 847 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 848#endif 849}; 850 851#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 852template<class _InputIterator, 853 class _Compare = less<typename iterator_traits<_InputIterator>::value_type>, 854 class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>, 855 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 856 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 857set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 858 -> set<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>; 859 860template<class _Key, class _Compare = less<_Key>, 861 class _Allocator = allocator<_Key>, 862 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 863 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 864set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 865 -> set<_Key, _Compare, _Allocator>; 866 867template<class _InputIterator, class _Allocator, 868 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 869set(_InputIterator, _InputIterator, _Allocator) 870 -> set<typename iterator_traits<_InputIterator>::value_type, 871 less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>; 872 873template<class _Key, class _Allocator, 874 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 875set(initializer_list<_Key>, _Allocator) 876 -> set<_Key, less<_Key>, _Allocator>; 877#endif 878 879#ifndef _LIBCPP_CXX03_LANG 880 881template <class _Key, class _Compare, class _Allocator> 882set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 883 : __tree_(_VSTD::move(__s.__tree_), __a) 884{ 885 if (__a != __s.get_allocator()) 886 { 887 const_iterator __e = cend(); 888 while (!__s.empty()) 889 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 890 } 891} 892 893#endif // _LIBCPP_CXX03_LANG 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.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 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 _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 911} 912 913template <class _Key, class _Compare, class _Allocator> 914inline _LIBCPP_INLINE_VISIBILITY 915bool 916operator!=(const set<_Key, _Compare, _Allocator>& __x, 917 const set<_Key, _Compare, _Allocator>& __y) 918{ 919 return !(__x == __y); 920} 921 922template <class _Key, class _Compare, class _Allocator> 923inline _LIBCPP_INLINE_VISIBILITY 924bool 925operator> (const set<_Key, _Compare, _Allocator>& __x, 926 const set<_Key, _Compare, _Allocator>& __y) 927{ 928 return __y < __x; 929} 930 931template <class _Key, class _Compare, class _Allocator> 932inline _LIBCPP_INLINE_VISIBILITY 933bool 934operator>=(const set<_Key, _Compare, _Allocator>& __x, 935 const set<_Key, _Compare, _Allocator>& __y) 936{ 937 return !(__x < __y); 938} 939 940template <class _Key, class _Compare, class _Allocator> 941inline _LIBCPP_INLINE_VISIBILITY 942bool 943operator<=(const set<_Key, _Compare, _Allocator>& __x, 944 const set<_Key, _Compare, _Allocator>& __y) 945{ 946 return !(__y < __x); 947} 948 949// specialized algorithms: 950template <class _Key, class _Compare, class _Allocator> 951inline _LIBCPP_INLINE_VISIBILITY 952void 953swap(set<_Key, _Compare, _Allocator>& __x, 954 set<_Key, _Compare, _Allocator>& __y) 955 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 956{ 957 __x.swap(__y); 958} 959 960#if _LIBCPP_STD_VER > 17 961template <class _Key, class _Compare, class _Allocator, class _Predicate> 962inline _LIBCPP_INLINE_VISIBILITY 963void erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) 964{ __libcpp_erase_if_container(__c, __pred); } 965#endif 966 967template <class _Key, class _Compare = less<_Key>, 968 class _Allocator = allocator<_Key> > 969class _LIBCPP_TEMPLATE_VIS multiset 970{ 971public: 972 // types: 973 typedef _Key key_type; 974 typedef key_type value_type; 975 typedef _Compare key_compare; 976 typedef key_compare value_compare; 977 typedef typename __identity<_Allocator>::type allocator_type; 978 typedef value_type& reference; 979 typedef const value_type& const_reference; 980 981 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 982 "Allocator::value_type must be same type as value_type"); 983 984private: 985 typedef __tree<value_type, value_compare, allocator_type> __base; 986 typedef allocator_traits<allocator_type> __alloc_traits; 987 typedef typename __base::__node_holder __node_holder; 988 989 __base __tree_; 990 991public: 992 typedef typename __base::pointer pointer; 993 typedef typename __base::const_pointer const_pointer; 994 typedef typename __base::size_type size_type; 995 typedef typename __base::difference_type difference_type; 996 typedef typename __base::const_iterator iterator; 997 typedef typename __base::const_iterator const_iterator; 998 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 999 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1000 1001#if _LIBCPP_STD_VER > 14 1002 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 1003#endif 1004 1005 template <class _Key2, class _Compare2, class _Alloc2> 1006 friend class _LIBCPP_TEMPLATE_VIS set; 1007 template <class _Key2, class _Compare2, class _Alloc2> 1008 friend class _LIBCPP_TEMPLATE_VIS multiset; 1009 1010 // construct/copy/destroy: 1011 _LIBCPP_INLINE_VISIBILITY 1012 multiset() 1013 _NOEXCEPT_( 1014 is_nothrow_default_constructible<allocator_type>::value && 1015 is_nothrow_default_constructible<key_compare>::value && 1016 is_nothrow_copy_constructible<key_compare>::value) 1017 : __tree_(value_compare()) {} 1018 1019 _LIBCPP_INLINE_VISIBILITY 1020 explicit multiset(const value_compare& __comp) 1021 _NOEXCEPT_( 1022 is_nothrow_default_constructible<allocator_type>::value && 1023 is_nothrow_copy_constructible<key_compare>::value) 1024 : __tree_(__comp) {} 1025 1026 _LIBCPP_INLINE_VISIBILITY 1027 explicit multiset(const value_compare& __comp, const allocator_type& __a) 1028 : __tree_(__comp, __a) {} 1029 template <class _InputIterator> 1030 _LIBCPP_INLINE_VISIBILITY 1031 multiset(_InputIterator __f, _InputIterator __l, 1032 const value_compare& __comp = value_compare()) 1033 : __tree_(__comp) 1034 { 1035 insert(__f, __l); 1036 } 1037 1038#if _LIBCPP_STD_VER > 11 1039 template <class _InputIterator> 1040 _LIBCPP_INLINE_VISIBILITY 1041 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1042 : multiset(__f, __l, key_compare(), __a) {} 1043#endif 1044 1045 template <class _InputIterator> 1046 _LIBCPP_INLINE_VISIBILITY 1047 multiset(_InputIterator __f, _InputIterator __l, 1048 const value_compare& __comp, const allocator_type& __a) 1049 : __tree_(__comp, __a) 1050 { 1051 insert(__f, __l); 1052 } 1053 1054 _LIBCPP_INLINE_VISIBILITY 1055 multiset(const multiset& __s) 1056 : __tree_(__s.__tree_.value_comp(), 1057 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 1058 { 1059 insert(__s.begin(), __s.end()); 1060 } 1061 1062 _LIBCPP_INLINE_VISIBILITY 1063 multiset& operator=(const multiset& __s) 1064 { 1065 __tree_ = __s.__tree_; 1066 return *this; 1067 } 1068 1069#ifndef _LIBCPP_CXX03_LANG 1070 _LIBCPP_INLINE_VISIBILITY 1071 multiset(multiset&& __s) 1072 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1073 : __tree_(_VSTD::move(__s.__tree_)) {} 1074 1075 multiset(multiset&& __s, const allocator_type& __a); 1076#endif // _LIBCPP_CXX03_LANG 1077 _LIBCPP_INLINE_VISIBILITY 1078 explicit multiset(const allocator_type& __a) 1079 : __tree_(__a) {} 1080 _LIBCPP_INLINE_VISIBILITY 1081 multiset(const multiset& __s, const allocator_type& __a) 1082 : __tree_(__s.__tree_.value_comp(), __a) 1083 { 1084 insert(__s.begin(), __s.end()); 1085 } 1086 1087#ifndef _LIBCPP_CXX03_LANG 1088 _LIBCPP_INLINE_VISIBILITY 1089 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 1090 : __tree_(__comp) 1091 { 1092 insert(__il.begin(), __il.end()); 1093 } 1094 1095 _LIBCPP_INLINE_VISIBILITY 1096 multiset(initializer_list<value_type> __il, const value_compare& __comp, 1097 const allocator_type& __a) 1098 : __tree_(__comp, __a) 1099 { 1100 insert(__il.begin(), __il.end()); 1101 } 1102 1103#if _LIBCPP_STD_VER > 11 1104 _LIBCPP_INLINE_VISIBILITY 1105 multiset(initializer_list<value_type> __il, const allocator_type& __a) 1106 : multiset(__il, key_compare(), __a) {} 1107#endif 1108 1109 _LIBCPP_INLINE_VISIBILITY 1110 multiset& operator=(initializer_list<value_type> __il) 1111 { 1112 __tree_.__assign_multi(__il.begin(), __il.end()); 1113 return *this; 1114 } 1115 1116 _LIBCPP_INLINE_VISIBILITY 1117 multiset& operator=(multiset&& __s) 1118 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1119 { 1120 __tree_ = _VSTD::move(__s.__tree_); 1121 return *this; 1122 } 1123#endif // _LIBCPP_CXX03_LANG 1124 1125 _LIBCPP_INLINE_VISIBILITY 1126 ~multiset() { 1127 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1128 } 1129 1130 _LIBCPP_INLINE_VISIBILITY 1131 iterator begin() _NOEXCEPT {return __tree_.begin();} 1132 _LIBCPP_INLINE_VISIBILITY 1133 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1134 _LIBCPP_INLINE_VISIBILITY 1135 iterator end() _NOEXCEPT {return __tree_.end();} 1136 _LIBCPP_INLINE_VISIBILITY 1137 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1138 1139 _LIBCPP_INLINE_VISIBILITY 1140 reverse_iterator rbegin() _NOEXCEPT 1141 {return reverse_iterator(end());} 1142 _LIBCPP_INLINE_VISIBILITY 1143 const_reverse_iterator rbegin() const _NOEXCEPT 1144 {return const_reverse_iterator(end());} 1145 _LIBCPP_INLINE_VISIBILITY 1146 reverse_iterator rend() _NOEXCEPT 1147 {return reverse_iterator(begin());} 1148 _LIBCPP_INLINE_VISIBILITY 1149 const_reverse_iterator rend() const _NOEXCEPT 1150 {return const_reverse_iterator(begin());} 1151 1152 _LIBCPP_INLINE_VISIBILITY 1153 const_iterator cbegin() const _NOEXCEPT {return begin();} 1154 _LIBCPP_INLINE_VISIBILITY 1155 const_iterator cend() const _NOEXCEPT {return end();} 1156 _LIBCPP_INLINE_VISIBILITY 1157 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1158 _LIBCPP_INLINE_VISIBILITY 1159 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1160 1161 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1162 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1163 _LIBCPP_INLINE_VISIBILITY 1164 size_type size() const _NOEXCEPT {return __tree_.size();} 1165 _LIBCPP_INLINE_VISIBILITY 1166 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1167 1168 // modifiers: 1169#ifndef _LIBCPP_CXX03_LANG 1170 template <class... _Args> 1171 _LIBCPP_INLINE_VISIBILITY 1172 iterator emplace(_Args&&... __args) 1173 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1174 template <class... _Args> 1175 _LIBCPP_INLINE_VISIBILITY 1176 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1177 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1178#endif // _LIBCPP_CXX03_LANG 1179 1180 _LIBCPP_INLINE_VISIBILITY 1181 iterator insert(const value_type& __v) 1182 {return __tree_.__insert_multi(__v);} 1183 _LIBCPP_INLINE_VISIBILITY 1184 iterator insert(const_iterator __p, const value_type& __v) 1185 {return __tree_.__insert_multi(__p, __v);} 1186 1187 template <class _InputIterator> 1188 _LIBCPP_INLINE_VISIBILITY 1189 void insert(_InputIterator __f, _InputIterator __l) 1190 { 1191 for (const_iterator __e = cend(); __f != __l; ++__f) 1192 __tree_.__insert_multi(__e, *__f); 1193 } 1194 1195#ifndef _LIBCPP_CXX03_LANG 1196 _LIBCPP_INLINE_VISIBILITY 1197 iterator insert(value_type&& __v) 1198 {return __tree_.__insert_multi(_VSTD::move(__v));} 1199 1200 _LIBCPP_INLINE_VISIBILITY 1201 iterator insert(const_iterator __p, value_type&& __v) 1202 {return __tree_.__insert_multi(__p, _VSTD::move(__v));} 1203 1204 _LIBCPP_INLINE_VISIBILITY 1205 void insert(initializer_list<value_type> __il) 1206 {insert(__il.begin(), __il.end());} 1207#endif // _LIBCPP_CXX03_LANG 1208 1209 _LIBCPP_INLINE_VISIBILITY 1210 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1211 _LIBCPP_INLINE_VISIBILITY 1212 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1213 _LIBCPP_INLINE_VISIBILITY 1214 iterator erase(const_iterator __f, const_iterator __l) 1215 {return __tree_.erase(__f, __l);} 1216 _LIBCPP_INLINE_VISIBILITY 1217 void clear() _NOEXCEPT {__tree_.clear();} 1218 1219#if _LIBCPP_STD_VER > 14 1220 _LIBCPP_INLINE_VISIBILITY 1221 iterator insert(node_type&& __nh) 1222 { 1223 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1224 "node_type with incompatible allocator passed to multiset::insert()"); 1225 return __tree_.template __node_handle_insert_multi<node_type>( 1226 _VSTD::move(__nh)); 1227 } 1228 _LIBCPP_INLINE_VISIBILITY 1229 iterator insert(const_iterator __hint, node_type&& __nh) 1230 { 1231 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1232 "node_type with incompatible allocator passed to multiset::insert()"); 1233 return __tree_.template __node_handle_insert_multi<node_type>( 1234 __hint, _VSTD::move(__nh)); 1235 } 1236 _LIBCPP_INLINE_VISIBILITY 1237 node_type extract(key_type const& __key) 1238 { 1239 return __tree_.template __node_handle_extract<node_type>(__key); 1240 } 1241 _LIBCPP_INLINE_VISIBILITY 1242 node_type extract(const_iterator __it) 1243 { 1244 return __tree_.template __node_handle_extract<node_type>(__it); 1245 } 1246 template <class _Compare2> 1247 _LIBCPP_INLINE_VISIBILITY 1248 void merge(multiset<key_type, _Compare2, allocator_type>& __source) 1249 { 1250 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1251 "merging container with incompatible allocator"); 1252 __tree_.__node_handle_merge_multi(__source.__tree_); 1253 } 1254 template <class _Compare2> 1255 _LIBCPP_INLINE_VISIBILITY 1256 void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 1257 { 1258 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1259 "merging container with incompatible allocator"); 1260 __tree_.__node_handle_merge_multi(__source.__tree_); 1261 } 1262 template <class _Compare2> 1263 _LIBCPP_INLINE_VISIBILITY 1264 void merge(set<key_type, _Compare2, allocator_type>& __source) 1265 { 1266 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1267 "merging container with incompatible allocator"); 1268 __tree_.__node_handle_merge_multi(__source.__tree_); 1269 } 1270 template <class _Compare2> 1271 _LIBCPP_INLINE_VISIBILITY 1272 void merge(set<key_type, _Compare2, allocator_type>&& __source) 1273 { 1274 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1275 "merging container with incompatible allocator"); 1276 __tree_.__node_handle_merge_multi(__source.__tree_); 1277 } 1278#endif 1279 1280 _LIBCPP_INLINE_VISIBILITY 1281 void swap(multiset& __s) 1282 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1283 {__tree_.swap(__s.__tree_);} 1284 1285 _LIBCPP_INLINE_VISIBILITY 1286 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1287 _LIBCPP_INLINE_VISIBILITY 1288 key_compare key_comp() const {return __tree_.value_comp();} 1289 _LIBCPP_INLINE_VISIBILITY 1290 value_compare value_comp() const {return __tree_.value_comp();} 1291 1292 // set operations: 1293 _LIBCPP_INLINE_VISIBILITY 1294 iterator find(const key_type& __k) {return __tree_.find(__k);} 1295 _LIBCPP_INLINE_VISIBILITY 1296 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1297#if _LIBCPP_STD_VER > 11 1298 template <typename _K2> 1299 _LIBCPP_INLINE_VISIBILITY 1300 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1301 find(const _K2& __k) {return __tree_.find(__k);} 1302 template <typename _K2> 1303 _LIBCPP_INLINE_VISIBILITY 1304 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1305 find(const _K2& __k) const {return __tree_.find(__k);} 1306#endif 1307 1308 _LIBCPP_INLINE_VISIBILITY 1309 size_type count(const key_type& __k) const 1310 {return __tree_.__count_multi(__k);} 1311#if _LIBCPP_STD_VER > 11 1312 template <typename _K2> 1313 _LIBCPP_INLINE_VISIBILITY 1314 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1315 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1316#endif 1317 1318#if _LIBCPP_STD_VER > 17 1319 _LIBCPP_INLINE_VISIBILITY 1320 bool contains(const key_type& __k) const {return find(__k) != end();} 1321#endif // _LIBCPP_STD_VER > 17 1322 1323 _LIBCPP_INLINE_VISIBILITY 1324 iterator lower_bound(const key_type& __k) 1325 {return __tree_.lower_bound(__k);} 1326 _LIBCPP_INLINE_VISIBILITY 1327 const_iterator lower_bound(const key_type& __k) const 1328 {return __tree_.lower_bound(__k);} 1329#if _LIBCPP_STD_VER > 11 1330 template <typename _K2> 1331 _LIBCPP_INLINE_VISIBILITY 1332 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1333 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1334 1335 template <typename _K2> 1336 _LIBCPP_INLINE_VISIBILITY 1337 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1338 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1339#endif 1340 1341 _LIBCPP_INLINE_VISIBILITY 1342 iterator upper_bound(const key_type& __k) 1343 {return __tree_.upper_bound(__k);} 1344 _LIBCPP_INLINE_VISIBILITY 1345 const_iterator upper_bound(const key_type& __k) const 1346 {return __tree_.upper_bound(__k);} 1347#if _LIBCPP_STD_VER > 11 1348 template <typename _K2> 1349 _LIBCPP_INLINE_VISIBILITY 1350 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1351 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1352 template <typename _K2> 1353 _LIBCPP_INLINE_VISIBILITY 1354 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1355 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1356#endif 1357 1358 _LIBCPP_INLINE_VISIBILITY 1359 pair<iterator,iterator> equal_range(const key_type& __k) 1360 {return __tree_.__equal_range_multi(__k);} 1361 _LIBCPP_INLINE_VISIBILITY 1362 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1363 {return __tree_.__equal_range_multi(__k);} 1364#if _LIBCPP_STD_VER > 11 1365 template <typename _K2> 1366 _LIBCPP_INLINE_VISIBILITY 1367 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1368 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1369 template <typename _K2> 1370 _LIBCPP_INLINE_VISIBILITY 1371 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1372 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1373#endif 1374}; 1375 1376#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 1377template<class _InputIterator, 1378 class _Compare = less<typename iterator_traits<_InputIterator>::value_type>, 1379 class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>, 1380 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 1381 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 1382multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1383 -> multiset<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>; 1384 1385template<class _Key, class _Compare = less<_Key>, 1386 class _Allocator = allocator<_Key>, 1387 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 1388 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 1389multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 1390 -> multiset<_Key, _Compare, _Allocator>; 1391 1392template<class _InputIterator, class _Allocator, 1393 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1394multiset(_InputIterator, _InputIterator, _Allocator) 1395 -> multiset<typename iterator_traits<_InputIterator>::value_type, 1396 less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>; 1397 1398template<class _Key, class _Allocator, 1399 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1400multiset(initializer_list<_Key>, _Allocator) 1401 -> multiset<_Key, less<_Key>, _Allocator>; 1402#endif 1403 1404#ifndef _LIBCPP_CXX03_LANG 1405 1406template <class _Key, class _Compare, class _Allocator> 1407multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1408 : __tree_(_VSTD::move(__s.__tree_), __a) 1409{ 1410 if (__a != __s.get_allocator()) 1411 { 1412 const_iterator __e = cend(); 1413 while (!__s.empty()) 1414 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1415 } 1416} 1417 1418#endif // _LIBCPP_CXX03_LANG 1419 1420template <class _Key, class _Compare, class _Allocator> 1421inline _LIBCPP_INLINE_VISIBILITY 1422bool 1423operator==(const multiset<_Key, _Compare, _Allocator>& __x, 1424 const multiset<_Key, _Compare, _Allocator>& __y) 1425{ 1426 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1427} 1428 1429template <class _Key, class _Compare, class _Allocator> 1430inline _LIBCPP_INLINE_VISIBILITY 1431bool 1432operator< (const multiset<_Key, _Compare, _Allocator>& __x, 1433 const multiset<_Key, _Compare, _Allocator>& __y) 1434{ 1435 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1436} 1437 1438template <class _Key, class _Compare, class _Allocator> 1439inline _LIBCPP_INLINE_VISIBILITY 1440bool 1441operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1442 const multiset<_Key, _Compare, _Allocator>& __y) 1443{ 1444 return !(__x == __y); 1445} 1446 1447template <class _Key, class _Compare, class _Allocator> 1448inline _LIBCPP_INLINE_VISIBILITY 1449bool 1450operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1451 const multiset<_Key, _Compare, _Allocator>& __y) 1452{ 1453 return __y < __x; 1454} 1455 1456template <class _Key, class _Compare, class _Allocator> 1457inline _LIBCPP_INLINE_VISIBILITY 1458bool 1459operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1460 const multiset<_Key, _Compare, _Allocator>& __y) 1461{ 1462 return !(__x < __y); 1463} 1464 1465template <class _Key, class _Compare, class _Allocator> 1466inline _LIBCPP_INLINE_VISIBILITY 1467bool 1468operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1469 const multiset<_Key, _Compare, _Allocator>& __y) 1470{ 1471 return !(__y < __x); 1472} 1473 1474template <class _Key, class _Compare, class _Allocator> 1475inline _LIBCPP_INLINE_VISIBILITY 1476void 1477swap(multiset<_Key, _Compare, _Allocator>& __x, 1478 multiset<_Key, _Compare, _Allocator>& __y) 1479 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1480{ 1481 __x.swap(__y); 1482} 1483 1484#if _LIBCPP_STD_VER > 17 1485template <class _Key, class _Compare, class _Allocator, class _Predicate> 1486inline _LIBCPP_INLINE_VISIBILITY 1487void erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) 1488{ __libcpp_erase_if_container(__c, __pred); } 1489#endif 1490 1491_LIBCPP_END_NAMESPACE_STD 1492 1493#endif // _LIBCPP_SET 1494