| OLD | NEW |
|---|
| (Empty) | |
| 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_compa
re()); |
| 67 set(initializer_list<value_type> il, const value_compare& comp, |
| 68 const allocator_type& a); |
| 69 template <class InputIterator> |
| 70 set(InputIterator first, InputIterator last, const allocator_type& a) |
| 71 : set(first, last, Compare(), a) {} // C++14 |
| 72 set(initializer_list<value_type> il, const allocator_type& a) |
| 73 : set(il, Compare(), a) {} // C++14 |
| 74 ~set(); |
| 75 |
| 76 set& operator=(const set& s); |
| 77 set& operator=(set&& s) |
| 78 noexcept( |
| 79 allocator_type::propagate_on_container_move_assignment::value && |
| 80 is_nothrow_move_assignable<allocator_type>::value && |
| 81 is_nothrow_move_assignable<key_compare>::value); |
| 82 set& operator=(initializer_list<value_type> il); |
| 83 |
| 84 // iterators: |
| 85 iterator begin() noexcept; |
| 86 const_iterator begin() const noexcept; |
| 87 iterator end() noexcept; |
| 88 const_iterator end() const noexcept; |
| 89 |
| 90 reverse_iterator rbegin() noexcept; |
| 91 const_reverse_iterator rbegin() const noexcept; |
| 92 reverse_iterator rend() noexcept; |
| 93 const_reverse_iterator rend() const noexcept; |
| 94 |
| 95 const_iterator cbegin() const noexcept; |
| 96 const_iterator cend() const noexcept; |
| 97 const_reverse_iterator crbegin() const noexcept; |
| 98 const_reverse_iterator crend() const noexcept; |
| 99 |
| 100 // capacity: |
| 101 bool empty() const noexcept; |
| 102 size_type size() const noexcept; |
| 103 size_type max_size() const noexcept; |
| 104 |
| 105 // modifiers: |
| 106 template <class... Args> |
| 107 pair<iterator, bool> emplace(Args&&... args); |
| 108 template <class... Args> |
| 109 iterator emplace_hint(const_iterator position, Args&&... args); |
| 110 pair<iterator,bool> insert(const value_type& v); |
| 111 pair<iterator,bool> insert(value_type&& v); |
| 112 iterator insert(const_iterator position, const value_type& v); |
| 113 iterator insert(const_iterator position, value_type&& v); |
| 114 template <class InputIterator> |
| 115 void insert(InputIterator first, InputIterator last); |
| 116 void insert(initializer_list<value_type> il); |
| 117 |
| 118 iterator erase(const_iterator position); |
| 119 size_type erase(const key_type& k); |
| 120 iterator erase(const_iterator first, const_iterator last); |
| 121 void clear() noexcept; |
| 122 |
| 123 void swap(set& s) |
| 124 noexcept( |
| 125 __is_nothrow_swappable<key_compare>::value && |
| 126 (!allocator_type::propagate_on_container_swap::value || |
| 127 __is_nothrow_swappable<allocator_type>::value)); |
| 128 |
| 129 // observers: |
| 130 allocator_type get_allocator() const noexcept; |
| 131 key_compare key_comp() const; |
| 132 value_compare value_comp() const; |
| 133 |
| 134 // set operations: |
| 135 iterator find(const key_type& k); |
| 136 const_iterator find(const key_type& k) const; |
| 137 template<typename K> |
| 138 iterator find(const K& x); |
| 139 template<typename K> |
| 140 const_iterator find(const K& x) const; // C++14 |
| 141 template<typename K> |
| 142 size_type count(const K& x) const; // C++14 |
| 143 |
| 144 size_type count(const key_type& k) const; |
| 145 iterator lower_bound(const key_type& k); |
| 146 const_iterator lower_bound(const key_type& k) const; |
| 147 template<typename K> |
| 148 iterator lower_bound(const K& x); // C++14 |
| 149 template<typename K> |
| 150 const_iterator lower_bound(const K& x) const; // C++14 |
| 151 |
| 152 iterator upper_bound(const key_type& k); |
| 153 const_iterator upper_bound(const key_type& k) const; |
| 154 template<typename K> |
| 155 iterator upper_bound(const K& x); // C++14 |
| 156 template<typename K> |
| 157 const_iterator upper_bound(const K& x) const; // C++14 |
| 158 pair<iterator,iterator> equal_range(const key_type& k); |
| 159 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; |
| 160 template<typename K> |
| 161 pair<iterator,iterator> equal_range(const K& x); // C
++14 |
| 162 template<typename K> |
| 163 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C
++14 |
| 164 }; |
| 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 template <class Key, class Compare, class Allocator> |
| 172 bool |
| 173 operator< (const set<Key, Compare, Allocator>& x, |
| 174 const set<Key, Compare, Allocator>& y); |
| 175 |
| 176 template <class Key, class Compare, class Allocator> |
| 177 bool |
| 178 operator!=(const set<Key, Compare, Allocator>& x, |
| 179 const set<Key, Compare, Allocator>& y); |
| 180 |
| 181 template <class Key, class Compare, class Allocator> |
| 182 bool |
| 183 operator> (const set<Key, Compare, Allocator>& x, |
| 184 const set<Key, Compare, Allocator>& y); |
| 185 |
| 186 template <class Key, class Compare, class Allocator> |
| 187 bool |
| 188 operator>=(const set<Key, Compare, Allocator>& x, |
| 189 const set<Key, Compare, Allocator>& y); |
| 190 |
| 191 template <class Key, class Compare, class Allocator> |
| 192 bool |
| 193 operator<=(const set<Key, Compare, Allocator>& x, |
| 194 const set<Key, Compare, Allocator>& y); |
| 195 |
| 196 // specialized algorithms: |
| 197 template <class Key, class Compare, class Allocator> |
| 198 void |
| 199 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) |
| 200 noexcept(noexcept(x.swap(y))); |
| 201 |
| 202 template <class Key, class Compare = less<Key>, |
| 203 class Allocator = allocator<Key>> |
| 204 class multiset |
| 205 { |
| 206 public: |
| 207 // types: |
| 208 typedef Key key_type; |
| 209 typedef key_type value_type; |
| 210 typedef Compare key_compare; |
| 211 typedef key_compare value_compare; |
| 212 typedef Allocator allocator_type; |
| 213 typedef typename allocator_type::reference reference; |
| 214 typedef typename allocator_type::const_reference const_reference; |
| 215 typedef typename allocator_type::size_type size_type; |
| 216 typedef typename allocator_type::difference_type difference_type; |
| 217 typedef typename allocator_type::pointer pointer; |
| 218 typedef typename allocator_type::const_pointer const_pointer; |
| 219 |
| 220 typedef implementation-defined iterator; |
| 221 typedef implementation-defined const_iterator; |
| 222 typedef std::reverse_iterator<iterator> reverse_iterator; |
| 223 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
| 224 |
| 225 // construct/copy/destroy: |
| 226 multiset() |
| 227 noexcept( |
| 228 is_nothrow_default_constructible<allocator_type>::value && |
| 229 is_nothrow_default_constructible<key_compare>::value && |
| 230 is_nothrow_copy_constructible<key_compare>::value); |
| 231 explicit multiset(const value_compare& comp); |
| 232 multiset(const value_compare& comp, const allocator_type& a); |
| 233 template <class InputIterator> |
| 234 multiset(InputIterator first, InputIterator last, |
| 235 const value_compare& comp = value_compare()); |
| 236 template <class InputIterator> |
| 237 multiset(InputIterator first, InputIterator last, |
| 238 const value_compare& comp, const allocator_type& a); |
| 239 multiset(const multiset& s); |
| 240 multiset(multiset&& s) |
| 241 noexcept( |
| 242 is_nothrow_move_constructible<allocator_type>::value && |
| 243 is_nothrow_move_constructible<key_compare>::value); |
| 244 explicit multiset(const allocator_type& a); |
| 245 multiset(const multiset& s, const allocator_type& a); |
| 246 multiset(multiset&& s, const allocator_type& a); |
| 247 multiset(initializer_list<value_type> il, const value_compare& comp = value_
compare()); |
| 248 multiset(initializer_list<value_type> il, const value_compare& comp, |
| 249 const allocator_type& a); |
| 250 template <class InputIterator> |
| 251 multiset(InputIterator first, InputIterator last, const allocator_type&
a) |
| 252 : set(first, last, Compare(), a) {} // C++14 |
| 253 multiset(initializer_list<value_type> il, const allocator_type& a) |
| 254 : set(il, Compare(), a) {} // C++14 |
| 255 ~multiset(); |
| 256 |
| 257 multiset& operator=(const multiset& s); |
| 258 multiset& operator=(multiset&& s) |
| 259 noexcept( |
| 260 allocator_type::propagate_on_container_move_assignment::value && |
| 261 is_nothrow_move_assignable<allocator_type>::value && |
| 262 is_nothrow_move_assignable<key_compare>::value); |
| 263 multiset& operator=(initializer_list<value_type> il); |
| 264 |
| 265 // iterators: |
| 266 iterator begin() noexcept; |
| 267 const_iterator begin() const noexcept; |
| 268 iterator end() noexcept; |
| 269 const_iterator end() const noexcept; |
| 270 |
| 271 reverse_iterator rbegin() noexcept; |
| 272 const_reverse_iterator rbegin() const noexcept; |
| 273 reverse_iterator rend() noexcept; |
| 274 const_reverse_iterator rend() const noexcept; |
| 275 |
| 276 const_iterator cbegin() const noexcept; |
| 277 const_iterator cend() const noexcept; |
| 278 const_reverse_iterator crbegin() const noexcept; |
| 279 const_reverse_iterator crend() const noexcept; |
| 280 |
| 281 // capacity: |
| 282 bool empty() const noexcept; |
| 283 size_type size() const noexcept; |
| 284 size_type max_size() const noexcept; |
| 285 |
| 286 // modifiers: |
| 287 template <class... Args> |
| 288 iterator emplace(Args&&... args); |
| 289 template <class... Args> |
| 290 iterator emplace_hint(const_iterator position, Args&&... args); |
| 291 iterator insert(const value_type& v); |
| 292 iterator insert(value_type&& v); |
| 293 iterator insert(const_iterator position, const value_type& v); |
| 294 iterator insert(const_iterator position, value_type&& v); |
| 295 template <class InputIterator> |
| 296 void insert(InputIterator first, InputIterator last); |
| 297 void insert(initializer_list<value_type> il); |
| 298 |
| 299 iterator erase(const_iterator position); |
| 300 size_type erase(const key_type& k); |
| 301 iterator erase(const_iterator first, const_iterator last); |
| 302 void clear() noexcept; |
| 303 |
| 304 void swap(multiset& s) |
| 305 noexcept( |
| 306 __is_nothrow_swappable<key_compare>::value && |
| 307 (!allocator_type::propagate_on_container_swap::value || |
| 308 __is_nothrow_swappable<allocator_type>::value)); |
| 309 |
| 310 // observers: |
| 311 allocator_type get_allocator() const noexcept; |
| 312 key_compare key_comp() const; |
| 313 value_compare value_comp() const; |
| 314 |
| 315 // set operations: |
| 316 iterator find(const key_type& k); |
| 317 const_iterator find(const key_type& k) const; |
| 318 template<typename K> |
| 319 iterator find(const K& x); |
| 320 template<typename K> |
| 321 const_iterator find(const K& x) const; // C++14 |
| 322 |
| 323 size_type count(const key_type& k) const; |
| 324 iterator lower_bound(const key_type& k); |
| 325 const_iterator lower_bound(const key_type& k) const; |
| 326 template<typename K> |
| 327 iterator lower_bound(const K& x); // C++14 |
| 328 template<typename K> |
| 329 const_iterator lower_bound(const K& x) const; // C++14 |
| 330 |
| 331 iterator upper_bound(const key_type& k); |
| 332 const_iterator upper_bound(const key_type& k) const; |
| 333 template<typename K> |
| 334 iterator upper_bound(const K& x); // C++14 |
| 335 template<typename K> |
| 336 const_iterator upper_bound(const K& x) const; // C++14 |
| 337 |
| 338 pair<iterator,iterator> equal_range(const key_type& k); |
| 339 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; |
| 340 template<typename K> |
| 341 pair<iterator,iterator> equal_range(const K& x); // C
++14 |
| 342 template<typename K> |
| 343 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C
++14 |
| 344 }; |
| 345 |
| 346 template <class Key, class Compare, class Allocator> |
| 347 bool |
| 348 operator==(const multiset<Key, Compare, Allocator>& x, |
| 349 const multiset<Key, Compare, Allocator>& y); |
| 350 |
| 351 template <class Key, class Compare, class Allocator> |
| 352 bool |
| 353 operator< (const multiset<Key, Compare, Allocator>& x, |
| 354 const multiset<Key, Compare, Allocator>& y); |
| 355 |
| 356 template <class Key, class Compare, class Allocator> |
| 357 bool |
| 358 operator!=(const multiset<Key, Compare, Allocator>& x, |
| 359 const multiset<Key, Compare, Allocator>& y); |
| 360 |
| 361 template <class Key, class Compare, class Allocator> |
| 362 bool |
| 363 operator> (const multiset<Key, Compare, Allocator>& x, |
| 364 const multiset<Key, Compare, Allocator>& y); |
| 365 |
| 366 template <class Key, class Compare, class Allocator> |
| 367 bool |
| 368 operator>=(const multiset<Key, Compare, Allocator>& x, |
| 369 const multiset<Key, Compare, Allocator>& y); |
| 370 |
| 371 template <class Key, class Compare, class Allocator> |
| 372 bool |
| 373 operator<=(const multiset<Key, Compare, Allocator>& x, |
| 374 const multiset<Key, Compare, Allocator>& y); |
| 375 |
| 376 // specialized algorithms: |
| 377 template <class Key, class Compare, class Allocator> |
| 378 void |
| 379 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) |
| 380 noexcept(noexcept(x.swap(y))); |
| 381 |
| 382 } // std |
| 383 |
| 384 */ |
| 385 |
| 386 #include <__config> |
| 387 #include <__tree> |
| 388 #include <functional> |
| 389 |
| 390 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 391 #pragma GCC system_header |
| 392 #endif |
| 393 |
| 394 _LIBCPP_BEGIN_NAMESPACE_STD |
| 395 |
| 396 template <class _Key, class _Compare = less<_Key>, |
| 397 class _Allocator = allocator<_Key> > |
| 398 class _LIBCPP_TYPE_VIS_ONLY set |
| 399 { |
| 400 public: |
| 401 // types: |
| 402 typedef _Key key_type; |
| 403 typedef key_type value_type; |
| 404 typedef _Compare key_compare; |
| 405 typedef key_compare value_compare; |
| 406 typedef _Allocator allocator_type; |
| 407 typedef value_type& reference; |
| 408 typedef const value_type& const_reference; |
| 409 |
| 410 private: |
| 411 typedef __tree<value_type, value_compare, allocator_type> __base; |
| 412 typedef allocator_traits<allocator_type> __alloc_traits; |
| 413 typedef typename __base::__node_holder __node_holder; |
| 414 |
| 415 __base __tree_; |
| 416 |
| 417 public: |
| 418 typedef typename __base::pointer pointer; |
| 419 typedef typename __base::const_pointer const_pointer; |
| 420 typedef typename __base::size_type size_type; |
| 421 typedef typename __base::difference_type difference_type; |
| 422 typedef typename __base::const_iterator iterator; |
| 423 typedef typename __base::const_iterator const_iterator; |
| 424 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
| 425 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; |
| 426 |
| 427 _LIBCPP_INLINE_VISIBILITY |
| 428 explicit set(const value_compare& __comp = value_compare()) |
| 429 _NOEXCEPT_( |
| 430 is_nothrow_default_constructible<allocator_type>::value && |
| 431 is_nothrow_default_constructible<key_compare>::value && |
| 432 is_nothrow_copy_constructible<key_compare>::value) |
| 433 : __tree_(__comp) {} |
| 434 _LIBCPP_INLINE_VISIBILITY |
| 435 set(const value_compare& __comp, const allocator_type& __a) |
| 436 : __tree_(__comp, __a) {} |
| 437 template <class _InputIterator> |
| 438 _LIBCPP_INLINE_VISIBILITY |
| 439 set(_InputIterator __f, _InputIterator __l, |
| 440 const value_compare& __comp = value_compare()) |
| 441 : __tree_(__comp) |
| 442 { |
| 443 insert(__f, __l); |
| 444 } |
| 445 |
| 446 template <class _InputIterator> |
| 447 _LIBCPP_INLINE_VISIBILITY |
| 448 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, |
| 449 const allocator_type& __a) |
| 450 : __tree_(__comp, __a) |
| 451 { |
| 452 insert(__f, __l); |
| 453 } |
| 454 |
| 455 #if _LIBCPP_STD_VER > 11 |
| 456 template <class _InputIterator> |
| 457 _LIBCPP_INLINE_VISIBILITY |
| 458 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) |
| 459 : set(__f, __l, key_compare(), __a) {} |
| 460 #endif |
| 461 |
| 462 _LIBCPP_INLINE_VISIBILITY |
| 463 set(const set& __s) |
| 464 : __tree_(__s.__tree_) |
| 465 { |
| 466 insert(__s.begin(), __s.end()); |
| 467 } |
| 468 |
| 469 _LIBCPP_INLINE_VISIBILITY |
| 470 set& operator=(const set& __s) |
| 471 { |
| 472 __tree_ = __s.__tree_; |
| 473 return *this; |
| 474 } |
| 475 |
| 476 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 477 _LIBCPP_INLINE_VISIBILITY |
| 478 set(set&& __s) |
| 479 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) |
| 480 : __tree_(_VSTD::move(__s.__tree_)) {} |
| 481 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 482 |
| 483 _LIBCPP_INLINE_VISIBILITY |
| 484 explicit set(const allocator_type& __a) |
| 485 : __tree_(__a) {} |
| 486 |
| 487 _LIBCPP_INLINE_VISIBILITY |
| 488 set(const set& __s, const allocator_type& __a) |
| 489 : __tree_(__s.__tree_.value_comp(), __a) |
| 490 { |
| 491 insert(__s.begin(), __s.end()); |
| 492 } |
| 493 |
| 494 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 495 set(set&& __s, const allocator_type& __a); |
| 496 #endif |
| 497 |
| 498 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 499 _LIBCPP_INLINE_VISIBILITY |
| 500 set(initializer_list<value_type> __il, const value_compare& __comp = value_c
ompare()) |
| 501 : __tree_(__comp) |
| 502 { |
| 503 insert(__il.begin(), __il.end()); |
| 504 } |
| 505 |
| 506 _LIBCPP_INLINE_VISIBILITY |
| 507 set(initializer_list<value_type> __il, const value_compare& __comp, |
| 508 const allocator_type& __a) |
| 509 : __tree_(__comp, __a) |
| 510 { |
| 511 insert(__il.begin(), __il.end()); |
| 512 } |
| 513 |
| 514 #if _LIBCPP_STD_VER > 11 |
| 515 _LIBCPP_INLINE_VISIBILITY |
| 516 set(initializer_list<value_type> __il, const allocator_type& __a) |
| 517 : set(__il, key_compare(), __a) {} |
| 518 #endif |
| 519 |
| 520 _LIBCPP_INLINE_VISIBILITY |
| 521 set& operator=(initializer_list<value_type> __il) |
| 522 { |
| 523 __tree_.__assign_unique(__il.begin(), __il.end()); |
| 524 return *this; |
| 525 } |
| 526 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 527 |
| 528 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 529 _LIBCPP_INLINE_VISIBILITY |
| 530 set& operator=(set&& __s) |
| 531 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) |
| 532 { |
| 533 __tree_ = _VSTD::move(__s.__tree_); |
| 534 return *this; |
| 535 } |
| 536 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 537 |
| 538 _LIBCPP_INLINE_VISIBILITY |
| 539 iterator begin() _NOEXCEPT {return __tree_.begin();} |
| 540 _LIBCPP_INLINE_VISIBILITY |
| 541 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} |
| 542 _LIBCPP_INLINE_VISIBILITY |
| 543 iterator end() _NOEXCEPT {return __tree_.end();} |
| 544 _LIBCPP_INLINE_VISIBILITY |
| 545 const_iterator end() const _NOEXCEPT {return __tree_.end();} |
| 546 |
| 547 _LIBCPP_INLINE_VISIBILITY |
| 548 reverse_iterator rbegin() _NOEXCEPT |
| 549 {return reverse_iterator(end());} |
| 550 _LIBCPP_INLINE_VISIBILITY |
| 551 const_reverse_iterator rbegin() const _NOEXCEPT |
| 552 {return const_reverse_iterator(end());} |
| 553 _LIBCPP_INLINE_VISIBILITY |
| 554 reverse_iterator rend() _NOEXCEPT |
| 555 {return reverse_iterator(begin());} |
| 556 _LIBCPP_INLINE_VISIBILITY |
| 557 const_reverse_iterator rend() const _NOEXCEPT |
| 558 {return const_reverse_iterator(begin());} |
| 559 |
| 560 _LIBCPP_INLINE_VISIBILITY |
| 561 const_iterator cbegin() const _NOEXCEPT {return begin();} |
| 562 _LIBCPP_INLINE_VISIBILITY |
| 563 const_iterator cend() const _NOEXCEPT {return end();} |
| 564 _LIBCPP_INLINE_VISIBILITY |
| 565 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} |
| 566 _LIBCPP_INLINE_VISIBILITY |
| 567 const_reverse_iterator crend() const _NOEXCEPT {return rend();} |
| 568 |
| 569 _LIBCPP_INLINE_VISIBILITY |
| 570 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} |
| 571 _LIBCPP_INLINE_VISIBILITY |
| 572 size_type size() const _NOEXCEPT {return __tree_.size();} |
| 573 _LIBCPP_INLINE_VISIBILITY |
| 574 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} |
| 575 |
| 576 // modifiers: |
| 577 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIAD
ICS) |
| 578 template <class... _Args> |
| 579 _LIBCPP_INLINE_VISIBILITY |
| 580 pair<iterator, bool> emplace(_Args&&... __args) |
| 581 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} |
| 582 template <class... _Args> |
| 583 _LIBCPP_INLINE_VISIBILITY |
| 584 iterator emplace_hint(const_iterator __p, _Args&&... __args) |
| 585 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__a
rgs)...);} |
| 586 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO
_VARIADICS) |
| 587 _LIBCPP_INLINE_VISIBILITY |
| 588 pair<iterator,bool> insert(const value_type& __v) |
| 589 {return __tree_.__insert_unique(__v);} |
| 590 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 591 _LIBCPP_INLINE_VISIBILITY |
| 592 pair<iterator,bool> insert(value_type&& __v) |
| 593 {return __tree_.__insert_unique(_VSTD::move(__v));} |
| 594 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 595 _LIBCPP_INLINE_VISIBILITY |
| 596 iterator insert(const_iterator __p, const value_type& __v) |
| 597 {return __tree_.__insert_unique(__p, __v);} |
| 598 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 599 _LIBCPP_INLINE_VISIBILITY |
| 600 iterator insert(const_iterator __p, value_type&& __v) |
| 601 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} |
| 602 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 603 template <class _InputIterator> |
| 604 _LIBCPP_INLINE_VISIBILITY |
| 605 void insert(_InputIterator __f, _InputIterator __l) |
| 606 { |
| 607 for (const_iterator __e = cend(); __f != __l; ++__f) |
| 608 __tree_.__insert_unique(__e, *__f); |
| 609 } |
| 610 |
| 611 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 612 _LIBCPP_INLINE_VISIBILITY |
| 613 void insert(initializer_list<value_type> __il) |
| 614 {insert(__il.begin(), __il.end());} |
| 615 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 616 |
| 617 _LIBCPP_INLINE_VISIBILITY |
| 618 iterator erase(const_iterator __p) {return __tree_.erase(__p);} |
| 619 _LIBCPP_INLINE_VISIBILITY |
| 620 size_type erase(const key_type& __k) |
| 621 {return __tree_.__erase_unique(__k);} |
| 622 _LIBCPP_INLINE_VISIBILITY |
| 623 iterator erase(const_iterator __f, const_iterator __l) |
| 624 {return __tree_.erase(__f, __l);} |
| 625 _LIBCPP_INLINE_VISIBILITY |
| 626 void clear() _NOEXCEPT {__tree_.clear();} |
| 627 |
| 628 _LIBCPP_INLINE_VISIBILITY |
| 629 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) |
| 630 {__tree_.swap(__s.__tree_);} |
| 631 |
| 632 _LIBCPP_INLINE_VISIBILITY |
| 633 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} |
| 634 _LIBCPP_INLINE_VISIBILITY |
| 635 key_compare key_comp() const {return __tree_.value_comp();} |
| 636 _LIBCPP_INLINE_VISIBILITY |
| 637 value_compare value_comp() const {return __tree_.value_comp();} |
| 638 |
| 639 // set operations: |
| 640 _LIBCPP_INLINE_VISIBILITY |
| 641 iterator find(const key_type& __k) {return __tree_.find(__k);} |
| 642 _LIBCPP_INLINE_VISIBILITY |
| 643 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} |
| 644 #if _LIBCPP_STD_VER > 11 |
| 645 template <typename _K2> |
| 646 _LIBCPP_INLINE_VISIBILITY |
| 647 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 648 find(const _K2& __k) {return __tree_.find(__k);} |
| 649 template <typename _K2> |
| 650 _LIBCPP_INLINE_VISIBILITY |
| 651 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 652 find(const _K2& __k) const {return __tree_.find(__k);} |
| 653 #endif |
| 654 |
| 655 _LIBCPP_INLINE_VISIBILITY |
| 656 size_type count(const key_type& __k) const |
| 657 {return __tree_.__count_unique(__k);} |
| 658 _LIBCPP_INLINE_VISIBILITY |
| 659 iterator lower_bound(const key_type& __k) |
| 660 {return __tree_.lower_bound(__k);} |
| 661 _LIBCPP_INLINE_VISIBILITY |
| 662 const_iterator lower_bound(const key_type& __k) const |
| 663 {return __tree_.lower_bound(__k);} |
| 664 #if _LIBCPP_STD_VER > 11 |
| 665 template <typename _K2> |
| 666 _LIBCPP_INLINE_VISIBILITY |
| 667 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 668 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} |
| 669 |
| 670 template <typename _K2> |
| 671 _LIBCPP_INLINE_VISIBILITY |
| 672 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 673 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} |
| 674 #endif |
| 675 |
| 676 _LIBCPP_INLINE_VISIBILITY |
| 677 iterator upper_bound(const key_type& __k) |
| 678 {return __tree_.upper_bound(__k);} |
| 679 _LIBCPP_INLINE_VISIBILITY |
| 680 const_iterator upper_bound(const key_type& __k) const |
| 681 {return __tree_.upper_bound(__k);} |
| 682 #if _LIBCPP_STD_VER > 11 |
| 683 template <typename _K2> |
| 684 _LIBCPP_INLINE_VISIBILITY |
| 685 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type |
| 686 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} |
| 687 template <typename _K2> |
| 688 _LIBCPP_INLINE_VISIBILITY |
| 689 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::t
ype |
| 690 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} |
| 691 #endif |
| 692 |
| 693 _LIBCPP_INLINE_VISIBILITY |
| 694 pair<iterator,iterator> equal_range(const key_type& __k) |
| 695 {return __tree_.__equal_range_unique(__k);} |
| 696 _LIBCPP_INLINE_VISIBILITY |
| 697 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const |
| 698 {return __tree_.__equal_range_unique(__k);} |
| 699 #if _LIBCPP_STD_VER > 11 |
| 700 template <typename _K2> |
| 701 _LIBCPP_INLINE_VISIBILITY |
| 702 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iter
ator>>::type |
| 703 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);
} |
| 704 template <typename _K2> |
| 705 _LIBCPP_INLINE_VISIBILITY |
| 706 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterato
r,const_iterator>>::type |
| 707 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);
} |
| 708 #endif |
| 709 }; |
| 710 |
| 711 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 712 |
| 713 template <class _Key, class _Compare, class _Allocator> |
| 714 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) |
| 715 : __tree_(_VSTD::move(__s.__tree_), __a) |
| 716 { |
| 717 if (__a != __s.get_allocator()) |
| 718 { |
| 719 const_iterator __e = cend(); |
| 720 while (!__s.empty()) |
| 721 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); |
| 722 } |
| 723 } |
| 724 |
| 725 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 726 |
| 727 template <class _Key, class _Compare, class _Allocator> |
| 728 inline _LIBCPP_INLINE_VISIBILITY |
| 729 bool |
| 730 operator==(const set<_Key, _Compare, _Allocator>& __x, |
| 731 const set<_Key, _Compare, _Allocator>& __y) |
| 732 { |
| 733 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.
begin()); |
| 734 } |
| 735 |
| 736 template <class _Key, class _Compare, class _Allocator> |
| 737 inline _LIBCPP_INLINE_VISIBILITY |
| 738 bool |
| 739 operator< (const set<_Key, _Compare, _Allocator>& __x, |
| 740 const set<_Key, _Compare, _Allocator>& __y) |
| 741 { |
| 742 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), _
_y.end()); |
| 743 } |
| 744 |
| 745 template <class _Key, class _Compare, class _Allocator> |
| 746 inline _LIBCPP_INLINE_VISIBILITY |
| 747 bool |
| 748 operator!=(const set<_Key, _Compare, _Allocator>& __x, |
| 749 const set<_Key, _Compare, _Allocator>& __y) |
| 750 { |
| 751 return !(__x == __y); |
| 752 } |
| 753 |
| 754 template <class _Key, class _Compare, class _Allocator> |
| 755 inline _LIBCPP_INLINE_VISIBILITY |
| 756 bool |
| 757 operator> (const set<_Key, _Compare, _Allocator>& __x, |
| 758 const set<_Key, _Compare, _Allocator>& __y) |
| 759 { |
| 760 return __y < __x; |
| 761 } |
| 762 |
| 763 template <class _Key, class _Compare, class _Allocator> |
| 764 inline _LIBCPP_INLINE_VISIBILITY |
| 765 bool |
| 766 operator>=(const set<_Key, _Compare, _Allocator>& __x, |
| 767 const set<_Key, _Compare, _Allocator>& __y) |
| 768 { |
| 769 return !(__x < __y); |
| 770 } |
| 771 |
| 772 template <class _Key, class _Compare, class _Allocator> |
| 773 inline _LIBCPP_INLINE_VISIBILITY |
| 774 bool |
| 775 operator<=(const set<_Key, _Compare, _Allocator>& __x, |
| 776 const set<_Key, _Compare, _Allocator>& __y) |
| 777 { |
| 778 return !(__y < __x); |
| 779 } |
| 780 |
| 781 // specialized algorithms: |
| 782 template <class _Key, class _Compare, class _Allocator> |
| 783 inline _LIBCPP_INLINE_VISIBILITY |
| 784 void |
| 785 swap(set<_Key, _Compare, _Allocator>& __x, |
| 786 set<_Key, _Compare, _Allocator>& __y) |
| 787 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
| 788 { |
| 789 __x.swap(__y); |
| 790 } |
| 791 |
| 792 template <class _Key, class _Compare = less<_Key>, |
| 793 class _Allocator = allocator<_Key> > |
| 794 class _LIBCPP_TYPE_VIS_ONLY multiset |
| 795 { |
| 796 public: |
| 797 // types: |
| 798 typedef _Key key_type; |
| 799 typedef key_type value_type; |
| 800 typedef _Compare key_compare; |
| 801 typedef key_compare value_compare; |
| 802 typedef _Allocator allocator_type; |
| 803 typedef value_type& reference; |
| 804 typedef const value_type& const_reference; |
| 805 |
| 806 private: |
| 807 typedef __tree<value_type, value_compare, allocator_type> __base; |
| 808 typedef allocator_traits<allocator_type> __alloc_traits; |
| 809 typedef typename __base::__node_holder __node_holder; |
| 810 |
| 811 __base __tree_; |
| 812 |
| 813 public: |
| 814 typedef typename __base::pointer pointer; |
| 815 typedef typename __base::const_pointer const_pointer; |
| 816 typedef typename __base::size_type size_type; |
| 817 typedef typename __base::difference_type difference_type; |
| 818 typedef typename __base::const_iterator iterator; |
| 819 typedef typename __base::const_iterator const_iterator; |
| 820 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
| 821 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; |
| 822 |
| 823 // construct/copy/destroy: |
| 824 _LIBCPP_INLINE_VISIBILITY |
| 825 explicit multiset(const value_compare& __comp = value_compare()) |
| 826 _NOEXCEPT_( |
| 827 is_nothrow_default_constructible<allocator_type>::value && |
| 828 is_nothrow_default_constructible<key_compare>::value && |
| 829 is_nothrow_copy_constructible<key_compare>::value) |
| 830 : __tree_(__comp) {} |
| 831 _LIBCPP_INLINE_VISIBILITY |
| 832 multiset(const value_compare& __comp, const allocator_type& __a) |
| 833 : __tree_(__comp, __a) {} |
| 834 template <class _InputIterator> |
| 835 _LIBCPP_INLINE_VISIBILITY |
| 836 multiset(_InputIterator __f, _InputIterator __l, |
| 837 const value_compare& __comp = value_compare()) |
| 838 : __tree_(__comp) |
| 839 { |
| 840 insert(__f, __l); |
| 841 } |
| 842 |
| 843 #if _LIBCPP_STD_VER > 11 |
| 844 template <class _InputIterator> |
| 845 _LIBCPP_INLINE_VISIBILITY |
| 846 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& _
_a) |
| 847 : multiset(__f, __l, key_compare(), __a) {} |
| 848 #endif |
| 849 |
| 850 template <class _InputIterator> |
| 851 _LIBCPP_INLINE_VISIBILITY |
| 852 multiset(_InputIterator __f, _InputIterator __l, |
| 853 const value_compare& __comp, const allocator_type& __a) |
| 854 : __tree_(__comp, __a) |
| 855 { |
| 856 insert(__f, __l); |
| 857 } |
| 858 |
| 859 _LIBCPP_INLINE_VISIBILITY |
| 860 multiset(const multiset& __s) |
| 861 : __tree_(__s.__tree_.value_comp(), |
| 862 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__al
loc())) |
| 863 { |
| 864 insert(__s.begin(), __s.end()); |
| 865 } |
| 866 |
| 867 _LIBCPP_INLINE_VISIBILITY |
| 868 multiset& operator=(const multiset& __s) |
| 869 { |
| 870 __tree_ = __s.__tree_; |
| 871 return *this; |
| 872 } |
| 873 |
| 874 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 875 _LIBCPP_INLINE_VISIBILITY |
| 876 multiset(multiset&& __s) |
| 877 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) |
| 878 : __tree_(_VSTD::move(__s.__tree_)) {} |
| 879 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 880 _LIBCPP_INLINE_VISIBILITY |
| 881 explicit multiset(const allocator_type& __a) |
| 882 : __tree_(__a) {} |
| 883 _LIBCPP_INLINE_VISIBILITY |
| 884 multiset(const multiset& __s, const allocator_type& __a) |
| 885 : __tree_(__s.__tree_.value_comp(), __a) |
| 886 { |
| 887 insert(__s.begin(), __s.end()); |
| 888 } |
| 889 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 890 multiset(multiset&& __s, const allocator_type& __a); |
| 891 #endif |
| 892 |
| 893 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 894 _LIBCPP_INLINE_VISIBILITY |
| 895 multiset(initializer_list<value_type> __il, const value_compare& __comp = va
lue_compare()) |
| 896 : __tree_(__comp) |
| 897 { |
| 898 insert(__il.begin(), __il.end()); |
| 899 } |
| 900 |
| 901 _LIBCPP_INLINE_VISIBILITY |
| 902 multiset(initializer_list<value_type> __il, const value_compare& __comp, |
| 903 const allocator_type& __a) |
| 904 : __tree_(__comp, __a) |
| 905 { |
| 906 insert(__il.begin(), __il.end()); |
| 907 } |
| 908 |
| 909 #if _LIBCPP_STD_VER > 11 |
| 910 _LIBCPP_INLINE_VISIBILITY |
| 911 multiset(initializer_list<value_type> __il, const allocator_type& __a) |
| 912 : multiset(__il, key_compare(), __a) {} |
| 913 #endif |
| 914 |
| 915 _LIBCPP_INLINE_VISIBILITY |
| 916 multiset& operator=(initializer_list<value_type> __il) |
| 917 { |
| 918 __tree_.__assign_multi(__il.begin(), __il.end()); |
| 919 return *this; |
| 920 } |
| 921 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 922 |
| 923 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 924 _LIBCPP_INLINE_VISIBILITY |
| 925 multiset& operator=(multiset&& __s) |
| 926 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) |
| 927 { |
| 928 __tree_ = _VSTD::move(__s.__tree_); |
| 929 return *this; |
| 930 } |
| 931 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 932 |
| 933 _LIBCPP_INLINE_VISIBILITY |
| 934 iterator begin() _NOEXCEPT {return __tree_.begin();} |
| 935 _LIBCPP_INLINE_VISIBILITY |
| 936 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} |
| 937 _LIBCPP_INLINE_VISIBILITY |
| 938 iterator end() _NOEXCEPT {return __tree_.end();} |
| 939 _LIBCPP_INLINE_VISIBILITY |
| 940 const_iterator end() const _NOEXCEPT {return __tree_.end();} |
| 941 |
| 942 _LIBCPP_INLINE_VISIBILITY |
| 943 reverse_iterator rbegin() _NOEXCEPT |
| 944 {return reverse_iterator(end());} |
| 945 _LIBCPP_INLINE_VISIBILITY |
| 946 const_reverse_iterator rbegin() const _NOEXCEPT |
| 947 {return const_reverse_iterator(end());} |
| 948 _LIBCPP_INLINE_VISIBILITY |
| 949 reverse_iterator rend() _NOEXCEPT |
| 950 {return reverse_iterator(begin());} |
| 951 _LIBCPP_INLINE_VISIBILITY |
| 952 const_reverse_iterator rend() const _NOEXCEPT |
| 953 {return const_reverse_iterator(begin());} |
| 954 |
| 955 _LIBCPP_INLINE_VISIBILITY |
| 956 const_iterator cbegin() const _NOEXCEPT {return begin();} |
| 957 _LIBCPP_INLINE_VISIBILITY |
| 958 const_iterator cend() const _NOEXCEPT {return end();} |
| 959 _LIBCPP_INLINE_VISIBILITY |
| 960 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} |
| 961 _LIBCPP_INLINE_VISIBILITY |
| 962 const_reverse_iterator crend() const _NOEXCEPT {return rend();} |
| 963 |
| 964 _LIBCPP_INLINE_VISIBILITY |
| 965 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} |
| 966 _LIBCPP_INLINE_VISIBILITY |
| 967 size_type size() const _NOEXCEPT {return __tree_.size();} |
| 968 _LIBCPP_INLINE_VISIBILITY |
| 969 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} |
| 970 |
| 971 // modifiers: |
| 972 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIAD
ICS) |
| 973 template <class... _Args> |
| 974 _LIBCPP_INLINE_VISIBILITY |
| 975 iterator emplace(_Args&&... __args) |
| 976 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} |
| 977 template <class... _Args> |
| 978 _LIBCPP_INLINE_VISIBILITY |
| 979 iterator emplace_hint(const_iterator __p, _Args&&... __args) |
| 980 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__ar
gs)...);} |
| 981 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO
_VARIADICS) |
| 982 _LIBCPP_INLINE_VISIBILITY |
| 983 iterator insert(const value_type& __v) |
| 984 {return __tree_.__insert_multi(__v);} |
| 985 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 986 _LIBCPP_INLINE_VISIBILITY |
| 987 iterator insert(value_type&& __v) |
| 988 {return __tree_.__insert_multi(_VSTD::move(__v));} |
| 989 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 990 _LIBCPP_INLINE_VISIBILITY |
| 991 iterator insert(const_iterator __p, const value_type& __v) |
| 992 {return __tree_.__insert_multi(__p, __v);} |
| 993 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 994 _LIBCPP_INLINE_VISIBILITY |
| 995 iterator insert(const_iterator __p, value_type&& __v) |
| 996 {return __tree_.__insert_multi(_VSTD::move(__v));} |
| 997 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 998 template <class _InputIterator> |
| 999 _LIBCPP_INLINE_VISIBILITY |
| 1000 void insert(_InputIterator __f, _InputIterator __l) |
| 1001 { |
| 1002 for (const_iterator __e = cend(); __f != __l; ++__f) |
| 1003 __tree_.__insert_multi(__e, *__f); |
| 1004 } |
| 1005 |
| 1006 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1007 _LIBCPP_INLINE_VISIBILITY |
| 1008 void insert(initializer_list<value_type> __il) |
| 1009 {insert(__il.begin(), __il.end());} |
| 1010 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
| 1011 |
| 1012 _LIBCPP_INLINE_VISIBILITY |
| 1013 iterator erase(const_iterator __p) {return __tree_.erase(__p);} |
| 1014 _LIBCPP_INLINE_VISIBILITY |
| 1015 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} |
| 1016 _LIBCPP_INLINE_VISIBILITY |
| 1017 iterator erase(const_iterator __f, const_iterator __l) |
| 1018 {return __tree_.erase(__f, __l);} |
| 1019 _LIBCPP_INLINE_VISIBILITY |
| 1020 void clear() _NOEXCEPT {__tree_.clear();} |
| 1021 |
| 1022 _LIBCPP_INLINE_VISIBILITY |
| 1023 void swap(multiset& __s) |
| 1024 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) |
| 1025 {__tree_.swap(__s.__tree_);} |
| 1026 |
| 1027 _LIBCPP_INLINE_VISIBILITY |
| 1028 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} |
| 1029 _LIBCPP_INLINE_VISIBILITY |
| 1030 key_compare key_comp() const {return __tree_.value_comp();} |
| 1031 _LIBCPP_INLINE_VISIBILITY |
| 1032 value_compare value_comp() const {return __tree_.value_comp();} |
| 1033 |
| 1034 // set operations: |
| 1035 _LIBCPP_INLINE_VISIBILITY |
| 1036 iterator find(const key_type& __k) {return __tree_.find(__k);} |
| 1037 _LIBCPP_INLINE_VISIBILITY |
| 1038 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} |
| 1039 #if _LIBCPP_STD_VER > 11 |
| 1040 template <typename _K2> |
| 1041 _LIBCPP_INLINE_VISIBILITY |
| 1042 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iter
ator>::type |
| 1043 find(const _K2& __k) {return __tree_.find(__k);} |
| 1044 template <typename _K2> |
| 1045 _LIBCPP_INLINE_VISIBILITY |
| 1046 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,cons
t_iterator>::type |
| 1047 find(const _K2& __k) const {return __tree_.find(__k);} |
| 1048 #endif |
| 1049 |
| 1050 _LIBCPP_INLINE_VISIBILITY |
| 1051 size_type count(const key_type& __k) const |
| 1052 {return __tree_.__count_multi(__k);} |
| 1053 |
| 1054 _LIBCPP_INLINE_VISIBILITY |
| 1055 iterator lower_bound(const key_type& __k) |
| 1056 {return __tree_.lower_bound(__k);} |
| 1057 _LIBCPP_INLINE_VISIBILITY |
| 1058 const_iterator lower_bound(const key_type& __k) const |
| 1059 {return __tree_.lower_bound(__k);} |
| 1060 #if _LIBCPP_STD_VER > 11 |
| 1061 template <typename _K2> |
| 1062 _LIBCPP_INLINE_VISIBILITY |
| 1063 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iter
ator>::type |
| 1064 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} |
| 1065 |
| 1066 template <typename _K2> |
| 1067 _LIBCPP_INLINE_VISIBILITY |
| 1068 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,cons
t_iterator>::type |
| 1069 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} |
| 1070 #endif |
| 1071 |
| 1072 _LIBCPP_INLINE_VISIBILITY |
| 1073 iterator upper_bound(const key_type& __k) |
| 1074 {return __tree_.upper_bound(__k);} |
| 1075 _LIBCPP_INLINE_VISIBILITY |
| 1076 const_iterator upper_bound(const key_type& __k) const |
| 1077 {return __tree_.upper_bound(__k);} |
| 1078 #if _LIBCPP_STD_VER > 11 |
| 1079 template <typename _K2> |
| 1080 _LIBCPP_INLINE_VISIBILITY |
| 1081 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iter
ator>::type |
| 1082 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} |
| 1083 template <typename _K2> |
| 1084 _LIBCPP_INLINE_VISIBILITY |
| 1085 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,cons
t_iterator>::type |
| 1086 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} |
| 1087 #endif |
| 1088 |
| 1089 _LIBCPP_INLINE_VISIBILITY |
| 1090 pair<iterator,iterator> equal_range(const key_type& __k) |
| 1091 {return __tree_.__equal_range_multi(__k);} |
| 1092 _LIBCPP_INLINE_VISIBILITY |
| 1093 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const |
| 1094 {return __tree_.__equal_range_multi(__k);} |
| 1095 #if _LIBCPP_STD_VER > 11 |
| 1096 template <typename _K2> |
| 1097 _LIBCPP_INLINE_VISIBILITY |
| 1098 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair
<iterator,iterator>>::type |
| 1099 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} |
| 1100 template <typename _K2> |
| 1101 _LIBCPP_INLINE_VISIBILITY |
| 1102 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair
<const_iterator,const_iterator>>::type |
| 1103 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} |
| 1104 #endif |
| 1105 }; |
| 1106 |
| 1107 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1108 |
| 1109 template <class _Key, class _Compare, class _Allocator> |
| 1110 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_t
ype& __a) |
| 1111 : __tree_(_VSTD::move(__s.__tree_), __a) |
| 1112 { |
| 1113 if (__a != __s.get_allocator()) |
| 1114 { |
| 1115 const_iterator __e = cend(); |
| 1116 while (!__s.empty()) |
| 1117 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); |
| 1118 } |
| 1119 } |
| 1120 |
| 1121 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
| 1122 |
| 1123 template <class _Key, class _Compare, class _Allocator> |
| 1124 inline _LIBCPP_INLINE_VISIBILITY |
| 1125 bool |
| 1126 operator==(const multiset<_Key, _Compare, _Allocator>& __x, |
| 1127 const multiset<_Key, _Compare, _Allocator>& __y) |
| 1128 { |
| 1129 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.
begin()); |
| 1130 } |
| 1131 |
| 1132 template <class _Key, class _Compare, class _Allocator> |
| 1133 inline _LIBCPP_INLINE_VISIBILITY |
| 1134 bool |
| 1135 operator< (const multiset<_Key, _Compare, _Allocator>& __x, |
| 1136 const multiset<_Key, _Compare, _Allocator>& __y) |
| 1137 { |
| 1138 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), _
_y.end()); |
| 1139 } |
| 1140 |
| 1141 template <class _Key, class _Compare, class _Allocator> |
| 1142 inline _LIBCPP_INLINE_VISIBILITY |
| 1143 bool |
| 1144 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, |
| 1145 const multiset<_Key, _Compare, _Allocator>& __y) |
| 1146 { |
| 1147 return !(__x == __y); |
| 1148 } |
| 1149 |
| 1150 template <class _Key, class _Compare, class _Allocator> |
| 1151 inline _LIBCPP_INLINE_VISIBILITY |
| 1152 bool |
| 1153 operator> (const multiset<_Key, _Compare, _Allocator>& __x, |
| 1154 const multiset<_Key, _Compare, _Allocator>& __y) |
| 1155 { |
| 1156 return __y < __x; |
| 1157 } |
| 1158 |
| 1159 template <class _Key, class _Compare, class _Allocator> |
| 1160 inline _LIBCPP_INLINE_VISIBILITY |
| 1161 bool |
| 1162 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, |
| 1163 const multiset<_Key, _Compare, _Allocator>& __y) |
| 1164 { |
| 1165 return !(__x < __y); |
| 1166 } |
| 1167 |
| 1168 template <class _Key, class _Compare, class _Allocator> |
| 1169 inline _LIBCPP_INLINE_VISIBILITY |
| 1170 bool |
| 1171 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, |
| 1172 const multiset<_Key, _Compare, _Allocator>& __y) |
| 1173 { |
| 1174 return !(__y < __x); |
| 1175 } |
| 1176 |
| 1177 template <class _Key, class _Compare, class _Allocator> |
| 1178 inline _LIBCPP_INLINE_VISIBILITY |
| 1179 void |
| 1180 swap(multiset<_Key, _Compare, _Allocator>& __x, |
| 1181 multiset<_Key, _Compare, _Allocator>& __y) |
| 1182 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
| 1183 { |
| 1184 __x.swap(__y); |
| 1185 } |
| 1186 |
| 1187 _LIBCPP_END_NAMESPACE_STD |
| 1188 |
| 1189 #endif // _LIBCPP_SET |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 75213003:
Add libc++ and libc++abi to third-party. (Closed)
Base URL: https://src.chromium.org/chrome/trunk/src/