1227825Stheraven// -*- C++ -*- 2227825Stheraven//===---------------------------- set -------------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_SET 12227825Stheraven#define _LIBCPP_SET 13227825Stheraven 14227825Stheraven/* 15227825Stheraven 16227825Stheraven set synopsis 17227825Stheraven 18227825Stheravennamespace std 19227825Stheraven{ 20227825Stheraven 21227825Stheraventemplate <class Key, class Compare = less<Key>, 22227825Stheraven class Allocator = allocator<Key>> 23227825Stheravenclass set 24227825Stheraven{ 25227825Stheravenpublic: 26227825Stheraven // types: 27227825Stheraven typedef Key key_type; 28227825Stheraven typedef key_type value_type; 29227825Stheraven typedef Compare key_compare; 30227825Stheraven typedef key_compare value_compare; 31227825Stheraven typedef Allocator allocator_type; 32227825Stheraven typedef typename allocator_type::reference reference; 33227825Stheraven typedef typename allocator_type::const_reference const_reference; 34227825Stheraven typedef typename allocator_type::size_type size_type; 35227825Stheraven typedef typename allocator_type::difference_type difference_type; 36227825Stheraven typedef typename allocator_type::pointer pointer; 37227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 38227825Stheraven 39227825Stheraven typedef implementation-defined iterator; 40227825Stheraven typedef implementation-defined const_iterator; 41227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 42227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 43227825Stheraven 44227825Stheraven // construct/copy/destroy: 45227825Stheraven set() 46227825Stheraven noexcept( 47227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 48227825Stheraven is_nothrow_default_constructible<key_compare>::value && 49227825Stheraven is_nothrow_copy_constructible<key_compare>::value); 50227825Stheraven explicit set(const value_compare& comp); 51227825Stheraven set(const value_compare& comp, const allocator_type& a); 52227825Stheraven template <class InputIterator> 53227825Stheraven set(InputIterator first, InputIterator last, 54227825Stheraven const value_compare& comp = value_compare()); 55227825Stheraven template <class InputIterator> 56227825Stheraven set(InputIterator first, InputIterator last, const value_compare& comp, 57227825Stheraven const allocator_type& a); 58227825Stheraven set(const set& s); 59227825Stheraven set(set&& s) 60227825Stheraven noexcept( 61227825Stheraven is_nothrow_move_constructible<allocator_type>::value && 62227825Stheraven is_nothrow_move_constructible<key_compare>::value); 63227825Stheraven explicit set(const allocator_type& a); 64227825Stheraven set(const set& s, const allocator_type& a); 65227825Stheraven set(set&& s, const allocator_type& a); 66227825Stheraven set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 67227825Stheraven set(initializer_list<value_type> il, const value_compare& comp, 68227825Stheraven const allocator_type& a); 69261272Sdim template <class InputIterator> 70261272Sdim set(InputIterator first, InputIterator last, const allocator_type& a) 71261272Sdim : set(first, last, Compare(), a) {} // C++14 72261272Sdim set(initializer_list<value_type> il, const allocator_type& a) 73261272Sdim : set(il, Compare(), a) {} // C++14 74227825Stheraven ~set(); 75227825Stheraven 76227825Stheraven set& operator=(const set& s); 77227825Stheraven set& operator=(set&& s) 78227825Stheraven noexcept( 79227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 80227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 81227825Stheraven is_nothrow_move_assignable<key_compare>::value); 82227825Stheraven set& operator=(initializer_list<value_type> il); 83227825Stheraven 84227825Stheraven // iterators: 85227825Stheraven iterator begin() noexcept; 86227825Stheraven const_iterator begin() const noexcept; 87227825Stheraven iterator end() noexcept; 88227825Stheraven const_iterator end() const noexcept; 89227825Stheraven 90227825Stheraven reverse_iterator rbegin() noexcept; 91227825Stheraven const_reverse_iterator rbegin() const noexcept; 92227825Stheraven reverse_iterator rend() noexcept; 93227825Stheraven const_reverse_iterator rend() const noexcept; 94227825Stheraven 95227825Stheraven const_iterator cbegin() const noexcept; 96227825Stheraven const_iterator cend() const noexcept; 97227825Stheraven const_reverse_iterator crbegin() const noexcept; 98227825Stheraven const_reverse_iterator crend() const noexcept; 99227825Stheraven 100227825Stheraven // capacity: 101227825Stheraven bool empty() const noexcept; 102227825Stheraven size_type size() const noexcept; 103227825Stheraven size_type max_size() const noexcept; 104227825Stheraven 105227825Stheraven // modifiers: 106227825Stheraven template <class... Args> 107227825Stheraven pair<iterator, bool> emplace(Args&&... args); 108227825Stheraven template <class... Args> 109227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 110227825Stheraven pair<iterator,bool> insert(const value_type& v); 111227825Stheraven pair<iterator,bool> insert(value_type&& v); 112227825Stheraven iterator insert(const_iterator position, const value_type& v); 113227825Stheraven iterator insert(const_iterator position, value_type&& v); 114227825Stheraven template <class InputIterator> 115227825Stheraven void insert(InputIterator first, InputIterator last); 116227825Stheraven void insert(initializer_list<value_type> il); 117227825Stheraven 118227825Stheraven iterator erase(const_iterator position); 119288943Sdim iterator erase(iterator position); // C++14 120227825Stheraven size_type erase(const key_type& k); 121227825Stheraven iterator erase(const_iterator first, const_iterator last); 122227825Stheraven void clear() noexcept; 123227825Stheraven 124227825Stheraven void swap(set& s) 125227825Stheraven noexcept( 126227825Stheraven __is_nothrow_swappable<key_compare>::value && 127227825Stheraven (!allocator_type::propagate_on_container_swap::value || 128227825Stheraven __is_nothrow_swappable<allocator_type>::value)); 129227825Stheraven 130227825Stheraven // observers: 131227825Stheraven allocator_type get_allocator() const noexcept; 132227825Stheraven key_compare key_comp() const; 133227825Stheraven value_compare value_comp() const; 134227825Stheraven 135227825Stheraven // set operations: 136227825Stheraven iterator find(const key_type& k); 137227825Stheraven const_iterator find(const key_type& k) const; 138261272Sdim template<typename K> 139261272Sdim iterator find(const K& x); 140261272Sdim template<typename K> 141261272Sdim const_iterator find(const K& x) const; // C++14 142261272Sdim template<typename K> 143261272Sdim size_type count(const K& x) const; // C++14 144261272Sdim 145227825Stheraven size_type count(const key_type& k) const; 146227825Stheraven iterator lower_bound(const key_type& k); 147227825Stheraven const_iterator lower_bound(const key_type& k) const; 148261272Sdim template<typename K> 149261272Sdim iterator lower_bound(const K& x); // C++14 150261272Sdim template<typename K> 151261272Sdim const_iterator lower_bound(const K& x) const; // C++14 152261272Sdim 153227825Stheraven iterator upper_bound(const key_type& k); 154227825Stheraven const_iterator upper_bound(const key_type& k) const; 155261272Sdim template<typename K> 156261272Sdim iterator upper_bound(const K& x); // C++14 157261272Sdim template<typename K> 158261272Sdim const_iterator upper_bound(const K& x) const; // C++14 159227825Stheraven pair<iterator,iterator> equal_range(const key_type& k); 160227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 161261272Sdim template<typename K> 162261272Sdim pair<iterator,iterator> equal_range(const K& x); // C++14 163261272Sdim template<typename K> 164261272Sdim pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 165227825Stheraven}; 166227825Stheraven 167227825Stheraventemplate <class Key, class Compare, class Allocator> 168227825Stheravenbool 169227825Stheravenoperator==(const set<Key, Compare, Allocator>& x, 170227825Stheraven const set<Key, Compare, Allocator>& y); 171227825Stheraven 172227825Stheraventemplate <class Key, class Compare, class Allocator> 173227825Stheravenbool 174227825Stheravenoperator< (const set<Key, Compare, Allocator>& x, 175227825Stheraven const set<Key, Compare, Allocator>& y); 176227825Stheraven 177227825Stheraventemplate <class Key, class Compare, class Allocator> 178227825Stheravenbool 179227825Stheravenoperator!=(const set<Key, Compare, Allocator>& x, 180227825Stheraven const set<Key, Compare, Allocator>& y); 181227825Stheraven 182227825Stheraventemplate <class Key, class Compare, class Allocator> 183227825Stheravenbool 184227825Stheravenoperator> (const set<Key, Compare, Allocator>& x, 185227825Stheraven const set<Key, Compare, Allocator>& y); 186227825Stheraven 187227825Stheraventemplate <class Key, class Compare, class Allocator> 188227825Stheravenbool 189227825Stheravenoperator>=(const set<Key, Compare, Allocator>& x, 190227825Stheraven const set<Key, Compare, Allocator>& y); 191227825Stheraven 192227825Stheraventemplate <class Key, class Compare, class Allocator> 193227825Stheravenbool 194227825Stheravenoperator<=(const set<Key, Compare, Allocator>& x, 195227825Stheraven const set<Key, Compare, Allocator>& y); 196227825Stheraven 197227825Stheraven// specialized algorithms: 198227825Stheraventemplate <class Key, class Compare, class Allocator> 199227825Stheravenvoid 200227825Stheravenswap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 201227825Stheraven noexcept(noexcept(x.swap(y))); 202227825Stheraven 203227825Stheraventemplate <class Key, class Compare = less<Key>, 204227825Stheraven class Allocator = allocator<Key>> 205227825Stheravenclass multiset 206227825Stheraven{ 207227825Stheravenpublic: 208227825Stheraven // types: 209227825Stheraven typedef Key key_type; 210227825Stheraven typedef key_type value_type; 211227825Stheraven typedef Compare key_compare; 212227825Stheraven typedef key_compare value_compare; 213227825Stheraven typedef Allocator allocator_type; 214227825Stheraven typedef typename allocator_type::reference reference; 215227825Stheraven typedef typename allocator_type::const_reference const_reference; 216227825Stheraven typedef typename allocator_type::size_type size_type; 217227825Stheraven typedef typename allocator_type::difference_type difference_type; 218227825Stheraven typedef typename allocator_type::pointer pointer; 219227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 220227825Stheraven 221227825Stheraven typedef implementation-defined iterator; 222227825Stheraven typedef implementation-defined const_iterator; 223227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 224227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 225227825Stheraven 226227825Stheraven // construct/copy/destroy: 227227825Stheraven multiset() 228227825Stheraven noexcept( 229227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 230227825Stheraven is_nothrow_default_constructible<key_compare>::value && 231227825Stheraven is_nothrow_copy_constructible<key_compare>::value); 232227825Stheraven explicit multiset(const value_compare& comp); 233227825Stheraven multiset(const value_compare& comp, const allocator_type& a); 234227825Stheraven template <class InputIterator> 235227825Stheraven multiset(InputIterator first, InputIterator last, 236227825Stheraven const value_compare& comp = value_compare()); 237227825Stheraven template <class InputIterator> 238227825Stheraven multiset(InputIterator first, InputIterator last, 239227825Stheraven const value_compare& comp, const allocator_type& a); 240227825Stheraven multiset(const multiset& s); 241227825Stheraven multiset(multiset&& s) 242227825Stheraven noexcept( 243227825Stheraven is_nothrow_move_constructible<allocator_type>::value && 244227825Stheraven is_nothrow_move_constructible<key_compare>::value); 245227825Stheraven explicit multiset(const allocator_type& a); 246227825Stheraven multiset(const multiset& s, const allocator_type& a); 247227825Stheraven multiset(multiset&& s, const allocator_type& a); 248227825Stheraven multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 249227825Stheraven multiset(initializer_list<value_type> il, const value_compare& comp, 250227825Stheraven const allocator_type& a); 251261272Sdim template <class InputIterator> 252261272Sdim multiset(InputIterator first, InputIterator last, const allocator_type& a) 253261272Sdim : set(first, last, Compare(), a) {} // C++14 254261272Sdim multiset(initializer_list<value_type> il, const allocator_type& a) 255261272Sdim : set(il, Compare(), a) {} // C++14 256227825Stheraven ~multiset(); 257227825Stheraven 258227825Stheraven multiset& operator=(const multiset& s); 259227825Stheraven multiset& operator=(multiset&& s) 260227825Stheraven noexcept( 261227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 262227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 263227825Stheraven is_nothrow_move_assignable<key_compare>::value); 264227825Stheraven multiset& operator=(initializer_list<value_type> il); 265227825Stheraven 266227825Stheraven // iterators: 267227825Stheraven iterator begin() noexcept; 268227825Stheraven const_iterator begin() const noexcept; 269227825Stheraven iterator end() noexcept; 270227825Stheraven const_iterator end() const noexcept; 271227825Stheraven 272227825Stheraven reverse_iterator rbegin() noexcept; 273227825Stheraven const_reverse_iterator rbegin() const noexcept; 274227825Stheraven reverse_iterator rend() noexcept; 275227825Stheraven const_reverse_iterator rend() const noexcept; 276227825Stheraven 277227825Stheraven const_iterator cbegin() const noexcept; 278227825Stheraven const_iterator cend() const noexcept; 279227825Stheraven const_reverse_iterator crbegin() const noexcept; 280227825Stheraven const_reverse_iterator crend() const noexcept; 281227825Stheraven 282227825Stheraven // capacity: 283227825Stheraven bool empty() const noexcept; 284227825Stheraven size_type size() const noexcept; 285227825Stheraven size_type max_size() const noexcept; 286227825Stheraven 287227825Stheraven // modifiers: 288227825Stheraven template <class... Args> 289227825Stheraven iterator emplace(Args&&... args); 290227825Stheraven template <class... Args> 291227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 292227825Stheraven iterator insert(const value_type& v); 293227825Stheraven iterator insert(value_type&& v); 294227825Stheraven iterator insert(const_iterator position, const value_type& v); 295227825Stheraven iterator insert(const_iterator position, value_type&& v); 296227825Stheraven template <class InputIterator> 297227825Stheraven void insert(InputIterator first, InputIterator last); 298227825Stheraven void insert(initializer_list<value_type> il); 299227825Stheraven 300227825Stheraven iterator erase(const_iterator position); 301288943Sdim iterator erase(iterator position); // C++14 302227825Stheraven size_type erase(const key_type& k); 303227825Stheraven iterator erase(const_iterator first, const_iterator last); 304227825Stheraven void clear() noexcept; 305227825Stheraven 306227825Stheraven void swap(multiset& s) 307227825Stheraven noexcept( 308227825Stheraven __is_nothrow_swappable<key_compare>::value && 309227825Stheraven (!allocator_type::propagate_on_container_swap::value || 310227825Stheraven __is_nothrow_swappable<allocator_type>::value)); 311227825Stheraven 312227825Stheraven // observers: 313227825Stheraven allocator_type get_allocator() const noexcept; 314227825Stheraven key_compare key_comp() const; 315227825Stheraven value_compare value_comp() const; 316227825Stheraven 317227825Stheraven // set operations: 318227825Stheraven iterator find(const key_type& k); 319227825Stheraven const_iterator find(const key_type& k) const; 320261272Sdim template<typename K> 321261272Sdim iterator find(const K& x); 322261272Sdim template<typename K> 323261272Sdim const_iterator find(const K& x) const; // C++14 324261272Sdim 325227825Stheraven size_type count(const key_type& k) const; 326227825Stheraven iterator lower_bound(const key_type& k); 327227825Stheraven const_iterator lower_bound(const key_type& k) const; 328261272Sdim template<typename K> 329261272Sdim iterator lower_bound(const K& x); // C++14 330261272Sdim template<typename K> 331261272Sdim const_iterator lower_bound(const K& x) const; // C++14 332261272Sdim 333227825Stheraven iterator upper_bound(const key_type& k); 334227825Stheraven const_iterator upper_bound(const key_type& k) const; 335261272Sdim template<typename K> 336261272Sdim iterator upper_bound(const K& x); // C++14 337261272Sdim template<typename K> 338261272Sdim const_iterator upper_bound(const K& x) const; // C++14 339261272Sdim 340227825Stheraven pair<iterator,iterator> equal_range(const key_type& k); 341227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 342261272Sdim template<typename K> 343261272Sdim pair<iterator,iterator> equal_range(const K& x); // C++14 344261272Sdim template<typename K> 345261272Sdim pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 346227825Stheraven}; 347227825Stheraven 348227825Stheraventemplate <class Key, class Compare, class Allocator> 349227825Stheravenbool 350227825Stheravenoperator==(const multiset<Key, Compare, Allocator>& x, 351227825Stheraven const multiset<Key, Compare, Allocator>& y); 352227825Stheraven 353227825Stheraventemplate <class Key, class Compare, class Allocator> 354227825Stheravenbool 355227825Stheravenoperator< (const multiset<Key, Compare, Allocator>& x, 356227825Stheraven const multiset<Key, Compare, Allocator>& y); 357227825Stheraven 358227825Stheraventemplate <class Key, class Compare, class Allocator> 359227825Stheravenbool 360227825Stheravenoperator!=(const multiset<Key, Compare, Allocator>& x, 361227825Stheraven const multiset<Key, Compare, Allocator>& y); 362227825Stheraven 363227825Stheraventemplate <class Key, class Compare, class Allocator> 364227825Stheravenbool 365227825Stheravenoperator> (const multiset<Key, Compare, Allocator>& x, 366227825Stheraven const multiset<Key, Compare, Allocator>& y); 367227825Stheraven 368227825Stheraventemplate <class Key, class Compare, class Allocator> 369227825Stheravenbool 370227825Stheravenoperator>=(const multiset<Key, Compare, Allocator>& x, 371227825Stheraven const multiset<Key, Compare, Allocator>& y); 372227825Stheraven 373227825Stheraventemplate <class Key, class Compare, class Allocator> 374227825Stheravenbool 375227825Stheravenoperator<=(const multiset<Key, Compare, Allocator>& x, 376227825Stheraven const multiset<Key, Compare, Allocator>& y); 377227825Stheraven 378227825Stheraven// specialized algorithms: 379227825Stheraventemplate <class Key, class Compare, class Allocator> 380227825Stheravenvoid 381227825Stheravenswap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 382227825Stheraven noexcept(noexcept(x.swap(y))); 383227825Stheraven 384227825Stheraven} // std 385227825Stheraven 386227825Stheraven*/ 387227825Stheraven 388227825Stheraven#include <__config> 389227825Stheraven#include <__tree> 390227825Stheraven#include <functional> 391227825Stheraven 392227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 393227825Stheraven#pragma GCC system_header 394227825Stheraven#endif 395227825Stheraven 396227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 397227825Stheraven 398227825Stheraventemplate <class _Key, class _Compare = less<_Key>, 399227825Stheraven class _Allocator = allocator<_Key> > 400261272Sdimclass _LIBCPP_TYPE_VIS_ONLY set 401227825Stheraven{ 402227825Stheravenpublic: 403227825Stheraven // types: 404227825Stheraven typedef _Key key_type; 405227825Stheraven typedef key_type value_type; 406227825Stheraven typedef _Compare key_compare; 407227825Stheraven typedef key_compare value_compare; 408227825Stheraven typedef _Allocator allocator_type; 409227825Stheraven typedef value_type& reference; 410227825Stheraven typedef const value_type& const_reference; 411227825Stheraven 412300770Sdim static_assert((is_same<typename allocator_type::value_type, value_type>::value), 413300770Sdim "Allocator::value_type must be same type as value_type"); 414300770Sdim 415227825Stheravenprivate: 416227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 417227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 418227825Stheraven typedef typename __base::__node_holder __node_holder; 419227825Stheraven 420227825Stheraven __base __tree_; 421227825Stheraven 422227825Stheravenpublic: 423227825Stheraven typedef typename __base::pointer pointer; 424227825Stheraven typedef typename __base::const_pointer const_pointer; 425227825Stheraven typedef typename __base::size_type size_type; 426227825Stheraven typedef typename __base::difference_type difference_type; 427227825Stheraven typedef typename __base::const_iterator iterator; 428227825Stheraven typedef typename __base::const_iterator const_iterator; 429227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 430227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 431227825Stheraven 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433276792Sdim set() 434227825Stheraven _NOEXCEPT_( 435227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 436227825Stheraven is_nothrow_default_constructible<key_compare>::value && 437227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 438276792Sdim : __tree_(value_compare()) {} 439276792Sdim 440276792Sdim _LIBCPP_INLINE_VISIBILITY 441276792Sdim explicit set(const value_compare& __comp) 442276792Sdim _NOEXCEPT_( 443276792Sdim is_nothrow_default_constructible<allocator_type>::value && 444276792Sdim is_nothrow_copy_constructible<key_compare>::value) 445227825Stheraven : __tree_(__comp) {} 446276792Sdim 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448276792Sdim explicit set(const value_compare& __comp, const allocator_type& __a) 449227825Stheraven : __tree_(__comp, __a) {} 450227825Stheraven template <class _InputIterator> 451227825Stheraven _LIBCPP_INLINE_VISIBILITY 452227825Stheraven set(_InputIterator __f, _InputIterator __l, 453227825Stheraven const value_compare& __comp = value_compare()) 454227825Stheraven : __tree_(__comp) 455227825Stheraven { 456227825Stheraven insert(__f, __l); 457227825Stheraven } 458227825Stheraven 459227825Stheraven template <class _InputIterator> 460227825Stheraven _LIBCPP_INLINE_VISIBILITY 461227825Stheraven set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 462227825Stheraven const allocator_type& __a) 463227825Stheraven : __tree_(__comp, __a) 464227825Stheraven { 465227825Stheraven insert(__f, __l); 466227825Stheraven } 467227825Stheraven 468261272Sdim#if _LIBCPP_STD_VER > 11 469261272Sdim template <class _InputIterator> 470261272Sdim _LIBCPP_INLINE_VISIBILITY 471261272Sdim set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 472261272Sdim : set(__f, __l, key_compare(), __a) {} 473261272Sdim#endif 474261272Sdim 475227825Stheraven _LIBCPP_INLINE_VISIBILITY 476227825Stheraven set(const set& __s) 477227825Stheraven : __tree_(__s.__tree_) 478227825Stheraven { 479227825Stheraven insert(__s.begin(), __s.end()); 480227825Stheraven } 481227825Stheraven 482227825Stheraven _LIBCPP_INLINE_VISIBILITY 483227825Stheraven set& operator=(const set& __s) 484227825Stheraven { 485227825Stheraven __tree_ = __s.__tree_; 486227825Stheraven return *this; 487227825Stheraven } 488227825Stheraven 489227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 490227825Stheraven _LIBCPP_INLINE_VISIBILITY 491227825Stheraven set(set&& __s) 492227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 493227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 494227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 495227825Stheraven 496227825Stheraven _LIBCPP_INLINE_VISIBILITY 497227825Stheraven explicit set(const allocator_type& __a) 498227825Stheraven : __tree_(__a) {} 499227825Stheraven 500227825Stheraven _LIBCPP_INLINE_VISIBILITY 501227825Stheraven set(const set& __s, const allocator_type& __a) 502227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 503227825Stheraven { 504227825Stheraven insert(__s.begin(), __s.end()); 505227825Stheraven } 506227825Stheraven 507227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 508227825Stheraven set(set&& __s, const allocator_type& __a); 509227825Stheraven#endif 510227825Stheraven 511227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 512227825Stheraven _LIBCPP_INLINE_VISIBILITY 513227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 514227825Stheraven : __tree_(__comp) 515227825Stheraven { 516227825Stheraven insert(__il.begin(), __il.end()); 517227825Stheraven } 518227825Stheraven 519227825Stheraven _LIBCPP_INLINE_VISIBILITY 520227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp, 521227825Stheraven const allocator_type& __a) 522227825Stheraven : __tree_(__comp, __a) 523227825Stheraven { 524227825Stheraven insert(__il.begin(), __il.end()); 525227825Stheraven } 526227825Stheraven 527261272Sdim#if _LIBCPP_STD_VER > 11 528261272Sdim _LIBCPP_INLINE_VISIBILITY 529261272Sdim set(initializer_list<value_type> __il, const allocator_type& __a) 530261272Sdim : set(__il, key_compare(), __a) {} 531261272Sdim#endif 532261272Sdim 533227825Stheraven _LIBCPP_INLINE_VISIBILITY 534227825Stheraven set& operator=(initializer_list<value_type> __il) 535227825Stheraven { 536227825Stheraven __tree_.__assign_unique(__il.begin(), __il.end()); 537227825Stheraven return *this; 538227825Stheraven } 539227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 540227825Stheraven 541227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 542227825Stheraven _LIBCPP_INLINE_VISIBILITY 543227825Stheraven set& operator=(set&& __s) 544227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 545227825Stheraven { 546227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 547227825Stheraven return *this; 548227825Stheraven } 549227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 550227825Stheraven 551227825Stheraven _LIBCPP_INLINE_VISIBILITY 552227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 555227825Stheraven _LIBCPP_INLINE_VISIBILITY 556227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 557227825Stheraven _LIBCPP_INLINE_VISIBILITY 558227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 559227825Stheraven 560227825Stheraven _LIBCPP_INLINE_VISIBILITY 561227825Stheraven reverse_iterator rbegin() _NOEXCEPT 562227825Stheraven {return reverse_iterator(end());} 563227825Stheraven _LIBCPP_INLINE_VISIBILITY 564227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 565227825Stheraven {return const_reverse_iterator(end());} 566227825Stheraven _LIBCPP_INLINE_VISIBILITY 567227825Stheraven reverse_iterator rend() _NOEXCEPT 568227825Stheraven {return reverse_iterator(begin());} 569227825Stheraven _LIBCPP_INLINE_VISIBILITY 570227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 571227825Stheraven {return const_reverse_iterator(begin());} 572227825Stheraven 573227825Stheraven _LIBCPP_INLINE_VISIBILITY 574227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 575227825Stheraven _LIBCPP_INLINE_VISIBILITY 576227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 577227825Stheraven _LIBCPP_INLINE_VISIBILITY 578227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 579227825Stheraven _LIBCPP_INLINE_VISIBILITY 580227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 581227825Stheraven 582227825Stheraven _LIBCPP_INLINE_VISIBILITY 583227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 584227825Stheraven _LIBCPP_INLINE_VISIBILITY 585227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 586227825Stheraven _LIBCPP_INLINE_VISIBILITY 587227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 588227825Stheraven 589227825Stheraven // modifiers: 590227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 591227825Stheraven template <class... _Args> 592227825Stheraven _LIBCPP_INLINE_VISIBILITY 593227825Stheraven pair<iterator, bool> emplace(_Args&&... __args) 594227825Stheraven {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 595227825Stheraven template <class... _Args> 596227825Stheraven _LIBCPP_INLINE_VISIBILITY 597227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 598227825Stheraven {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 599227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 600227825Stheraven _LIBCPP_INLINE_VISIBILITY 601227825Stheraven pair<iterator,bool> insert(const value_type& __v) 602227825Stheraven {return __tree_.__insert_unique(__v);} 603227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 604227825Stheraven _LIBCPP_INLINE_VISIBILITY 605227825Stheraven pair<iterator,bool> insert(value_type&& __v) 606227825Stheraven {return __tree_.__insert_unique(_VSTD::move(__v));} 607227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 608227825Stheraven _LIBCPP_INLINE_VISIBILITY 609227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 610227825Stheraven {return __tree_.__insert_unique(__p, __v);} 611227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 612227825Stheraven _LIBCPP_INLINE_VISIBILITY 613227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 614227825Stheraven {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 615227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 616227825Stheraven template <class _InputIterator> 617227825Stheraven _LIBCPP_INLINE_VISIBILITY 618227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 619227825Stheraven { 620227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 621227825Stheraven __tree_.__insert_unique(__e, *__f); 622227825Stheraven } 623227825Stheraven 624227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 625227825Stheraven _LIBCPP_INLINE_VISIBILITY 626227825Stheraven void insert(initializer_list<value_type> __il) 627227825Stheraven {insert(__il.begin(), __il.end());} 628227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 629227825Stheraven 630227825Stheraven _LIBCPP_INLINE_VISIBILITY 631227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 632227825Stheraven _LIBCPP_INLINE_VISIBILITY 633227825Stheraven size_type erase(const key_type& __k) 634227825Stheraven {return __tree_.__erase_unique(__k);} 635227825Stheraven _LIBCPP_INLINE_VISIBILITY 636227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 637227825Stheraven {return __tree_.erase(__f, __l);} 638227825Stheraven _LIBCPP_INLINE_VISIBILITY 639227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 640227825Stheraven 641227825Stheraven _LIBCPP_INLINE_VISIBILITY 642227825Stheraven void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 643227825Stheraven {__tree_.swap(__s.__tree_);} 644227825Stheraven 645227825Stheraven _LIBCPP_INLINE_VISIBILITY 646227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 647227825Stheraven _LIBCPP_INLINE_VISIBILITY 648227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 649227825Stheraven _LIBCPP_INLINE_VISIBILITY 650227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 651227825Stheraven 652227825Stheraven // set operations: 653227825Stheraven _LIBCPP_INLINE_VISIBILITY 654227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 655227825Stheraven _LIBCPP_INLINE_VISIBILITY 656227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 657261272Sdim#if _LIBCPP_STD_VER > 11 658261272Sdim template <typename _K2> 659227825Stheraven _LIBCPP_INLINE_VISIBILITY 660261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 661261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 662261272Sdim template <typename _K2> 663261272Sdim _LIBCPP_INLINE_VISIBILITY 664261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 665261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 666261272Sdim#endif 667261272Sdim 668261272Sdim _LIBCPP_INLINE_VISIBILITY 669227825Stheraven size_type count(const key_type& __k) const 670227825Stheraven {return __tree_.__count_unique(__k);} 671276792Sdim#if _LIBCPP_STD_VER > 11 672276792Sdim template <typename _K2> 673227825Stheraven _LIBCPP_INLINE_VISIBILITY 674276792Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 675276792Sdim count(const _K2& __k) {return __tree_.__count_unique(__k);} 676276792Sdim#endif 677276792Sdim _LIBCPP_INLINE_VISIBILITY 678227825Stheraven iterator lower_bound(const key_type& __k) 679227825Stheraven {return __tree_.lower_bound(__k);} 680227825Stheraven _LIBCPP_INLINE_VISIBILITY 681227825Stheraven const_iterator lower_bound(const key_type& __k) const 682227825Stheraven {return __tree_.lower_bound(__k);} 683261272Sdim#if _LIBCPP_STD_VER > 11 684261272Sdim template <typename _K2> 685227825Stheraven _LIBCPP_INLINE_VISIBILITY 686261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 687261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 688261272Sdim 689261272Sdim template <typename _K2> 690261272Sdim _LIBCPP_INLINE_VISIBILITY 691261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 692261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 693261272Sdim#endif 694261272Sdim 695261272Sdim _LIBCPP_INLINE_VISIBILITY 696227825Stheraven iterator upper_bound(const key_type& __k) 697227825Stheraven {return __tree_.upper_bound(__k);} 698227825Stheraven _LIBCPP_INLINE_VISIBILITY 699227825Stheraven const_iterator upper_bound(const key_type& __k) const 700227825Stheraven {return __tree_.upper_bound(__k);} 701261272Sdim#if _LIBCPP_STD_VER > 11 702261272Sdim template <typename _K2> 703227825Stheraven _LIBCPP_INLINE_VISIBILITY 704261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 705261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 706261272Sdim template <typename _K2> 707261272Sdim _LIBCPP_INLINE_VISIBILITY 708261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 709261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 710261272Sdim#endif 711261272Sdim 712261272Sdim _LIBCPP_INLINE_VISIBILITY 713227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 714227825Stheraven {return __tree_.__equal_range_unique(__k);} 715227825Stheraven _LIBCPP_INLINE_VISIBILITY 716227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 717227825Stheraven {return __tree_.__equal_range_unique(__k);} 718261272Sdim#if _LIBCPP_STD_VER > 11 719261272Sdim template <typename _K2> 720261272Sdim _LIBCPP_INLINE_VISIBILITY 721261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 722261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 723261272Sdim template <typename _K2> 724261272Sdim _LIBCPP_INLINE_VISIBILITY 725261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 726261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 727261272Sdim#endif 728227825Stheraven}; 729227825Stheraven 730227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 731227825Stheraven 732227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 733227825Stheravenset<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 734227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 735227825Stheraven{ 736227825Stheraven if (__a != __s.get_allocator()) 737227825Stheraven { 738227825Stheraven const_iterator __e = cend(); 739227825Stheraven while (!__s.empty()) 740227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 741227825Stheraven } 742227825Stheraven} 743227825Stheraven 744227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 745227825Stheraven 746227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 747227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 748227825Stheravenbool 749227825Stheravenoperator==(const set<_Key, _Compare, _Allocator>& __x, 750227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 751227825Stheraven{ 752227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 753227825Stheraven} 754227825Stheraven 755227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 756227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 757227825Stheravenbool 758227825Stheravenoperator< (const set<_Key, _Compare, _Allocator>& __x, 759227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 760227825Stheraven{ 761227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 762227825Stheraven} 763227825Stheraven 764227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 765227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 766227825Stheravenbool 767227825Stheravenoperator!=(const set<_Key, _Compare, _Allocator>& __x, 768227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 769227825Stheraven{ 770227825Stheraven return !(__x == __y); 771227825Stheraven} 772227825Stheraven 773227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 774227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 775227825Stheravenbool 776227825Stheravenoperator> (const set<_Key, _Compare, _Allocator>& __x, 777227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 778227825Stheraven{ 779227825Stheraven return __y < __x; 780227825Stheraven} 781227825Stheraven 782227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 783227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 784227825Stheravenbool 785227825Stheravenoperator>=(const set<_Key, _Compare, _Allocator>& __x, 786227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 787227825Stheraven{ 788227825Stheraven return !(__x < __y); 789227825Stheraven} 790227825Stheraven 791227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 792227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 793227825Stheravenbool 794227825Stheravenoperator<=(const set<_Key, _Compare, _Allocator>& __x, 795227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 796227825Stheraven{ 797227825Stheraven return !(__y < __x); 798227825Stheraven} 799227825Stheraven 800227825Stheraven// specialized algorithms: 801227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 802227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 803227825Stheravenvoid 804227825Stheravenswap(set<_Key, _Compare, _Allocator>& __x, 805227825Stheraven set<_Key, _Compare, _Allocator>& __y) 806227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 807227825Stheraven{ 808227825Stheraven __x.swap(__y); 809227825Stheraven} 810227825Stheraven 811227825Stheraventemplate <class _Key, class _Compare = less<_Key>, 812227825Stheraven class _Allocator = allocator<_Key> > 813261272Sdimclass _LIBCPP_TYPE_VIS_ONLY multiset 814227825Stheraven{ 815227825Stheravenpublic: 816227825Stheraven // types: 817227825Stheraven typedef _Key key_type; 818227825Stheraven typedef key_type value_type; 819227825Stheraven typedef _Compare key_compare; 820227825Stheraven typedef key_compare value_compare; 821227825Stheraven typedef _Allocator allocator_type; 822227825Stheraven typedef value_type& reference; 823227825Stheraven typedef const value_type& const_reference; 824227825Stheraven 825300770Sdim static_assert((is_same<typename allocator_type::value_type, value_type>::value), 826300770Sdim "Allocator::value_type must be same type as value_type"); 827300770Sdim 828227825Stheravenprivate: 829227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 830227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 831227825Stheraven typedef typename __base::__node_holder __node_holder; 832227825Stheraven 833227825Stheraven __base __tree_; 834227825Stheraven 835227825Stheravenpublic: 836227825Stheraven typedef typename __base::pointer pointer; 837227825Stheraven typedef typename __base::const_pointer const_pointer; 838227825Stheraven typedef typename __base::size_type size_type; 839227825Stheraven typedef typename __base::difference_type difference_type; 840227825Stheraven typedef typename __base::const_iterator iterator; 841227825Stheraven typedef typename __base::const_iterator const_iterator; 842227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 843227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 844227825Stheraven 845227825Stheraven // construct/copy/destroy: 846227825Stheraven _LIBCPP_INLINE_VISIBILITY 847276792Sdim multiset() 848227825Stheraven _NOEXCEPT_( 849227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 850227825Stheraven is_nothrow_default_constructible<key_compare>::value && 851227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 852276792Sdim : __tree_(value_compare()) {} 853276792Sdim 854276792Sdim _LIBCPP_INLINE_VISIBILITY 855276792Sdim explicit multiset(const value_compare& __comp) 856276792Sdim _NOEXCEPT_( 857276792Sdim is_nothrow_default_constructible<allocator_type>::value && 858276792Sdim is_nothrow_copy_constructible<key_compare>::value) 859227825Stheraven : __tree_(__comp) {} 860276792Sdim 861227825Stheraven _LIBCPP_INLINE_VISIBILITY 862276792Sdim explicit multiset(const value_compare& __comp, const allocator_type& __a) 863227825Stheraven : __tree_(__comp, __a) {} 864227825Stheraven template <class _InputIterator> 865227825Stheraven _LIBCPP_INLINE_VISIBILITY 866227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 867227825Stheraven const value_compare& __comp = value_compare()) 868227825Stheraven : __tree_(__comp) 869227825Stheraven { 870227825Stheraven insert(__f, __l); 871227825Stheraven } 872227825Stheraven 873261272Sdim#if _LIBCPP_STD_VER > 11 874261272Sdim template <class _InputIterator> 875261272Sdim _LIBCPP_INLINE_VISIBILITY 876261272Sdim multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 877261272Sdim : multiset(__f, __l, key_compare(), __a) {} 878261272Sdim#endif 879261272Sdim 880227825Stheraven template <class _InputIterator> 881227825Stheraven _LIBCPP_INLINE_VISIBILITY 882227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 883227825Stheraven const value_compare& __comp, const allocator_type& __a) 884227825Stheraven : __tree_(__comp, __a) 885227825Stheraven { 886227825Stheraven insert(__f, __l); 887227825Stheraven } 888227825Stheraven 889227825Stheraven _LIBCPP_INLINE_VISIBILITY 890227825Stheraven multiset(const multiset& __s) 891227825Stheraven : __tree_(__s.__tree_.value_comp(), 892227825Stheraven __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 893227825Stheraven { 894227825Stheraven insert(__s.begin(), __s.end()); 895227825Stheraven } 896227825Stheraven 897227825Stheraven _LIBCPP_INLINE_VISIBILITY 898227825Stheraven multiset& operator=(const multiset& __s) 899227825Stheraven { 900227825Stheraven __tree_ = __s.__tree_; 901227825Stheraven return *this; 902227825Stheraven } 903227825Stheraven 904227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906227825Stheraven multiset(multiset&& __s) 907227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 908227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 909227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 910227825Stheraven _LIBCPP_INLINE_VISIBILITY 911227825Stheraven explicit multiset(const allocator_type& __a) 912227825Stheraven : __tree_(__a) {} 913227825Stheraven _LIBCPP_INLINE_VISIBILITY 914227825Stheraven multiset(const multiset& __s, const allocator_type& __a) 915227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 916227825Stheraven { 917227825Stheraven insert(__s.begin(), __s.end()); 918227825Stheraven } 919227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 920227825Stheraven multiset(multiset&& __s, const allocator_type& __a); 921227825Stheraven#endif 922227825Stheraven 923227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 924227825Stheraven _LIBCPP_INLINE_VISIBILITY 925227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 926227825Stheraven : __tree_(__comp) 927227825Stheraven { 928227825Stheraven insert(__il.begin(), __il.end()); 929227825Stheraven } 930227825Stheraven 931227825Stheraven _LIBCPP_INLINE_VISIBILITY 932227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp, 933227825Stheraven const allocator_type& __a) 934227825Stheraven : __tree_(__comp, __a) 935227825Stheraven { 936227825Stheraven insert(__il.begin(), __il.end()); 937227825Stheraven } 938227825Stheraven 939261272Sdim#if _LIBCPP_STD_VER > 11 940261272Sdim _LIBCPP_INLINE_VISIBILITY 941261272Sdim multiset(initializer_list<value_type> __il, const allocator_type& __a) 942261272Sdim : multiset(__il, key_compare(), __a) {} 943261272Sdim#endif 944261272Sdim 945227825Stheraven _LIBCPP_INLINE_VISIBILITY 946227825Stheraven multiset& operator=(initializer_list<value_type> __il) 947227825Stheraven { 948227825Stheraven __tree_.__assign_multi(__il.begin(), __il.end()); 949227825Stheraven return *this; 950227825Stheraven } 951227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 952227825Stheraven 953227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 954227825Stheraven _LIBCPP_INLINE_VISIBILITY 955227825Stheraven multiset& operator=(multiset&& __s) 956227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 957227825Stheraven { 958227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 959227825Stheraven return *this; 960227825Stheraven } 961227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 962227825Stheraven 963227825Stheraven _LIBCPP_INLINE_VISIBILITY 964227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 965227825Stheraven _LIBCPP_INLINE_VISIBILITY 966227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 967227825Stheraven _LIBCPP_INLINE_VISIBILITY 968227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 969227825Stheraven _LIBCPP_INLINE_VISIBILITY 970227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 971227825Stheraven 972227825Stheraven _LIBCPP_INLINE_VISIBILITY 973227825Stheraven reverse_iterator rbegin() _NOEXCEPT 974227825Stheraven {return reverse_iterator(end());} 975227825Stheraven _LIBCPP_INLINE_VISIBILITY 976227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 977227825Stheraven {return const_reverse_iterator(end());} 978227825Stheraven _LIBCPP_INLINE_VISIBILITY 979227825Stheraven reverse_iterator rend() _NOEXCEPT 980227825Stheraven {return reverse_iterator(begin());} 981227825Stheraven _LIBCPP_INLINE_VISIBILITY 982227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 983227825Stheraven {return const_reverse_iterator(begin());} 984227825Stheraven 985227825Stheraven _LIBCPP_INLINE_VISIBILITY 986227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 987227825Stheraven _LIBCPP_INLINE_VISIBILITY 988227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 989227825Stheraven _LIBCPP_INLINE_VISIBILITY 990227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 991227825Stheraven _LIBCPP_INLINE_VISIBILITY 992227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 993227825Stheraven 994227825Stheraven _LIBCPP_INLINE_VISIBILITY 995227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 996227825Stheraven _LIBCPP_INLINE_VISIBILITY 997227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 998227825Stheraven _LIBCPP_INLINE_VISIBILITY 999227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1000227825Stheraven 1001227825Stheraven // modifiers: 1002227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1003227825Stheraven template <class... _Args> 1004227825Stheraven _LIBCPP_INLINE_VISIBILITY 1005227825Stheraven iterator emplace(_Args&&... __args) 1006227825Stheraven {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1007227825Stheraven template <class... _Args> 1008227825Stheraven _LIBCPP_INLINE_VISIBILITY 1009227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 1010227825Stheraven {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1011227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1012227825Stheraven _LIBCPP_INLINE_VISIBILITY 1013227825Stheraven iterator insert(const value_type& __v) 1014227825Stheraven {return __tree_.__insert_multi(__v);} 1015227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1016227825Stheraven _LIBCPP_INLINE_VISIBILITY 1017227825Stheraven iterator insert(value_type&& __v) 1018227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 1019227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020227825Stheraven _LIBCPP_INLINE_VISIBILITY 1021227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 1022227825Stheraven {return __tree_.__insert_multi(__p, __v);} 1023227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1024227825Stheraven _LIBCPP_INLINE_VISIBILITY 1025227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 1026227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 1027227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1028227825Stheraven template <class _InputIterator> 1029227825Stheraven _LIBCPP_INLINE_VISIBILITY 1030227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 1031227825Stheraven { 1032227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 1033227825Stheraven __tree_.__insert_multi(__e, *__f); 1034227825Stheraven } 1035227825Stheraven 1036227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1037227825Stheraven _LIBCPP_INLINE_VISIBILITY 1038227825Stheraven void insert(initializer_list<value_type> __il) 1039227825Stheraven {insert(__il.begin(), __il.end());} 1040227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1041227825Stheraven 1042227825Stheraven _LIBCPP_INLINE_VISIBILITY 1043227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1044227825Stheraven _LIBCPP_INLINE_VISIBILITY 1045227825Stheraven size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1046227825Stheraven _LIBCPP_INLINE_VISIBILITY 1047227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 1048227825Stheraven {return __tree_.erase(__f, __l);} 1049227825Stheraven _LIBCPP_INLINE_VISIBILITY 1050227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 1051227825Stheraven 1052227825Stheraven _LIBCPP_INLINE_VISIBILITY 1053227825Stheraven void swap(multiset& __s) 1054227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1055227825Stheraven {__tree_.swap(__s.__tree_);} 1056227825Stheraven 1057227825Stheraven _LIBCPP_INLINE_VISIBILITY 1058227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1059227825Stheraven _LIBCPP_INLINE_VISIBILITY 1060227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 1061227825Stheraven _LIBCPP_INLINE_VISIBILITY 1062227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 1063227825Stheraven 1064227825Stheraven // set operations: 1065227825Stheraven _LIBCPP_INLINE_VISIBILITY 1066227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 1067227825Stheraven _LIBCPP_INLINE_VISIBILITY 1068227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1069261272Sdim#if _LIBCPP_STD_VER > 11 1070261272Sdim template <typename _K2> 1071227825Stheraven _LIBCPP_INLINE_VISIBILITY 1072261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1073261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 1074261272Sdim template <typename _K2> 1075261272Sdim _LIBCPP_INLINE_VISIBILITY 1076261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1077261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 1078261272Sdim#endif 1079261272Sdim 1080261272Sdim _LIBCPP_INLINE_VISIBILITY 1081227825Stheraven size_type count(const key_type& __k) const 1082227825Stheraven {return __tree_.__count_multi(__k);} 1083276792Sdim#if _LIBCPP_STD_VER > 11 1084276792Sdim template <typename _K2> 1085276792Sdim _LIBCPP_INLINE_VISIBILITY 1086276792Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1087276792Sdim count(const _K2& __k) {return __tree_.__count_multi(__k);} 1088276792Sdim#endif 1089261272Sdim 1090227825Stheraven _LIBCPP_INLINE_VISIBILITY 1091227825Stheraven iterator lower_bound(const key_type& __k) 1092227825Stheraven {return __tree_.lower_bound(__k);} 1093227825Stheraven _LIBCPP_INLINE_VISIBILITY 1094227825Stheraven const_iterator lower_bound(const key_type& __k) const 1095227825Stheraven {return __tree_.lower_bound(__k);} 1096261272Sdim#if _LIBCPP_STD_VER > 11 1097261272Sdim template <typename _K2> 1098227825Stheraven _LIBCPP_INLINE_VISIBILITY 1099261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1100261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1101261272Sdim 1102261272Sdim template <typename _K2> 1103261272Sdim _LIBCPP_INLINE_VISIBILITY 1104261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1105261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1106261272Sdim#endif 1107261272Sdim 1108261272Sdim _LIBCPP_INLINE_VISIBILITY 1109227825Stheraven iterator upper_bound(const key_type& __k) 1110227825Stheraven {return __tree_.upper_bound(__k);} 1111227825Stheraven _LIBCPP_INLINE_VISIBILITY 1112227825Stheraven const_iterator upper_bound(const key_type& __k) const 1113227825Stheraven {return __tree_.upper_bound(__k);} 1114261272Sdim#if _LIBCPP_STD_VER > 11 1115261272Sdim template <typename _K2> 1116227825Stheraven _LIBCPP_INLINE_VISIBILITY 1117261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1118261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1119261272Sdim template <typename _K2> 1120261272Sdim _LIBCPP_INLINE_VISIBILITY 1121261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1122261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1123261272Sdim#endif 1124261272Sdim 1125261272Sdim _LIBCPP_INLINE_VISIBILITY 1126227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 1127227825Stheraven {return __tree_.__equal_range_multi(__k);} 1128227825Stheraven _LIBCPP_INLINE_VISIBILITY 1129227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1130227825Stheraven {return __tree_.__equal_range_multi(__k);} 1131261272Sdim#if _LIBCPP_STD_VER > 11 1132261272Sdim template <typename _K2> 1133261272Sdim _LIBCPP_INLINE_VISIBILITY 1134261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1135261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1136261272Sdim template <typename _K2> 1137261272Sdim _LIBCPP_INLINE_VISIBILITY 1138261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1139261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1140261272Sdim#endif 1141227825Stheraven}; 1142227825Stheraven 1143227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1144227825Stheraven 1145227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1146227825Stheravenmultiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1147227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 1148227825Stheraven{ 1149227825Stheraven if (__a != __s.get_allocator()) 1150227825Stheraven { 1151227825Stheraven const_iterator __e = cend(); 1152227825Stheraven while (!__s.empty()) 1153227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1154227825Stheraven } 1155227825Stheraven} 1156227825Stheraven 1157227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1158227825Stheraven 1159227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1160227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1161227825Stheravenbool 1162227825Stheravenoperator==(const multiset<_Key, _Compare, _Allocator>& __x, 1163227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1164227825Stheraven{ 1165227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1166227825Stheraven} 1167227825Stheraven 1168227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1169227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1170227825Stheravenbool 1171227825Stheravenoperator< (const multiset<_Key, _Compare, _Allocator>& __x, 1172227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1173227825Stheraven{ 1174227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1175227825Stheraven} 1176227825Stheraven 1177227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1178227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1179227825Stheravenbool 1180227825Stheravenoperator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1181227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1182227825Stheraven{ 1183227825Stheraven return !(__x == __y); 1184227825Stheraven} 1185227825Stheraven 1186227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1187227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1188227825Stheravenbool 1189227825Stheravenoperator> (const multiset<_Key, _Compare, _Allocator>& __x, 1190227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1191227825Stheraven{ 1192227825Stheraven return __y < __x; 1193227825Stheraven} 1194227825Stheraven 1195227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1196227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1197227825Stheravenbool 1198227825Stheravenoperator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1199227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1200227825Stheraven{ 1201227825Stheraven return !(__x < __y); 1202227825Stheraven} 1203227825Stheraven 1204227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1205227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1206227825Stheravenbool 1207227825Stheravenoperator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1208227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1209227825Stheraven{ 1210227825Stheraven return !(__y < __x); 1211227825Stheraven} 1212227825Stheraven 1213227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1214227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1215227825Stheravenvoid 1216227825Stheravenswap(multiset<_Key, _Compare, _Allocator>& __x, 1217227825Stheraven multiset<_Key, _Compare, _Allocator>& __y) 1218227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1219227825Stheraven{ 1220227825Stheraven __x.swap(__y); 1221227825Stheraven} 1222227825Stheraven 1223227825Stheraven_LIBCPP_END_NAMESPACE_STD 1224227825Stheraven 1225227825Stheraven#endif // _LIBCPP_SET 1226