set revision 276792
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); 119227825Stheraven size_type erase(const key_type& k); 120227825Stheraven iterator erase(const_iterator first, const_iterator last); 121227825Stheraven void clear() noexcept; 122227825Stheraven 123227825Stheraven void swap(set& s) 124227825Stheraven noexcept( 125227825Stheraven __is_nothrow_swappable<key_compare>::value && 126227825Stheraven (!allocator_type::propagate_on_container_swap::value || 127227825Stheraven __is_nothrow_swappable<allocator_type>::value)); 128227825Stheraven 129227825Stheraven // observers: 130227825Stheraven allocator_type get_allocator() const noexcept; 131227825Stheraven key_compare key_comp() const; 132227825Stheraven value_compare value_comp() const; 133227825Stheraven 134227825Stheraven // set operations: 135227825Stheraven iterator find(const key_type& k); 136227825Stheraven const_iterator find(const key_type& k) const; 137261272Sdim template<typename K> 138261272Sdim iterator find(const K& x); 139261272Sdim template<typename K> 140261272Sdim const_iterator find(const K& x) const; // C++14 141261272Sdim template<typename K> 142261272Sdim size_type count(const K& x) const; // C++14 143261272Sdim 144227825Stheraven size_type count(const key_type& k) const; 145227825Stheraven iterator lower_bound(const key_type& k); 146227825Stheraven const_iterator lower_bound(const key_type& k) const; 147261272Sdim template<typename K> 148261272Sdim iterator lower_bound(const K& x); // C++14 149261272Sdim template<typename K> 150261272Sdim const_iterator lower_bound(const K& x) const; // C++14 151261272Sdim 152227825Stheraven iterator upper_bound(const key_type& k); 153227825Stheraven const_iterator upper_bound(const key_type& k) const; 154261272Sdim template<typename K> 155261272Sdim iterator upper_bound(const K& x); // C++14 156261272Sdim template<typename K> 157261272Sdim const_iterator upper_bound(const K& x) const; // C++14 158227825Stheraven pair<iterator,iterator> equal_range(const key_type& k); 159227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 160261272Sdim template<typename K> 161261272Sdim pair<iterator,iterator> equal_range(const K& x); // C++14 162261272Sdim template<typename K> 163261272Sdim pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 164227825Stheraven}; 165227825Stheraven 166227825Stheraventemplate <class Key, class Compare, class Allocator> 167227825Stheravenbool 168227825Stheravenoperator==(const set<Key, Compare, Allocator>& x, 169227825Stheraven const set<Key, Compare, Allocator>& y); 170227825Stheraven 171227825Stheraventemplate <class Key, class Compare, class Allocator> 172227825Stheravenbool 173227825Stheravenoperator< (const set<Key, Compare, Allocator>& x, 174227825Stheraven const set<Key, Compare, Allocator>& y); 175227825Stheraven 176227825Stheraventemplate <class Key, class Compare, class Allocator> 177227825Stheravenbool 178227825Stheravenoperator!=(const set<Key, Compare, Allocator>& x, 179227825Stheraven const set<Key, Compare, Allocator>& y); 180227825Stheraven 181227825Stheraventemplate <class Key, class Compare, class Allocator> 182227825Stheravenbool 183227825Stheravenoperator> (const set<Key, Compare, Allocator>& x, 184227825Stheraven const set<Key, Compare, Allocator>& y); 185227825Stheraven 186227825Stheraventemplate <class Key, class Compare, class Allocator> 187227825Stheravenbool 188227825Stheravenoperator>=(const set<Key, Compare, Allocator>& x, 189227825Stheraven const set<Key, Compare, Allocator>& y); 190227825Stheraven 191227825Stheraventemplate <class Key, class Compare, class Allocator> 192227825Stheravenbool 193227825Stheravenoperator<=(const set<Key, Compare, Allocator>& x, 194227825Stheraven const set<Key, Compare, Allocator>& y); 195227825Stheraven 196227825Stheraven// specialized algorithms: 197227825Stheraventemplate <class Key, class Compare, class Allocator> 198227825Stheravenvoid 199227825Stheravenswap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 200227825Stheraven noexcept(noexcept(x.swap(y))); 201227825Stheraven 202227825Stheraventemplate <class Key, class Compare = less<Key>, 203227825Stheraven class Allocator = allocator<Key>> 204227825Stheravenclass multiset 205227825Stheraven{ 206227825Stheravenpublic: 207227825Stheraven // types: 208227825Stheraven typedef Key key_type; 209227825Stheraven typedef key_type value_type; 210227825Stheraven typedef Compare key_compare; 211227825Stheraven typedef key_compare value_compare; 212227825Stheraven typedef Allocator allocator_type; 213227825Stheraven typedef typename allocator_type::reference reference; 214227825Stheraven typedef typename allocator_type::const_reference const_reference; 215227825Stheraven typedef typename allocator_type::size_type size_type; 216227825Stheraven typedef typename allocator_type::difference_type difference_type; 217227825Stheraven typedef typename allocator_type::pointer pointer; 218227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 219227825Stheraven 220227825Stheraven typedef implementation-defined iterator; 221227825Stheraven typedef implementation-defined const_iterator; 222227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 223227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 224227825Stheraven 225227825Stheraven // construct/copy/destroy: 226227825Stheraven multiset() 227227825Stheraven noexcept( 228227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 229227825Stheraven is_nothrow_default_constructible<key_compare>::value && 230227825Stheraven is_nothrow_copy_constructible<key_compare>::value); 231227825Stheraven explicit multiset(const value_compare& comp); 232227825Stheraven multiset(const value_compare& comp, const allocator_type& a); 233227825Stheraven template <class InputIterator> 234227825Stheraven multiset(InputIterator first, InputIterator last, 235227825Stheraven const value_compare& comp = value_compare()); 236227825Stheraven template <class InputIterator> 237227825Stheraven multiset(InputIterator first, InputIterator last, 238227825Stheraven const value_compare& comp, const allocator_type& a); 239227825Stheraven multiset(const multiset& s); 240227825Stheraven multiset(multiset&& s) 241227825Stheraven noexcept( 242227825Stheraven is_nothrow_move_constructible<allocator_type>::value && 243227825Stheraven is_nothrow_move_constructible<key_compare>::value); 244227825Stheraven explicit multiset(const allocator_type& a); 245227825Stheraven multiset(const multiset& s, const allocator_type& a); 246227825Stheraven multiset(multiset&& s, const allocator_type& a); 247227825Stheraven multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 248227825Stheraven multiset(initializer_list<value_type> il, const value_compare& comp, 249227825Stheraven const allocator_type& a); 250261272Sdim template <class InputIterator> 251261272Sdim multiset(InputIterator first, InputIterator last, const allocator_type& a) 252261272Sdim : set(first, last, Compare(), a) {} // C++14 253261272Sdim multiset(initializer_list<value_type> il, const allocator_type& a) 254261272Sdim : set(il, Compare(), a) {} // C++14 255227825Stheraven ~multiset(); 256227825Stheraven 257227825Stheraven multiset& operator=(const multiset& s); 258227825Stheraven multiset& operator=(multiset&& s) 259227825Stheraven noexcept( 260227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 261227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 262227825Stheraven is_nothrow_move_assignable<key_compare>::value); 263227825Stheraven multiset& operator=(initializer_list<value_type> il); 264227825Stheraven 265227825Stheraven // iterators: 266227825Stheraven iterator begin() noexcept; 267227825Stheraven const_iterator begin() const noexcept; 268227825Stheraven iterator end() noexcept; 269227825Stheraven const_iterator end() const noexcept; 270227825Stheraven 271227825Stheraven reverse_iterator rbegin() noexcept; 272227825Stheraven const_reverse_iterator rbegin() const noexcept; 273227825Stheraven reverse_iterator rend() noexcept; 274227825Stheraven const_reverse_iterator rend() const noexcept; 275227825Stheraven 276227825Stheraven const_iterator cbegin() const noexcept; 277227825Stheraven const_iterator cend() const noexcept; 278227825Stheraven const_reverse_iterator crbegin() const noexcept; 279227825Stheraven const_reverse_iterator crend() const noexcept; 280227825Stheraven 281227825Stheraven // capacity: 282227825Stheraven bool empty() const noexcept; 283227825Stheraven size_type size() const noexcept; 284227825Stheraven size_type max_size() const noexcept; 285227825Stheraven 286227825Stheraven // modifiers: 287227825Stheraven template <class... Args> 288227825Stheraven iterator emplace(Args&&... args); 289227825Stheraven template <class... Args> 290227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 291227825Stheraven iterator insert(const value_type& v); 292227825Stheraven iterator insert(value_type&& v); 293227825Stheraven iterator insert(const_iterator position, const value_type& v); 294227825Stheraven iterator insert(const_iterator position, value_type&& v); 295227825Stheraven template <class InputIterator> 296227825Stheraven void insert(InputIterator first, InputIterator last); 297227825Stheraven void insert(initializer_list<value_type> il); 298227825Stheraven 299227825Stheraven iterator erase(const_iterator position); 300227825Stheraven size_type erase(const key_type& k); 301227825Stheraven iterator erase(const_iterator first, const_iterator last); 302227825Stheraven void clear() noexcept; 303227825Stheraven 304227825Stheraven void swap(multiset& s) 305227825Stheraven noexcept( 306227825Stheraven __is_nothrow_swappable<key_compare>::value && 307227825Stheraven (!allocator_type::propagate_on_container_swap::value || 308227825Stheraven __is_nothrow_swappable<allocator_type>::value)); 309227825Stheraven 310227825Stheraven // observers: 311227825Stheraven allocator_type get_allocator() const noexcept; 312227825Stheraven key_compare key_comp() const; 313227825Stheraven value_compare value_comp() const; 314227825Stheraven 315227825Stheraven // set operations: 316227825Stheraven iterator find(const key_type& k); 317227825Stheraven const_iterator find(const key_type& k) const; 318261272Sdim template<typename K> 319261272Sdim iterator find(const K& x); 320261272Sdim template<typename K> 321261272Sdim const_iterator find(const K& x) const; // C++14 322261272Sdim 323227825Stheraven size_type count(const key_type& k) const; 324227825Stheraven iterator lower_bound(const key_type& k); 325227825Stheraven const_iterator lower_bound(const key_type& k) const; 326261272Sdim template<typename K> 327261272Sdim iterator lower_bound(const K& x); // C++14 328261272Sdim template<typename K> 329261272Sdim const_iterator lower_bound(const K& x) const; // C++14 330261272Sdim 331227825Stheraven iterator upper_bound(const key_type& k); 332227825Stheraven const_iterator upper_bound(const key_type& k) const; 333261272Sdim template<typename K> 334261272Sdim iterator upper_bound(const K& x); // C++14 335261272Sdim template<typename K> 336261272Sdim const_iterator upper_bound(const K& x) const; // C++14 337261272Sdim 338227825Stheraven pair<iterator,iterator> equal_range(const key_type& k); 339227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 340261272Sdim template<typename K> 341261272Sdim pair<iterator,iterator> equal_range(const K& x); // C++14 342261272Sdim template<typename K> 343261272Sdim pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 344227825Stheraven}; 345227825Stheraven 346227825Stheraventemplate <class Key, class Compare, class Allocator> 347227825Stheravenbool 348227825Stheravenoperator==(const multiset<Key, Compare, Allocator>& x, 349227825Stheraven const multiset<Key, Compare, Allocator>& y); 350227825Stheraven 351227825Stheraventemplate <class Key, class Compare, class Allocator> 352227825Stheravenbool 353227825Stheravenoperator< (const multiset<Key, Compare, Allocator>& x, 354227825Stheraven const multiset<Key, Compare, Allocator>& y); 355227825Stheraven 356227825Stheraventemplate <class Key, class Compare, class Allocator> 357227825Stheravenbool 358227825Stheravenoperator!=(const multiset<Key, Compare, Allocator>& x, 359227825Stheraven const multiset<Key, Compare, Allocator>& y); 360227825Stheraven 361227825Stheraventemplate <class Key, class Compare, class Allocator> 362227825Stheravenbool 363227825Stheravenoperator> (const multiset<Key, Compare, Allocator>& x, 364227825Stheraven const multiset<Key, Compare, Allocator>& y); 365227825Stheraven 366227825Stheraventemplate <class Key, class Compare, class Allocator> 367227825Stheravenbool 368227825Stheravenoperator>=(const multiset<Key, Compare, Allocator>& x, 369227825Stheraven const multiset<Key, Compare, Allocator>& y); 370227825Stheraven 371227825Stheraventemplate <class Key, class Compare, class Allocator> 372227825Stheravenbool 373227825Stheravenoperator<=(const multiset<Key, Compare, Allocator>& x, 374227825Stheraven const multiset<Key, Compare, Allocator>& y); 375227825Stheraven 376227825Stheraven// specialized algorithms: 377227825Stheraventemplate <class Key, class Compare, class Allocator> 378227825Stheravenvoid 379227825Stheravenswap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 380227825Stheraven noexcept(noexcept(x.swap(y))); 381227825Stheraven 382227825Stheraven} // std 383227825Stheraven 384227825Stheraven*/ 385227825Stheraven 386227825Stheraven#include <__config> 387227825Stheraven#include <__tree> 388227825Stheraven#include <functional> 389227825Stheraven 390227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 391227825Stheraven#pragma GCC system_header 392227825Stheraven#endif 393227825Stheraven 394227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 395227825Stheraven 396227825Stheraventemplate <class _Key, class _Compare = less<_Key>, 397227825Stheraven class _Allocator = allocator<_Key> > 398261272Sdimclass _LIBCPP_TYPE_VIS_ONLY set 399227825Stheraven{ 400227825Stheravenpublic: 401227825Stheraven // types: 402227825Stheraven typedef _Key key_type; 403227825Stheraven typedef key_type value_type; 404227825Stheraven typedef _Compare key_compare; 405227825Stheraven typedef key_compare value_compare; 406227825Stheraven typedef _Allocator allocator_type; 407227825Stheraven typedef value_type& reference; 408227825Stheraven typedef const value_type& const_reference; 409227825Stheraven 410227825Stheravenprivate: 411227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 412227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 413227825Stheraven typedef typename __base::__node_holder __node_holder; 414227825Stheraven 415227825Stheraven __base __tree_; 416227825Stheraven 417227825Stheravenpublic: 418227825Stheraven typedef typename __base::pointer pointer; 419227825Stheraven typedef typename __base::const_pointer const_pointer; 420227825Stheraven typedef typename __base::size_type size_type; 421227825Stheraven typedef typename __base::difference_type difference_type; 422227825Stheraven typedef typename __base::const_iterator iterator; 423227825Stheraven typedef typename __base::const_iterator const_iterator; 424227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 425227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 426227825Stheraven 427227825Stheraven _LIBCPP_INLINE_VISIBILITY 428276792Sdim set() 429227825Stheraven _NOEXCEPT_( 430227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 431227825Stheraven is_nothrow_default_constructible<key_compare>::value && 432227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 433276792Sdim : __tree_(value_compare()) {} 434276792Sdim 435276792Sdim _LIBCPP_INLINE_VISIBILITY 436276792Sdim explicit set(const value_compare& __comp) 437276792Sdim _NOEXCEPT_( 438276792Sdim is_nothrow_default_constructible<allocator_type>::value && 439276792Sdim is_nothrow_copy_constructible<key_compare>::value) 440227825Stheraven : __tree_(__comp) {} 441276792Sdim 442227825Stheraven _LIBCPP_INLINE_VISIBILITY 443276792Sdim explicit set(const value_compare& __comp, const allocator_type& __a) 444227825Stheraven : __tree_(__comp, __a) {} 445227825Stheraven template <class _InputIterator> 446227825Stheraven _LIBCPP_INLINE_VISIBILITY 447227825Stheraven set(_InputIterator __f, _InputIterator __l, 448227825Stheraven const value_compare& __comp = value_compare()) 449227825Stheraven : __tree_(__comp) 450227825Stheraven { 451227825Stheraven insert(__f, __l); 452227825Stheraven } 453227825Stheraven 454227825Stheraven template <class _InputIterator> 455227825Stheraven _LIBCPP_INLINE_VISIBILITY 456227825Stheraven set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 457227825Stheraven const allocator_type& __a) 458227825Stheraven : __tree_(__comp, __a) 459227825Stheraven { 460227825Stheraven insert(__f, __l); 461227825Stheraven } 462227825Stheraven 463261272Sdim#if _LIBCPP_STD_VER > 11 464261272Sdim template <class _InputIterator> 465261272Sdim _LIBCPP_INLINE_VISIBILITY 466261272Sdim set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 467261272Sdim : set(__f, __l, key_compare(), __a) {} 468261272Sdim#endif 469261272Sdim 470227825Stheraven _LIBCPP_INLINE_VISIBILITY 471227825Stheraven set(const set& __s) 472227825Stheraven : __tree_(__s.__tree_) 473227825Stheraven { 474227825Stheraven insert(__s.begin(), __s.end()); 475227825Stheraven } 476227825Stheraven 477227825Stheraven _LIBCPP_INLINE_VISIBILITY 478227825Stheraven set& operator=(const set& __s) 479227825Stheraven { 480227825Stheraven __tree_ = __s.__tree_; 481227825Stheraven return *this; 482227825Stheraven } 483227825Stheraven 484227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 485227825Stheraven _LIBCPP_INLINE_VISIBILITY 486227825Stheraven set(set&& __s) 487227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 488227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 489227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 490227825Stheraven 491227825Stheraven _LIBCPP_INLINE_VISIBILITY 492227825Stheraven explicit set(const allocator_type& __a) 493227825Stheraven : __tree_(__a) {} 494227825Stheraven 495227825Stheraven _LIBCPP_INLINE_VISIBILITY 496227825Stheraven set(const set& __s, const allocator_type& __a) 497227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 498227825Stheraven { 499227825Stheraven insert(__s.begin(), __s.end()); 500227825Stheraven } 501227825Stheraven 502227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 503227825Stheraven set(set&& __s, const allocator_type& __a); 504227825Stheraven#endif 505227825Stheraven 506227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 507227825Stheraven _LIBCPP_INLINE_VISIBILITY 508227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 509227825Stheraven : __tree_(__comp) 510227825Stheraven { 511227825Stheraven insert(__il.begin(), __il.end()); 512227825Stheraven } 513227825Stheraven 514227825Stheraven _LIBCPP_INLINE_VISIBILITY 515227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp, 516227825Stheraven const allocator_type& __a) 517227825Stheraven : __tree_(__comp, __a) 518227825Stheraven { 519227825Stheraven insert(__il.begin(), __il.end()); 520227825Stheraven } 521227825Stheraven 522261272Sdim#if _LIBCPP_STD_VER > 11 523261272Sdim _LIBCPP_INLINE_VISIBILITY 524261272Sdim set(initializer_list<value_type> __il, const allocator_type& __a) 525261272Sdim : set(__il, key_compare(), __a) {} 526261272Sdim#endif 527261272Sdim 528227825Stheraven _LIBCPP_INLINE_VISIBILITY 529227825Stheraven set& operator=(initializer_list<value_type> __il) 530227825Stheraven { 531227825Stheraven __tree_.__assign_unique(__il.begin(), __il.end()); 532227825Stheraven return *this; 533227825Stheraven } 534227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 535227825Stheraven 536227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 537227825Stheraven _LIBCPP_INLINE_VISIBILITY 538227825Stheraven set& operator=(set&& __s) 539227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 540227825Stheraven { 541227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 542227825Stheraven return *this; 543227825Stheraven } 544227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 545227825Stheraven 546227825Stheraven _LIBCPP_INLINE_VISIBILITY 547227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 548227825Stheraven _LIBCPP_INLINE_VISIBILITY 549227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 550227825Stheraven _LIBCPP_INLINE_VISIBILITY 551227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 552227825Stheraven _LIBCPP_INLINE_VISIBILITY 553227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 554227825Stheraven 555227825Stheraven _LIBCPP_INLINE_VISIBILITY 556227825Stheraven reverse_iterator rbegin() _NOEXCEPT 557227825Stheraven {return reverse_iterator(end());} 558227825Stheraven _LIBCPP_INLINE_VISIBILITY 559227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 560227825Stheraven {return const_reverse_iterator(end());} 561227825Stheraven _LIBCPP_INLINE_VISIBILITY 562227825Stheraven reverse_iterator rend() _NOEXCEPT 563227825Stheraven {return reverse_iterator(begin());} 564227825Stheraven _LIBCPP_INLINE_VISIBILITY 565227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 566227825Stheraven {return const_reverse_iterator(begin());} 567227825Stheraven 568227825Stheraven _LIBCPP_INLINE_VISIBILITY 569227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 572227825Stheraven _LIBCPP_INLINE_VISIBILITY 573227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 574227825Stheraven _LIBCPP_INLINE_VISIBILITY 575227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 576227825Stheraven 577227825Stheraven _LIBCPP_INLINE_VISIBILITY 578227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 579227825Stheraven _LIBCPP_INLINE_VISIBILITY 580227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 581227825Stheraven _LIBCPP_INLINE_VISIBILITY 582227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 583227825Stheraven 584227825Stheraven // modifiers: 585227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 586227825Stheraven template <class... _Args> 587227825Stheraven _LIBCPP_INLINE_VISIBILITY 588227825Stheraven pair<iterator, bool> emplace(_Args&&... __args) 589227825Stheraven {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 590227825Stheraven template <class... _Args> 591227825Stheraven _LIBCPP_INLINE_VISIBILITY 592227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 593227825Stheraven {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 594227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 595227825Stheraven _LIBCPP_INLINE_VISIBILITY 596227825Stheraven pair<iterator,bool> insert(const value_type& __v) 597227825Stheraven {return __tree_.__insert_unique(__v);} 598227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 599227825Stheraven _LIBCPP_INLINE_VISIBILITY 600227825Stheraven pair<iterator,bool> insert(value_type&& __v) 601227825Stheraven {return __tree_.__insert_unique(_VSTD::move(__v));} 602227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 603227825Stheraven _LIBCPP_INLINE_VISIBILITY 604227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 605227825Stheraven {return __tree_.__insert_unique(__p, __v);} 606227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 607227825Stheraven _LIBCPP_INLINE_VISIBILITY 608227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 609227825Stheraven {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 610227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 611227825Stheraven template <class _InputIterator> 612227825Stheraven _LIBCPP_INLINE_VISIBILITY 613227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 614227825Stheraven { 615227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 616227825Stheraven __tree_.__insert_unique(__e, *__f); 617227825Stheraven } 618227825Stheraven 619227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 620227825Stheraven _LIBCPP_INLINE_VISIBILITY 621227825Stheraven void insert(initializer_list<value_type> __il) 622227825Stheraven {insert(__il.begin(), __il.end());} 623227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 624227825Stheraven 625227825Stheraven _LIBCPP_INLINE_VISIBILITY 626227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 627227825Stheraven _LIBCPP_INLINE_VISIBILITY 628227825Stheraven size_type erase(const key_type& __k) 629227825Stheraven {return __tree_.__erase_unique(__k);} 630227825Stheraven _LIBCPP_INLINE_VISIBILITY 631227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 632227825Stheraven {return __tree_.erase(__f, __l);} 633227825Stheraven _LIBCPP_INLINE_VISIBILITY 634227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 635227825Stheraven 636227825Stheraven _LIBCPP_INLINE_VISIBILITY 637227825Stheraven void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 638227825Stheraven {__tree_.swap(__s.__tree_);} 639227825Stheraven 640227825Stheraven _LIBCPP_INLINE_VISIBILITY 641227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 642227825Stheraven _LIBCPP_INLINE_VISIBILITY 643227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 644227825Stheraven _LIBCPP_INLINE_VISIBILITY 645227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 646227825Stheraven 647227825Stheraven // set operations: 648227825Stheraven _LIBCPP_INLINE_VISIBILITY 649227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 650227825Stheraven _LIBCPP_INLINE_VISIBILITY 651227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 652261272Sdim#if _LIBCPP_STD_VER > 11 653261272Sdim template <typename _K2> 654227825Stheraven _LIBCPP_INLINE_VISIBILITY 655261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 656261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 657261272Sdim template <typename _K2> 658261272Sdim _LIBCPP_INLINE_VISIBILITY 659261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 660261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 661261272Sdim#endif 662261272Sdim 663261272Sdim _LIBCPP_INLINE_VISIBILITY 664227825Stheraven size_type count(const key_type& __k) const 665227825Stheraven {return __tree_.__count_unique(__k);} 666276792Sdim#if _LIBCPP_STD_VER > 11 667276792Sdim template <typename _K2> 668227825Stheraven _LIBCPP_INLINE_VISIBILITY 669276792Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 670276792Sdim count(const _K2& __k) {return __tree_.__count_unique(__k);} 671276792Sdim#endif 672276792Sdim _LIBCPP_INLINE_VISIBILITY 673227825Stheraven iterator lower_bound(const key_type& __k) 674227825Stheraven {return __tree_.lower_bound(__k);} 675227825Stheraven _LIBCPP_INLINE_VISIBILITY 676227825Stheraven const_iterator lower_bound(const key_type& __k) const 677227825Stheraven {return __tree_.lower_bound(__k);} 678261272Sdim#if _LIBCPP_STD_VER > 11 679261272Sdim template <typename _K2> 680227825Stheraven _LIBCPP_INLINE_VISIBILITY 681261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 682261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 683261272Sdim 684261272Sdim template <typename _K2> 685261272Sdim _LIBCPP_INLINE_VISIBILITY 686261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 687261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 688261272Sdim#endif 689261272Sdim 690261272Sdim _LIBCPP_INLINE_VISIBILITY 691227825Stheraven iterator upper_bound(const key_type& __k) 692227825Stheraven {return __tree_.upper_bound(__k);} 693227825Stheraven _LIBCPP_INLINE_VISIBILITY 694227825Stheraven const_iterator upper_bound(const key_type& __k) const 695227825Stheraven {return __tree_.upper_bound(__k);} 696261272Sdim#if _LIBCPP_STD_VER > 11 697261272Sdim template <typename _K2> 698227825Stheraven _LIBCPP_INLINE_VISIBILITY 699261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 700261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 701261272Sdim template <typename _K2> 702261272Sdim _LIBCPP_INLINE_VISIBILITY 703261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 704261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 705261272Sdim#endif 706261272Sdim 707261272Sdim _LIBCPP_INLINE_VISIBILITY 708227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 709227825Stheraven {return __tree_.__equal_range_unique(__k);} 710227825Stheraven _LIBCPP_INLINE_VISIBILITY 711227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 712227825Stheraven {return __tree_.__equal_range_unique(__k);} 713261272Sdim#if _LIBCPP_STD_VER > 11 714261272Sdim template <typename _K2> 715261272Sdim _LIBCPP_INLINE_VISIBILITY 716261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 717261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 718261272Sdim template <typename _K2> 719261272Sdim _LIBCPP_INLINE_VISIBILITY 720261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 721261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 722261272Sdim#endif 723227825Stheraven}; 724227825Stheraven 725227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 726227825Stheraven 727227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 728227825Stheravenset<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 729227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 730227825Stheraven{ 731227825Stheraven if (__a != __s.get_allocator()) 732227825Stheraven { 733227825Stheraven const_iterator __e = cend(); 734227825Stheraven while (!__s.empty()) 735227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 736227825Stheraven } 737227825Stheraven} 738227825Stheraven 739227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 740227825Stheraven 741227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 742227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 743227825Stheravenbool 744227825Stheravenoperator==(const set<_Key, _Compare, _Allocator>& __x, 745227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 746227825Stheraven{ 747227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 748227825Stheraven} 749227825Stheraven 750227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 751227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 752227825Stheravenbool 753227825Stheravenoperator< (const set<_Key, _Compare, _Allocator>& __x, 754227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 755227825Stheraven{ 756227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 757227825Stheraven} 758227825Stheraven 759227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 760227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 761227825Stheravenbool 762227825Stheravenoperator!=(const set<_Key, _Compare, _Allocator>& __x, 763227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 764227825Stheraven{ 765227825Stheraven return !(__x == __y); 766227825Stheraven} 767227825Stheraven 768227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 769227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 770227825Stheravenbool 771227825Stheravenoperator> (const set<_Key, _Compare, _Allocator>& __x, 772227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 773227825Stheraven{ 774227825Stheraven return __y < __x; 775227825Stheraven} 776227825Stheraven 777227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 778227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 779227825Stheravenbool 780227825Stheravenoperator>=(const set<_Key, _Compare, _Allocator>& __x, 781227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 782227825Stheraven{ 783227825Stheraven return !(__x < __y); 784227825Stheraven} 785227825Stheraven 786227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 787227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 788227825Stheravenbool 789227825Stheravenoperator<=(const set<_Key, _Compare, _Allocator>& __x, 790227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 791227825Stheraven{ 792227825Stheraven return !(__y < __x); 793227825Stheraven} 794227825Stheraven 795227825Stheraven// specialized algorithms: 796227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 797227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 798227825Stheravenvoid 799227825Stheravenswap(set<_Key, _Compare, _Allocator>& __x, 800227825Stheraven set<_Key, _Compare, _Allocator>& __y) 801227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 802227825Stheraven{ 803227825Stheraven __x.swap(__y); 804227825Stheraven} 805227825Stheraven 806227825Stheraventemplate <class _Key, class _Compare = less<_Key>, 807227825Stheraven class _Allocator = allocator<_Key> > 808261272Sdimclass _LIBCPP_TYPE_VIS_ONLY multiset 809227825Stheraven{ 810227825Stheravenpublic: 811227825Stheraven // types: 812227825Stheraven typedef _Key key_type; 813227825Stheraven typedef key_type value_type; 814227825Stheraven typedef _Compare key_compare; 815227825Stheraven typedef key_compare value_compare; 816227825Stheraven typedef _Allocator allocator_type; 817227825Stheraven typedef value_type& reference; 818227825Stheraven typedef const value_type& const_reference; 819227825Stheraven 820227825Stheravenprivate: 821227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 822227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 823227825Stheraven typedef typename __base::__node_holder __node_holder; 824227825Stheraven 825227825Stheraven __base __tree_; 826227825Stheraven 827227825Stheravenpublic: 828227825Stheraven typedef typename __base::pointer pointer; 829227825Stheraven typedef typename __base::const_pointer const_pointer; 830227825Stheraven typedef typename __base::size_type size_type; 831227825Stheraven typedef typename __base::difference_type difference_type; 832227825Stheraven typedef typename __base::const_iterator iterator; 833227825Stheraven typedef typename __base::const_iterator const_iterator; 834227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 835227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 836227825Stheraven 837227825Stheraven // construct/copy/destroy: 838227825Stheraven _LIBCPP_INLINE_VISIBILITY 839276792Sdim multiset() 840227825Stheraven _NOEXCEPT_( 841227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 842227825Stheraven is_nothrow_default_constructible<key_compare>::value && 843227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 844276792Sdim : __tree_(value_compare()) {} 845276792Sdim 846276792Sdim _LIBCPP_INLINE_VISIBILITY 847276792Sdim explicit multiset(const value_compare& __comp) 848276792Sdim _NOEXCEPT_( 849276792Sdim is_nothrow_default_constructible<allocator_type>::value && 850276792Sdim is_nothrow_copy_constructible<key_compare>::value) 851227825Stheraven : __tree_(__comp) {} 852276792Sdim 853227825Stheraven _LIBCPP_INLINE_VISIBILITY 854276792Sdim explicit multiset(const value_compare& __comp, const allocator_type& __a) 855227825Stheraven : __tree_(__comp, __a) {} 856227825Stheraven template <class _InputIterator> 857227825Stheraven _LIBCPP_INLINE_VISIBILITY 858227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 859227825Stheraven const value_compare& __comp = value_compare()) 860227825Stheraven : __tree_(__comp) 861227825Stheraven { 862227825Stheraven insert(__f, __l); 863227825Stheraven } 864227825Stheraven 865261272Sdim#if _LIBCPP_STD_VER > 11 866261272Sdim template <class _InputIterator> 867261272Sdim _LIBCPP_INLINE_VISIBILITY 868261272Sdim multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 869261272Sdim : multiset(__f, __l, key_compare(), __a) {} 870261272Sdim#endif 871261272Sdim 872227825Stheraven template <class _InputIterator> 873227825Stheraven _LIBCPP_INLINE_VISIBILITY 874227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 875227825Stheraven const value_compare& __comp, const allocator_type& __a) 876227825Stheraven : __tree_(__comp, __a) 877227825Stheraven { 878227825Stheraven insert(__f, __l); 879227825Stheraven } 880227825Stheraven 881227825Stheraven _LIBCPP_INLINE_VISIBILITY 882227825Stheraven multiset(const multiset& __s) 883227825Stheraven : __tree_(__s.__tree_.value_comp(), 884227825Stheraven __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 885227825Stheraven { 886227825Stheraven insert(__s.begin(), __s.end()); 887227825Stheraven } 888227825Stheraven 889227825Stheraven _LIBCPP_INLINE_VISIBILITY 890227825Stheraven multiset& operator=(const multiset& __s) 891227825Stheraven { 892227825Stheraven __tree_ = __s.__tree_; 893227825Stheraven return *this; 894227825Stheraven } 895227825Stheraven 896227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 897227825Stheraven _LIBCPP_INLINE_VISIBILITY 898227825Stheraven multiset(multiset&& __s) 899227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 900227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 901227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 902227825Stheraven _LIBCPP_INLINE_VISIBILITY 903227825Stheraven explicit multiset(const allocator_type& __a) 904227825Stheraven : __tree_(__a) {} 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906227825Stheraven multiset(const multiset& __s, const allocator_type& __a) 907227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 908227825Stheraven { 909227825Stheraven insert(__s.begin(), __s.end()); 910227825Stheraven } 911227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 912227825Stheraven multiset(multiset&& __s, const allocator_type& __a); 913227825Stheraven#endif 914227825Stheraven 915227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 916227825Stheraven _LIBCPP_INLINE_VISIBILITY 917227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 918227825Stheraven : __tree_(__comp) 919227825Stheraven { 920227825Stheraven insert(__il.begin(), __il.end()); 921227825Stheraven } 922227825Stheraven 923227825Stheraven _LIBCPP_INLINE_VISIBILITY 924227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp, 925227825Stheraven const allocator_type& __a) 926227825Stheraven : __tree_(__comp, __a) 927227825Stheraven { 928227825Stheraven insert(__il.begin(), __il.end()); 929227825Stheraven } 930227825Stheraven 931261272Sdim#if _LIBCPP_STD_VER > 11 932261272Sdim _LIBCPP_INLINE_VISIBILITY 933261272Sdim multiset(initializer_list<value_type> __il, const allocator_type& __a) 934261272Sdim : multiset(__il, key_compare(), __a) {} 935261272Sdim#endif 936261272Sdim 937227825Stheraven _LIBCPP_INLINE_VISIBILITY 938227825Stheraven multiset& operator=(initializer_list<value_type> __il) 939227825Stheraven { 940227825Stheraven __tree_.__assign_multi(__il.begin(), __il.end()); 941227825Stheraven return *this; 942227825Stheraven } 943227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 944227825Stheraven 945227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 946227825Stheraven _LIBCPP_INLINE_VISIBILITY 947227825Stheraven multiset& operator=(multiset&& __s) 948227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 949227825Stheraven { 950227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 951227825Stheraven return *this; 952227825Stheraven } 953227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 954227825Stheraven 955227825Stheraven _LIBCPP_INLINE_VISIBILITY 956227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 957227825Stheraven _LIBCPP_INLINE_VISIBILITY 958227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 959227825Stheraven _LIBCPP_INLINE_VISIBILITY 960227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 961227825Stheraven _LIBCPP_INLINE_VISIBILITY 962227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 963227825Stheraven 964227825Stheraven _LIBCPP_INLINE_VISIBILITY 965227825Stheraven reverse_iterator rbegin() _NOEXCEPT 966227825Stheraven {return reverse_iterator(end());} 967227825Stheraven _LIBCPP_INLINE_VISIBILITY 968227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 969227825Stheraven {return const_reverse_iterator(end());} 970227825Stheraven _LIBCPP_INLINE_VISIBILITY 971227825Stheraven reverse_iterator rend() _NOEXCEPT 972227825Stheraven {return reverse_iterator(begin());} 973227825Stheraven _LIBCPP_INLINE_VISIBILITY 974227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 975227825Stheraven {return const_reverse_iterator(begin());} 976227825Stheraven 977227825Stheraven _LIBCPP_INLINE_VISIBILITY 978227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 979227825Stheraven _LIBCPP_INLINE_VISIBILITY 980227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 981227825Stheraven _LIBCPP_INLINE_VISIBILITY 982227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 983227825Stheraven _LIBCPP_INLINE_VISIBILITY 984227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 985227825Stheraven 986227825Stheraven _LIBCPP_INLINE_VISIBILITY 987227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 988227825Stheraven _LIBCPP_INLINE_VISIBILITY 989227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 990227825Stheraven _LIBCPP_INLINE_VISIBILITY 991227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 992227825Stheraven 993227825Stheraven // modifiers: 994227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 995227825Stheraven template <class... _Args> 996227825Stheraven _LIBCPP_INLINE_VISIBILITY 997227825Stheraven iterator emplace(_Args&&... __args) 998227825Stheraven {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 999227825Stheraven template <class... _Args> 1000227825Stheraven _LIBCPP_INLINE_VISIBILITY 1001227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 1002227825Stheraven {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1003227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1004227825Stheraven _LIBCPP_INLINE_VISIBILITY 1005227825Stheraven iterator insert(const value_type& __v) 1006227825Stheraven {return __tree_.__insert_multi(__v);} 1007227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1008227825Stheraven _LIBCPP_INLINE_VISIBILITY 1009227825Stheraven iterator insert(value_type&& __v) 1010227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 1011227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1012227825Stheraven _LIBCPP_INLINE_VISIBILITY 1013227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 1014227825Stheraven {return __tree_.__insert_multi(__p, __v);} 1015227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1016227825Stheraven _LIBCPP_INLINE_VISIBILITY 1017227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 1018227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 1019227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020227825Stheraven template <class _InputIterator> 1021227825Stheraven _LIBCPP_INLINE_VISIBILITY 1022227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 1023227825Stheraven { 1024227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 1025227825Stheraven __tree_.__insert_multi(__e, *__f); 1026227825Stheraven } 1027227825Stheraven 1028227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1029227825Stheraven _LIBCPP_INLINE_VISIBILITY 1030227825Stheraven void insert(initializer_list<value_type> __il) 1031227825Stheraven {insert(__il.begin(), __il.end());} 1032227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1033227825Stheraven 1034227825Stheraven _LIBCPP_INLINE_VISIBILITY 1035227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1036227825Stheraven _LIBCPP_INLINE_VISIBILITY 1037227825Stheraven size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1038227825Stheraven _LIBCPP_INLINE_VISIBILITY 1039227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 1040227825Stheraven {return __tree_.erase(__f, __l);} 1041227825Stheraven _LIBCPP_INLINE_VISIBILITY 1042227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 1043227825Stheraven 1044227825Stheraven _LIBCPP_INLINE_VISIBILITY 1045227825Stheraven void swap(multiset& __s) 1046227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1047227825Stheraven {__tree_.swap(__s.__tree_);} 1048227825Stheraven 1049227825Stheraven _LIBCPP_INLINE_VISIBILITY 1050227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1051227825Stheraven _LIBCPP_INLINE_VISIBILITY 1052227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 1053227825Stheraven _LIBCPP_INLINE_VISIBILITY 1054227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 1055227825Stheraven 1056227825Stheraven // set operations: 1057227825Stheraven _LIBCPP_INLINE_VISIBILITY 1058227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 1059227825Stheraven _LIBCPP_INLINE_VISIBILITY 1060227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1061261272Sdim#if _LIBCPP_STD_VER > 11 1062261272Sdim template <typename _K2> 1063227825Stheraven _LIBCPP_INLINE_VISIBILITY 1064261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1065261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 1066261272Sdim template <typename _K2> 1067261272Sdim _LIBCPP_INLINE_VISIBILITY 1068261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1069261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 1070261272Sdim#endif 1071261272Sdim 1072261272Sdim _LIBCPP_INLINE_VISIBILITY 1073227825Stheraven size_type count(const key_type& __k) const 1074227825Stheraven {return __tree_.__count_multi(__k);} 1075276792Sdim#if _LIBCPP_STD_VER > 11 1076276792Sdim template <typename _K2> 1077276792Sdim _LIBCPP_INLINE_VISIBILITY 1078276792Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1079276792Sdim count(const _K2& __k) {return __tree_.__count_multi(__k);} 1080276792Sdim#endif 1081261272Sdim 1082227825Stheraven _LIBCPP_INLINE_VISIBILITY 1083227825Stheraven iterator lower_bound(const key_type& __k) 1084227825Stheraven {return __tree_.lower_bound(__k);} 1085227825Stheraven _LIBCPP_INLINE_VISIBILITY 1086227825Stheraven const_iterator lower_bound(const key_type& __k) const 1087227825Stheraven {return __tree_.lower_bound(__k);} 1088261272Sdim#if _LIBCPP_STD_VER > 11 1089261272Sdim template <typename _K2> 1090227825Stheraven _LIBCPP_INLINE_VISIBILITY 1091261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1092261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1093261272Sdim 1094261272Sdim template <typename _K2> 1095261272Sdim _LIBCPP_INLINE_VISIBILITY 1096261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1097261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1098261272Sdim#endif 1099261272Sdim 1100261272Sdim _LIBCPP_INLINE_VISIBILITY 1101227825Stheraven iterator upper_bound(const key_type& __k) 1102227825Stheraven {return __tree_.upper_bound(__k);} 1103227825Stheraven _LIBCPP_INLINE_VISIBILITY 1104227825Stheraven const_iterator upper_bound(const key_type& __k) const 1105227825Stheraven {return __tree_.upper_bound(__k);} 1106261272Sdim#if _LIBCPP_STD_VER > 11 1107261272Sdim template <typename _K2> 1108227825Stheraven _LIBCPP_INLINE_VISIBILITY 1109261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1110261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1111261272Sdim template <typename _K2> 1112261272Sdim _LIBCPP_INLINE_VISIBILITY 1113261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1114261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1115261272Sdim#endif 1116261272Sdim 1117261272Sdim _LIBCPP_INLINE_VISIBILITY 1118227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 1119227825Stheraven {return __tree_.__equal_range_multi(__k);} 1120227825Stheraven _LIBCPP_INLINE_VISIBILITY 1121227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1122227825Stheraven {return __tree_.__equal_range_multi(__k);} 1123261272Sdim#if _LIBCPP_STD_VER > 11 1124261272Sdim template <typename _K2> 1125261272Sdim _LIBCPP_INLINE_VISIBILITY 1126261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1127261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1128261272Sdim template <typename _K2> 1129261272Sdim _LIBCPP_INLINE_VISIBILITY 1130261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1131261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1132261272Sdim#endif 1133227825Stheraven}; 1134227825Stheraven 1135227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1136227825Stheraven 1137227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1138227825Stheravenmultiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1139227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 1140227825Stheraven{ 1141227825Stheraven if (__a != __s.get_allocator()) 1142227825Stheraven { 1143227825Stheraven const_iterator __e = cend(); 1144227825Stheraven while (!__s.empty()) 1145227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1146227825Stheraven } 1147227825Stheraven} 1148227825Stheraven 1149227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1150227825Stheraven 1151227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1152227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1153227825Stheravenbool 1154227825Stheravenoperator==(const multiset<_Key, _Compare, _Allocator>& __x, 1155227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1156227825Stheraven{ 1157227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1158227825Stheraven} 1159227825Stheraven 1160227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1161227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1162227825Stheravenbool 1163227825Stheravenoperator< (const multiset<_Key, _Compare, _Allocator>& __x, 1164227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1165227825Stheraven{ 1166227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1167227825Stheraven} 1168227825Stheraven 1169227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1170227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1171227825Stheravenbool 1172227825Stheravenoperator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1173227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1174227825Stheraven{ 1175227825Stheraven return !(__x == __y); 1176227825Stheraven} 1177227825Stheraven 1178227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1179227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1180227825Stheravenbool 1181227825Stheravenoperator> (const multiset<_Key, _Compare, _Allocator>& __x, 1182227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1183227825Stheraven{ 1184227825Stheraven return __y < __x; 1185227825Stheraven} 1186227825Stheraven 1187227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1188227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1189227825Stheravenbool 1190227825Stheravenoperator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1191227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1192227825Stheraven{ 1193227825Stheraven return !(__x < __y); 1194227825Stheraven} 1195227825Stheraven 1196227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1197227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1198227825Stheravenbool 1199227825Stheravenoperator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1200227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1201227825Stheraven{ 1202227825Stheraven return !(__y < __x); 1203227825Stheraven} 1204227825Stheraven 1205227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1206227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1207227825Stheravenvoid 1208227825Stheravenswap(multiset<_Key, _Compare, _Allocator>& __x, 1209227825Stheraven multiset<_Key, _Compare, _Allocator>& __y) 1210227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1211227825Stheraven{ 1212227825Stheraven __x.swap(__y); 1213227825Stheraven} 1214227825Stheraven 1215227825Stheraven_LIBCPP_END_NAMESPACE_STD 1216227825Stheraven 1217227825Stheraven#endif // _LIBCPP_SET 1218