set revision 249989
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); 69227825Stheraven ~set(); 70227825Stheraven 71227825Stheraven set& operator=(const set& s); 72227825Stheraven set& operator=(set&& s) 73227825Stheraven noexcept( 74227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 75227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 76227825Stheraven is_nothrow_move_assignable<key_compare>::value); 77227825Stheraven set& operator=(initializer_list<value_type> il); 78227825Stheraven 79227825Stheraven // iterators: 80227825Stheraven iterator begin() noexcept; 81227825Stheraven const_iterator begin() const noexcept; 82227825Stheraven iterator end() noexcept; 83227825Stheraven const_iterator end() const noexcept; 84227825Stheraven 85227825Stheraven reverse_iterator rbegin() noexcept; 86227825Stheraven const_reverse_iterator rbegin() const noexcept; 87227825Stheraven reverse_iterator rend() noexcept; 88227825Stheraven const_reverse_iterator rend() const noexcept; 89227825Stheraven 90227825Stheraven const_iterator cbegin() const noexcept; 91227825Stheraven const_iterator cend() const noexcept; 92227825Stheraven const_reverse_iterator crbegin() const noexcept; 93227825Stheraven const_reverse_iterator crend() const noexcept; 94227825Stheraven 95227825Stheraven // capacity: 96227825Stheraven bool empty() const noexcept; 97227825Stheraven size_type size() const noexcept; 98227825Stheraven size_type max_size() const noexcept; 99227825Stheraven 100227825Stheraven // modifiers: 101227825Stheraven template <class... Args> 102227825Stheraven pair<iterator, bool> emplace(Args&&... args); 103227825Stheraven template <class... Args> 104227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 105227825Stheraven pair<iterator,bool> insert(const value_type& v); 106227825Stheraven pair<iterator,bool> insert(value_type&& v); 107227825Stheraven iterator insert(const_iterator position, const value_type& v); 108227825Stheraven iterator insert(const_iterator position, value_type&& v); 109227825Stheraven template <class InputIterator> 110227825Stheraven void insert(InputIterator first, InputIterator last); 111227825Stheraven void insert(initializer_list<value_type> il); 112227825Stheraven 113227825Stheraven iterator erase(const_iterator position); 114227825Stheraven size_type erase(const key_type& k); 115227825Stheraven iterator erase(const_iterator first, const_iterator last); 116227825Stheraven void clear() noexcept; 117227825Stheraven 118227825Stheraven void swap(set& s) 119227825Stheraven noexcept( 120232924Stheraven __is_nothrow_swappable<key_compare>::value && 121232924Stheraven (!allocator_type::propagate_on_container_swap::value || 122227825Stheraven __is_nothrow_swappable<allocator_type>::value)); 123227825Stheraven 124227825Stheraven // observers: 125227825Stheraven allocator_type get_allocator() const noexcept; 126227825Stheraven key_compare key_comp() const; 127227825Stheraven value_compare value_comp() const; 128227825Stheraven 129232924Stheraven // set operations: 130232924Stheraven iterator find(const key_type& k); 131232924Stheraven const_iterator find(const key_type& k) const; 132232924Stheraven size_type count(const key_type& k) const; 133232924Stheraven iterator lower_bound(const key_type& k); 134232924Stheraven const_iterator lower_bound(const key_type& k) const; 135232924Stheraven iterator upper_bound(const key_type& k); 136232924Stheraven const_iterator upper_bound(const key_type& k) const; 137232924Stheraven pair<iterator,iterator> equal_range(const key_type& k); 138232924Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 139232924Stheraven}; 140232924Stheraven 141232924Stheraventemplate <class Key, class Compare, class Allocator> 142232924Stheravenbool 143232924Stheravenoperator==(const set<Key, Compare, Allocator>& x, 144232924Stheraven const set<Key, Compare, Allocator>& y); 145232924Stheraven 146232924Stheraventemplate <class Key, class Compare, class Allocator> 147232924Stheravenbool 148232924Stheravenoperator< (const set<Key, Compare, Allocator>& x, 149232924Stheraven const set<Key, Compare, Allocator>& y); 150232924Stheraven 151232924Stheraventemplate <class Key, class Compare, class Allocator> 152232924Stheravenbool 153232924Stheravenoperator!=(const set<Key, Compare, Allocator>& x, 154232924Stheraven const set<Key, Compare, Allocator>& y); 155232924Stheraven 156232924Stheraventemplate <class Key, class Compare, class Allocator> 157232924Stheravenbool 158232924Stheravenoperator> (const set<Key, Compare, Allocator>& x, 159232924Stheraven const set<Key, Compare, Allocator>& y); 160232924Stheraven 161232924Stheraventemplate <class Key, class Compare, class Allocator> 162232924Stheravenbool 163232924Stheravenoperator>=(const set<Key, Compare, Allocator>& x, 164232924Stheraven const set<Key, Compare, Allocator>& y); 165232924Stheraven 166232924Stheraventemplate <class Key, class Compare, class Allocator> 167227825Stheravenbool 168227825Stheravenoperator<=(const set<Key, Compare, Allocator>& x, 169232924Stheraven const set<Key, Compare, Allocator>& y); 170232924Stheraven 171232924Stheraven// specialized algorithms: 172232924Stheraventemplate <class Key, class Compare, class Allocator> 173232924Stheravenvoid 174232924Stheravenswap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 175232924Stheraven noexcept(noexcept(x.swap(y))); 176232924Stheraven 177232924Stheraventemplate <class Key, class Compare = less<Key>, 178232924Stheraven class Allocator = allocator<Key>> 179232924Stheravenclass multiset 180232924Stheraven{ 181232924Stheravenpublic: 182232924Stheraven // types: 183232924Stheraven typedef Key key_type; 184232924Stheraven typedef key_type value_type; 185232924Stheraven typedef Compare key_compare; 186232924Stheraven typedef key_compare value_compare; 187232924Stheraven typedef Allocator allocator_type; 188232924Stheraven typedef typename allocator_type::reference reference; 189227825Stheraven typedef typename allocator_type::const_reference const_reference; 190227825Stheraven typedef typename allocator_type::size_type size_type; 191227825Stheraven typedef typename allocator_type::difference_type difference_type; 192227825Stheraven typedef typename allocator_type::pointer pointer; 193227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 194227825Stheraven 195227825Stheraven typedef implementation-defined iterator; 196227825Stheraven typedef implementation-defined const_iterator; 197227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 198227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 199227825Stheraven 200227825Stheraven // construct/copy/destroy: 201227825Stheraven multiset() 202227825Stheraven noexcept( 203227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 204227825Stheraven is_nothrow_default_constructible<key_compare>::value && 205227825Stheraven is_nothrow_copy_constructible<key_compare>::value); 206227825Stheraven explicit multiset(const value_compare& comp); 207227825Stheraven multiset(const value_compare& comp, const allocator_type& a); 208232924Stheraven template <class InputIterator> 209232924Stheraven multiset(InputIterator first, InputIterator last, 210232924Stheraven const value_compare& comp = value_compare()); 211232924Stheraven template <class InputIterator> 212232924Stheraven multiset(InputIterator first, InputIterator last, 213227825Stheraven const value_compare& comp, const allocator_type& a); 214227825Stheraven multiset(const multiset& s); 215227825Stheraven multiset(multiset&& s) 216227825Stheraven noexcept( 217227825Stheraven is_nothrow_move_constructible<allocator_type>::value && 218227825Stheraven is_nothrow_move_constructible<key_compare>::value); 219227825Stheraven explicit multiset(const allocator_type& a); 220227825Stheraven multiset(const multiset& s, const allocator_type& a); 221227825Stheraven multiset(multiset&& s, const allocator_type& a); 222227825Stheraven multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 223227825Stheraven multiset(initializer_list<value_type> il, const value_compare& comp, 224227825Stheraven const allocator_type& a); 225227825Stheraven ~multiset(); 226227825Stheraven 227227825Stheraven multiset& operator=(const multiset& s); 228227825Stheraven multiset& operator=(multiset&& s) 229227825Stheraven noexcept( 230227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 231227825Stheraven is_nothrow_move_assignable<allocator_type>::value && 232227825Stheraven is_nothrow_move_assignable<key_compare>::value); 233227825Stheraven multiset& operator=(initializer_list<value_type> il); 234227825Stheraven 235227825Stheraven // iterators: 236227825Stheraven iterator begin() noexcept; 237227825Stheraven const_iterator begin() const noexcept; 238227825Stheraven iterator end() noexcept; 239227825Stheraven const_iterator end() const noexcept; 240227825Stheraven 241227825Stheraven reverse_iterator rbegin() noexcept; 242227825Stheraven const_reverse_iterator rbegin() const noexcept; 243227825Stheraven reverse_iterator rend() noexcept; 244227825Stheraven const_reverse_iterator rend() const noexcept; 245227825Stheraven 246227825Stheraven const_iterator cbegin() const noexcept; 247227825Stheraven const_iterator cend() const noexcept; 248227825Stheraven const_reverse_iterator crbegin() const noexcept; 249227825Stheraven const_reverse_iterator crend() const noexcept; 250227825Stheraven 251227825Stheraven // capacity: 252227825Stheraven bool empty() const noexcept; 253227825Stheraven size_type size() const noexcept; 254227825Stheraven size_type max_size() const noexcept; 255227825Stheraven 256227825Stheraven // modifiers: 257227825Stheraven template <class... Args> 258227825Stheraven iterator emplace(Args&&... args); 259227825Stheraven template <class... Args> 260227825Stheraven iterator emplace_hint(const_iterator position, Args&&... args); 261232924Stheraven iterator insert(const value_type& v); 262227825Stheraven iterator insert(value_type&& v); 263227825Stheraven iterator insert(const_iterator position, const value_type& v); 264227825Stheraven iterator insert(const_iterator position, value_type&& v); 265227825Stheraven template <class InputIterator> 266227825Stheraven void insert(InputIterator first, InputIterator last); 267232924Stheraven void insert(initializer_list<value_type> il); 268227825Stheraven 269227825Stheraven iterator erase(const_iterator position); 270227825Stheraven size_type erase(const key_type& k); 271227825Stheraven iterator erase(const_iterator first, const_iterator last); 272227825Stheraven void clear() noexcept; 273227825Stheraven 274227825Stheraven void swap(multiset& s) 275227825Stheraven noexcept( 276227825Stheraven __is_nothrow_swappable<key_compare>::value && 277232924Stheraven (!allocator_type::propagate_on_container_swap::value || 278227825Stheraven __is_nothrow_swappable<allocator_type>::value)); 279227825Stheraven 280227825Stheraven // observers: 281227825Stheraven allocator_type get_allocator() const noexcept; 282227825Stheraven key_compare key_comp() const; 283232924Stheraven value_compare value_comp() const; 284227825Stheraven 285227825Stheraven // set operations: 286227825Stheraven iterator find(const key_type& k); 287227825Stheraven const_iterator find(const key_type& k) const; 288227825Stheraven size_type count(const key_type& k) const; 289227825Stheraven iterator lower_bound(const key_type& k); 290227825Stheraven const_iterator lower_bound(const key_type& k) const; 291232924Stheraven iterator upper_bound(const key_type& k); 292227825Stheraven const_iterator upper_bound(const key_type& k) const; 293227825Stheraven pair<iterator,iterator> equal_range(const key_type& k); 294227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 295227825Stheraven}; 296227825Stheraven 297232924Stheraventemplate <class Key, class Compare, class Allocator> 298227825Stheravenbool 299227825Stheravenoperator==(const multiset<Key, Compare, Allocator>& x, 300227825Stheraven const multiset<Key, Compare, Allocator>& y); 301227825Stheraven 302227825Stheraventemplate <class Key, class Compare, class Allocator> 303227825Stheravenbool 304227825Stheravenoperator< (const multiset<Key, Compare, Allocator>& x, 305232924Stheraven const multiset<Key, Compare, Allocator>& y); 306227825Stheraven 307227825Stheraventemplate <class Key, class Compare, class Allocator> 308227825Stheravenbool 309227825Stheravenoperator!=(const multiset<Key, Compare, Allocator>& x, 310227825Stheraven const multiset<Key, Compare, Allocator>& y); 311232924Stheraven 312227825Stheraventemplate <class Key, class Compare, class Allocator> 313227825Stheravenbool 314227825Stheravenoperator> (const multiset<Key, Compare, Allocator>& x, 315227825Stheraven const multiset<Key, Compare, Allocator>& y); 316227825Stheraven 317227825Stheraventemplate <class Key, class Compare, class Allocator> 318227825Stheravenbool 319227825Stheravenoperator>=(const multiset<Key, Compare, Allocator>& x, 320227825Stheraven const multiset<Key, Compare, Allocator>& y); 321227825Stheraven 322227825Stheraventemplate <class Key, class Compare, class Allocator> 323227825Stheravenbool 324227825Stheravenoperator<=(const multiset<Key, Compare, Allocator>& x, 325227825Stheraven const multiset<Key, Compare, Allocator>& y); 326227825Stheraven 327227825Stheraven// specialized algorithms: 328227825Stheraventemplate <class Key, class Compare, class Allocator> 329227825Stheravenvoid 330227825Stheravenswap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 331227825Stheraven noexcept(noexcept(x.swap(y))); 332227825Stheraven 333227825Stheraven} // std 334227825Stheraven 335227825Stheraven*/ 336227825Stheraven 337227825Stheraven#include <__config> 338227825Stheraven#include <__tree> 339227825Stheraven#include <functional> 340227825Stheraven 341227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 342227825Stheraven#pragma GCC system_header 343227825Stheraven#endif 344227825Stheraven 345227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 346227825Stheraven 347227825Stheraventemplate <class _Key, class _Compare = less<_Key>, 348227825Stheraven class _Allocator = allocator<_Key> > 349227825Stheravenclass _LIBCPP_TYPE_VIS set 350227825Stheraven{ 351227825Stheravenpublic: 352227825Stheraven // types: 353227825Stheraven typedef _Key key_type; 354227825Stheraven typedef key_type value_type; 355227825Stheraven typedef _Compare key_compare; 356227825Stheraven typedef key_compare value_compare; 357227825Stheraven typedef _Allocator allocator_type; 358227825Stheraven typedef value_type& reference; 359227825Stheraven typedef const value_type& const_reference; 360227825Stheraven 361227825Stheravenprivate: 362227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 363227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 364227825Stheraven typedef typename __base::__node_holder __node_holder; 365227825Stheraven 366227825Stheraven __base __tree_; 367227825Stheraven 368227825Stheravenpublic: 369227825Stheraven typedef typename __base::pointer pointer; 370227825Stheraven typedef typename __base::const_pointer const_pointer; 371227825Stheraven typedef typename __base::size_type size_type; 372227825Stheraven typedef typename __base::difference_type difference_type; 373227825Stheraven typedef typename __base::const_iterator iterator; 374227825Stheraven typedef typename __base::const_iterator const_iterator; 375227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 376227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 377227825Stheraven 378227825Stheraven _LIBCPP_INLINE_VISIBILITY 379227825Stheraven explicit set(const value_compare& __comp = value_compare()) 380227825Stheraven _NOEXCEPT_( 381227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 382227825Stheraven is_nothrow_default_constructible<key_compare>::value && 383227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 384227825Stheraven : __tree_(__comp) {} 385227825Stheraven _LIBCPP_INLINE_VISIBILITY 386227825Stheraven set(const value_compare& __comp, const allocator_type& __a) 387227825Stheraven : __tree_(__comp, __a) {} 388227825Stheraven template <class _InputIterator> 389227825Stheraven _LIBCPP_INLINE_VISIBILITY 390227825Stheraven set(_InputIterator __f, _InputIterator __l, 391227825Stheraven const value_compare& __comp = value_compare()) 392227825Stheraven : __tree_(__comp) 393227825Stheraven { 394227825Stheraven insert(__f, __l); 395227825Stheraven } 396227825Stheraven 397227825Stheraven template <class _InputIterator> 398227825Stheraven _LIBCPP_INLINE_VISIBILITY 399227825Stheraven set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 400227825Stheraven const allocator_type& __a) 401227825Stheraven : __tree_(__comp, __a) 402227825Stheraven { 403227825Stheraven insert(__f, __l); 404227825Stheraven } 405227825Stheraven 406227825Stheraven _LIBCPP_INLINE_VISIBILITY 407227825Stheraven set(const set& __s) 408227825Stheraven : __tree_(__s.__tree_) 409227825Stheraven { 410227825Stheraven insert(__s.begin(), __s.end()); 411227825Stheraven } 412227825Stheraven 413227825Stheraven _LIBCPP_INLINE_VISIBILITY 414227825Stheraven set& operator=(const set& __s) 415227825Stheraven { 416227825Stheraven __tree_ = __s.__tree_; 417227825Stheraven return *this; 418227825Stheraven } 419227825Stheraven 420227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 421227825Stheraven _LIBCPP_INLINE_VISIBILITY 422227825Stheraven set(set&& __s) 423227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 424227825Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 425232924Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 426232924Stheraven 427227825Stheraven _LIBCPP_INLINE_VISIBILITY 428232924Stheraven explicit set(const allocator_type& __a) 429227825Stheraven : __tree_(__a) {} 430227825Stheraven 431227825Stheraven _LIBCPP_INLINE_VISIBILITY 432227825Stheraven set(const set& __s, const allocator_type& __a) 433227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 434227825Stheraven { 435227825Stheraven insert(__s.begin(), __s.end()); 436227825Stheraven } 437227825Stheraven 438227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 439227825Stheraven set(set&& __s, const allocator_type& __a); 440227825Stheraven#endif 441227825Stheraven 442227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 443227825Stheraven _LIBCPP_INLINE_VISIBILITY 444227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 445227825Stheraven : __tree_(__comp) 446227825Stheraven { 447227825Stheraven insert(__il.begin(), __il.end()); 448227825Stheraven } 449227825Stheraven 450227825Stheraven _LIBCPP_INLINE_VISIBILITY 451227825Stheraven set(initializer_list<value_type> __il, const value_compare& __comp, 452227825Stheraven const allocator_type& __a) 453227825Stheraven : __tree_(__comp, __a) 454227825Stheraven { 455227825Stheraven insert(__il.begin(), __il.end()); 456227825Stheraven } 457227825Stheraven 458227825Stheraven _LIBCPP_INLINE_VISIBILITY 459227825Stheraven set& operator=(initializer_list<value_type> __il) 460227825Stheraven { 461227825Stheraven __tree_.__assign_unique(__il.begin(), __il.end()); 462227825Stheraven return *this; 463227825Stheraven } 464227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 465227825Stheraven 466227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 467227825Stheraven _LIBCPP_INLINE_VISIBILITY 468227825Stheraven set& operator=(set&& __s) 469227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 470227825Stheraven { 471227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 472227825Stheraven return *this; 473227825Stheraven } 474227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 475227825Stheraven 476227825Stheraven _LIBCPP_INLINE_VISIBILITY 477227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 478227825Stheraven _LIBCPP_INLINE_VISIBILITY 479227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 480227825Stheraven _LIBCPP_INLINE_VISIBILITY 481227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 482227825Stheraven _LIBCPP_INLINE_VISIBILITY 483227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 484227825Stheraven 485227825Stheraven _LIBCPP_INLINE_VISIBILITY 486227825Stheraven reverse_iterator rbegin() _NOEXCEPT 487227825Stheraven {return reverse_iterator(end());} 488227825Stheraven _LIBCPP_INLINE_VISIBILITY 489227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 490227825Stheraven {return const_reverse_iterator(end());} 491227825Stheraven _LIBCPP_INLINE_VISIBILITY 492227825Stheraven reverse_iterator rend() _NOEXCEPT 493227825Stheraven {return reverse_iterator(begin());} 494227825Stheraven _LIBCPP_INLINE_VISIBILITY 495227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 496227825Stheraven {return const_reverse_iterator(begin());} 497227825Stheraven 498227825Stheraven _LIBCPP_INLINE_VISIBILITY 499227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 500227825Stheraven _LIBCPP_INLINE_VISIBILITY 501227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 502227825Stheraven _LIBCPP_INLINE_VISIBILITY 503232924Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 504232924Stheraven _LIBCPP_INLINE_VISIBILITY 505232924Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 506232924Stheraven 507232924Stheraven _LIBCPP_INLINE_VISIBILITY 508232924Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 509232924Stheraven _LIBCPP_INLINE_VISIBILITY 510232924Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 511227825Stheraven _LIBCPP_INLINE_VISIBILITY 512227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 513227825Stheraven 514227825Stheraven // modifiers: 515227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 516227825Stheraven template <class... _Args> 517227825Stheraven _LIBCPP_INLINE_VISIBILITY 518227825Stheraven pair<iterator, bool> emplace(_Args&&... __args) 519227825Stheraven {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 520227825Stheraven template <class... _Args> 521227825Stheraven _LIBCPP_INLINE_VISIBILITY 522227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 523227825Stheraven {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 524227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 525227825Stheraven _LIBCPP_INLINE_VISIBILITY 526227825Stheraven pair<iterator,bool> insert(const value_type& __v) 527232924Stheraven {return __tree_.__insert_unique(__v);} 528227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 529232924Stheraven _LIBCPP_INLINE_VISIBILITY 530227825Stheraven pair<iterator,bool> insert(value_type&& __v) 531232924Stheraven {return __tree_.__insert_unique(_VSTD::move(__v));} 532227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 533227825Stheraven _LIBCPP_INLINE_VISIBILITY 534227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 535227825Stheraven {return __tree_.__insert_unique(__p, __v);} 536227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 537227825Stheraven _LIBCPP_INLINE_VISIBILITY 538227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 539227825Stheraven {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 540227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 541227825Stheraven template <class _InputIterator> 542227825Stheraven _LIBCPP_INLINE_VISIBILITY 543227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 544227825Stheraven { 545227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 546227825Stheraven __tree_.__insert_unique(__e, *__f); 547227825Stheraven } 548227825Stheraven 549227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 550227825Stheraven _LIBCPP_INLINE_VISIBILITY 551227825Stheraven void insert(initializer_list<value_type> __il) 552227825Stheraven {insert(__il.begin(), __il.end());} 553227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 554227825Stheraven 555227825Stheraven _LIBCPP_INLINE_VISIBILITY 556227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 557227825Stheraven _LIBCPP_INLINE_VISIBILITY 558227825Stheraven size_type erase(const key_type& __k) 559227825Stheraven {return __tree_.__erase_unique(__k);} 560227825Stheraven _LIBCPP_INLINE_VISIBILITY 561227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 562227825Stheraven {return __tree_.erase(__f, __l);} 563227825Stheraven _LIBCPP_INLINE_VISIBILITY 564227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 565227825Stheraven 566227825Stheraven _LIBCPP_INLINE_VISIBILITY 567227825Stheraven void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 568227825Stheraven {__tree_.swap(__s.__tree_);} 569227825Stheraven 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571227825Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 572227825Stheraven _LIBCPP_INLINE_VISIBILITY 573227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 574227825Stheraven _LIBCPP_INLINE_VISIBILITY 575227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 576227825Stheraven 577227825Stheraven // set operations: 578227825Stheraven _LIBCPP_INLINE_VISIBILITY 579227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 580227825Stheraven _LIBCPP_INLINE_VISIBILITY 581227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 582227825Stheraven _LIBCPP_INLINE_VISIBILITY 583227825Stheraven size_type count(const key_type& __k) const 584227825Stheraven {return __tree_.__count_unique(__k);} 585227825Stheraven _LIBCPP_INLINE_VISIBILITY 586227825Stheraven iterator lower_bound(const key_type& __k) 587227825Stheraven {return __tree_.lower_bound(__k);} 588227825Stheraven _LIBCPP_INLINE_VISIBILITY 589227825Stheraven const_iterator lower_bound(const key_type& __k) const 590227825Stheraven {return __tree_.lower_bound(__k);} 591227825Stheraven _LIBCPP_INLINE_VISIBILITY 592227825Stheraven iterator upper_bound(const key_type& __k) 593227825Stheraven {return __tree_.upper_bound(__k);} 594227825Stheraven _LIBCPP_INLINE_VISIBILITY 595227825Stheraven const_iterator upper_bound(const key_type& __k) const 596227825Stheraven {return __tree_.upper_bound(__k);} 597227825Stheraven _LIBCPP_INLINE_VISIBILITY 598227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 599227825Stheraven {return __tree_.__equal_range_unique(__k);} 600227825Stheraven _LIBCPP_INLINE_VISIBILITY 601227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 602227825Stheraven {return __tree_.__equal_range_unique(__k);} 603227825Stheraven}; 604227825Stheraven 605227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 606227825Stheraven 607227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 608227825Stheravenset<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 609227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 610227825Stheraven{ 611227825Stheraven if (__a != __s.get_allocator()) 612227825Stheraven { 613227825Stheraven const_iterator __e = cend(); 614227825Stheraven while (!__s.empty()) 615227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 616227825Stheraven } 617227825Stheraven} 618227825Stheraven 619227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 620227825Stheraven 621227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 622227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 623227825Stheravenbool 624227825Stheravenoperator==(const set<_Key, _Compare, _Allocator>& __x, 625227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 626227825Stheraven{ 627227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 628227825Stheraven} 629227825Stheraven 630227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 631227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 632227825Stheravenbool 633227825Stheravenoperator< (const set<_Key, _Compare, _Allocator>& __x, 634227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 635227825Stheraven{ 636227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 637227825Stheraven} 638227825Stheraven 639227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 640227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 641227825Stheravenbool 642227825Stheravenoperator!=(const set<_Key, _Compare, _Allocator>& __x, 643227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 644227825Stheraven{ 645227825Stheraven return !(__x == __y); 646227825Stheraven} 647227825Stheraven 648227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 649227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 650227825Stheravenbool 651232924Stheravenoperator> (const set<_Key, _Compare, _Allocator>& __x, 652227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 653232924Stheraven{ 654232924Stheraven return __y < __x; 655227825Stheraven} 656232924Stheraven 657227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 658227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 659227825Stheravenbool 660227825Stheravenoperator>=(const set<_Key, _Compare, _Allocator>& __x, 661227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 662227825Stheraven{ 663227825Stheraven return !(__x < __y); 664227825Stheraven} 665227825Stheraven 666227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 667227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 668227825Stheravenbool 669227825Stheravenoperator<=(const set<_Key, _Compare, _Allocator>& __x, 670227825Stheraven const set<_Key, _Compare, _Allocator>& __y) 671227825Stheraven{ 672227825Stheraven return !(__y < __x); 673227825Stheraven} 674227825Stheraven 675227825Stheraven// specialized algorithms: 676227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 677232924Stheraveninline _LIBCPP_INLINE_VISIBILITY 678227825Stheravenvoid 679227825Stheravenswap(set<_Key, _Compare, _Allocator>& __x, 680227825Stheraven set<_Key, _Compare, _Allocator>& __y) 681227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 682227825Stheraven{ 683227825Stheraven __x.swap(__y); 684227825Stheraven} 685227825Stheraven 686232924Stheraventemplate <class _Key, class _Compare = less<_Key>, 687227825Stheraven class _Allocator = allocator<_Key> > 688227825Stheravenclass _LIBCPP_TYPE_VIS multiset 689227825Stheraven{ 690227825Stheravenpublic: 691227825Stheraven // types: 692227825Stheraven typedef _Key key_type; 693227825Stheraven typedef key_type value_type; 694227825Stheraven typedef _Compare key_compare; 695232924Stheraven typedef key_compare value_compare; 696227825Stheraven typedef _Allocator allocator_type; 697227825Stheraven typedef value_type& reference; 698227825Stheraven typedef const value_type& const_reference; 699227825Stheraven 700227825Stheravenprivate: 701227825Stheraven typedef __tree<value_type, value_compare, allocator_type> __base; 702227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 703227825Stheraven typedef typename __base::__node_holder __node_holder; 704227825Stheraven 705227825Stheraven __base __tree_; 706227825Stheraven 707227825Stheravenpublic: 708227825Stheraven typedef typename __base::pointer pointer; 709227825Stheraven typedef typename __base::const_pointer const_pointer; 710227825Stheraven typedef typename __base::size_type size_type; 711227825Stheraven typedef typename __base::difference_type difference_type; 712227825Stheraven typedef typename __base::const_iterator iterator; 713227825Stheraven typedef typename __base::const_iterator const_iterator; 714227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 715227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 716227825Stheraven 717227825Stheraven // construct/copy/destroy: 718227825Stheraven _LIBCPP_INLINE_VISIBILITY 719227825Stheraven explicit multiset(const value_compare& __comp = value_compare()) 720227825Stheraven _NOEXCEPT_( 721227825Stheraven is_nothrow_default_constructible<allocator_type>::value && 722227825Stheraven is_nothrow_default_constructible<key_compare>::value && 723227825Stheraven is_nothrow_copy_constructible<key_compare>::value) 724227825Stheraven : __tree_(__comp) {} 725227825Stheraven _LIBCPP_INLINE_VISIBILITY 726227825Stheraven multiset(const value_compare& __comp, const allocator_type& __a) 727227825Stheraven : __tree_(__comp, __a) {} 728227825Stheraven template <class _InputIterator> 729227825Stheraven _LIBCPP_INLINE_VISIBILITY 730227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 731227825Stheraven const value_compare& __comp = value_compare()) 732227825Stheraven : __tree_(__comp) 733227825Stheraven { 734227825Stheraven insert(__f, __l); 735227825Stheraven } 736227825Stheraven 737227825Stheraven template <class _InputIterator> 738227825Stheraven _LIBCPP_INLINE_VISIBILITY 739227825Stheraven multiset(_InputIterator __f, _InputIterator __l, 740227825Stheraven const value_compare& __comp, const allocator_type& __a) 741227825Stheraven : __tree_(__comp, __a) 742227825Stheraven { 743227825Stheraven insert(__f, __l); 744227825Stheraven } 745227825Stheraven 746227825Stheraven _LIBCPP_INLINE_VISIBILITY 747227825Stheraven multiset(const multiset& __s) 748227825Stheraven : __tree_(__s.__tree_.value_comp(), 749227825Stheraven __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 750227825Stheraven { 751227825Stheraven insert(__s.begin(), __s.end()); 752227825Stheraven } 753227825Stheraven 754227825Stheraven _LIBCPP_INLINE_VISIBILITY 755227825Stheraven multiset& operator=(const multiset& __s) 756227825Stheraven { 757227825Stheraven __tree_ = __s.__tree_; 758232924Stheraven return *this; 759227825Stheraven } 760227825Stheraven 761227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 762227825Stheraven _LIBCPP_INLINE_VISIBILITY 763227825Stheraven multiset(multiset&& __s) 764227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 765232924Stheraven : __tree_(_VSTD::move(__s.__tree_)) {} 766227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 767227825Stheraven _LIBCPP_INLINE_VISIBILITY 768227825Stheraven explicit multiset(const allocator_type& __a) 769227825Stheraven : __tree_(__a) {} 770227825Stheraven _LIBCPP_INLINE_VISIBILITY 771227825Stheraven multiset(const multiset& __s, const allocator_type& __a) 772227825Stheraven : __tree_(__s.__tree_.value_comp(), __a) 773227825Stheraven { 774227825Stheraven insert(__s.begin(), __s.end()); 775227825Stheraven } 776227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 777227825Stheraven multiset(multiset&& __s, const allocator_type& __a); 778227825Stheraven#endif 779227825Stheraven 780227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 781227825Stheraven _LIBCPP_INLINE_VISIBILITY 782227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 783227825Stheraven : __tree_(__comp) 784227825Stheraven { 785227825Stheraven insert(__il.begin(), __il.end()); 786227825Stheraven } 787227825Stheraven 788227825Stheraven _LIBCPP_INLINE_VISIBILITY 789227825Stheraven multiset(initializer_list<value_type> __il, const value_compare& __comp, 790227825Stheraven const allocator_type& __a) 791227825Stheraven : __tree_(__comp, __a) 792227825Stheraven { 793227825Stheraven insert(__il.begin(), __il.end()); 794227825Stheraven } 795227825Stheraven 796232924Stheraven _LIBCPP_INLINE_VISIBILITY 797227825Stheraven multiset& operator=(initializer_list<value_type> __il) 798227825Stheraven { 799227825Stheraven __tree_.__assign_multi(__il.begin(), __il.end()); 800227825Stheraven return *this; 801227825Stheraven } 802227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 803232924Stheraven 804232924Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 805227825Stheraven _LIBCPP_INLINE_VISIBILITY 806227825Stheraven multiset& operator=(multiset&& __s) 807227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 808227825Stheraven { 809227825Stheraven __tree_ = _VSTD::move(__s.__tree_); 810227825Stheraven return *this; 811227825Stheraven } 812227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 813227825Stheraven 814227825Stheraven _LIBCPP_INLINE_VISIBILITY 815227825Stheraven iterator begin() _NOEXCEPT {return __tree_.begin();} 816227825Stheraven _LIBCPP_INLINE_VISIBILITY 817227825Stheraven const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 818227825Stheraven _LIBCPP_INLINE_VISIBILITY 819227825Stheraven iterator end() _NOEXCEPT {return __tree_.end();} 820227825Stheraven _LIBCPP_INLINE_VISIBILITY 821227825Stheraven const_iterator end() const _NOEXCEPT {return __tree_.end();} 822227825Stheraven 823227825Stheraven _LIBCPP_INLINE_VISIBILITY 824227825Stheraven reverse_iterator rbegin() _NOEXCEPT 825227825Stheraven {return reverse_iterator(end());} 826227825Stheraven _LIBCPP_INLINE_VISIBILITY 827227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 828227825Stheraven {return const_reverse_iterator(end());} 829227825Stheraven _LIBCPP_INLINE_VISIBILITY 830227825Stheraven reverse_iterator rend() _NOEXCEPT 831227825Stheraven {return reverse_iterator(begin());} 832227825Stheraven _LIBCPP_INLINE_VISIBILITY 833227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 834227825Stheraven {return const_reverse_iterator(begin());} 835227825Stheraven 836227825Stheraven _LIBCPP_INLINE_VISIBILITY 837227825Stheraven const_iterator cbegin() const _NOEXCEPT {return begin();} 838227825Stheraven _LIBCPP_INLINE_VISIBILITY 839227825Stheraven const_iterator cend() const _NOEXCEPT {return end();} 840227825Stheraven _LIBCPP_INLINE_VISIBILITY 841227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 842227825Stheraven _LIBCPP_INLINE_VISIBILITY 843227825Stheraven const_reverse_iterator crend() const _NOEXCEPT {return rend();} 844227825Stheraven 845227825Stheraven _LIBCPP_INLINE_VISIBILITY 846227825Stheraven bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 847227825Stheraven _LIBCPP_INLINE_VISIBILITY 848227825Stheraven size_type size() const _NOEXCEPT {return __tree_.size();} 849227825Stheraven _LIBCPP_INLINE_VISIBILITY 850227825Stheraven size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 851227825Stheraven 852227825Stheraven // modifiers: 853227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 854227825Stheraven template <class... _Args> 855227825Stheraven _LIBCPP_INLINE_VISIBILITY 856227825Stheraven iterator emplace(_Args&&... __args) 857227825Stheraven {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 858227825Stheraven template <class... _Args> 859227825Stheraven _LIBCPP_INLINE_VISIBILITY 860227825Stheraven iterator emplace_hint(const_iterator __p, _Args&&... __args) 861227825Stheraven {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 862227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 863227825Stheraven _LIBCPP_INLINE_VISIBILITY 864227825Stheraven iterator insert(const value_type& __v) 865227825Stheraven {return __tree_.__insert_multi(__v);} 866227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 867227825Stheraven _LIBCPP_INLINE_VISIBILITY 868227825Stheraven iterator insert(value_type&& __v) 869227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 870227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 871227825Stheraven _LIBCPP_INLINE_VISIBILITY 872227825Stheraven iterator insert(const_iterator __p, const value_type& __v) 873227825Stheraven {return __tree_.__insert_multi(__p, __v);} 874227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 875227825Stheraven _LIBCPP_INLINE_VISIBILITY 876227825Stheraven iterator insert(const_iterator __p, value_type&& __v) 877227825Stheraven {return __tree_.__insert_multi(_VSTD::move(__v));} 878227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 879227825Stheraven template <class _InputIterator> 880227825Stheraven _LIBCPP_INLINE_VISIBILITY 881227825Stheraven void insert(_InputIterator __f, _InputIterator __l) 882227825Stheraven { 883227825Stheraven for (const_iterator __e = cend(); __f != __l; ++__f) 884227825Stheraven __tree_.__insert_multi(__e, *__f); 885227825Stheraven } 886227825Stheraven 887227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 888227825Stheraven _LIBCPP_INLINE_VISIBILITY 889227825Stheraven void insert(initializer_list<value_type> __il) 890227825Stheraven {insert(__il.begin(), __il.end());} 891227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 892227825Stheraven 893227825Stheraven _LIBCPP_INLINE_VISIBILITY 894227825Stheraven iterator erase(const_iterator __p) {return __tree_.erase(__p);} 895227825Stheraven _LIBCPP_INLINE_VISIBILITY 896227825Stheraven size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 897227825Stheraven _LIBCPP_INLINE_VISIBILITY 898227825Stheraven iterator erase(const_iterator __f, const_iterator __l) 899227825Stheraven {return __tree_.erase(__f, __l);} 900227825Stheraven _LIBCPP_INLINE_VISIBILITY 901227825Stheraven void clear() _NOEXCEPT {__tree_.clear();} 902227825Stheraven 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven void swap(multiset& __s) 905227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 906227825Stheraven {__tree_.swap(__s.__tree_);} 907227825Stheraven 908227825Stheraven _LIBCPP_INLINE_VISIBILITY 909232924Stheraven allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 910227825Stheraven _LIBCPP_INLINE_VISIBILITY 911227825Stheraven key_compare key_comp() const {return __tree_.value_comp();} 912227825Stheraven _LIBCPP_INLINE_VISIBILITY 913227825Stheraven value_compare value_comp() const {return __tree_.value_comp();} 914227825Stheraven 915227825Stheraven // set operations: 916227825Stheraven _LIBCPP_INLINE_VISIBILITY 917227825Stheraven iterator find(const key_type& __k) {return __tree_.find(__k);} 918227825Stheraven _LIBCPP_INLINE_VISIBILITY 919227825Stheraven const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 920227825Stheraven _LIBCPP_INLINE_VISIBILITY 921227825Stheraven size_type count(const key_type& __k) const 922227825Stheraven {return __tree_.__count_multi(__k);} 923227825Stheraven _LIBCPP_INLINE_VISIBILITY 924227825Stheraven iterator lower_bound(const key_type& __k) 925227825Stheraven {return __tree_.lower_bound(__k);} 926227825Stheraven _LIBCPP_INLINE_VISIBILITY 927227825Stheraven const_iterator lower_bound(const key_type& __k) const 928227825Stheraven {return __tree_.lower_bound(__k);} 929227825Stheraven _LIBCPP_INLINE_VISIBILITY 930227825Stheraven iterator upper_bound(const key_type& __k) 931227825Stheraven {return __tree_.upper_bound(__k);} 932227825Stheraven _LIBCPP_INLINE_VISIBILITY 933227825Stheraven const_iterator upper_bound(const key_type& __k) const 934227825Stheraven {return __tree_.upper_bound(__k);} 935227825Stheraven _LIBCPP_INLINE_VISIBILITY 936227825Stheraven pair<iterator,iterator> equal_range(const key_type& __k) 937227825Stheraven {return __tree_.__equal_range_multi(__k);} 938227825Stheraven _LIBCPP_INLINE_VISIBILITY 939227825Stheraven pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 940227825Stheraven {return __tree_.__equal_range_multi(__k);} 941227825Stheraven}; 942227825Stheraven 943227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 944227825Stheraven 945227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 946227825Stheravenmultiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 947227825Stheraven : __tree_(_VSTD::move(__s.__tree_), __a) 948227825Stheraven{ 949227825Stheraven if (__a != __s.get_allocator()) 950227825Stheraven { 951227825Stheraven const_iterator __e = cend(); 952227825Stheraven while (!__s.empty()) 953227825Stheraven insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 954227825Stheraven } 955227825Stheraven} 956227825Stheraven 957227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 958227825Stheraven 959227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 960227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 961227825Stheravenbool 962227825Stheravenoperator==(const multiset<_Key, _Compare, _Allocator>& __x, 963227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 964227825Stheraven{ 965227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 966227825Stheraven} 967227825Stheraven 968227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 969227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 970227825Stheravenbool 971227825Stheravenoperator< (const multiset<_Key, _Compare, _Allocator>& __x, 972227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 973227825Stheraven{ 974227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 975227825Stheraven} 976227825Stheraven 977227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 978227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 979227825Stheravenbool 980227825Stheravenoperator!=(const multiset<_Key, _Compare, _Allocator>& __x, 981227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 982227825Stheraven{ 983227825Stheraven return !(__x == __y); 984227825Stheraven} 985227825Stheraven 986227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 987227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 988227825Stheravenbool 989227825Stheravenoperator> (const multiset<_Key, _Compare, _Allocator>& __x, 990227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 991227825Stheraven{ 992227825Stheraven return __y < __x; 993227825Stheraven} 994227825Stheraven 995227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 996227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 997227825Stheravenbool 998227825Stheravenoperator>=(const multiset<_Key, _Compare, _Allocator>& __x, 999227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1000227825Stheraven{ 1001227825Stheraven return !(__x < __y); 1002227825Stheraven} 1003227825Stheraven 1004227825Stheraventemplate <class _Key, class _Compare, class _Allocator> 1005227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1006227825Stheravenbool 1007227825Stheravenoperator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1008227825Stheraven const multiset<_Key, _Compare, _Allocator>& __y) 1009{ 1010 return !(__y < __x); 1011} 1012 1013template <class _Key, class _Compare, class _Allocator> 1014inline _LIBCPP_INLINE_VISIBILITY 1015void 1016swap(multiset<_Key, _Compare, _Allocator>& __x, 1017 multiset<_Key, _Compare, _Allocator>& __y) 1018 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1019{ 1020 __x.swap(__y); 1021} 1022 1023_LIBCPP_END_NAMESPACE_STD 1024 1025#endif // _LIBCPP_SET 1026