1 // -*- C++ -*- 2 //===---------------------------- set -------------------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_SET 12 #define _LIBCPP_SET 13 14 /* 15 16 set synopsis 17 18 namespace std 19 { 20 21 template <class Key, class Compare = less<Key>, 22 class Allocator = allocator<Key>> 23 class set 24 { 25 public: 26 // types: 27 typedef Key key_type; 28 typedef key_type value_type; 29 typedef Compare key_compare; 30 typedef key_compare value_compare; 31 typedef Allocator allocator_type; 32 typedef typename allocator_type::reference reference; 33 typedef typename allocator_type::const_reference const_reference; 34 typedef typename allocator_type::size_type size_type; 35 typedef typename allocator_type::difference_type difference_type; 36 typedef typename allocator_type::pointer pointer; 37 typedef typename allocator_type::const_pointer const_pointer; 38 39 typedef implementation-defined iterator; 40 typedef implementation-defined const_iterator; 41 typedef std::reverse_iterator<iterator> reverse_iterator; 42 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 43 44 // construct/copy/destroy: 45 set() 46 noexcept( 47 is_nothrow_default_constructible<allocator_type>::value && 48 is_nothrow_default_constructible<key_compare>::value && 49 is_nothrow_copy_constructible<key_compare>::value); 50 explicit set(const value_compare& comp); 51 set(const value_compare& comp, const allocator_type& a); 52 template <class InputIterator> 53 set(InputIterator first, InputIterator last, 54 const value_compare& comp = value_compare()); 55 template <class InputIterator> 56 set(InputIterator first, InputIterator last, const value_compare& comp, 57 const allocator_type& a); 58 set(const set& s); 59 set(set&& s) 60 noexcept( 61 is_nothrow_move_constructible<allocator_type>::value && 62 is_nothrow_move_constructible<key_compare>::value); 63 explicit set(const allocator_type& a); 64 set(const set& s, const allocator_type& a); 65 set(set&& s, const allocator_type& a); 66 set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 67 set(initializer_list<value_type> il, const value_compare& comp, 68 const allocator_type& a); 69 ~set(); 70 71 set& operator=(const set& s); 72 set& operator=(set&& s) 73 noexcept( 74 allocator_type::propagate_on_container_move_assignment::value && 75 is_nothrow_move_assignable<allocator_type>::value && 76 is_nothrow_move_assignable<key_compare>::value); 77 set& operator=(initializer_list<value_type> il); 78 79 // iterators: 80 iterator begin() noexcept; 81 const_iterator begin() const noexcept; 82 iterator end() noexcept; 83 const_iterator end() const noexcept; 84 85 reverse_iterator rbegin() noexcept; 86 const_reverse_iterator rbegin() const noexcept; 87 reverse_iterator rend() noexcept; 88 const_reverse_iterator rend() const noexcept; 89 90 const_iterator cbegin() const noexcept; 91 const_iterator cend() const noexcept; 92 const_reverse_iterator crbegin() const noexcept; 93 const_reverse_iterator crend() const noexcept; 94 95 // capacity: 96 bool empty() const noexcept; 97 size_type size() const noexcept; 98 size_type max_size() const noexcept; 99 100 // modifiers: 101 template <class... Args> 102 pair<iterator, bool> emplace(Args&&... args); 103 template <class... Args> 104 iterator emplace_hint(const_iterator position, Args&&... args); 105 pair<iterator,bool> insert(const value_type& v); 106 pair<iterator,bool> insert(value_type&& v); 107 iterator insert(const_iterator position, const value_type& v); 108 iterator insert(const_iterator position, value_type&& v); 109 template <class InputIterator> 110 void insert(InputIterator first, InputIterator last); 111 void insert(initializer_list<value_type> il); 112 113 iterator erase(const_iterator position); 114 size_type erase(const key_type& k); 115 iterator erase(const_iterator first, const_iterator last); 116 void clear() noexcept; 117 118 void swap(set& s) 119 noexcept( 120 __is_nothrow_swappable<key_compare>::value && 121 (!allocator_type::propagate_on_container_swap::value || 122 __is_nothrow_swappable<allocator_type>::value)); 123 124 // observers: 125 allocator_type get_allocator() const noexcept; 126 key_compare key_comp() const; 127 value_compare value_comp() const; 128 129 // set operations: 130 iterator find(const key_type& k); 131 const_iterator find(const key_type& k) const; 132 size_type count(const key_type& k) const; 133 iterator lower_bound(const key_type& k); 134 const_iterator lower_bound(const key_type& k) const; 135 iterator upper_bound(const key_type& k); 136 const_iterator upper_bound(const key_type& k) const; 137 pair<iterator,iterator> equal_range(const key_type& k); 138 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 139 }; 140 141 template <class Key, class Compare, class Allocator> 142 bool 143 operator==(const set<Key, Compare, Allocator>& x, 144 const set<Key, Compare, Allocator>& y); 145 146 template <class Key, class Compare, class Allocator> 147 bool 148 operator< (const set<Key, Compare, Allocator>& x, 149 const set<Key, Compare, Allocator>& y); 150 151 template <class Key, class Compare, class Allocator> 152 bool 153 operator!=(const set<Key, Compare, Allocator>& x, 154 const set<Key, Compare, Allocator>& y); 155 156 template <class Key, class Compare, class Allocator> 157 bool 158 operator> (const set<Key, Compare, Allocator>& x, 159 const set<Key, Compare, Allocator>& y); 160 161 template <class Key, class Compare, class Allocator> 162 bool 163 operator>=(const set<Key, Compare, Allocator>& x, 164 const set<Key, Compare, Allocator>& y); 165 166 template <class Key, class Compare, class Allocator> 167 bool 168 operator<=(const set<Key, Compare, Allocator>& x, 169 const set<Key, Compare, Allocator>& y); 170 171 // specialized algorithms: 172 template <class Key, class Compare, class Allocator> 173 void 174 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 175 noexcept(noexcept(x.swap(y))); 176 177 template <class Key, class Compare = less<Key>, 178 class Allocator = allocator<Key>> 179 class multiset 180 { 181 public: 182 // types: 183 typedef Key key_type; 184 typedef key_type value_type; 185 typedef Compare key_compare; 186 typedef key_compare value_compare; 187 typedef Allocator allocator_type; 188 typedef typename allocator_type::reference reference; 189 typedef typename allocator_type::const_reference const_reference; 190 typedef typename allocator_type::size_type size_type; 191 typedef typename allocator_type::difference_type difference_type; 192 typedef typename allocator_type::pointer pointer; 193 typedef typename allocator_type::const_pointer const_pointer; 194 195 typedef implementation-defined iterator; 196 typedef implementation-defined const_iterator; 197 typedef std::reverse_iterator<iterator> reverse_iterator; 198 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 199 200 // construct/copy/destroy: 201 multiset() 202 noexcept( 203 is_nothrow_default_constructible<allocator_type>::value && 204 is_nothrow_default_constructible<key_compare>::value && 205 is_nothrow_copy_constructible<key_compare>::value); 206 explicit multiset(const value_compare& comp); 207 multiset(const value_compare& comp, const allocator_type& a); 208 template <class InputIterator> 209 multiset(InputIterator first, InputIterator last, 210 const value_compare& comp = value_compare()); 211 template <class InputIterator> 212 multiset(InputIterator first, InputIterator last, 213 const value_compare& comp, const allocator_type& a); 214 multiset(const multiset& s); 215 multiset(multiset&& s) 216 noexcept( 217 is_nothrow_move_constructible<allocator_type>::value && 218 is_nothrow_move_constructible<key_compare>::value); 219 explicit multiset(const allocator_type& a); 220 multiset(const multiset& s, const allocator_type& a); 221 multiset(multiset&& s, const allocator_type& a); 222 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 223 multiset(initializer_list<value_type> il, const value_compare& comp, 224 const allocator_type& a); 225 ~multiset(); 226 227 multiset& operator=(const multiset& s); 228 multiset& operator=(multiset&& s) 229 noexcept( 230 allocator_type::propagate_on_container_move_assignment::value && 231 is_nothrow_move_assignable<allocator_type>::value && 232 is_nothrow_move_assignable<key_compare>::value); 233 multiset& operator=(initializer_list<value_type> il); 234 235 // iterators: 236 iterator begin() noexcept; 237 const_iterator begin() const noexcept; 238 iterator end() noexcept; 239 const_iterator end() const noexcept; 240 241 reverse_iterator rbegin() noexcept; 242 const_reverse_iterator rbegin() const noexcept; 243 reverse_iterator rend() noexcept; 244 const_reverse_iterator rend() const noexcept; 245 246 const_iterator cbegin() const noexcept; 247 const_iterator cend() const noexcept; 248 const_reverse_iterator crbegin() const noexcept; 249 const_reverse_iterator crend() const noexcept; 250 251 // capacity: 252 bool empty() const noexcept; 253 size_type size() const noexcept; 254 size_type max_size() const noexcept; 255 256 // modifiers: 257 template <class... Args> 258 iterator emplace(Args&&... args); 259 template <class... Args> 260 iterator emplace_hint(const_iterator position, Args&&... args); 261 iterator insert(const value_type& v); 262 iterator insert(value_type&& v); 263 iterator insert(const_iterator position, const value_type& v); 264 iterator insert(const_iterator position, value_type&& v); 265 template <class InputIterator> 266 void insert(InputIterator first, InputIterator last); 267 void insert(initializer_list<value_type> il); 268 269 iterator erase(const_iterator position); 270 size_type erase(const key_type& k); 271 iterator erase(const_iterator first, const_iterator last); 272 void clear() noexcept; 273 274 void swap(multiset& s) 275 noexcept( 276 __is_nothrow_swappable<key_compare>::value && 277 (!allocator_type::propagate_on_container_swap::value || 278 __is_nothrow_swappable<allocator_type>::value)); 279 280 // observers: 281 allocator_type get_allocator() const noexcept; 282 key_compare key_comp() const; 283 value_compare value_comp() const; 284 285 // set operations: 286 iterator find(const key_type& k); 287 const_iterator find(const key_type& k) const; 288 size_type count(const key_type& k) const; 289 iterator lower_bound(const key_type& k); 290 const_iterator lower_bound(const key_type& k) const; 291 iterator upper_bound(const key_type& k); 292 const_iterator upper_bound(const key_type& k) const; 293 pair<iterator,iterator> equal_range(const key_type& k); 294 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 295 }; 296 297 template <class Key, class Compare, class Allocator> 298 bool 299 operator==(const multiset<Key, Compare, Allocator>& x, 300 const multiset<Key, Compare, Allocator>& y); 301 302 template <class Key, class Compare, class Allocator> 303 bool 304 operator< (const multiset<Key, Compare, Allocator>& x, 305 const multiset<Key, Compare, Allocator>& y); 306 307 template <class Key, class Compare, class Allocator> 308 bool 309 operator!=(const multiset<Key, Compare, Allocator>& x, 310 const multiset<Key, Compare, Allocator>& y); 311 312 template <class Key, class Compare, class Allocator> 313 bool 314 operator> (const multiset<Key, Compare, Allocator>& x, 315 const multiset<Key, Compare, Allocator>& y); 316 317 template <class Key, class Compare, class Allocator> 318 bool 319 operator>=(const multiset<Key, Compare, Allocator>& x, 320 const multiset<Key, Compare, Allocator>& y); 321 322 template <class Key, class Compare, class Allocator> 323 bool 324 operator<=(const multiset<Key, Compare, Allocator>& x, 325 const multiset<Key, Compare, Allocator>& y); 326 327 // specialized algorithms: 328 template <class Key, class Compare, class Allocator> 329 void 330 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 331 noexcept(noexcept(x.swap(y))); 332 333 } // std 334 335 */ 336 337 #include <__config> 338 #include <__tree> 339 #include <functional> 340 341 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 342 #pragma GCC system_header 343 #endif 344 345 _LIBCPP_BEGIN_NAMESPACE_STD 346 347 template <class _Key, class _Compare = less<_Key>, 348 class _Allocator = allocator<_Key> > 349 class _LIBCPP_TYPE_VIS set 350 { 351 public: 352 // types: 353 typedef _Key key_type; 354 typedef key_type value_type; 355 typedef _Compare key_compare; 356 typedef key_compare value_compare; 357 typedef _Allocator allocator_type; 358 typedef value_type& reference; 359 typedef const value_type& const_reference; 360 361 private: 362 typedef __tree<value_type, value_compare, allocator_type> __base; 363 typedef allocator_traits<allocator_type> __alloc_traits; 364 typedef typename __base::__node_holder __node_holder; 365 366 __base __tree_; 367 368 public: 369 typedef typename __base::pointer pointer; 370 typedef typename __base::const_pointer const_pointer; 371 typedef typename __base::size_type size_type; 372 typedef typename __base::difference_type difference_type; 373 typedef typename __base::const_iterator iterator; 374 typedef typename __base::const_iterator const_iterator; 375 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 376 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 377 378 _LIBCPP_INLINE_VISIBILITY 379 explicit set(const value_compare& __comp = value_compare()) 380 _NOEXCEPT_( 381 is_nothrow_default_constructible<allocator_type>::value && 382 is_nothrow_default_constructible<key_compare>::value && 383 is_nothrow_copy_constructible<key_compare>::value) 384 : __tree_(__comp) {} 385 _LIBCPP_INLINE_VISIBILITY 386 set(const value_compare& __comp, const allocator_type& __a) 387 : __tree_(__comp, __a) {} 388 template <class _InputIterator> 389 _LIBCPP_INLINE_VISIBILITY 390 set(_InputIterator __f, _InputIterator __l, 391 const value_compare& __comp = value_compare()) 392 : __tree_(__comp) 393 { 394 insert(__f, __l); 395 } 396 397 template <class _InputIterator> 398 _LIBCPP_INLINE_VISIBILITY 399 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 400 const allocator_type& __a) 401 : __tree_(__comp, __a) 402 { 403 insert(__f, __l); 404 } 405 406 _LIBCPP_INLINE_VISIBILITY 407 set(const set& __s) 408 : __tree_(__s.__tree_) 409 { 410 insert(__s.begin(), __s.end()); 411 } 412 413 _LIBCPP_INLINE_VISIBILITY 414 set& operator=(const set& __s) 415 { 416 __tree_ = __s.__tree_; 417 return *this; 418 } 419 420 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 421 _LIBCPP_INLINE_VISIBILITY 422 set(set&& __s) 423 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 424 : __tree_(_VSTD::move(__s.__tree_)) {} 425 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 426 427 _LIBCPP_INLINE_VISIBILITY 428 explicit set(const allocator_type& __a) 429 : __tree_(__a) {} 430 431 _LIBCPP_INLINE_VISIBILITY 432 set(const set& __s, const allocator_type& __a) 433 : __tree_(__s.__tree_.value_comp(), __a) 434 { 435 insert(__s.begin(), __s.end()); 436 } 437 438 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 439 set(set&& __s, const allocator_type& __a); 440 #endif 441 442 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 443 _LIBCPP_INLINE_VISIBILITY 444 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 445 : __tree_(__comp) 446 { 447 insert(__il.begin(), __il.end()); 448 } 449 450 _LIBCPP_INLINE_VISIBILITY 451 set(initializer_list<value_type> __il, const value_compare& __comp, 452 const allocator_type& __a) 453 : __tree_(__comp, __a) 454 { 455 insert(__il.begin(), __il.end()); 456 } 457 458 _LIBCPP_INLINE_VISIBILITY 459 set& operator=(initializer_list<value_type> __il) 460 { 461 __tree_.__assign_unique(__il.begin(), __il.end()); 462 return *this; 463 } 464 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 465 466 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 467 _LIBCPP_INLINE_VISIBILITY 468 set& operator=(set&& __s) 469 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 470 { 471 __tree_ = _VSTD::move(__s.__tree_); 472 return *this; 473 } 474 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 475 476 _LIBCPP_INLINE_VISIBILITY 477 iterator begin() _NOEXCEPT {return __tree_.begin();} 478 _LIBCPP_INLINE_VISIBILITY 479 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 480 _LIBCPP_INLINE_VISIBILITY 481 iterator end() _NOEXCEPT {return __tree_.end();} 482 _LIBCPP_INLINE_VISIBILITY 483 const_iterator end() const _NOEXCEPT {return __tree_.end();} 484 485 _LIBCPP_INLINE_VISIBILITY 486 reverse_iterator rbegin() _NOEXCEPT 487 {return reverse_iterator(end());} 488 _LIBCPP_INLINE_VISIBILITY 489 const_reverse_iterator rbegin() const _NOEXCEPT 490 {return const_reverse_iterator(end());} 491 _LIBCPP_INLINE_VISIBILITY 492 reverse_iterator rend() _NOEXCEPT 493 {return reverse_iterator(begin());} 494 _LIBCPP_INLINE_VISIBILITY 495 const_reverse_iterator rend() const _NOEXCEPT 496 {return const_reverse_iterator(begin());} 497 498 _LIBCPP_INLINE_VISIBILITY 499 const_iterator cbegin() const _NOEXCEPT {return begin();} 500 _LIBCPP_INLINE_VISIBILITY 501 const_iterator cend() const _NOEXCEPT {return end();} 502 _LIBCPP_INLINE_VISIBILITY 503 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 504 _LIBCPP_INLINE_VISIBILITY 505 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 506 507 _LIBCPP_INLINE_VISIBILITY 508 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 509 _LIBCPP_INLINE_VISIBILITY 510 size_type size() const _NOEXCEPT {return __tree_.size();} 511 _LIBCPP_INLINE_VISIBILITY 512 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 513 514 // modifiers: 515 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 516 template <class... _Args> 517 _LIBCPP_INLINE_VISIBILITY 518 pair<iterator, bool> emplace(_Args&&... __args) 519 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 520 template <class... _Args> 521 _LIBCPP_INLINE_VISIBILITY 522 iterator emplace_hint(const_iterator __p, _Args&&... __args) 523 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 524 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 525 _LIBCPP_INLINE_VISIBILITY 526 pair<iterator,bool> insert(const value_type& __v) 527 {return __tree_.__insert_unique(__v);} 528 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 529 _LIBCPP_INLINE_VISIBILITY 530 pair<iterator,bool> insert(value_type&& __v) 531 {return __tree_.__insert_unique(_VSTD::move(__v));} 532 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 533 _LIBCPP_INLINE_VISIBILITY 534 iterator insert(const_iterator __p, const value_type& __v) 535 {return __tree_.__insert_unique(__p, __v);} 536 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 537 _LIBCPP_INLINE_VISIBILITY 538 iterator insert(const_iterator __p, value_type&& __v) 539 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 540 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 541 template <class _InputIterator> 542 _LIBCPP_INLINE_VISIBILITY 543 void insert(_InputIterator __f, _InputIterator __l) 544 { 545 for (const_iterator __e = cend(); __f != __l; ++__f) 546 __tree_.__insert_unique(__e, *__f); 547 } 548 549 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 550 _LIBCPP_INLINE_VISIBILITY 551 void insert(initializer_list<value_type> __il) 552 {insert(__il.begin(), __il.end());} 553 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 554 555 _LIBCPP_INLINE_VISIBILITY 556 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 557 _LIBCPP_INLINE_VISIBILITY 558 size_type erase(const key_type& __k) 559 {return __tree_.__erase_unique(__k);} 560 _LIBCPP_INLINE_VISIBILITY 561 iterator erase(const_iterator __f, const_iterator __l) 562 {return __tree_.erase(__f, __l);} 563 _LIBCPP_INLINE_VISIBILITY 564 void clear() _NOEXCEPT {__tree_.clear();} 565 566 _LIBCPP_INLINE_VISIBILITY 567 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 568 {__tree_.swap(__s.__tree_);} 569 570 _LIBCPP_INLINE_VISIBILITY 571 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 572 _LIBCPP_INLINE_VISIBILITY 573 key_compare key_comp() const {return __tree_.value_comp();} 574 _LIBCPP_INLINE_VISIBILITY 575 value_compare value_comp() const {return __tree_.value_comp();} 576 577 // set operations: 578 _LIBCPP_INLINE_VISIBILITY 579 iterator find(const key_type& __k) {return __tree_.find(__k);} 580 _LIBCPP_INLINE_VISIBILITY 581 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 582 _LIBCPP_INLINE_VISIBILITY 583 size_type count(const key_type& __k) const 584 {return __tree_.__count_unique(__k);} 585 _LIBCPP_INLINE_VISIBILITY 586 iterator lower_bound(const key_type& __k) 587 {return __tree_.lower_bound(__k);} 588 _LIBCPP_INLINE_VISIBILITY 589 const_iterator lower_bound(const key_type& __k) const 590 {return __tree_.lower_bound(__k);} 591 _LIBCPP_INLINE_VISIBILITY 592 iterator upper_bound(const key_type& __k) 593 {return __tree_.upper_bound(__k);} 594 _LIBCPP_INLINE_VISIBILITY 595 const_iterator upper_bound(const key_type& __k) const 596 {return __tree_.upper_bound(__k);} 597 _LIBCPP_INLINE_VISIBILITY 598 pair<iterator,iterator> equal_range(const key_type& __k) 599 {return __tree_.__equal_range_unique(__k);} 600 _LIBCPP_INLINE_VISIBILITY 601 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 602 {return __tree_.__equal_range_unique(__k);} 603 }; 604 605 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 606 607 template <class _Key, class _Compare, class _Allocator> 608 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 609 : __tree_(_VSTD::move(__s.__tree_), __a) 610 { 611 if (__a != __s.get_allocator()) 612 { 613 const_iterator __e = cend(); 614 while (!__s.empty()) 615 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 616 } 617 } 618 619 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 620 621 template <class _Key, class _Compare, class _Allocator> 622 inline _LIBCPP_INLINE_VISIBILITY 623 bool 624 operator==(const set<_Key, _Compare, _Allocator>& __x, 625 const set<_Key, _Compare, _Allocator>& __y) 626 { 627 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 628 } 629 630 template <class _Key, class _Compare, class _Allocator> 631 inline _LIBCPP_INLINE_VISIBILITY 632 bool 633 operator< (const set<_Key, _Compare, _Allocator>& __x, 634 const set<_Key, _Compare, _Allocator>& __y) 635 { 636 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 637 } 638 639 template <class _Key, class _Compare, class _Allocator> 640 inline _LIBCPP_INLINE_VISIBILITY 641 bool 642 operator!=(const set<_Key, _Compare, _Allocator>& __x, 643 const set<_Key, _Compare, _Allocator>& __y) 644 { 645 return !(__x == __y); 646 } 647 648 template <class _Key, class _Compare, class _Allocator> 649 inline _LIBCPP_INLINE_VISIBILITY 650 bool 651 operator> (const set<_Key, _Compare, _Allocator>& __x, 652 const set<_Key, _Compare, _Allocator>& __y) 653 { 654 return __y < __x; 655 } 656 657 template <class _Key, class _Compare, class _Allocator> 658 inline _LIBCPP_INLINE_VISIBILITY 659 bool 660 operator>=(const set<_Key, _Compare, _Allocator>& __x, 661 const set<_Key, _Compare, _Allocator>& __y) 662 { 663 return !(__x < __y); 664 } 665 666 template <class _Key, class _Compare, class _Allocator> 667 inline _LIBCPP_INLINE_VISIBILITY 668 bool 669 operator<=(const set<_Key, _Compare, _Allocator>& __x, 670 const set<_Key, _Compare, _Allocator>& __y) 671 { 672 return !(__y < __x); 673 } 674 675 // specialized algorithms: 676 template <class _Key, class _Compare, class _Allocator> 677 inline _LIBCPP_INLINE_VISIBILITY 678 void 679 swap(set<_Key, _Compare, _Allocator>& __x, 680 set<_Key, _Compare, _Allocator>& __y) 681 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 682 { 683 __x.swap(__y); 684 } 685 686 template <class _Key, class _Compare = less<_Key>, 687 class _Allocator = allocator<_Key> > 688 class _LIBCPP_TYPE_VIS multiset 689 { 690 public: 691 // types: 692 typedef _Key key_type; 693 typedef key_type value_type; 694 typedef _Compare key_compare; 695 typedef key_compare value_compare; 696 typedef _Allocator allocator_type; 697 typedef value_type& reference; 698 typedef const value_type& const_reference; 699 700 private: 701 typedef __tree<value_type, value_compare, allocator_type> __base; 702 typedef allocator_traits<allocator_type> __alloc_traits; 703 typedef typename __base::__node_holder __node_holder; 704 705 __base __tree_; 706 707 public: 708 typedef typename __base::pointer pointer; 709 typedef typename __base::const_pointer const_pointer; 710 typedef typename __base::size_type size_type; 711 typedef typename __base::difference_type difference_type; 712 typedef typename __base::const_iterator iterator; 713 typedef typename __base::const_iterator const_iterator; 714 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 715 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 716 717 // construct/copy/destroy: 718 _LIBCPP_INLINE_VISIBILITY 719 explicit multiset(const value_compare& __comp = value_compare()) 720 _NOEXCEPT_( 721 is_nothrow_default_constructible<allocator_type>::value && 722 is_nothrow_default_constructible<key_compare>::value && 723 is_nothrow_copy_constructible<key_compare>::value) 724 : __tree_(__comp) {} 725 _LIBCPP_INLINE_VISIBILITY 726 multiset(const value_compare& __comp, const allocator_type& __a) 727 : __tree_(__comp, __a) {} 728 template <class _InputIterator> 729 _LIBCPP_INLINE_VISIBILITY 730 multiset(_InputIterator __f, _InputIterator __l, 731 const value_compare& __comp = value_compare()) 732 : __tree_(__comp) 733 { 734 insert(__f, __l); 735 } 736 737 template <class _InputIterator> 738 _LIBCPP_INLINE_VISIBILITY 739 multiset(_InputIterator __f, _InputIterator __l, 740 const value_compare& __comp, const allocator_type& __a) 741 : __tree_(__comp, __a) 742 { 743 insert(__f, __l); 744 } 745 746 _LIBCPP_INLINE_VISIBILITY 747 multiset(const multiset& __s) 748 : __tree_(__s.__tree_.value_comp(), 749 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 750 { 751 insert(__s.begin(), __s.end()); 752 } 753 754 _LIBCPP_INLINE_VISIBILITY 755 multiset& operator=(const multiset& __s) 756 { 757 __tree_ = __s.__tree_; 758 return *this; 759 } 760 761 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 762 _LIBCPP_INLINE_VISIBILITY 763 multiset(multiset&& __s) 764 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 765 : __tree_(_VSTD::move(__s.__tree_)) {} 766 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 767 _LIBCPP_INLINE_VISIBILITY 768 explicit multiset(const allocator_type& __a) 769 : __tree_(__a) {} 770 _LIBCPP_INLINE_VISIBILITY 771 multiset(const multiset& __s, const allocator_type& __a) 772 : __tree_(__s.__tree_.value_comp(), __a) 773 { 774 insert(__s.begin(), __s.end()); 775 } 776 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 777 multiset(multiset&& __s, const allocator_type& __a); 778 #endif 779 780 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 781 _LIBCPP_INLINE_VISIBILITY 782 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 783 : __tree_(__comp) 784 { 785 insert(__il.begin(), __il.end()); 786 } 787 788 _LIBCPP_INLINE_VISIBILITY 789 multiset(initializer_list<value_type> __il, const value_compare& __comp, 790 const allocator_type& __a) 791 : __tree_(__comp, __a) 792 { 793 insert(__il.begin(), __il.end()); 794 } 795 796 _LIBCPP_INLINE_VISIBILITY 797 multiset& operator=(initializer_list<value_type> __il) 798 { 799 __tree_.__assign_multi(__il.begin(), __il.end()); 800 return *this; 801 } 802 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 803 804 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 805 _LIBCPP_INLINE_VISIBILITY 806 multiset& operator=(multiset&& __s) 807 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 808 { 809 __tree_ = _VSTD::move(__s.__tree_); 810 return *this; 811 } 812 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 813 814 _LIBCPP_INLINE_VISIBILITY 815 iterator begin() _NOEXCEPT {return __tree_.begin();} 816 _LIBCPP_INLINE_VISIBILITY 817 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 818 _LIBCPP_INLINE_VISIBILITY 819 iterator end() _NOEXCEPT {return __tree_.end();} 820 _LIBCPP_INLINE_VISIBILITY 821 const_iterator end() const _NOEXCEPT {return __tree_.end();} 822 823 _LIBCPP_INLINE_VISIBILITY 824 reverse_iterator rbegin() _NOEXCEPT 825 {return reverse_iterator(end());} 826 _LIBCPP_INLINE_VISIBILITY 827 const_reverse_iterator rbegin() const _NOEXCEPT 828 {return const_reverse_iterator(end());} 829 _LIBCPP_INLINE_VISIBILITY 830 reverse_iterator rend() _NOEXCEPT 831 {return reverse_iterator(begin());} 832 _LIBCPP_INLINE_VISIBILITY 833 const_reverse_iterator rend() const _NOEXCEPT 834 {return const_reverse_iterator(begin());} 835 836 _LIBCPP_INLINE_VISIBILITY 837 const_iterator cbegin() const _NOEXCEPT {return begin();} 838 _LIBCPP_INLINE_VISIBILITY 839 const_iterator cend() const _NOEXCEPT {return end();} 840 _LIBCPP_INLINE_VISIBILITY 841 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 842 _LIBCPP_INLINE_VISIBILITY 843 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 844 845 _LIBCPP_INLINE_VISIBILITY 846 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 847 _LIBCPP_INLINE_VISIBILITY 848 size_type size() const _NOEXCEPT {return __tree_.size();} 849 _LIBCPP_INLINE_VISIBILITY 850 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 851 852 // modifiers: 853 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 854 template <class... _Args> 855 _LIBCPP_INLINE_VISIBILITY 856 iterator emplace(_Args&&... __args) 857 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 858 template <class... _Args> 859 _LIBCPP_INLINE_VISIBILITY 860 iterator emplace_hint(const_iterator __p, _Args&&... __args) 861 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 862 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 863 _LIBCPP_INLINE_VISIBILITY 864 iterator insert(const value_type& __v) 865 {return __tree_.__insert_multi(__v);} 866 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 867 _LIBCPP_INLINE_VISIBILITY 868 iterator insert(value_type&& __v) 869 {return __tree_.__insert_multi(_VSTD::move(__v));} 870 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 871 _LIBCPP_INLINE_VISIBILITY 872 iterator insert(const_iterator __p, const value_type& __v) 873 {return __tree_.__insert_multi(__p, __v);} 874 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 875 _LIBCPP_INLINE_VISIBILITY 876 iterator insert(const_iterator __p, value_type&& __v) 877 {return __tree_.__insert_multi(_VSTD::move(__v));} 878 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 879 template <class _InputIterator> 880 _LIBCPP_INLINE_VISIBILITY 881 void insert(_InputIterator __f, _InputIterator __l) 882 { 883 for (const_iterator __e = cend(); __f != __l; ++__f) 884 __tree_.__insert_multi(__e, *__f); 885 } 886 887 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 888 _LIBCPP_INLINE_VISIBILITY 889 void insert(initializer_list<value_type> __il) 890 {insert(__il.begin(), __il.end());} 891 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 892 893 _LIBCPP_INLINE_VISIBILITY 894 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 895 _LIBCPP_INLINE_VISIBILITY 896 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 897 _LIBCPP_INLINE_VISIBILITY 898 iterator erase(const_iterator __f, const_iterator __l) 899 {return __tree_.erase(__f, __l);} 900 _LIBCPP_INLINE_VISIBILITY 901 void clear() _NOEXCEPT {__tree_.clear();} 902 903 _LIBCPP_INLINE_VISIBILITY 904 void swap(multiset& __s) 905 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 906 {__tree_.swap(__s.__tree_);} 907 908 _LIBCPP_INLINE_VISIBILITY 909 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 910 _LIBCPP_INLINE_VISIBILITY 911 key_compare key_comp() const {return __tree_.value_comp();} 912 _LIBCPP_INLINE_VISIBILITY 913 value_compare value_comp() const {return __tree_.value_comp();} 914 915 // set operations: 916 _LIBCPP_INLINE_VISIBILITY 917 iterator find(const key_type& __k) {return __tree_.find(__k);} 918 _LIBCPP_INLINE_VISIBILITY 919 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 920 _LIBCPP_INLINE_VISIBILITY 921 size_type count(const key_type& __k) const 922 {return __tree_.__count_multi(__k);} 923 _LIBCPP_INLINE_VISIBILITY 924 iterator lower_bound(const key_type& __k) 925 {return __tree_.lower_bound(__k);} 926 _LIBCPP_INLINE_VISIBILITY 927 const_iterator lower_bound(const key_type& __k) const 928 {return __tree_.lower_bound(__k);} 929 _LIBCPP_INLINE_VISIBILITY 930 iterator upper_bound(const key_type& __k) 931 {return __tree_.upper_bound(__k);} 932 _LIBCPP_INLINE_VISIBILITY 933 const_iterator upper_bound(const key_type& __k) const 934 {return __tree_.upper_bound(__k);} 935 _LIBCPP_INLINE_VISIBILITY 936 pair<iterator,iterator> equal_range(const key_type& __k) 937 {return __tree_.__equal_range_multi(__k);} 938 _LIBCPP_INLINE_VISIBILITY 939 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 940 {return __tree_.__equal_range_multi(__k);} 941 }; 942 943 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 944 945 template <class _Key, class _Compare, class _Allocator> 946 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 947 : __tree_(_VSTD::move(__s.__tree_), __a) 948 { 949 if (__a != __s.get_allocator()) 950 { 951 const_iterator __e = cend(); 952 while (!__s.empty()) 953 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 954 } 955 } 956 957 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 958 959 template <class _Key, class _Compare, class _Allocator> 960 inline _LIBCPP_INLINE_VISIBILITY 961 bool 962 operator==(const multiset<_Key, _Compare, _Allocator>& __x, 963 const multiset<_Key, _Compare, _Allocator>& __y) 964 { 965 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 966 } 967 968 template <class _Key, class _Compare, class _Allocator> 969 inline _LIBCPP_INLINE_VISIBILITY 970 bool 971 operator< (const multiset<_Key, _Compare, _Allocator>& __x, 972 const multiset<_Key, _Compare, _Allocator>& __y) 973 { 974 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 975 } 976 977 template <class _Key, class _Compare, class _Allocator> 978 inline _LIBCPP_INLINE_VISIBILITY 979 bool 980 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 981 const multiset<_Key, _Compare, _Allocator>& __y) 982 { 983 return !(__x == __y); 984 } 985 986 template <class _Key, class _Compare, class _Allocator> 987 inline _LIBCPP_INLINE_VISIBILITY 988 bool 989 operator> (const multiset<_Key, _Compare, _Allocator>& __x, 990 const multiset<_Key, _Compare, _Allocator>& __y) 991 { 992 return __y < __x; 993 } 994 995 template <class _Key, class _Compare, class _Allocator> 996 inline _LIBCPP_INLINE_VISIBILITY 997 bool 998 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 999 const multiset<_Key, _Compare, _Allocator>& __y) 1000 { 1001 return !(__x < __y); 1002 } 1003 1004 template <class _Key, class _Compare, class _Allocator> 1005 inline _LIBCPP_INLINE_VISIBILITY 1006 bool 1007 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1008 const multiset<_Key, _Compare, _Allocator>& __y) 1009 { 1010 return !(__y < __x); 1011 } 1012 1013 template <class _Key, class _Compare, class _Allocator> 1014 inline _LIBCPP_INLINE_VISIBILITY 1015 void 1016 swap(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
