set revision 261272
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 428227825Stheraven explicit set(const value_compare& __comp = value_compare()) 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) 433227825Stheraven : __tree_(__comp) {} 434227825Stheraven _LIBCPP_INLINE_VISIBILITY 435227825Stheraven set(const value_compare& __comp, const allocator_type& __a) 436227825Stheraven : __tree_(__comp, __a) {} 437227825Stheraven template <class _InputIterator> 438227825Stheraven _LIBCPP_INLINE_VISIBILITY 439227825Stheraven set(_InputIterator __f, _InputIterator __l, 440227825Stheraven const value_compare& __comp = value_compare()) 441227825Stheraven : __tree_(__comp) 442227825Stheraven { 443227825Stheraven insert(__f, __l); 444227825Stheraven } 445227825Stheraven 446227825Stheraven template <class _InputIterator> 447227825Stheraven _LIBCPP_INLINE_VISIBILITY 448227825Stheraven set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 449227825Stheraven const allocator_type& __a) 450227825Stheraven : __tree_(__comp, __a) 451227825Stheraven { 452227825Stheraven insert(__f, __l); 453227825Stheraven } 454227825Stheraven 455261272Sdim#if _LIBCPP_STD_VER > 11 456261272Sdim template <class _InputIterator> 457261272Sdim _LIBCPP_INLINE_VISIBILITY 458261272Sdim set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 459261272Sdim : set(__f, __l, key_compare(), __a) {} 460261272Sdim#endif 461261272Sdim 462227825Stheraven _LIBCPP_INLINE_VISIBILITY 463227825Stheraven set(const set& __s) 464227825Stheraven : __tree_(__s.__tree_) 465227825Stheraven { 466227825Stheraven insert(__s.begin(), __s.end()); 467227825Stheraven } 468227825Stheraven 469227825Stheraven _LIBCPP_INLINE_VISIBILITY 470227825Stheraven set& operator=(const set& __s) 471227825Stheraven { 472227825Stheraven __tree_ = __s.__tree_; 473227825Stheraven return *this; 474227825Stheraven } 475227825Stheraven 476227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 477227825Stheraven _LIBCPP_INLINE_VISIBILITY 478227825Stheraven set(set&& __s) 479227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 480227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 481227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 482227825Stheraven 483227825Stheraven _LIBCPP_INLINE_VISIBILITY 484227825Stheraven explicit set(const allocator_type& __a) 485227825Stheraven : __tree_(__a) {} 486227825Stheraven 487227825Stheraven _LIBCPP_INLINE_VISIBILITY 488227825Stheraven set(const set& __s, const allocator_type& __a) 489227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 490227825Stheraven { 491227825Stheraven insert(__s.begin(), __s.end()); 492227825Stheraven } 493227825Stheraven 494227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 495227825Stheraven set(set&& __s, const allocator_type& __a); 496227825Stheraven#endif 497227825Stheraven 498227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 499227825Stheraven _LIBCPP_INLINE_VISIBILITY 500227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 501227825Stheraven : __tree_(__comp) 502227825Stheraven { 503227825Stheraven insert(__il.begin(), __il.end()); 504227825Stheraven } 505227825Stheraven 506227825Stheraven _LIBCPP_INLINE_VISIBILITY 507227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp, 508227825Stheraven const allocator_type& __a) 509227825Stheraven : __tree_(__comp, __a) 510227825Stheraven { 511227825Stheraven insert(__il.begin(), __il.end()); 512227825Stheraven } 513227825Stheraven 514261272Sdim#if _LIBCPP_STD_VER > 11 515261272Sdim _LIBCPP_INLINE_VISIBILITY 516261272Sdim set(initializer_list<value_type> __il, const allocator_type& __a) 517261272Sdim : set(__il, key_compare(), __a) {} 518261272Sdim#endif 519261272Sdim 520227825Stheraven _LIBCPP_INLINE_VISIBILITY 521227825Stheraven set& operator=(initializer_list<value_type> __il) 522227825Stheraven { 523227825Stheraven __tree_.__assign_unique(__il.begin(), __il.end()); 524227825Stheraven return *this; 525227825Stheraven } 526227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 527227825Stheraven 528227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 529227825Stheraven _LIBCPP_INLINE_VISIBILITY 530227825Stheraven set& operator=(set&& __s) 531227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 532227825Stheraven { 533227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 534227825Stheraven return *this; 535227825Stheraven } 536227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 537227825Stheraven 538227825Stheraven _LIBCPP_INLINE_VISIBILITY 539227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 540227825Stheraven _LIBCPP_INLINE_VISIBILITY 541227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 542227825Stheraven _LIBCPP_INLINE_VISIBILITY 543227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 544227825Stheraven _LIBCPP_INLINE_VISIBILITY 545227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 546227825Stheraven 547227825Stheraven _LIBCPP_INLINE_VISIBILITY 548227825Stheraven reverse_iterator rbegin() _NOEXCEPT 549227825Stheraven {return reverse_iterator(end());} 550227825Stheraven _LIBCPP_INLINE_VISIBILITY 551227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 552227825Stheraven {return const_reverse_iterator(end());} 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven reverse_iterator rend() _NOEXCEPT 555227825Stheraven {return reverse_iterator(begin());} 556227825Stheraven _LIBCPP_INLINE_VISIBILITY 557227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 558227825Stheraven {return const_reverse_iterator(begin());} 559227825Stheraven 560227825Stheraven _LIBCPP_INLINE_VISIBILITY 561227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 562227825Stheraven _LIBCPP_INLINE_VISIBILITY 563227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 564227825Stheraven _LIBCPP_INLINE_VISIBILITY 565227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 566227825Stheraven _LIBCPP_INLINE_VISIBILITY 567227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 568227825Stheraven 569227825Stheraven _LIBCPP_INLINE_VISIBILITY 570227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 571227825Stheraven _LIBCPP_INLINE_VISIBILITY 572227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 573227825Stheraven _LIBCPP_INLINE_VISIBILITY 574227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 575227825Stheraven 576227825Stheraven // modifiers: 577227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 578227825Stheraven template <class... _Args> 579227825Stheraven _LIBCPP_INLINE_VISIBILITY 580227825Stheraven pair<iterator, bool> emplace(_Args&&... __args) 581227825Stheraven {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 582227825Stheraven template <class... _Args> 583227825Stheraven _LIBCPP_INLINE_VISIBILITY 584227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 585227825Stheraven {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 586227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 587227825Stheraven _LIBCPP_INLINE_VISIBILITY 588227825Stheraven pair<iterator,bool> insert(const value_type& __v) 589227825Stheraven {return __tree_.__insert_unique(__v);} 590227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 591227825Stheraven _LIBCPP_INLINE_VISIBILITY 592227825Stheraven pair<iterator,bool> insert(value_type&& __v) 593227825Stheraven {return __tree_.__insert_unique(_VSTD::move(__v));} 594227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 595227825Stheraven _LIBCPP_INLINE_VISIBILITY 596227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 597227825Stheraven {return __tree_.__insert_unique(__p, __v);} 598227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 599227825Stheraven _LIBCPP_INLINE_VISIBILITY 600227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 601227825Stheraven {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 602227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 603227825Stheraven template <class _InputIterator> 604227825Stheraven _LIBCPP_INLINE_VISIBILITY 605227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 606227825Stheraven { 607227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 608227825Stheraven __tree_.__insert_unique(__e, *__f); 609227825Stheraven } 610227825Stheraven 611227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 612227825Stheraven _LIBCPP_INLINE_VISIBILITY 613227825Stheraven void insert(initializer_list<value_type> __il) 614227825Stheraven {insert(__il.begin(), __il.end());} 615227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 616227825Stheraven 617227825Stheraven _LIBCPP_INLINE_VISIBILITY 618227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 619227825Stheraven _LIBCPP_INLINE_VISIBILITY 620227825Stheraven size_type erase(const key_type& __k) 621227825Stheraven {return __tree_.__erase_unique(__k);} 622227825Stheraven _LIBCPP_INLINE_VISIBILITY 623227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 624227825Stheraven {return __tree_.erase(__f, __l);} 625227825Stheraven _LIBCPP_INLINE_VISIBILITY 626227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 627227825Stheraven 628227825Stheraven _LIBCPP_INLINE_VISIBILITY 629227825Stheraven void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 630227825Stheraven {__tree_.swap(__s.__tree_);} 631227825Stheraven 632227825Stheraven _LIBCPP_INLINE_VISIBILITY 633227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 634227825Stheraven _LIBCPP_INLINE_VISIBILITY 635227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 636227825Stheraven _LIBCPP_INLINE_VISIBILITY 637227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 638227825Stheraven 639227825Stheraven // set operations: 640227825Stheraven _LIBCPP_INLINE_VISIBILITY 641227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 642227825Stheraven _LIBCPP_INLINE_VISIBILITY 643227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 644261272Sdim#if _LIBCPP_STD_VER > 11 645261272Sdim template <typename _K2> 646227825Stheraven _LIBCPP_INLINE_VISIBILITY 647261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 648261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 649261272Sdim template <typename _K2> 650261272Sdim _LIBCPP_INLINE_VISIBILITY 651261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 652261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 653261272Sdim#endif 654261272Sdim 655261272Sdim _LIBCPP_INLINE_VISIBILITY 656227825Stheraven size_type count(const key_type& __k) const 657227825Stheraven {return __tree_.__count_unique(__k);} 658227825Stheraven _LIBCPP_INLINE_VISIBILITY 659227825Stheraven iterator lower_bound(const key_type& __k) 660227825Stheraven {return __tree_.lower_bound(__k);} 661227825Stheraven _LIBCPP_INLINE_VISIBILITY 662227825Stheraven const_iterator lower_bound(const key_type& __k) const 663227825Stheraven {return __tree_.lower_bound(__k);} 664261272Sdim#if _LIBCPP_STD_VER > 11 665261272Sdim template <typename _K2> 666227825Stheraven _LIBCPP_INLINE_VISIBILITY 667261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 668261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 669261272Sdim 670261272Sdim template <typename _K2> 671261272Sdim _LIBCPP_INLINE_VISIBILITY 672261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 673261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 674261272Sdim#endif 675261272Sdim 676261272Sdim _LIBCPP_INLINE_VISIBILITY 677227825Stheraven iterator upper_bound(const key_type& __k) 678227825Stheraven {return __tree_.upper_bound(__k);} 679227825Stheraven _LIBCPP_INLINE_VISIBILITY 680227825Stheraven const_iterator upper_bound(const key_type& __k) const 681227825Stheraven {return __tree_.upper_bound(__k);} 682261272Sdim#if _LIBCPP_STD_VER > 11 683261272Sdim template <typename _K2> 684227825Stheraven _LIBCPP_INLINE_VISIBILITY 685261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 686261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 687261272Sdim template <typename _K2> 688261272Sdim _LIBCPP_INLINE_VISIBILITY 689261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 690261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 691261272Sdim#endif 692261272Sdim 693261272Sdim _LIBCPP_INLINE_VISIBILITY 694227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 695227825Stheraven {return __tree_.__equal_range_unique(__k);} 696227825Stheraven _LIBCPP_INLINE_VISIBILITY 697227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 698227825Stheraven {return __tree_.__equal_range_unique(__k);} 699261272Sdim#if _LIBCPP_STD_VER > 11 700261272Sdim template <typename _K2> 701261272Sdim _LIBCPP_INLINE_VISIBILITY 702261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 703261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 704261272Sdim template <typename _K2> 705261272Sdim _LIBCPP_INLINE_VISIBILITY 706261272Sdim typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 707261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 708261272Sdim#endif 709227825Stheraven}; 710227825Stheraven 711227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 712227825Stheraven 713227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 714227825Stheravenset<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 715227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 716227825Stheraven{ 717227825Stheraven if (__a != __s.get_allocator()) 718227825Stheraven { 719227825Stheraven const_iterator __e = cend(); 720227825Stheraven while (!__s.empty()) 721227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 722227825Stheraven } 723227825Stheraven} 724227825Stheraven 725227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 726227825Stheraven 727227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 728227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 729227825Stheravenbool 730227825Stheravenoperator==(const set<_Key, _Compare, _Allocator>& __x, 731227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 732227825Stheraven{ 733227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 734227825Stheraven} 735227825Stheraven 736227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 737227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 738227825Stheravenbool 739227825Stheravenoperator< (const set<_Key, _Compare, _Allocator>& __x, 740227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 741227825Stheraven{ 742227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 743227825Stheraven} 744227825Stheraven 745227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 746227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 747227825Stheravenbool 748227825Stheravenoperator!=(const set<_Key, _Compare, _Allocator>& __x, 749227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 750227825Stheraven{ 751227825Stheraven return !(__x == __y); 752227825Stheraven} 753227825Stheraven 754227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 755227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 756227825Stheravenbool 757227825Stheravenoperator> (const set<_Key, _Compare, _Allocator>& __x, 758227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 759227825Stheraven{ 760227825Stheraven return __y < __x; 761227825Stheraven} 762227825Stheraven 763227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 764227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 765227825Stheravenbool 766227825Stheravenoperator>=(const set<_Key, _Compare, _Allocator>& __x, 767227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 768227825Stheraven{ 769227825Stheraven return !(__x < __y); 770227825Stheraven} 771227825Stheraven 772227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 773227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 774227825Stheravenbool 775227825Stheravenoperator<=(const set<_Key, _Compare, _Allocator>& __x, 776227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 777227825Stheraven{ 778227825Stheraven return !(__y < __x); 779227825Stheraven} 780227825Stheraven 781227825Stheraven// specialized algorithms: 782227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 783227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 784227825Stheravenvoid 785227825Stheravenswap(set<_Key, _Compare, _Allocator>& __x, 786227825Stheraven set<_Key, _Compare, _Allocator>& __y) 787227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 788227825Stheraven{ 789227825Stheraven __x.swap(__y); 790227825Stheraven} 791227825Stheraven 792227825Stheraventemplate <class _Key, class _Compare = less<_Key>, 793227825Stheraven class _Allocator = allocator<_Key> > 794261272Sdimclass _LIBCPP_TYPE_VIS_ONLY multiset 795227825Stheraven{ 796227825Stheravenpublic: 797227825Stheraven // types: 798227825Stheraven typedef _Key key_type; 799227825Stheraven typedef key_type value_type; 800227825Stheraven typedef _Compare key_compare; 801227825Stheraven typedef key_compare value_compare; 802227825Stheraven typedef _Allocator allocator_type; 803227825Stheraven typedef value_type& reference; 804227825Stheraven typedef const value_type& const_reference; 805227825Stheraven 806227825Stheravenprivate: 807227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 808227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 809227825Stheraven typedef typename __base::__node_holder __node_holder; 810227825Stheraven 811227825Stheraven __base __tree_; 812227825Stheraven 813227825Stheravenpublic: 814227825Stheraven typedef typename __base::pointer pointer; 815227825Stheraven typedef typename __base::const_pointer const_pointer; 816227825Stheraven typedef typename __base::size_type size_type; 817227825Stheraven typedef typename __base::difference_type difference_type; 818227825Stheraven typedef typename __base::const_iterator iterator; 819227825Stheraven typedef typename __base::const_iterator const_iterator; 820227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 821227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 822227825Stheraven 823227825Stheraven // construct/copy/destroy: 824227825Stheraven _LIBCPP_INLINE_VISIBILITY 825227825Stheraven explicit multiset(const value_compare& __comp = value_compare()) 826227825Stheraven _NOEXCEPT_( 827227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 828227825Stheraven is_nothrow_default_constructible<key_compare>::value && 829227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 830227825Stheraven : __tree_(__comp) {} 831227825Stheraven _LIBCPP_INLINE_VISIBILITY 832227825Stheraven multiset(const value_compare& __comp, const allocator_type& __a) 833227825Stheraven : __tree_(__comp, __a) {} 834227825Stheraven template <class _InputIterator> 835227825Stheraven _LIBCPP_INLINE_VISIBILITY 836227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 837227825Stheraven const value_compare& __comp = value_compare()) 838227825Stheraven : __tree_(__comp) 839227825Stheraven { 840227825Stheraven insert(__f, __l); 841227825Stheraven } 842227825Stheraven 843261272Sdim#if _LIBCPP_STD_VER > 11 844261272Sdim template <class _InputIterator> 845261272Sdim _LIBCPP_INLINE_VISIBILITY 846261272Sdim multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 847261272Sdim : multiset(__f, __l, key_compare(), __a) {} 848261272Sdim#endif 849261272Sdim 850227825Stheraven template <class _InputIterator> 851227825Stheraven _LIBCPP_INLINE_VISIBILITY 852227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 853227825Stheraven const value_compare& __comp, const allocator_type& __a) 854227825Stheraven : __tree_(__comp, __a) 855227825Stheraven { 856227825Stheraven insert(__f, __l); 857227825Stheraven } 858227825Stheraven 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven multiset(const multiset& __s) 861227825Stheraven : __tree_(__s.__tree_.value_comp(), 862227825Stheraven __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 863227825Stheraven { 864227825Stheraven insert(__s.begin(), __s.end()); 865227825Stheraven } 866227825Stheraven 867227825Stheraven _LIBCPP_INLINE_VISIBILITY 868227825Stheraven multiset& operator=(const multiset& __s) 869227825Stheraven { 870227825Stheraven __tree_ = __s.__tree_; 871227825Stheraven return *this; 872227825Stheraven } 873227825Stheraven 874227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 875227825Stheraven _LIBCPP_INLINE_VISIBILITY 876227825Stheraven multiset(multiset&& __s) 877227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 878227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 879227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 880227825Stheraven _LIBCPP_INLINE_VISIBILITY 881227825Stheraven explicit multiset(const allocator_type& __a) 882227825Stheraven : __tree_(__a) {} 883227825Stheraven _LIBCPP_INLINE_VISIBILITY 884227825Stheraven multiset(const multiset& __s, const allocator_type& __a) 885227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 886227825Stheraven { 887227825Stheraven insert(__s.begin(), __s.end()); 888227825Stheraven } 889227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 890227825Stheraven multiset(multiset&& __s, const allocator_type& __a); 891227825Stheraven#endif 892227825Stheraven 893227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 894227825Stheraven _LIBCPP_INLINE_VISIBILITY 895227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 896227825Stheraven : __tree_(__comp) 897227825Stheraven { 898227825Stheraven insert(__il.begin(), __il.end()); 899227825Stheraven } 900227825Stheraven 901227825Stheraven _LIBCPP_INLINE_VISIBILITY 902227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp, 903227825Stheraven const allocator_type& __a) 904227825Stheraven : __tree_(__comp, __a) 905227825Stheraven { 906227825Stheraven insert(__il.begin(), __il.end()); 907227825Stheraven } 908227825Stheraven 909261272Sdim#if _LIBCPP_STD_VER > 11 910261272Sdim _LIBCPP_INLINE_VISIBILITY 911261272Sdim multiset(initializer_list<value_type> __il, const allocator_type& __a) 912261272Sdim : multiset(__il, key_compare(), __a) {} 913261272Sdim#endif 914261272Sdim 915227825Stheraven _LIBCPP_INLINE_VISIBILITY 916227825Stheraven multiset& operator=(initializer_list<value_type> __il) 917227825Stheraven { 918227825Stheraven __tree_.__assign_multi(__il.begin(), __il.end()); 919227825Stheraven return *this; 920227825Stheraven } 921227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 922227825Stheraven 923227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 924227825Stheraven _LIBCPP_INLINE_VISIBILITY 925227825Stheraven multiset& operator=(multiset&& __s) 926227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 927227825Stheraven { 928227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 929227825Stheraven return *this; 930227825Stheraven } 931227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 932227825Stheraven 933227825Stheraven _LIBCPP_INLINE_VISIBILITY 934227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 935227825Stheraven _LIBCPP_INLINE_VISIBILITY 936227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 937227825Stheraven _LIBCPP_INLINE_VISIBILITY 938227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 939227825Stheraven _LIBCPP_INLINE_VISIBILITY 940227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 941227825Stheraven 942227825Stheraven _LIBCPP_INLINE_VISIBILITY 943227825Stheraven reverse_iterator rbegin() _NOEXCEPT 944227825Stheraven {return reverse_iterator(end());} 945227825Stheraven _LIBCPP_INLINE_VISIBILITY 946227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 947227825Stheraven {return const_reverse_iterator(end());} 948227825Stheraven _LIBCPP_INLINE_VISIBILITY 949227825Stheraven reverse_iterator rend() _NOEXCEPT 950227825Stheraven {return reverse_iterator(begin());} 951227825Stheraven _LIBCPP_INLINE_VISIBILITY 952227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 953227825Stheraven {return const_reverse_iterator(begin());} 954227825Stheraven 955227825Stheraven _LIBCPP_INLINE_VISIBILITY 956227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 957227825Stheraven _LIBCPP_INLINE_VISIBILITY 958227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 959227825Stheraven _LIBCPP_INLINE_VISIBILITY 960227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 961227825Stheraven _LIBCPP_INLINE_VISIBILITY 962227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 963227825Stheraven 964227825Stheraven _LIBCPP_INLINE_VISIBILITY 965227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 966227825Stheraven _LIBCPP_INLINE_VISIBILITY 967227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 968227825Stheraven _LIBCPP_INLINE_VISIBILITY 969227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 970227825Stheraven 971227825Stheraven // modifiers: 972227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 973227825Stheraven template <class... _Args> 974227825Stheraven _LIBCPP_INLINE_VISIBILITY 975227825Stheraven iterator emplace(_Args&&... __args) 976227825Stheraven {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 977227825Stheraven template <class... _Args> 978227825Stheraven _LIBCPP_INLINE_VISIBILITY 979227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 980227825Stheraven {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 981227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 982227825Stheraven _LIBCPP_INLINE_VISIBILITY 983227825Stheraven iterator insert(const value_type& __v) 984227825Stheraven {return __tree_.__insert_multi(__v);} 985227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 986227825Stheraven _LIBCPP_INLINE_VISIBILITY 987227825Stheraven iterator insert(value_type&& __v) 988227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 989227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 990227825Stheraven _LIBCPP_INLINE_VISIBILITY 991227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 992227825Stheraven {return __tree_.__insert_multi(__p, __v);} 993227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 994227825Stheraven _LIBCPP_INLINE_VISIBILITY 995227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 996227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 997227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 998227825Stheraven template <class _InputIterator> 999227825Stheraven _LIBCPP_INLINE_VISIBILITY 1000227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 1001227825Stheraven { 1002227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 1003227825Stheraven __tree_.__insert_multi(__e, *__f); 1004227825Stheraven } 1005227825Stheraven 1006227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1007227825Stheraven _LIBCPP_INLINE_VISIBILITY 1008227825Stheraven void insert(initializer_list<value_type> __il) 1009227825Stheraven {insert(__il.begin(), __il.end());} 1010227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1011227825Stheraven 1012227825Stheraven _LIBCPP_INLINE_VISIBILITY 1013227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1014227825Stheraven _LIBCPP_INLINE_VISIBILITY 1015227825Stheraven size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1016227825Stheraven _LIBCPP_INLINE_VISIBILITY 1017227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 1018227825Stheraven {return __tree_.erase(__f, __l);} 1019227825Stheraven _LIBCPP_INLINE_VISIBILITY 1020227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 1021227825Stheraven 1022227825Stheraven _LIBCPP_INLINE_VISIBILITY 1023227825Stheraven void swap(multiset& __s) 1024227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1025227825Stheraven {__tree_.swap(__s.__tree_);} 1026227825Stheraven 1027227825Stheraven _LIBCPP_INLINE_VISIBILITY 1028227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1029227825Stheraven _LIBCPP_INLINE_VISIBILITY 1030227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 1031227825Stheraven _LIBCPP_INLINE_VISIBILITY 1032227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 1033227825Stheraven 1034227825Stheraven // set operations: 1035227825Stheraven _LIBCPP_INLINE_VISIBILITY 1036227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 1037227825Stheraven _LIBCPP_INLINE_VISIBILITY 1038227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1039261272Sdim#if _LIBCPP_STD_VER > 11 1040261272Sdim template <typename _K2> 1041227825Stheraven _LIBCPP_INLINE_VISIBILITY 1042261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1043261272Sdim find(const _K2& __k) {return __tree_.find(__k);} 1044261272Sdim template <typename _K2> 1045261272Sdim _LIBCPP_INLINE_VISIBILITY 1046261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1047261272Sdim find(const _K2& __k) const {return __tree_.find(__k);} 1048261272Sdim#endif 1049261272Sdim 1050261272Sdim _LIBCPP_INLINE_VISIBILITY 1051227825Stheraven size_type count(const key_type& __k) const 1052227825Stheraven {return __tree_.__count_multi(__k);} 1053261272Sdim 1054227825Stheraven _LIBCPP_INLINE_VISIBILITY 1055227825Stheraven iterator lower_bound(const key_type& __k) 1056227825Stheraven {return __tree_.lower_bound(__k);} 1057227825Stheraven _LIBCPP_INLINE_VISIBILITY 1058227825Stheraven const_iterator lower_bound(const key_type& __k) const 1059227825Stheraven {return __tree_.lower_bound(__k);} 1060261272Sdim#if _LIBCPP_STD_VER > 11 1061261272Sdim template <typename _K2> 1062227825Stheraven _LIBCPP_INLINE_VISIBILITY 1063261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1064261272Sdim lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1065261272Sdim 1066261272Sdim template <typename _K2> 1067261272Sdim _LIBCPP_INLINE_VISIBILITY 1068261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1069261272Sdim lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1070261272Sdim#endif 1071261272Sdim 1072261272Sdim _LIBCPP_INLINE_VISIBILITY 1073227825Stheraven iterator upper_bound(const key_type& __k) 1074227825Stheraven {return __tree_.upper_bound(__k);} 1075227825Stheraven _LIBCPP_INLINE_VISIBILITY 1076227825Stheraven const_iterator upper_bound(const key_type& __k) const 1077227825Stheraven {return __tree_.upper_bound(__k);} 1078261272Sdim#if _LIBCPP_STD_VER > 11 1079261272Sdim template <typename _K2> 1080227825Stheraven _LIBCPP_INLINE_VISIBILITY 1081261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1082261272Sdim upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1083261272Sdim template <typename _K2> 1084261272Sdim _LIBCPP_INLINE_VISIBILITY 1085261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1086261272Sdim upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1087261272Sdim#endif 1088261272Sdim 1089261272Sdim _LIBCPP_INLINE_VISIBILITY 1090227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 1091227825Stheraven {return __tree_.__equal_range_multi(__k);} 1092227825Stheraven _LIBCPP_INLINE_VISIBILITY 1093227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1094227825Stheraven {return __tree_.__equal_range_multi(__k);} 1095261272Sdim#if _LIBCPP_STD_VER > 11 1096261272Sdim template <typename _K2> 1097261272Sdim _LIBCPP_INLINE_VISIBILITY 1098261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1099261272Sdim equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1100261272Sdim template <typename _K2> 1101261272Sdim _LIBCPP_INLINE_VISIBILITY 1102261272Sdim typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1103261272Sdim equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1104261272Sdim#endif 1105227825Stheraven}; 1106227825Stheraven 1107227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1108227825Stheraven 1109227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1110227825Stheravenmultiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1111227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 1112227825Stheraven{ 1113227825Stheraven if (__a != __s.get_allocator()) 1114227825Stheraven { 1115227825Stheraven const_iterator __e = cend(); 1116227825Stheraven while (!__s.empty()) 1117227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1118227825Stheraven } 1119227825Stheraven} 1120227825Stheraven 1121227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1122227825Stheraven 1123227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1124227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1125227825Stheravenbool 1126227825Stheravenoperator==(const multiset<_Key, _Compare, _Allocator>& __x, 1127227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1128227825Stheraven{ 1129227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1130227825Stheraven} 1131227825Stheraven 1132227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1133227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1134227825Stheravenbool 1135227825Stheravenoperator< (const multiset<_Key, _Compare, _Allocator>& __x, 1136227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1137227825Stheraven{ 1138227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1139227825Stheraven} 1140227825Stheraven 1141227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1142227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1143227825Stheravenbool 1144227825Stheravenoperator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1145227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1146227825Stheraven{ 1147227825Stheraven return !(__x == __y); 1148227825Stheraven} 1149227825Stheraven 1150227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1151227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1152227825Stheravenbool 1153227825Stheravenoperator> (const multiset<_Key, _Compare, _Allocator>& __x, 1154227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1155227825Stheraven{ 1156227825Stheraven return __y < __x; 1157227825Stheraven} 1158227825Stheraven 1159227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1160227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1161227825Stheravenbool 1162227825Stheravenoperator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1163227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1164227825Stheraven{ 1165227825Stheraven return !(__x < __y); 1166227825Stheraven} 1167227825Stheraven 1168227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1169227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1170227825Stheravenbool 1171227825Stheravenoperator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1172227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1173227825Stheraven{ 1174227825Stheraven return !(__y < __x); 1175227825Stheraven} 1176227825Stheraven 1177227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1178227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1179227825Stheravenvoid 1180227825Stheravenswap(multiset<_Key, _Compare, _Allocator>& __x, 1181227825Stheraven multiset<_Key, _Compare, _Allocator>& __y) 1182227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1183227825Stheraven{ 1184227825Stheraven __x.swap(__y); 1185227825Stheraven} 1186227825Stheraven 1187227825Stheraven_LIBCPP_END_NAMESPACE_STD 1188227825Stheraven 1189227825Stheraven#endif // _LIBCPP_SET 1190