set revision 288943
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 412227825Stheravenprivate: 413227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 414227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 415227825Stheraven typedef typename __base::__node_holder __node_holder; 416227825Stheraven 417227825Stheraven __base __tree_; 418227825Stheraven 419227825Stheravenpublic: 420227825Stheraven typedef typename __base::pointer pointer; 421227825Stheraven typedef typename __base::const_pointer const_pointer; 422227825Stheraven typedef typename __base::size_type size_type; 423227825Stheraven typedef typename __base::difference_type difference_type; 424227825Stheraven typedef typename __base::const_iterator iterator; 425227825Stheraven typedef typename __base::const_iterator const_iterator; 426227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 427227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 428227825Stheraven 429227825Stheraven _LIBCPP_INLINE_VISIBILITY 430276792Sdim set() 431227825Stheraven _NOEXCEPT_( 432227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 433227825Stheraven is_nothrow_default_constructible<key_compare>::value && 434227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 435276792Sdim : __tree_(value_compare()) {} 436276792Sdim 437276792Sdim _LIBCPP_INLINE_VISIBILITY 438276792Sdim explicit set(const value_compare& __comp) 439276792Sdim _NOEXCEPT_( 440276792Sdim is_nothrow_default_constructible<allocator_type>::value && 441276792Sdim is_nothrow_copy_constructible<key_compare>::value) 442227825Stheraven : __tree_(__comp) {} 443276792Sdim 444227825Stheraven _LIBCPP_INLINE_VISIBILITY 445276792Sdim explicit set(const value_compare& __comp, const allocator_type& __a) 446227825Stheraven : __tree_(__comp, __a) {} 447227825Stheraven template <class _InputIterator> 448227825Stheraven _LIBCPP_INLINE_VISIBILITY 449227825Stheraven set(_InputIterator __f, _InputIterator __l, 450227825Stheraven const value_compare& __comp = value_compare()) 451227825Stheraven : __tree_(__comp) 452227825Stheraven { 453227825Stheraven insert(__f, __l); 454227825Stheraven } 455227825Stheraven 456227825Stheraven template <class _InputIterator> 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458227825Stheraven set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 459227825Stheraven const allocator_type& __a) 460227825Stheraven : __tree_(__comp, __a) 461227825Stheraven { 462227825Stheraven insert(__f, __l); 463227825Stheraven } 464227825Stheraven 465261272Sdim#if _LIBCPP_STD_VER > 11 466261272Sdim template <class _InputIterator> 467261272Sdim _LIBCPP_INLINE_VISIBILITY 468261272Sdim set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 469261272Sdim : set(__f, __l, key_compare(), __a) {} 470261272Sdim#endif 471261272Sdim 472227825Stheraven _LIBCPP_INLINE_VISIBILITY 473227825Stheraven set(const set& __s) 474227825Stheraven : __tree_(__s.__tree_) 475227825Stheraven { 476227825Stheraven insert(__s.begin(), __s.end()); 477227825Stheraven } 478227825Stheraven 479227825Stheraven _LIBCPP_INLINE_VISIBILITY 480227825Stheraven set& operator=(const set& __s) 481227825Stheraven { 482227825Stheraven __tree_ = __s.__tree_; 483227825Stheraven return *this; 484227825Stheraven } 485227825Stheraven 486227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 487227825Stheraven _LIBCPP_INLINE_VISIBILITY 488227825Stheraven set(set&& __s) 489227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 490227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 491227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 492227825Stheraven 493227825Stheraven _LIBCPP_INLINE_VISIBILITY 494227825Stheraven explicit set(const allocator_type& __a) 495227825Stheraven : __tree_(__a) {} 496227825Stheraven 497227825Stheraven _LIBCPP_INLINE_VISIBILITY 498227825Stheraven set(const set& __s, const allocator_type& __a) 499227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 500227825Stheraven { 501227825Stheraven insert(__s.begin(), __s.end()); 502227825Stheraven } 503227825Stheraven 504227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 505227825Stheraven set(set&& __s, const allocator_type& __a); 506227825Stheraven#endif 507227825Stheraven 508227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 509227825Stheraven _LIBCPP_INLINE_VISIBILITY 510227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 511227825Stheraven : __tree_(__comp) 512227825Stheraven { 513227825Stheraven insert(__il.begin(), __il.end()); 514227825Stheraven } 515227825Stheraven 516227825Stheraven _LIBCPP_INLINE_VISIBILITY 517227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp, 518227825Stheraven const allocator_type& __a) 519227825Stheraven : __tree_(__comp, __a) 520227825Stheraven { 521227825Stheraven insert(__il.begin(), __il.end()); 522227825Stheraven } 523227825Stheraven 524261272Sdim#if _LIBCPP_STD_VER > 11 525261272Sdim _LIBCPP_INLINE_VISIBILITY 526261272Sdim set(initializer_list<value_type> __il, const allocator_type& __a) 527261272Sdim : set(__il, key_compare(), __a) {} 528261272Sdim#endif 529261272Sdim 530227825Stheraven _LIBCPP_INLINE_VISIBILITY 531227825Stheraven set& operator=(initializer_list<value_type> __il) 532227825Stheraven { 533227825Stheraven __tree_.__assign_unique(__il.begin(), __il.end()); 534227825Stheraven return *this; 535227825Stheraven } 536227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 537227825Stheraven 538227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 539227825Stheraven _LIBCPP_INLINE_VISIBILITY 540227825Stheraven set& operator=(set&& __s) 541227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 542227825Stheraven { 543227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 544227825Stheraven return *this; 545227825Stheraven } 546227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 547227825Stheraven 548227825Stheraven _LIBCPP_INLINE_VISIBILITY 549227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 550227825Stheraven _LIBCPP_INLINE_VISIBILITY 551227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 552227825Stheraven _LIBCPP_INLINE_VISIBILITY 553227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 554227825Stheraven _LIBCPP_INLINE_VISIBILITY 555227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 556227825Stheraven 557227825Stheraven _LIBCPP_INLINE_VISIBILITY 558227825Stheraven reverse_iterator rbegin() _NOEXCEPT 559227825Stheraven {return reverse_iterator(end());} 560227825Stheraven _LIBCPP_INLINE_VISIBILITY 561227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 562227825Stheraven {return const_reverse_iterator(end());} 563227825Stheraven _LIBCPP_INLINE_VISIBILITY 564227825Stheraven reverse_iterator rend() _NOEXCEPT 565227825Stheraven {return reverse_iterator(begin());} 566227825Stheraven _LIBCPP_INLINE_VISIBILITY 567227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 568227825Stheraven {return const_reverse_iterator(begin());} 569227825Stheraven 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 572227825Stheraven _LIBCPP_INLINE_VISIBILITY 573227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 574227825Stheraven _LIBCPP_INLINE_VISIBILITY 575227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 576227825Stheraven _LIBCPP_INLINE_VISIBILITY 577227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 578227825Stheraven 579227825Stheraven _LIBCPP_INLINE_VISIBILITY 580227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 581227825Stheraven _LIBCPP_INLINE_VISIBILITY 582227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 583227825Stheraven _LIBCPP_INLINE_VISIBILITY 584227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 585227825Stheraven 586227825Stheraven // modifiers: 587227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 588227825Stheraven template <class... _Args> 589227825Stheraven _LIBCPP_INLINE_VISIBILITY 590227825Stheraven pair<iterator, bool> emplace(_Args&&... __args) 591227825Stheraven {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 592227825Stheraven template <class... _Args> 593227825Stheraven _LIBCPP_INLINE_VISIBILITY 594227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 595227825Stheraven {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 596227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 597227825Stheraven _LIBCPP_INLINE_VISIBILITY 598227825Stheraven pair<iterator,bool> insert(const value_type& __v) 599227825Stheraven {return __tree_.__insert_unique(__v);} 600227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 601227825Stheraven _LIBCPP_INLINE_VISIBILITY 602227825Stheraven pair<iterator,bool> insert(value_type&& __v) 603227825Stheraven {return __tree_.__insert_unique(_VSTD::move(__v));} 604227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 605227825Stheraven _LIBCPP_INLINE_VISIBILITY 606227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 607227825Stheraven {return __tree_.__insert_unique(__p, __v);} 608227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 609227825Stheraven _LIBCPP_INLINE_VISIBILITY 610227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 611227825Stheraven {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 612227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 613227825Stheraven template <class _InputIterator> 614227825Stheraven _LIBCPP_INLINE_VISIBILITY 615227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 616227825Stheraven { 617227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 618227825Stheraven __tree_.__insert_unique(__e, *__f); 619227825Stheraven } 620227825Stheraven 621227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 622227825Stheraven _LIBCPP_INLINE_VISIBILITY 623227825Stheraven void insert(initializer_list<value_type> __il) 624227825Stheraven {insert(__il.begin(), __il.end());} 625227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 626227825Stheraven 627227825Stheraven _LIBCPP_INLINE_VISIBILITY 628227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 629227825Stheraven _LIBCPP_INLINE_VISIBILITY 630227825Stheraven size_type erase(const key_type& __k) 631227825Stheraven {return __tree_.__erase_unique(__k);} 632227825Stheraven _LIBCPP_INLINE_VISIBILITY 633227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 634227825Stheraven {return __tree_.erase(__f, __l);} 635227825Stheraven _LIBCPP_INLINE_VISIBILITY 636227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 637227825Stheraven 638227825Stheraven _LIBCPP_INLINE_VISIBILITY 639227825Stheraven void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 640227825Stheraven {__tree_.swap(__s.__tree_);} 641227825Stheraven 642227825Stheraven _LIBCPP_INLINE_VISIBILITY 643227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 644227825Stheraven _LIBCPP_INLINE_VISIBILITY 645227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 646227825Stheraven _LIBCPP_INLINE_VISIBILITY 647227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 648227825Stheraven 649227825Stheraven // set operations: 650227825Stheraven _LIBCPP_INLINE_VISIBILITY 651227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 652227825Stheraven _LIBCPP_INLINE_VISIBILITY 653227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 654261272Sdim#if _LIBCPP_STD_VER > 11 655261272Sdim template <typename _K2> 656227825Stheraven _LIBCPP_INLINE_VISIBILITY 657261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 658261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 659261272Sdim template <typename _K2> 660261272Sdim _LIBCPP_INLINE_VISIBILITY 661261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 662261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 663261272Sdim#endif 664261272Sdim 665261272Sdim _LIBCPP_INLINE_VISIBILITY 666227825Stheraven size_type count(const key_type& __k) const 667227825Stheraven {return __tree_.__count_unique(__k);} 668276792Sdim#if _LIBCPP_STD_VER > 11 669276792Sdim template <typename _K2> 670227825Stheraven _LIBCPP_INLINE_VISIBILITY 671276792Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 672276792Sdim count(const _K2& __k) {return __tree_.__count_unique(__k);} 673276792Sdim#endif 674276792Sdim _LIBCPP_INLINE_VISIBILITY 675227825Stheraven iterator lower_bound(const key_type& __k) 676227825Stheraven {return __tree_.lower_bound(__k);} 677227825Stheraven _LIBCPP_INLINE_VISIBILITY 678227825Stheraven const_iterator lower_bound(const key_type& __k) const 679227825Stheraven {return __tree_.lower_bound(__k);} 680261272Sdim#if _LIBCPP_STD_VER > 11 681261272Sdim template <typename _K2> 682227825Stheraven _LIBCPP_INLINE_VISIBILITY 683261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 684261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 685261272Sdim 686261272Sdim template <typename _K2> 687261272Sdim _LIBCPP_INLINE_VISIBILITY 688261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 689261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 690261272Sdim#endif 691261272Sdim 692261272Sdim _LIBCPP_INLINE_VISIBILITY 693227825Stheraven iterator upper_bound(const key_type& __k) 694227825Stheraven {return __tree_.upper_bound(__k);} 695227825Stheraven _LIBCPP_INLINE_VISIBILITY 696227825Stheraven const_iterator upper_bound(const key_type& __k) const 697227825Stheraven {return __tree_.upper_bound(__k);} 698261272Sdim#if _LIBCPP_STD_VER > 11 699261272Sdim template <typename _K2> 700227825Stheraven _LIBCPP_INLINE_VISIBILITY 701261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 702261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 703261272Sdim template <typename _K2> 704261272Sdim _LIBCPP_INLINE_VISIBILITY 705261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 706261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 707261272Sdim#endif 708261272Sdim 709261272Sdim _LIBCPP_INLINE_VISIBILITY 710227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 711227825Stheraven {return __tree_.__equal_range_unique(__k);} 712227825Stheraven _LIBCPP_INLINE_VISIBILITY 713227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 714227825Stheraven {return __tree_.__equal_range_unique(__k);} 715261272Sdim#if _LIBCPP_STD_VER > 11 716261272Sdim template <typename _K2> 717261272Sdim _LIBCPP_INLINE_VISIBILITY 718261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 719261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 720261272Sdim template <typename _K2> 721261272Sdim _LIBCPP_INLINE_VISIBILITY 722261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 723261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 724261272Sdim#endif 725227825Stheraven}; 726227825Stheraven 727227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 728227825Stheraven 729227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 730227825Stheravenset<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 731227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 732227825Stheraven{ 733227825Stheraven if (__a != __s.get_allocator()) 734227825Stheraven { 735227825Stheraven const_iterator __e = cend(); 736227825Stheraven while (!__s.empty()) 737227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 738227825Stheraven } 739227825Stheraven} 740227825Stheraven 741227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 742227825Stheraven 743227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 744227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 745227825Stheravenbool 746227825Stheravenoperator==(const set<_Key, _Compare, _Allocator>& __x, 747227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 748227825Stheraven{ 749227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 750227825Stheraven} 751227825Stheraven 752227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 753227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 754227825Stheravenbool 755227825Stheravenoperator< (const set<_Key, _Compare, _Allocator>& __x, 756227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 757227825Stheraven{ 758227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 759227825Stheraven} 760227825Stheraven 761227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 762227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 763227825Stheravenbool 764227825Stheravenoperator!=(const set<_Key, _Compare, _Allocator>& __x, 765227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 766227825Stheraven{ 767227825Stheraven return !(__x == __y); 768227825Stheraven} 769227825Stheraven 770227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 771227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 772227825Stheravenbool 773227825Stheravenoperator> (const set<_Key, _Compare, _Allocator>& __x, 774227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 775227825Stheraven{ 776227825Stheraven return __y < __x; 777227825Stheraven} 778227825Stheraven 779227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 780227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 781227825Stheravenbool 782227825Stheravenoperator>=(const set<_Key, _Compare, _Allocator>& __x, 783227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 784227825Stheraven{ 785227825Stheraven return !(__x < __y); 786227825Stheraven} 787227825Stheraven 788227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 789227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 790227825Stheravenbool 791227825Stheravenoperator<=(const set<_Key, _Compare, _Allocator>& __x, 792227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 793227825Stheraven{ 794227825Stheraven return !(__y < __x); 795227825Stheraven} 796227825Stheraven 797227825Stheraven// specialized algorithms: 798227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 799227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 800227825Stheravenvoid 801227825Stheravenswap(set<_Key, _Compare, _Allocator>& __x, 802227825Stheraven set<_Key, _Compare, _Allocator>& __y) 803227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 804227825Stheraven{ 805227825Stheraven __x.swap(__y); 806227825Stheraven} 807227825Stheraven 808227825Stheraventemplate <class _Key, class _Compare = less<_Key>, 809227825Stheraven class _Allocator = allocator<_Key> > 810261272Sdimclass _LIBCPP_TYPE_VIS_ONLY multiset 811227825Stheraven{ 812227825Stheravenpublic: 813227825Stheraven // types: 814227825Stheraven typedef _Key key_type; 815227825Stheraven typedef key_type value_type; 816227825Stheraven typedef _Compare key_compare; 817227825Stheraven typedef key_compare value_compare; 818227825Stheraven typedef _Allocator allocator_type; 819227825Stheraven typedef value_type& reference; 820227825Stheraven typedef const value_type& const_reference; 821227825Stheraven 822227825Stheravenprivate: 823227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 824227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 825227825Stheraven typedef typename __base::__node_holder __node_holder; 826227825Stheraven 827227825Stheraven __base __tree_; 828227825Stheraven 829227825Stheravenpublic: 830227825Stheraven typedef typename __base::pointer pointer; 831227825Stheraven typedef typename __base::const_pointer const_pointer; 832227825Stheraven typedef typename __base::size_type size_type; 833227825Stheraven typedef typename __base::difference_type difference_type; 834227825Stheraven typedef typename __base::const_iterator iterator; 835227825Stheraven typedef typename __base::const_iterator const_iterator; 836227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 837227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 838227825Stheraven 839227825Stheraven // construct/copy/destroy: 840227825Stheraven _LIBCPP_INLINE_VISIBILITY 841276792Sdim multiset() 842227825Stheraven _NOEXCEPT_( 843227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 844227825Stheraven is_nothrow_default_constructible<key_compare>::value && 845227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 846276792Sdim : __tree_(value_compare()) {} 847276792Sdim 848276792Sdim _LIBCPP_INLINE_VISIBILITY 849276792Sdim explicit multiset(const value_compare& __comp) 850276792Sdim _NOEXCEPT_( 851276792Sdim is_nothrow_default_constructible<allocator_type>::value && 852276792Sdim is_nothrow_copy_constructible<key_compare>::value) 853227825Stheraven : __tree_(__comp) {} 854276792Sdim 855227825Stheraven _LIBCPP_INLINE_VISIBILITY 856276792Sdim explicit multiset(const value_compare& __comp, const allocator_type& __a) 857227825Stheraven : __tree_(__comp, __a) {} 858227825Stheraven template <class _InputIterator> 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 861227825Stheraven const value_compare& __comp = value_compare()) 862227825Stheraven : __tree_(__comp) 863227825Stheraven { 864227825Stheraven insert(__f, __l); 865227825Stheraven } 866227825Stheraven 867261272Sdim#if _LIBCPP_STD_VER > 11 868261272Sdim template <class _InputIterator> 869261272Sdim _LIBCPP_INLINE_VISIBILITY 870261272Sdim multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 871261272Sdim : multiset(__f, __l, key_compare(), __a) {} 872261272Sdim#endif 873261272Sdim 874227825Stheraven template <class _InputIterator> 875227825Stheraven _LIBCPP_INLINE_VISIBILITY 876227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 877227825Stheraven const value_compare& __comp, const allocator_type& __a) 878227825Stheraven : __tree_(__comp, __a) 879227825Stheraven { 880227825Stheraven insert(__f, __l); 881227825Stheraven } 882227825Stheraven 883227825Stheraven _LIBCPP_INLINE_VISIBILITY 884227825Stheraven multiset(const multiset& __s) 885227825Stheraven : __tree_(__s.__tree_.value_comp(), 886227825Stheraven __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 887227825Stheraven { 888227825Stheraven insert(__s.begin(), __s.end()); 889227825Stheraven } 890227825Stheraven 891227825Stheraven _LIBCPP_INLINE_VISIBILITY 892227825Stheraven multiset& operator=(const multiset& __s) 893227825Stheraven { 894227825Stheraven __tree_ = __s.__tree_; 895227825Stheraven return *this; 896227825Stheraven } 897227825Stheraven 898227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 899227825Stheraven _LIBCPP_INLINE_VISIBILITY 900227825Stheraven multiset(multiset&& __s) 901227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 902227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 903227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 904227825Stheraven _LIBCPP_INLINE_VISIBILITY 905227825Stheraven explicit multiset(const allocator_type& __a) 906227825Stheraven : __tree_(__a) {} 907227825Stheraven _LIBCPP_INLINE_VISIBILITY 908227825Stheraven multiset(const multiset& __s, const allocator_type& __a) 909227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 910227825Stheraven { 911227825Stheraven insert(__s.begin(), __s.end()); 912227825Stheraven } 913227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 914227825Stheraven multiset(multiset&& __s, const allocator_type& __a); 915227825Stheraven#endif 916227825Stheraven 917227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 918227825Stheraven _LIBCPP_INLINE_VISIBILITY 919227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 920227825Stheraven : __tree_(__comp) 921227825Stheraven { 922227825Stheraven insert(__il.begin(), __il.end()); 923227825Stheraven } 924227825Stheraven 925227825Stheraven _LIBCPP_INLINE_VISIBILITY 926227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp, 927227825Stheraven const allocator_type& __a) 928227825Stheraven : __tree_(__comp, __a) 929227825Stheraven { 930227825Stheraven insert(__il.begin(), __il.end()); 931227825Stheraven } 932227825Stheraven 933261272Sdim#if _LIBCPP_STD_VER > 11 934261272Sdim _LIBCPP_INLINE_VISIBILITY 935261272Sdim multiset(initializer_list<value_type> __il, const allocator_type& __a) 936261272Sdim : multiset(__il, key_compare(), __a) {} 937261272Sdim#endif 938261272Sdim 939227825Stheraven _LIBCPP_INLINE_VISIBILITY 940227825Stheraven multiset& operator=(initializer_list<value_type> __il) 941227825Stheraven { 942227825Stheraven __tree_.__assign_multi(__il.begin(), __il.end()); 943227825Stheraven return *this; 944227825Stheraven } 945227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 946227825Stheraven 947227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 948227825Stheraven _LIBCPP_INLINE_VISIBILITY 949227825Stheraven multiset& operator=(multiset&& __s) 950227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 951227825Stheraven { 952227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 953227825Stheraven return *this; 954227825Stheraven } 955227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 956227825Stheraven 957227825Stheraven _LIBCPP_INLINE_VISIBILITY 958227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 959227825Stheraven _LIBCPP_INLINE_VISIBILITY 960227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 961227825Stheraven _LIBCPP_INLINE_VISIBILITY 962227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 963227825Stheraven _LIBCPP_INLINE_VISIBILITY 964227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 965227825Stheraven 966227825Stheraven _LIBCPP_INLINE_VISIBILITY 967227825Stheraven reverse_iterator rbegin() _NOEXCEPT 968227825Stheraven {return reverse_iterator(end());} 969227825Stheraven _LIBCPP_INLINE_VISIBILITY 970227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 971227825Stheraven {return const_reverse_iterator(end());} 972227825Stheraven _LIBCPP_INLINE_VISIBILITY 973227825Stheraven reverse_iterator rend() _NOEXCEPT 974227825Stheraven {return reverse_iterator(begin());} 975227825Stheraven _LIBCPP_INLINE_VISIBILITY 976227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 977227825Stheraven {return const_reverse_iterator(begin());} 978227825Stheraven 979227825Stheraven _LIBCPP_INLINE_VISIBILITY 980227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 981227825Stheraven _LIBCPP_INLINE_VISIBILITY 982227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 983227825Stheraven _LIBCPP_INLINE_VISIBILITY 984227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 985227825Stheraven _LIBCPP_INLINE_VISIBILITY 986227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 987227825Stheraven 988227825Stheraven _LIBCPP_INLINE_VISIBILITY 989227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 990227825Stheraven _LIBCPP_INLINE_VISIBILITY 991227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 992227825Stheraven _LIBCPP_INLINE_VISIBILITY 993227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 994227825Stheraven 995227825Stheraven // modifiers: 996227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 997227825Stheraven template <class... _Args> 998227825Stheraven _LIBCPP_INLINE_VISIBILITY 999227825Stheraven iterator emplace(_Args&&... __args) 1000227825Stheraven {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1001227825Stheraven template <class... _Args> 1002227825Stheraven _LIBCPP_INLINE_VISIBILITY 1003227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 1004227825Stheraven {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1005227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1006227825Stheraven _LIBCPP_INLINE_VISIBILITY 1007227825Stheraven iterator insert(const value_type& __v) 1008227825Stheraven {return __tree_.__insert_multi(__v);} 1009227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1010227825Stheraven _LIBCPP_INLINE_VISIBILITY 1011227825Stheraven iterator insert(value_type&& __v) 1012227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 1013227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1014227825Stheraven _LIBCPP_INLINE_VISIBILITY 1015227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 1016227825Stheraven {return __tree_.__insert_multi(__p, __v);} 1017227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1018227825Stheraven _LIBCPP_INLINE_VISIBILITY 1019227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 1020227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 1021227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1022227825Stheraven template <class _InputIterator> 1023227825Stheraven _LIBCPP_INLINE_VISIBILITY 1024227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 1025227825Stheraven { 1026227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 1027227825Stheraven __tree_.__insert_multi(__e, *__f); 1028227825Stheraven } 1029227825Stheraven 1030227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1031227825Stheraven _LIBCPP_INLINE_VISIBILITY 1032227825Stheraven void insert(initializer_list<value_type> __il) 1033227825Stheraven {insert(__il.begin(), __il.end());} 1034227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1035227825Stheraven 1036227825Stheraven _LIBCPP_INLINE_VISIBILITY 1037227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1038227825Stheraven _LIBCPP_INLINE_VISIBILITY 1039227825Stheraven size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1040227825Stheraven _LIBCPP_INLINE_VISIBILITY 1041227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 1042227825Stheraven {return __tree_.erase(__f, __l);} 1043227825Stheraven _LIBCPP_INLINE_VISIBILITY 1044227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 1045227825Stheraven 1046227825Stheraven _LIBCPP_INLINE_VISIBILITY 1047227825Stheraven void swap(multiset& __s) 1048227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1049227825Stheraven {__tree_.swap(__s.__tree_);} 1050227825Stheraven 1051227825Stheraven _LIBCPP_INLINE_VISIBILITY 1052227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1053227825Stheraven _LIBCPP_INLINE_VISIBILITY 1054227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 1055227825Stheraven _LIBCPP_INLINE_VISIBILITY 1056227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 1057227825Stheraven 1058227825Stheraven // set operations: 1059227825Stheraven _LIBCPP_INLINE_VISIBILITY 1060227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 1061227825Stheraven _LIBCPP_INLINE_VISIBILITY 1062227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1063261272Sdim#if _LIBCPP_STD_VER > 11 1064261272Sdim template <typename _K2> 1065227825Stheraven _LIBCPP_INLINE_VISIBILITY 1066261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1067261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 1068261272Sdim template <typename _K2> 1069261272Sdim _LIBCPP_INLINE_VISIBILITY 1070261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1071261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 1072261272Sdim#endif 1073261272Sdim 1074261272Sdim _LIBCPP_INLINE_VISIBILITY 1075227825Stheraven size_type count(const key_type& __k) const 1076227825Stheraven {return __tree_.__count_multi(__k);} 1077276792Sdim#if _LIBCPP_STD_VER > 11 1078276792Sdim template <typename _K2> 1079276792Sdim _LIBCPP_INLINE_VISIBILITY 1080276792Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1081276792Sdim count(const _K2& __k) {return __tree_.__count_multi(__k);} 1082276792Sdim#endif 1083261272Sdim 1084227825Stheraven _LIBCPP_INLINE_VISIBILITY 1085227825Stheraven iterator lower_bound(const key_type& __k) 1086227825Stheraven {return __tree_.lower_bound(__k);} 1087227825Stheraven _LIBCPP_INLINE_VISIBILITY 1088227825Stheraven const_iterator lower_bound(const key_type& __k) const 1089227825Stheraven {return __tree_.lower_bound(__k);} 1090261272Sdim#if _LIBCPP_STD_VER > 11 1091261272Sdim template <typename _K2> 1092227825Stheraven _LIBCPP_INLINE_VISIBILITY 1093261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1094261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1095261272Sdim 1096261272Sdim template <typename _K2> 1097261272Sdim _LIBCPP_INLINE_VISIBILITY 1098261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1099261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1100261272Sdim#endif 1101261272Sdim 1102261272Sdim _LIBCPP_INLINE_VISIBILITY 1103227825Stheraven iterator upper_bound(const key_type& __k) 1104227825Stheraven {return __tree_.upper_bound(__k);} 1105227825Stheraven _LIBCPP_INLINE_VISIBILITY 1106227825Stheraven const_iterator upper_bound(const key_type& __k) const 1107227825Stheraven {return __tree_.upper_bound(__k);} 1108261272Sdim#if _LIBCPP_STD_VER > 11 1109261272Sdim template <typename _K2> 1110227825Stheraven _LIBCPP_INLINE_VISIBILITY 1111261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1112261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1113261272Sdim template <typename _K2> 1114261272Sdim _LIBCPP_INLINE_VISIBILITY 1115261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1116261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1117261272Sdim#endif 1118261272Sdim 1119261272Sdim _LIBCPP_INLINE_VISIBILITY 1120227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 1121227825Stheraven {return __tree_.__equal_range_multi(__k);} 1122227825Stheraven _LIBCPP_INLINE_VISIBILITY 1123227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1124227825Stheraven {return __tree_.__equal_range_multi(__k);} 1125261272Sdim#if _LIBCPP_STD_VER > 11 1126261272Sdim template <typename _K2> 1127261272Sdim _LIBCPP_INLINE_VISIBILITY 1128261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1129261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1130261272Sdim template <typename _K2> 1131261272Sdim _LIBCPP_INLINE_VISIBILITY 1132261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1133261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1134261272Sdim#endif 1135227825Stheraven}; 1136227825Stheraven 1137227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1138227825Stheraven 1139227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1140227825Stheravenmultiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1141227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 1142227825Stheraven{ 1143227825Stheraven if (__a != __s.get_allocator()) 1144227825Stheraven { 1145227825Stheraven const_iterator __e = cend(); 1146227825Stheraven while (!__s.empty()) 1147227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1148227825Stheraven } 1149227825Stheraven} 1150227825Stheraven 1151227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1152227825Stheraven 1153227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1154227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1155227825Stheravenbool 1156227825Stheravenoperator==(const multiset<_Key, _Compare, _Allocator>& __x, 1157227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1158227825Stheraven{ 1159227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1160227825Stheraven} 1161227825Stheraven 1162227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1163227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1164227825Stheravenbool 1165227825Stheravenoperator< (const multiset<_Key, _Compare, _Allocator>& __x, 1166227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1167227825Stheraven{ 1168227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1169227825Stheraven} 1170227825Stheraven 1171227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1172227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1173227825Stheravenbool 1174227825Stheravenoperator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1175227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1176227825Stheraven{ 1177227825Stheraven return !(__x == __y); 1178227825Stheraven} 1179227825Stheraven 1180227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1181227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1182227825Stheravenbool 1183227825Stheravenoperator> (const multiset<_Key, _Compare, _Allocator>& __x, 1184227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1185227825Stheraven{ 1186227825Stheraven return __y < __x; 1187227825Stheraven} 1188227825Stheraven 1189227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1190227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1191227825Stheravenbool 1192227825Stheravenoperator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1193227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1194227825Stheraven{ 1195227825Stheraven return !(__x < __y); 1196227825Stheraven} 1197227825Stheraven 1198227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1199227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1200227825Stheravenbool 1201227825Stheravenoperator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1202227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1203227825Stheraven{ 1204227825Stheraven return !(__y < __x); 1205227825Stheraven} 1206227825Stheraven 1207227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1208227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1209227825Stheravenvoid 1210227825Stheravenswap(multiset<_Key, _Compare, _Allocator>& __x, 1211227825Stheraven multiset<_Key, _Compare, _Allocator>& __y) 1212227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1213227825Stheraven{ 1214227825Stheraven __x.swap(__y); 1215227825Stheraven} 1216227825Stheraven 1217227825Stheraven_LIBCPP_END_NAMESPACE_STD 1218227825Stheraven 1219227825Stheraven#endif // _LIBCPP_SET 1220