1 // Iterators -*- C++ -*- 2 3 // Copyright (C) 2001-2020 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996-1998 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_iterator.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{iterator} 54 * 55 * This file implements reverse_iterator, back_insert_iterator, 56 * front_insert_iterator, insert_iterator, __normal_iterator, and their 57 * supporting functions and overloaded operators. 58 */ 59 60 #ifndef _STL_ITERATOR_H 61 #define _STL_ITERATOR_H 1 62 63 #include <bits/cpp_type_traits.h> 64 #include <bits/stl_iterator_base_types.h> 65 #include <ext/type_traits.h> 66 #include <bits/move.h> 67 #include <bits/ptr_traits.h> 68 69 #if __cplusplus >= 201103L 70 # include <type_traits> 71 #endif 72 73 #if __cplusplus > 201703L 74 # define __cpp_lib_array_constexpr 201811L 75 # define __cpp_lib_constexpr_iterator 201811L 76 #elif __cplusplus == 201703L 77 # define __cpp_lib_array_constexpr 201803L 78 #endif 79 80 #if __cplusplus > 201703L 81 # include <compare> 82 # include <new> 83 # include <bits/iterator_concepts.h> 84 #endif 85 86 namespace std _GLIBCXX_VISIBILITY(default) 87 { 88 _GLIBCXX_BEGIN_NAMESPACE_VERSION 89 90 /** 91 * @addtogroup iterators 92 * @{ 93 */ 94 95 #if __cpp_lib_concepts 96 namespace __detail 97 { 98 // Weaken iterator_category _Cat to _Limit if it is derived from that, 99 // otherwise use _Otherwise. 100 template<typename _Cat, typename _Limit, typename _Otherwise = _Cat> 101 using __clamp_iter_cat 102 = conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>; 103 } 104 #endif 105 106 // 24.4.1 Reverse iterators 107 /** 108 * Bidirectional and random access iterators have corresponding reverse 109 * %iterator adaptors that iterate through the data structure in the 110 * opposite direction. They have the same signatures as the corresponding 111 * iterators. The fundamental relation between a reverse %iterator and its 112 * corresponding %iterator @c i is established by the identity: 113 * @code 114 * &*(reverse_iterator(i)) == &*(i - 1) 115 * @endcode 116 * 117 * <em>This mapping is dictated by the fact that while there is always a 118 * pointer past the end of an array, there might not be a valid pointer 119 * before the beginning of an array.</em> [24.4.1]/1,2 120 * 121 * Reverse iterators can be tricky and surprising at first. Their 122 * semantics make sense, however, and the trickiness is a side effect of 123 * the requirement that the iterators must be safe. 124 */ 125 template<typename _Iterator> 126 class reverse_iterator 127 : public iterator<typename iterator_traits<_Iterator>::iterator_category, 128 typename iterator_traits<_Iterator>::value_type, 129 typename iterator_traits<_Iterator>::difference_type, 130 typename iterator_traits<_Iterator>::pointer, 131 typename iterator_traits<_Iterator>::reference> 132 { 133 protected: 134 _Iterator current; 135 136 typedef iterator_traits<_Iterator> __traits_type; 137 138 public: 139 typedef _Iterator iterator_type; 140 typedef typename __traits_type::pointer pointer; 141 #if ! __cpp_lib_concepts 142 typedef typename __traits_type::difference_type difference_type; 143 typedef typename __traits_type::reference reference; 144 #else 145 using iterator_concept 146 = conditional_t<random_access_iterator<_Iterator>, 147 random_access_iterator_tag, 148 bidirectional_iterator_tag>; 149 using iterator_category 150 = __detail::__clamp_iter_cat<typename __traits_type::iterator_category, 151 random_access_iterator_tag>; 152 using value_type = iter_value_t<_Iterator>; 153 using difference_type = iter_difference_t<_Iterator>; 154 using reference = iter_reference_t<_Iterator>; 155 #endif 156 157 /** 158 * The default constructor value-initializes member @p current. 159 * If it is a pointer, that means it is zero-initialized. 160 */ 161 // _GLIBCXX_RESOLVE_LIB_DEFECTS 162 // 235 No specification of default ctor for reverse_iterator 163 // 1012. reverse_iterator default ctor should value initialize 164 _GLIBCXX17_CONSTEXPR 165 reverse_iterator() : current() { } 166 167 /** 168 * This %iterator will move in the opposite direction that @p x does. 169 */ 170 explicit _GLIBCXX17_CONSTEXPR 171 reverse_iterator(iterator_type __x) : current(__x) { } 172 173 /** 174 * The copy constructor is normal. 175 */ 176 _GLIBCXX17_CONSTEXPR 177 reverse_iterator(const reverse_iterator& __x) 178 : current(__x.current) { } 179 180 #if __cplusplus >= 201103L 181 reverse_iterator& operator=(const reverse_iterator&) = default; 182 #endif 183 184 /** 185 * A %reverse_iterator across other types can be copied if the 186 * underlying %iterator can be converted to the type of @c current. 187 */ 188 template<typename _Iter> 189 _GLIBCXX17_CONSTEXPR 190 reverse_iterator(const reverse_iterator<_Iter>& __x) 191 : current(__x.base()) { } 192 193 /** 194 * @return @c current, the %iterator used for underlying work. 195 */ 196 _GLIBCXX17_CONSTEXPR iterator_type 197 base() const 198 { return current; } 199 200 /** 201 * @return A reference to the value at @c --current 202 * 203 * This requires that @c --current is dereferenceable. 204 * 205 * @warning This implementation requires that for an iterator of the 206 * underlying iterator type, @c x, a reference obtained by 207 * @c *x remains valid after @c x has been modified or 208 * destroyed. This is a bug: http://gcc.gnu.org/PR51823 209 */ 210 _GLIBCXX17_CONSTEXPR reference 211 operator*() const 212 { 213 _Iterator __tmp = current; 214 return *--__tmp; 215 } 216 217 /** 218 * @return A pointer to the value at @c --current 219 * 220 * This requires that @c --current is dereferenceable. 221 */ 222 _GLIBCXX17_CONSTEXPR pointer 223 operator->() const 224 #if __cplusplus > 201703L && __cpp_concepts >= 201907L 225 requires is_pointer_v<_Iterator> 226 || requires(const _Iterator __i) { __i.operator->(); } 227 #endif 228 { 229 // _GLIBCXX_RESOLVE_LIB_DEFECTS 230 // 1052. operator-> should also support smart pointers 231 _Iterator __tmp = current; 232 --__tmp; 233 return _S_to_pointer(__tmp); 234 } 235 236 /** 237 * @return @c *this 238 * 239 * Decrements the underlying iterator. 240 */ 241 _GLIBCXX17_CONSTEXPR reverse_iterator& 242 operator++() 243 { 244 --current; 245 return *this; 246 } 247 248 /** 249 * @return The original value of @c *this 250 * 251 * Decrements the underlying iterator. 252 */ 253 _GLIBCXX17_CONSTEXPR reverse_iterator 254 operator++(int) 255 { 256 reverse_iterator __tmp = *this; 257 --current; 258 return __tmp; 259 } 260 261 /** 262 * @return @c *this 263 * 264 * Increments the underlying iterator. 265 */ 266 _GLIBCXX17_CONSTEXPR reverse_iterator& 267 operator--() 268 { 269 ++current; 270 return *this; 271 } 272 273 /** 274 * @return A reverse_iterator with the previous value of @c *this 275 * 276 * Increments the underlying iterator. 277 */ 278 _GLIBCXX17_CONSTEXPR reverse_iterator 279 operator--(int) 280 { 281 reverse_iterator __tmp = *this; 282 ++current; 283 return __tmp; 284 } 285 286 /** 287 * @return A reverse_iterator that refers to @c current - @a __n 288 * 289 * The underlying iterator must be a Random Access Iterator. 290 */ 291 _GLIBCXX17_CONSTEXPR reverse_iterator 292 operator+(difference_type __n) const 293 { return reverse_iterator(current - __n); } 294 295 /** 296 * @return *this 297 * 298 * Moves the underlying iterator backwards @a __n steps. 299 * The underlying iterator must be a Random Access Iterator. 300 */ 301 _GLIBCXX17_CONSTEXPR reverse_iterator& 302 operator+=(difference_type __n) 303 { 304 current -= __n; 305 return *this; 306 } 307 308 /** 309 * @return A reverse_iterator that refers to @c current - @a __n 310 * 311 * The underlying iterator must be a Random Access Iterator. 312 */ 313 _GLIBCXX17_CONSTEXPR reverse_iterator 314 operator-(difference_type __n) const 315 { return reverse_iterator(current + __n); } 316 317 /** 318 * @return *this 319 * 320 * Moves the underlying iterator forwards @a __n steps. 321 * The underlying iterator must be a Random Access Iterator. 322 */ 323 _GLIBCXX17_CONSTEXPR reverse_iterator& 324 operator-=(difference_type __n) 325 { 326 current += __n; 327 return *this; 328 } 329 330 /** 331 * @return The value at @c current - @a __n - 1 332 * 333 * The underlying iterator must be a Random Access Iterator. 334 */ 335 _GLIBCXX17_CONSTEXPR reference 336 operator[](difference_type __n) const 337 { return *(*this + __n); } 338 339 #if __cplusplus > 201703L && __cpp_lib_concepts 340 friend constexpr iter_rvalue_reference_t<_Iterator> 341 iter_move(const reverse_iterator& __i) 342 noexcept(is_nothrow_copy_constructible_v<_Iterator> 343 && noexcept(ranges::iter_move(--std::declval<_Iterator&>()))) 344 { 345 auto __tmp = __i.base(); 346 return ranges::iter_move(--__tmp); 347 } 348 349 template<indirectly_swappable<_Iterator> _Iter2> 350 friend constexpr void 351 iter_swap(const reverse_iterator& __x, 352 const reverse_iterator<_Iter2>& __y) 353 noexcept(is_nothrow_copy_constructible_v<_Iterator> 354 && is_nothrow_copy_constructible_v<_Iter2> 355 && noexcept(ranges::iter_swap(--std::declval<_Iterator&>(), 356 --std::declval<_Iter2&>()))) 357 { 358 auto __xtmp = __x.base(); 359 auto __ytmp = __y.base(); 360 ranges::iter_swap(--__xtmp, --__ytmp); 361 } 362 #endif 363 364 private: 365 template<typename _Tp> 366 static _GLIBCXX17_CONSTEXPR _Tp* 367 _S_to_pointer(_Tp* __p) 368 { return __p; } 369 370 template<typename _Tp> 371 static _GLIBCXX17_CONSTEXPR pointer 372 _S_to_pointer(_Tp __t) 373 { return __t.operator->(); } 374 }; 375 376 ///@{ 377 /** 378 * @param __x A %reverse_iterator. 379 * @param __y A %reverse_iterator. 380 * @return A simple bool. 381 * 382 * Reverse iterators forward comparisons to their underlying base() 383 * iterators. 384 * 385 */ 386 #if __cplusplus <= 201703L || ! defined __cpp_lib_concepts 387 template<typename _Iterator> 388 inline _GLIBCXX17_CONSTEXPR bool 389 operator==(const reverse_iterator<_Iterator>& __x, 390 const reverse_iterator<_Iterator>& __y) 391 { return __x.base() == __y.base(); } 392 393 template<typename _Iterator> 394 inline _GLIBCXX17_CONSTEXPR bool 395 operator<(const reverse_iterator<_Iterator>& __x, 396 const reverse_iterator<_Iterator>& __y) 397 { return __y.base() < __x.base(); } 398 399 template<typename _Iterator> 400 inline _GLIBCXX17_CONSTEXPR bool 401 operator!=(const reverse_iterator<_Iterator>& __x, 402 const reverse_iterator<_Iterator>& __y) 403 { return !(__x == __y); } 404 405 template<typename _Iterator> 406 inline _GLIBCXX17_CONSTEXPR bool 407 operator>(const reverse_iterator<_Iterator>& __x, 408 const reverse_iterator<_Iterator>& __y) 409 { return __y < __x; } 410 411 template<typename _Iterator> 412 inline _GLIBCXX17_CONSTEXPR bool 413 operator<=(const reverse_iterator<_Iterator>& __x, 414 const reverse_iterator<_Iterator>& __y) 415 { return !(__y < __x); } 416 417 template<typename _Iterator> 418 inline _GLIBCXX17_CONSTEXPR bool 419 operator>=(const reverse_iterator<_Iterator>& __x, 420 const reverse_iterator<_Iterator>& __y) 421 { return !(__x < __y); } 422 423 // _GLIBCXX_RESOLVE_LIB_DEFECTS 424 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 425 template<typename _IteratorL, typename _IteratorR> 426 inline _GLIBCXX17_CONSTEXPR bool 427 operator==(const reverse_iterator<_IteratorL>& __x, 428 const reverse_iterator<_IteratorR>& __y) 429 { return __x.base() == __y.base(); } 430 431 template<typename _IteratorL, typename _IteratorR> 432 inline _GLIBCXX17_CONSTEXPR bool 433 operator<(const reverse_iterator<_IteratorL>& __x, 434 const reverse_iterator<_IteratorR>& __y) 435 { return __y.base() < __x.base(); } 436 437 template<typename _IteratorL, typename _IteratorR> 438 inline _GLIBCXX17_CONSTEXPR bool 439 operator!=(const reverse_iterator<_IteratorL>& __x, 440 const reverse_iterator<_IteratorR>& __y) 441 { return !(__x == __y); } 442 443 template<typename _IteratorL, typename _IteratorR> 444 inline _GLIBCXX17_CONSTEXPR bool 445 operator>(const reverse_iterator<_IteratorL>& __x, 446 const reverse_iterator<_IteratorR>& __y) 447 { return __y < __x; } 448 449 template<typename _IteratorL, typename _IteratorR> 450 inline _GLIBCXX17_CONSTEXPR bool 451 operator<=(const reverse_iterator<_IteratorL>& __x, 452 const reverse_iterator<_IteratorR>& __y) 453 { return !(__y < __x); } 454 455 template<typename _IteratorL, typename _IteratorR> 456 inline _GLIBCXX17_CONSTEXPR bool 457 operator>=(const reverse_iterator<_IteratorL>& __x, 458 const reverse_iterator<_IteratorR>& __y) 459 { return !(__x < __y); } 460 #else // C++20 461 template<typename _IteratorL, typename _IteratorR> 462 constexpr bool 463 operator==(const reverse_iterator<_IteratorL>& __x, 464 const reverse_iterator<_IteratorR>& __y) 465 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; } 466 { return __x.base() == __y.base(); } 467 468 template<typename _IteratorL, typename _IteratorR> 469 constexpr bool 470 operator!=(const reverse_iterator<_IteratorL>& __x, 471 const reverse_iterator<_IteratorR>& __y) 472 requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; } 473 { return __x.base() != __y.base(); } 474 475 template<typename _IteratorL, typename _IteratorR> 476 constexpr bool 477 operator<(const reverse_iterator<_IteratorL>& __x, 478 const reverse_iterator<_IteratorR>& __y) 479 requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; } 480 { return __x.base() > __y.base(); } 481 482 template<typename _IteratorL, typename _IteratorR> 483 constexpr bool 484 operator>(const reverse_iterator<_IteratorL>& __x, 485 const reverse_iterator<_IteratorR>& __y) 486 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; } 487 { return __x.base() < __y.base(); } 488 489 template<typename _IteratorL, typename _IteratorR> 490 constexpr bool 491 operator<=(const reverse_iterator<_IteratorL>& __x, 492 const reverse_iterator<_IteratorR>& __y) 493 requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; } 494 { return __x.base() >= __y.base(); } 495 496 template<typename _IteratorL, typename _IteratorR> 497 constexpr bool 498 operator>=(const reverse_iterator<_IteratorL>& __x, 499 const reverse_iterator<_IteratorR>& __y) 500 requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; } 501 { return __x.base() <= __y.base(); } 502 503 template<typename _IteratorL, 504 three_way_comparable_with<_IteratorL> _IteratorR> 505 constexpr compare_three_way_result_t<_IteratorL, _IteratorR> 506 operator<=>(const reverse_iterator<_IteratorL>& __x, 507 const reverse_iterator<_IteratorR>& __y) 508 { return __y.base() <=> __x.base(); } 509 510 // Additional, non-standard overloads to avoid ambiguities with greedy, 511 // unconstrained overloads in associated namespaces. 512 513 template<typename _Iterator> 514 constexpr bool 515 operator==(const reverse_iterator<_Iterator>& __x, 516 const reverse_iterator<_Iterator>& __y) 517 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; } 518 { return __x.base() == __y.base(); } 519 520 template<three_way_comparable _Iterator> 521 constexpr compare_three_way_result_t<_Iterator, _Iterator> 522 operator<=>(const reverse_iterator<_Iterator>& __x, 523 const reverse_iterator<_Iterator>& __y) 524 { return __y.base() <=> __x.base(); } 525 #endif // C++20 526 ///@} 527 528 #if __cplusplus < 201103L 529 template<typename _Iterator> 530 inline typename reverse_iterator<_Iterator>::difference_type 531 operator-(const reverse_iterator<_Iterator>& __x, 532 const reverse_iterator<_Iterator>& __y) 533 { return __y.base() - __x.base(); } 534 535 template<typename _IteratorL, typename _IteratorR> 536 inline typename reverse_iterator<_IteratorL>::difference_type 537 operator-(const reverse_iterator<_IteratorL>& __x, 538 const reverse_iterator<_IteratorR>& __y) 539 { return __y.base() - __x.base(); } 540 #else 541 // _GLIBCXX_RESOLVE_LIB_DEFECTS 542 // DR 685. reverse_iterator/move_iterator difference has invalid signatures 543 template<typename _IteratorL, typename _IteratorR> 544 inline _GLIBCXX17_CONSTEXPR auto 545 operator-(const reverse_iterator<_IteratorL>& __x, 546 const reverse_iterator<_IteratorR>& __y) 547 -> decltype(__y.base() - __x.base()) 548 { return __y.base() - __x.base(); } 549 #endif 550 551 template<typename _Iterator> 552 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator> 553 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 554 const reverse_iterator<_Iterator>& __x) 555 { return reverse_iterator<_Iterator>(__x.base() - __n); } 556 557 #if __cplusplus >= 201103L 558 // Same as C++14 make_reverse_iterator but used in C++11 mode too. 559 template<typename _Iterator> 560 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator> 561 __make_reverse_iterator(_Iterator __i) 562 { return reverse_iterator<_Iterator>(__i); } 563 564 # if __cplusplus >= 201402L 565 # define __cpp_lib_make_reverse_iterator 201402 566 567 // _GLIBCXX_RESOLVE_LIB_DEFECTS 568 // DR 2285. make_reverse_iterator 569 /// Generator function for reverse_iterator. 570 template<typename _Iterator> 571 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator> 572 make_reverse_iterator(_Iterator __i) 573 { return reverse_iterator<_Iterator>(__i); } 574 575 # if __cplusplus > 201703L && defined __cpp_lib_concepts 576 template<typename _Iterator1, typename _Iterator2> 577 requires (!sized_sentinel_for<_Iterator1, _Iterator2>) 578 inline constexpr bool 579 disable_sized_sentinel_for<reverse_iterator<_Iterator1>, 580 reverse_iterator<_Iterator2>> = true; 581 # endif // C++20 582 # endif // C++14 583 584 template<typename _Iterator> 585 _GLIBCXX20_CONSTEXPR 586 auto 587 __niter_base(reverse_iterator<_Iterator> __it) 588 -> decltype(__make_reverse_iterator(__niter_base(__it.base()))) 589 { return __make_reverse_iterator(__niter_base(__it.base())); } 590 591 template<typename _Iterator> 592 struct __is_move_iterator<reverse_iterator<_Iterator> > 593 : __is_move_iterator<_Iterator> 594 { }; 595 596 template<typename _Iterator> 597 _GLIBCXX20_CONSTEXPR 598 auto 599 __miter_base(reverse_iterator<_Iterator> __it) 600 -> decltype(__make_reverse_iterator(__miter_base(__it.base()))) 601 { return __make_reverse_iterator(__miter_base(__it.base())); } 602 #endif // C++11 603 604 // 24.4.2.2.1 back_insert_iterator 605 /** 606 * @brief Turns assignment into insertion. 607 * 608 * These are output iterators, constructed from a container-of-T. 609 * Assigning a T to the iterator appends it to the container using 610 * push_back. 611 * 612 * Tip: Using the back_inserter function to create these iterators can 613 * save typing. 614 */ 615 template<typename _Container> 616 class back_insert_iterator 617 : public iterator<output_iterator_tag, void, void, void, void> 618 { 619 protected: 620 _Container* container; 621 622 public: 623 /// A nested typedef for the type of whatever container you used. 624 typedef _Container container_type; 625 #if __cplusplus > 201703L 626 using difference_type = ptrdiff_t; 627 628 constexpr back_insert_iterator() noexcept : container(nullptr) { } 629 #endif 630 631 /// The only way to create this %iterator is with a container. 632 explicit _GLIBCXX20_CONSTEXPR 633 back_insert_iterator(_Container& __x) 634 : container(std::__addressof(__x)) { } 635 636 /** 637 * @param __value An instance of whatever type 638 * container_type::const_reference is; presumably a 639 * reference-to-const T for container<T>. 640 * @return This %iterator, for chained operations. 641 * 642 * This kind of %iterator doesn't really have a @a position in the 643 * container (you can think of the position as being permanently at 644 * the end, if you like). Assigning a value to the %iterator will 645 * always append the value to the end of the container. 646 */ 647 #if __cplusplus < 201103L 648 back_insert_iterator& 649 operator=(typename _Container::const_reference __value) 650 { 651 container->push_back(__value); 652 return *this; 653 } 654 #else 655 _GLIBCXX20_CONSTEXPR 656 back_insert_iterator& 657 operator=(const typename _Container::value_type& __value) 658 { 659 container->push_back(__value); 660 return *this; 661 } 662 663 _GLIBCXX20_CONSTEXPR 664 back_insert_iterator& 665 operator=(typename _Container::value_type&& __value) 666 { 667 container->push_back(std::move(__value)); 668 return *this; 669 } 670 #endif 671 672 /// Simply returns *this. 673 _GLIBCXX20_CONSTEXPR 674 back_insert_iterator& 675 operator*() 676 { return *this; } 677 678 /// Simply returns *this. (This %iterator does not @a move.) 679 _GLIBCXX20_CONSTEXPR 680 back_insert_iterator& 681 operator++() 682 { return *this; } 683 684 /// Simply returns *this. (This %iterator does not @a move.) 685 _GLIBCXX20_CONSTEXPR 686 back_insert_iterator 687 operator++(int) 688 { return *this; } 689 }; 690 691 /** 692 * @param __x A container of arbitrary type. 693 * @return An instance of back_insert_iterator working on @p __x. 694 * 695 * This wrapper function helps in creating back_insert_iterator instances. 696 * Typing the name of the %iterator requires knowing the precise full 697 * type of the container, which can be tedious and impedes generic 698 * programming. Using this function lets you take advantage of automatic 699 * template parameter deduction, making the compiler match the correct 700 * types for you. 701 */ 702 template<typename _Container> 703 _GLIBCXX20_CONSTEXPR 704 inline back_insert_iterator<_Container> 705 back_inserter(_Container& __x) 706 { return back_insert_iterator<_Container>(__x); } 707 708 /** 709 * @brief Turns assignment into insertion. 710 * 711 * These are output iterators, constructed from a container-of-T. 712 * Assigning a T to the iterator prepends it to the container using 713 * push_front. 714 * 715 * Tip: Using the front_inserter function to create these iterators can 716 * save typing. 717 */ 718 template<typename _Container> 719 class front_insert_iterator 720 : public iterator<output_iterator_tag, void, void, void, void> 721 { 722 protected: 723 _Container* container; 724 725 public: 726 /// A nested typedef for the type of whatever container you used. 727 typedef _Container container_type; 728 #if __cplusplus > 201703L 729 using difference_type = ptrdiff_t; 730 731 constexpr front_insert_iterator() noexcept : container(nullptr) { } 732 #endif 733 734 /// The only way to create this %iterator is with a container. 735 explicit _GLIBCXX20_CONSTEXPR 736 front_insert_iterator(_Container& __x) 737 : container(std::__addressof(__x)) { } 738 739 /** 740 * @param __value An instance of whatever type 741 * container_type::const_reference is; presumably a 742 * reference-to-const T for container<T>. 743 * @return This %iterator, for chained operations. 744 * 745 * This kind of %iterator doesn't really have a @a position in the 746 * container (you can think of the position as being permanently at 747 * the front, if you like). Assigning a value to the %iterator will 748 * always prepend the value to the front of the container. 749 */ 750 #if __cplusplus < 201103L 751 front_insert_iterator& 752 operator=(typename _Container::const_reference __value) 753 { 754 container->push_front(__value); 755 return *this; 756 } 757 #else 758 _GLIBCXX20_CONSTEXPR 759 front_insert_iterator& 760 operator=(const typename _Container::value_type& __value) 761 { 762 container->push_front(__value); 763 return *this; 764 } 765 766 _GLIBCXX20_CONSTEXPR 767 front_insert_iterator& 768 operator=(typename _Container::value_type&& __value) 769 { 770 container->push_front(std::move(__value)); 771 return *this; 772 } 773 #endif 774 775 /// Simply returns *this. 776 _GLIBCXX20_CONSTEXPR 777 front_insert_iterator& 778 operator*() 779 { return *this; } 780 781 /// Simply returns *this. (This %iterator does not @a move.) 782 _GLIBCXX20_CONSTEXPR 783 front_insert_iterator& 784 operator++() 785 { return *this; } 786 787 /// Simply returns *this. (This %iterator does not @a move.) 788 _GLIBCXX20_CONSTEXPR 789 front_insert_iterator 790 operator++(int) 791 { return *this; } 792 }; 793 794 /** 795 * @param __x A container of arbitrary type. 796 * @return An instance of front_insert_iterator working on @p x. 797 * 798 * This wrapper function helps in creating front_insert_iterator instances. 799 * Typing the name of the %iterator requires knowing the precise full 800 * type of the container, which can be tedious and impedes generic 801 * programming. Using this function lets you take advantage of automatic 802 * template parameter deduction, making the compiler match the correct 803 * types for you. 804 */ 805 template<typename _Container> 806 _GLIBCXX20_CONSTEXPR 807 inline front_insert_iterator<_Container> 808 front_inserter(_Container& __x) 809 { return front_insert_iterator<_Container>(__x); } 810 811 /** 812 * @brief Turns assignment into insertion. 813 * 814 * These are output iterators, constructed from a container-of-T. 815 * Assigning a T to the iterator inserts it in the container at the 816 * %iterator's position, rather than overwriting the value at that 817 * position. 818 * 819 * (Sequences will actually insert a @e copy of the value before the 820 * %iterator's position.) 821 * 822 * Tip: Using the inserter function to create these iterators can 823 * save typing. 824 */ 825 template<typename _Container> 826 class insert_iterator 827 : public iterator<output_iterator_tag, void, void, void, void> 828 { 829 #if __cplusplus > 201703L && defined __cpp_lib_concepts 830 using _Iter = std::__detail::__range_iter_t<_Container>; 831 832 protected: 833 _Container* container = nullptr; 834 _Iter iter = _Iter(); 835 #else 836 typedef typename _Container::iterator _Iter; 837 838 protected: 839 _Container* container; 840 _Iter iter; 841 #endif 842 843 public: 844 /// A nested typedef for the type of whatever container you used. 845 typedef _Container container_type; 846 847 #if __cplusplus > 201703L && defined __cpp_lib_concepts 848 using difference_type = ptrdiff_t; 849 850 insert_iterator() = default; 851 #endif 852 853 /** 854 * The only way to create this %iterator is with a container and an 855 * initial position (a normal %iterator into the container). 856 */ 857 _GLIBCXX20_CONSTEXPR 858 insert_iterator(_Container& __x, _Iter __i) 859 : container(std::__addressof(__x)), iter(__i) {} 860 861 /** 862 * @param __value An instance of whatever type 863 * container_type::const_reference is; presumably a 864 * reference-to-const T for container<T>. 865 * @return This %iterator, for chained operations. 866 * 867 * This kind of %iterator maintains its own position in the 868 * container. Assigning a value to the %iterator will insert the 869 * value into the container at the place before the %iterator. 870 * 871 * The position is maintained such that subsequent assignments will 872 * insert values immediately after one another. For example, 873 * @code 874 * // vector v contains A and Z 875 * 876 * insert_iterator i (v, ++v.begin()); 877 * i = 1; 878 * i = 2; 879 * i = 3; 880 * 881 * // vector v contains A, 1, 2, 3, and Z 882 * @endcode 883 */ 884 #if __cplusplus < 201103L 885 insert_iterator& 886 operator=(typename _Container::const_reference __value) 887 { 888 iter = container->insert(iter, __value); 889 ++iter; 890 return *this; 891 } 892 #else 893 _GLIBCXX20_CONSTEXPR 894 insert_iterator& 895 operator=(const typename _Container::value_type& __value) 896 { 897 iter = container->insert(iter, __value); 898 ++iter; 899 return *this; 900 } 901 902 _GLIBCXX20_CONSTEXPR 903 insert_iterator& 904 operator=(typename _Container::value_type&& __value) 905 { 906 iter = container->insert(iter, std::move(__value)); 907 ++iter; 908 return *this; 909 } 910 #endif 911 912 /// Simply returns *this. 913 _GLIBCXX20_CONSTEXPR 914 insert_iterator& 915 operator*() 916 { return *this; } 917 918 /// Simply returns *this. (This %iterator does not @a move.) 919 _GLIBCXX20_CONSTEXPR 920 insert_iterator& 921 operator++() 922 { return *this; } 923 924 /// Simply returns *this. (This %iterator does not @a move.) 925 _GLIBCXX20_CONSTEXPR 926 insert_iterator& 927 operator++(int) 928 { return *this; } 929 }; 930 931 /** 932 * @param __x A container of arbitrary type. 933 * @param __i An iterator into the container. 934 * @return An instance of insert_iterator working on @p __x. 935 * 936 * This wrapper function helps in creating insert_iterator instances. 937 * Typing the name of the %iterator requires knowing the precise full 938 * type of the container, which can be tedious and impedes generic 939 * programming. Using this function lets you take advantage of automatic 940 * template parameter deduction, making the compiler match the correct 941 * types for you. 942 */ 943 #if __cplusplus > 201703L && defined __cpp_lib_concepts 944 template<typename _Container> 945 constexpr insert_iterator<_Container> 946 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i) 947 { return insert_iterator<_Container>(__x, __i); } 948 #else 949 template<typename _Container> 950 inline insert_iterator<_Container> 951 inserter(_Container& __x, typename _Container::iterator __i) 952 { return insert_iterator<_Container>(__x, __i); } 953 #endif 954 955 /// @} group iterators 956 957 _GLIBCXX_END_NAMESPACE_VERSION 958 } // namespace 959 960 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 961 { 962 _GLIBCXX_BEGIN_NAMESPACE_VERSION 963 964 // This iterator adapter is @a normal in the sense that it does not 965 // change the semantics of any of the operators of its iterator 966 // parameter. Its primary purpose is to convert an iterator that is 967 // not a class, e.g. a pointer, into an iterator that is a class. 968 // The _Container parameter exists solely so that different containers 969 // using this template can instantiate different types, even if the 970 // _Iterator parameter is the same. 971 template<typename _Iterator, typename _Container> 972 class __normal_iterator 973 { 974 protected: 975 _Iterator _M_current; 976 977 typedef std::iterator_traits<_Iterator> __traits_type; 978 979 public: 980 typedef _Iterator iterator_type; 981 typedef typename __traits_type::iterator_category iterator_category; 982 typedef typename __traits_type::value_type value_type; 983 typedef typename __traits_type::difference_type difference_type; 984 typedef typename __traits_type::reference reference; 985 typedef typename __traits_type::pointer pointer; 986 987 #if __cplusplus > 201703L && __cpp_lib_concepts 988 using iterator_concept = std::__detail::__iter_concept<_Iterator>; 989 #endif 990 991 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 992 : _M_current(_Iterator()) { } 993 994 explicit _GLIBCXX20_CONSTEXPR 995 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 996 : _M_current(__i) { } 997 998 // Allow iterator to const_iterator conversion 999 template<typename _Iter> 1000 _GLIBCXX20_CONSTEXPR 1001 __normal_iterator(const __normal_iterator<_Iter, 1002 typename __enable_if< 1003 (std::__are_same<_Iter, typename _Container::pointer>::__value), 1004 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT 1005 : _M_current(__i.base()) { } 1006 1007 // Forward iterator requirements 1008 _GLIBCXX20_CONSTEXPR 1009 reference 1010 operator*() const _GLIBCXX_NOEXCEPT 1011 { return *_M_current; } 1012 1013 _GLIBCXX20_CONSTEXPR 1014 pointer 1015 operator->() const _GLIBCXX_NOEXCEPT 1016 { return _M_current; } 1017 1018 _GLIBCXX20_CONSTEXPR 1019 __normal_iterator& 1020 operator++() _GLIBCXX_NOEXCEPT 1021 { 1022 ++_M_current; 1023 return *this; 1024 } 1025 1026 _GLIBCXX20_CONSTEXPR 1027 __normal_iterator 1028 operator++(int) _GLIBCXX_NOEXCEPT 1029 { return __normal_iterator(_M_current++); } 1030 1031 // Bidirectional iterator requirements 1032 _GLIBCXX20_CONSTEXPR 1033 __normal_iterator& 1034 operator--() _GLIBCXX_NOEXCEPT 1035 { 1036 --_M_current; 1037 return *this; 1038 } 1039 1040 _GLIBCXX20_CONSTEXPR 1041 __normal_iterator 1042 operator--(int) _GLIBCXX_NOEXCEPT 1043 { return __normal_iterator(_M_current--); } 1044 1045 // Random access iterator requirements 1046 _GLIBCXX20_CONSTEXPR 1047 reference 1048 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 1049 { return _M_current[__n]; } 1050 1051 _GLIBCXX20_CONSTEXPR 1052 __normal_iterator& 1053 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 1054 { _M_current += __n; return *this; } 1055 1056 _GLIBCXX20_CONSTEXPR 1057 __normal_iterator 1058 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 1059 { return __normal_iterator(_M_current + __n); } 1060 1061 _GLIBCXX20_CONSTEXPR 1062 __normal_iterator& 1063 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 1064 { _M_current -= __n; return *this; } 1065 1066 _GLIBCXX20_CONSTEXPR 1067 __normal_iterator 1068 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 1069 { return __normal_iterator(_M_current - __n); } 1070 1071 _GLIBCXX20_CONSTEXPR 1072 const _Iterator& 1073 base() const _GLIBCXX_NOEXCEPT 1074 { return _M_current; } 1075 }; 1076 1077 // Note: In what follows, the left- and right-hand-side iterators are 1078 // allowed to vary in types (conceptually in cv-qualification) so that 1079 // comparison between cv-qualified and non-cv-qualified iterators be 1080 // valid. However, the greedy and unfriendly operators in std::rel_ops 1081 // will make overload resolution ambiguous (when in scope) if we don't 1082 // provide overloads whose operands are of the same type. Can someone 1083 // remind me what generic programming is about? -- Gaby 1084 1085 #if __cpp_lib_three_way_comparison 1086 template<typename _IteratorL, typename _IteratorR, typename _Container> 1087 requires requires (_IteratorL __lhs, _IteratorR __rhs) 1088 { { __lhs == __rhs } -> std::convertible_to<bool>; } 1089 constexpr bool 1090 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 1091 const __normal_iterator<_IteratorR, _Container>& __rhs) 1092 noexcept(noexcept(__lhs.base() == __rhs.base())) 1093 { return __lhs.base() == __rhs.base(); } 1094 1095 template<typename _IteratorL, typename _IteratorR, typename _Container> 1096 constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL> 1097 operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs, 1098 const __normal_iterator<_IteratorR, _Container>& __rhs) 1099 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base()))) 1100 { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); } 1101 1102 template<typename _Iterator, typename _Container> 1103 constexpr bool 1104 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 1105 const __normal_iterator<_Iterator, _Container>& __rhs) 1106 noexcept(noexcept(__lhs.base() == __rhs.base())) 1107 requires requires { 1108 { __lhs.base() == __rhs.base() } -> std::convertible_to<bool>; 1109 } 1110 { return __lhs.base() == __rhs.base(); } 1111 1112 template<typename _Iterator, typename _Container> 1113 constexpr std::__detail::__synth3way_t<_Iterator> 1114 operator<=>(const __normal_iterator<_Iterator, _Container>& __lhs, 1115 const __normal_iterator<_Iterator, _Container>& __rhs) 1116 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base()))) 1117 { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); } 1118 #else 1119 // Forward iterator requirements 1120 template<typename _IteratorL, typename _IteratorR, typename _Container> 1121 _GLIBCXX20_CONSTEXPR 1122 inline bool 1123 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 1124 const __normal_iterator<_IteratorR, _Container>& __rhs) 1125 _GLIBCXX_NOEXCEPT 1126 { return __lhs.base() == __rhs.base(); } 1127 1128 template<typename _Iterator, typename _Container> 1129 _GLIBCXX20_CONSTEXPR 1130 inline bool 1131 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 1132 const __normal_iterator<_Iterator, _Container>& __rhs) 1133 _GLIBCXX_NOEXCEPT 1134 { return __lhs.base() == __rhs.base(); } 1135 1136 template<typename _IteratorL, typename _IteratorR, typename _Container> 1137 _GLIBCXX20_CONSTEXPR 1138 inline bool 1139 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 1140 const __normal_iterator<_IteratorR, _Container>& __rhs) 1141 _GLIBCXX_NOEXCEPT 1142 { return __lhs.base() != __rhs.base(); } 1143 1144 template<typename _Iterator, typename _Container> 1145 _GLIBCXX20_CONSTEXPR 1146 inline bool 1147 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 1148 const __normal_iterator<_Iterator, _Container>& __rhs) 1149 _GLIBCXX_NOEXCEPT 1150 { return __lhs.base() != __rhs.base(); } 1151 1152 // Random access iterator requirements 1153 template<typename _IteratorL, typename _IteratorR, typename _Container> 1154 inline bool 1155 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 1156 const __normal_iterator<_IteratorR, _Container>& __rhs) 1157 _GLIBCXX_NOEXCEPT 1158 { return __lhs.base() < __rhs.base(); } 1159 1160 template<typename _Iterator, typename _Container> 1161 _GLIBCXX20_CONSTEXPR 1162 inline bool 1163 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 1164 const __normal_iterator<_Iterator, _Container>& __rhs) 1165 _GLIBCXX_NOEXCEPT 1166 { return __lhs.base() < __rhs.base(); } 1167 1168 template<typename _IteratorL, typename _IteratorR, typename _Container> 1169 inline bool 1170 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 1171 const __normal_iterator<_IteratorR, _Container>& __rhs) 1172 _GLIBCXX_NOEXCEPT 1173 { return __lhs.base() > __rhs.base(); } 1174 1175 template<typename _Iterator, typename _Container> 1176 _GLIBCXX20_CONSTEXPR 1177 inline bool 1178 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 1179 const __normal_iterator<_Iterator, _Container>& __rhs) 1180 _GLIBCXX_NOEXCEPT 1181 { return __lhs.base() > __rhs.base(); } 1182 1183 template<typename _IteratorL, typename _IteratorR, typename _Container> 1184 inline bool 1185 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 1186 const __normal_iterator<_IteratorR, _Container>& __rhs) 1187 _GLIBCXX_NOEXCEPT 1188 { return __lhs.base() <= __rhs.base(); } 1189 1190 template<typename _Iterator, typename _Container> 1191 _GLIBCXX20_CONSTEXPR 1192 inline bool 1193 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 1194 const __normal_iterator<_Iterator, _Container>& __rhs) 1195 _GLIBCXX_NOEXCEPT 1196 { return __lhs.base() <= __rhs.base(); } 1197 1198 template<typename _IteratorL, typename _IteratorR, typename _Container> 1199 inline bool 1200 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 1201 const __normal_iterator<_IteratorR, _Container>& __rhs) 1202 _GLIBCXX_NOEXCEPT 1203 { return __lhs.base() >= __rhs.base(); } 1204 1205 template<typename _Iterator, typename _Container> 1206 _GLIBCXX20_CONSTEXPR 1207 inline bool 1208 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 1209 const __normal_iterator<_Iterator, _Container>& __rhs) 1210 _GLIBCXX_NOEXCEPT 1211 { return __lhs.base() >= __rhs.base(); } 1212 #endif // three-way comparison 1213 1214 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1215 // According to the resolution of DR179 not only the various comparison 1216 // operators but also operator- must accept mixed iterator/const_iterator 1217 // parameters. 1218 template<typename _IteratorL, typename _IteratorR, typename _Container> 1219 #if __cplusplus >= 201103L 1220 // DR 685. 1221 _GLIBCXX20_CONSTEXPR 1222 inline auto 1223 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 1224 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 1225 -> decltype(__lhs.base() - __rhs.base()) 1226 #else 1227 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 1228 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 1229 const __normal_iterator<_IteratorR, _Container>& __rhs) 1230 #endif 1231 { return __lhs.base() - __rhs.base(); } 1232 1233 template<typename _Iterator, typename _Container> 1234 _GLIBCXX20_CONSTEXPR 1235 inline typename __normal_iterator<_Iterator, _Container>::difference_type 1236 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 1237 const __normal_iterator<_Iterator, _Container>& __rhs) 1238 _GLIBCXX_NOEXCEPT 1239 { return __lhs.base() - __rhs.base(); } 1240 1241 template<typename _Iterator, typename _Container> 1242 _GLIBCXX20_CONSTEXPR 1243 inline __normal_iterator<_Iterator, _Container> 1244 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 1245 __n, const __normal_iterator<_Iterator, _Container>& __i) 1246 _GLIBCXX_NOEXCEPT 1247 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 1248 1249 _GLIBCXX_END_NAMESPACE_VERSION 1250 } // namespace 1251 1252 namespace std _GLIBCXX_VISIBILITY(default) 1253 { 1254 _GLIBCXX_BEGIN_NAMESPACE_VERSION 1255 1256 template<typename _Iterator, typename _Container> 1257 _GLIBCXX20_CONSTEXPR 1258 _Iterator 1259 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it) 1260 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value) 1261 { return __it.base(); } 1262 1263 #if __cplusplus >= 201103L 1264 /** 1265 * @addtogroup iterators 1266 * @{ 1267 */ 1268 1269 #if __cplusplus > 201703L && __cpp_lib_concepts 1270 template<semiregular _Sent> 1271 class move_sentinel 1272 { 1273 public: 1274 constexpr 1275 move_sentinel() 1276 noexcept(is_nothrow_default_constructible_v<_Sent>) 1277 : _M_last() { } 1278 1279 constexpr explicit 1280 move_sentinel(_Sent __s) 1281 noexcept(is_nothrow_move_constructible_v<_Sent>) 1282 : _M_last(std::move(__s)) { } 1283 1284 template<typename _S2> requires convertible_to<const _S2&, _Sent> 1285 constexpr 1286 move_sentinel(const move_sentinel<_S2>& __s) 1287 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>) 1288 : _M_last(__s.base()) 1289 { } 1290 1291 template<typename _S2> requires assignable_from<_Sent&, const _S2&> 1292 constexpr move_sentinel& 1293 operator=(const move_sentinel<_S2>& __s) 1294 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>) 1295 { 1296 _M_last = __s.base(); 1297 return *this; 1298 } 1299 1300 constexpr _Sent 1301 base() const 1302 noexcept(is_nothrow_copy_constructible_v<_Sent>) 1303 { return _M_last; } 1304 1305 private: 1306 _Sent _M_last; 1307 }; 1308 #endif // C++20 1309 1310 namespace __detail 1311 { 1312 #if __cplusplus > 201703L && __cpp_lib_concepts 1313 template<typename _Iterator> 1314 struct __move_iter_cat 1315 { }; 1316 1317 template<typename _Iterator> 1318 requires requires { typename iterator_traits<_Iterator>::iterator_category; } 1319 struct __move_iter_cat<_Iterator> 1320 { 1321 using iterator_category 1322 = __clamp_iter_cat<typename iterator_traits<_Iterator>::iterator_category, 1323 random_access_iterator_tag>; 1324 }; 1325 #endif 1326 } 1327 1328 // 24.4.3 Move iterators 1329 /** 1330 * Class template move_iterator is an iterator adapter with the same 1331 * behavior as the underlying iterator except that its dereference 1332 * operator implicitly converts the value returned by the underlying 1333 * iterator's dereference operator to an rvalue reference. Some 1334 * generic algorithms can be called with move iterators to replace 1335 * copying with moving. 1336 */ 1337 template<typename _Iterator> 1338 class move_iterator 1339 #if __cplusplus > 201703L && __cpp_lib_concepts 1340 : public __detail::__move_iter_cat<_Iterator> 1341 #endif 1342 { 1343 _Iterator _M_current; 1344 1345 using __traits_type = iterator_traits<_Iterator>; 1346 #if ! (__cplusplus > 201703L && __cpp_lib_concepts) 1347 using __base_ref = typename __traits_type::reference; 1348 #endif 1349 1350 public: 1351 using iterator_type = _Iterator; 1352 1353 #if __cplusplus > 201703L && __cpp_lib_concepts 1354 using iterator_concept = input_iterator_tag; 1355 // iterator_category defined in __move_iter_cat 1356 using value_type = iter_value_t<_Iterator>; 1357 using difference_type = iter_difference_t<_Iterator>; 1358 using pointer = _Iterator; 1359 using reference = iter_rvalue_reference_t<_Iterator>; 1360 #else 1361 typedef typename __traits_type::iterator_category iterator_category; 1362 typedef typename __traits_type::value_type value_type; 1363 typedef typename __traits_type::difference_type difference_type; 1364 // NB: DR 680. 1365 typedef _Iterator pointer; 1366 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1367 // 2106. move_iterator wrapping iterators returning prvalues 1368 typedef typename conditional<is_reference<__base_ref>::value, 1369 typename remove_reference<__base_ref>::type&&, 1370 __base_ref>::type reference; 1371 #endif 1372 1373 _GLIBCXX17_CONSTEXPR 1374 move_iterator() 1375 : _M_current() { } 1376 1377 explicit _GLIBCXX17_CONSTEXPR 1378 move_iterator(iterator_type __i) 1379 : _M_current(std::move(__i)) { } 1380 1381 template<typename _Iter> 1382 _GLIBCXX17_CONSTEXPR 1383 move_iterator(const move_iterator<_Iter>& __i) 1384 : _M_current(__i.base()) { } 1385 1386 template<typename _Iter> 1387 _GLIBCXX17_CONSTEXPR 1388 move_iterator& operator=(const move_iterator<_Iter>& __i) 1389 { 1390 _M_current = __i.base(); 1391 return *this; 1392 } 1393 1394 #if __cplusplus <= 201703L 1395 _GLIBCXX17_CONSTEXPR iterator_type 1396 base() const 1397 { return _M_current; } 1398 #else 1399 constexpr const iterator_type& 1400 base() const & noexcept 1401 { return _M_current; } 1402 1403 constexpr iterator_type 1404 base() && 1405 { return std::move(_M_current); } 1406 #endif 1407 1408 _GLIBCXX17_CONSTEXPR reference 1409 operator*() const 1410 #if __cplusplus > 201703L && __cpp_lib_concepts 1411 { return ranges::iter_move(_M_current); } 1412 #else 1413 { return static_cast<reference>(*_M_current); } 1414 #endif 1415 1416 _GLIBCXX17_CONSTEXPR pointer 1417 operator->() const 1418 { return _M_current; } 1419 1420 _GLIBCXX17_CONSTEXPR move_iterator& 1421 operator++() 1422 { 1423 ++_M_current; 1424 return *this; 1425 } 1426 1427 _GLIBCXX17_CONSTEXPR move_iterator 1428 operator++(int) 1429 { 1430 move_iterator __tmp = *this; 1431 ++_M_current; 1432 return __tmp; 1433 } 1434 1435 #if __cpp_lib_concepts 1436 constexpr void 1437 operator++(int) requires (!forward_iterator<_Iterator>) 1438 { ++_M_current; } 1439 #endif 1440 1441 _GLIBCXX17_CONSTEXPR move_iterator& 1442 operator--() 1443 { 1444 --_M_current; 1445 return *this; 1446 } 1447 1448 _GLIBCXX17_CONSTEXPR move_iterator 1449 operator--(int) 1450 { 1451 move_iterator __tmp = *this; 1452 --_M_current; 1453 return __tmp; 1454 } 1455 1456 _GLIBCXX17_CONSTEXPR move_iterator 1457 operator+(difference_type __n) const 1458 { return move_iterator(_M_current + __n); } 1459 1460 _GLIBCXX17_CONSTEXPR move_iterator& 1461 operator+=(difference_type __n) 1462 { 1463 _M_current += __n; 1464 return *this; 1465 } 1466 1467 _GLIBCXX17_CONSTEXPR move_iterator 1468 operator-(difference_type __n) const 1469 { return move_iterator(_M_current - __n); } 1470 1471 _GLIBCXX17_CONSTEXPR move_iterator& 1472 operator-=(difference_type __n) 1473 { 1474 _M_current -= __n; 1475 return *this; 1476 } 1477 1478 _GLIBCXX17_CONSTEXPR reference 1479 operator[](difference_type __n) const 1480 #if __cplusplus > 201703L && __cpp_lib_concepts 1481 { return ranges::iter_move(_M_current + __n); } 1482 #else 1483 { return std::move(_M_current[__n]); } 1484 #endif 1485 1486 #if __cplusplus > 201703L && __cpp_lib_concepts 1487 template<sentinel_for<_Iterator> _Sent> 1488 friend constexpr bool 1489 operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y) 1490 { return __x.base() == __y.base(); } 1491 1492 template<sized_sentinel_for<_Iterator> _Sent> 1493 friend constexpr iter_difference_t<_Iterator> 1494 operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y) 1495 { return __x.base() - __y.base(); } 1496 1497 template<sized_sentinel_for<_Iterator> _Sent> 1498 friend constexpr iter_difference_t<_Iterator> 1499 operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y) 1500 { return __x.base() - __y.base(); } 1501 1502 friend constexpr iter_rvalue_reference_t<_Iterator> 1503 iter_move(const move_iterator& __i) 1504 noexcept(noexcept(ranges::iter_move(__i._M_current))) 1505 { return ranges::iter_move(__i._M_current); } 1506 1507 template<indirectly_swappable<_Iterator> _Iter2> 1508 friend constexpr void 1509 iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y) 1510 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) 1511 { return ranges::iter_swap(__x._M_current, __y._M_current); } 1512 #endif // C++20 1513 }; 1514 1515 template<typename _IteratorL, typename _IteratorR> 1516 inline _GLIBCXX17_CONSTEXPR bool 1517 operator==(const move_iterator<_IteratorL>& __x, 1518 const move_iterator<_IteratorR>& __y) 1519 #if __cplusplus > 201703L && __cpp_lib_concepts 1520 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; } 1521 #endif 1522 { return __x.base() == __y.base(); } 1523 1524 #if __cpp_lib_three_way_comparison 1525 template<typename _IteratorL, 1526 three_way_comparable_with<_IteratorL> _IteratorR> 1527 constexpr compare_three_way_result_t<_IteratorL, _IteratorR> 1528 operator<=>(const move_iterator<_IteratorL>& __x, 1529 const move_iterator<_IteratorR>& __y) 1530 { return __x.base() <=> __y.base(); } 1531 #else 1532 template<typename _IteratorL, typename _IteratorR> 1533 inline _GLIBCXX17_CONSTEXPR bool 1534 operator!=(const move_iterator<_IteratorL>& __x, 1535 const move_iterator<_IteratorR>& __y) 1536 { return !(__x == __y); } 1537 #endif 1538 1539 template<typename _IteratorL, typename _IteratorR> 1540 inline _GLIBCXX17_CONSTEXPR bool 1541 operator<(const move_iterator<_IteratorL>& __x, 1542 const move_iterator<_IteratorR>& __y) 1543 #if __cplusplus > 201703L && __cpp_lib_concepts 1544 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; } 1545 #endif 1546 { return __x.base() < __y.base(); } 1547 1548 template<typename _IteratorL, typename _IteratorR> 1549 inline _GLIBCXX17_CONSTEXPR bool 1550 operator<=(const move_iterator<_IteratorL>& __x, 1551 const move_iterator<_IteratorR>& __y) 1552 #if __cplusplus > 201703L && __cpp_lib_concepts 1553 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; } 1554 #endif 1555 { return !(__y < __x); } 1556 1557 template<typename _IteratorL, typename _IteratorR> 1558 inline _GLIBCXX17_CONSTEXPR bool 1559 operator>(const move_iterator<_IteratorL>& __x, 1560 const move_iterator<_IteratorR>& __y) 1561 #if __cplusplus > 201703L && __cpp_lib_concepts 1562 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; } 1563 #endif 1564 { return __y < __x; } 1565 1566 template<typename _IteratorL, typename _IteratorR> 1567 inline _GLIBCXX17_CONSTEXPR bool 1568 operator>=(const move_iterator<_IteratorL>& __x, 1569 const move_iterator<_IteratorR>& __y) 1570 #if __cplusplus > 201703L && __cpp_lib_concepts 1571 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; } 1572 #endif 1573 { return !(__x < __y); } 1574 1575 // Note: See __normal_iterator operators note from Gaby to understand 1576 // why we have these extra overloads for some move_iterator operators. 1577 1578 template<typename _Iterator> 1579 inline _GLIBCXX17_CONSTEXPR bool 1580 operator==(const move_iterator<_Iterator>& __x, 1581 const move_iterator<_Iterator>& __y) 1582 { return __x.base() == __y.base(); } 1583 1584 #if __cpp_lib_three_way_comparison 1585 template<three_way_comparable _Iterator> 1586 constexpr compare_three_way_result_t<_Iterator> 1587 operator<=>(const move_iterator<_Iterator>& __x, 1588 const move_iterator<_Iterator>& __y) 1589 { return __x.base() <=> __y.base(); } 1590 #else 1591 template<typename _Iterator> 1592 inline _GLIBCXX17_CONSTEXPR bool 1593 operator!=(const move_iterator<_Iterator>& __x, 1594 const move_iterator<_Iterator>& __y) 1595 { return !(__x == __y); } 1596 1597 template<typename _Iterator> 1598 inline _GLIBCXX17_CONSTEXPR bool 1599 operator<(const move_iterator<_Iterator>& __x, 1600 const move_iterator<_Iterator>& __y) 1601 { return __x.base() < __y.base(); } 1602 1603 template<typename _Iterator> 1604 inline _GLIBCXX17_CONSTEXPR bool 1605 operator<=(const move_iterator<_Iterator>& __x, 1606 const move_iterator<_Iterator>& __y) 1607 { return !(__y < __x); } 1608 1609 template<typename _Iterator> 1610 inline _GLIBCXX17_CONSTEXPR bool 1611 operator>(const move_iterator<_Iterator>& __x, 1612 const move_iterator<_Iterator>& __y) 1613 { return __y < __x; } 1614 1615 template<typename _Iterator> 1616 inline _GLIBCXX17_CONSTEXPR bool 1617 operator>=(const move_iterator<_Iterator>& __x, 1618 const move_iterator<_Iterator>& __y) 1619 { return !(__x < __y); } 1620 #endif // ! C++20 1621 1622 // DR 685. 1623 template<typename _IteratorL, typename _IteratorR> 1624 inline _GLIBCXX17_CONSTEXPR auto 1625 operator-(const move_iterator<_IteratorL>& __x, 1626 const move_iterator<_IteratorR>& __y) 1627 -> decltype(__x.base() - __y.base()) 1628 { return __x.base() - __y.base(); } 1629 1630 template<typename _Iterator> 1631 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 1632 operator+(typename move_iterator<_Iterator>::difference_type __n, 1633 const move_iterator<_Iterator>& __x) 1634 { return __x + __n; } 1635 1636 template<typename _Iterator> 1637 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 1638 make_move_iterator(_Iterator __i) 1639 { return move_iterator<_Iterator>(std::move(__i)); } 1640 1641 template<typename _Iterator, typename _ReturnType 1642 = typename conditional<__move_if_noexcept_cond 1643 <typename iterator_traits<_Iterator>::value_type>::value, 1644 _Iterator, move_iterator<_Iterator>>::type> 1645 inline _GLIBCXX17_CONSTEXPR _ReturnType 1646 __make_move_if_noexcept_iterator(_Iterator __i) 1647 { return _ReturnType(__i); } 1648 1649 // Overload for pointers that matches std::move_if_noexcept more closely, 1650 // returning a constant iterator when we don't want to move. 1651 template<typename _Tp, typename _ReturnType 1652 = typename conditional<__move_if_noexcept_cond<_Tp>::value, 1653 const _Tp*, move_iterator<_Tp*>>::type> 1654 inline _GLIBCXX17_CONSTEXPR _ReturnType 1655 __make_move_if_noexcept_iterator(_Tp* __i) 1656 { return _ReturnType(__i); } 1657 1658 #if __cplusplus > 201703L && __cpp_lib_concepts 1659 // [iterators.common] Common iterators 1660 1661 namespace __detail 1662 { 1663 template<typename _It> 1664 concept __common_iter_has_arrow = indirectly_readable<const _It> 1665 && (requires(const _It& __it) { __it.operator->(); } 1666 || is_reference_v<iter_reference_t<_It>> 1667 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>); 1668 1669 template<typename _It> 1670 concept __common_iter_use_postfix_proxy 1671 = (!requires (_It& __i) { { *__i++ } -> __can_reference; }) 1672 && constructible_from<iter_value_t<_It>, iter_reference_t<_It>> 1673 && move_constructible<iter_value_t<_It>>; 1674 } // namespace __detail 1675 1676 /// An iterator/sentinel adaptor for representing a non-common range. 1677 template<input_or_output_iterator _It, sentinel_for<_It> _Sent> 1678 requires (!same_as<_It, _Sent>) && copyable<_It> 1679 class common_iterator 1680 { 1681 template<typename _Tp, typename _Up> 1682 static constexpr bool 1683 _S_noexcept1() 1684 { 1685 if constexpr (is_trivially_default_constructible_v<_Tp>) 1686 return is_nothrow_assignable_v<_Tp&, _Up>; 1687 else 1688 return is_nothrow_constructible_v<_Tp, _Up>; 1689 } 1690 1691 template<typename _It2, typename _Sent2> 1692 static constexpr bool 1693 _S_noexcept() 1694 { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); } 1695 1696 class __arrow_proxy 1697 { 1698 iter_value_t<_It> _M_keep; 1699 1700 constexpr 1701 __arrow_proxy(iter_reference_t<_It>&& __x) 1702 : _M_keep(std::move(__x)) { } 1703 1704 friend class common_iterator; 1705 1706 public: 1707 constexpr const iter_value_t<_It>* 1708 operator->() const noexcept 1709 { return std::__addressof(_M_keep); } 1710 }; 1711 1712 class __postfix_proxy 1713 { 1714 iter_value_t<_It> _M_keep; 1715 1716 constexpr 1717 __postfix_proxy(iter_reference_t<_It>&& __x) 1718 : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { } 1719 1720 friend class common_iterator; 1721 1722 public: 1723 constexpr const iter_value_t<_It>& 1724 operator*() const noexcept 1725 { return _M_keep; } 1726 }; 1727 1728 public: 1729 constexpr 1730 common_iterator() 1731 noexcept(is_nothrow_default_constructible_v<_It>) 1732 requires default_initializable<_It> 1733 : _M_it(), _M_index(0) 1734 { } 1735 1736 constexpr 1737 common_iterator(_It __i) 1738 noexcept(is_nothrow_move_constructible_v<_It>) 1739 : _M_it(std::move(__i)), _M_index(0) 1740 { } 1741 1742 constexpr 1743 common_iterator(_Sent __s) 1744 noexcept(is_nothrow_move_constructible_v<_Sent>) 1745 : _M_sent(std::move(__s)), _M_index(1) 1746 { } 1747 1748 template<typename _It2, typename _Sent2> 1749 requires convertible_to<const _It2&, _It> 1750 && convertible_to<const _Sent2&, _Sent> 1751 constexpr 1752 common_iterator(const common_iterator<_It2, _Sent2>& __x) 1753 noexcept(_S_noexcept<const _It2&, const _Sent2&>()) 1754 : _M_valueless(), _M_index(__x._M_index) 1755 { 1756 __glibcxx_assert(__x._M_has_value()); 1757 if (_M_index == 0) 1758 { 1759 if constexpr (is_trivially_default_constructible_v<_It>) 1760 _M_it = std::move(__x._M_it); 1761 else 1762 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it); 1763 } 1764 else if (_M_index == 1) 1765 { 1766 if constexpr (is_trivially_default_constructible_v<_Sent>) 1767 _M_sent = std::move(__x._M_sent); 1768 else 1769 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent); 1770 } 1771 } 1772 1773 constexpr 1774 common_iterator(const common_iterator& __x) 1775 noexcept(_S_noexcept<const _It&, const _Sent&>()) 1776 : _M_valueless(), _M_index(__x._M_index) 1777 { 1778 if (_M_index == 0) 1779 { 1780 if constexpr (is_trivially_default_constructible_v<_It>) 1781 _M_it = __x._M_it; 1782 else 1783 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it); 1784 } 1785 else if (_M_index == 1) 1786 { 1787 if constexpr (is_trivially_default_constructible_v<_Sent>) 1788 _M_sent = __x._M_sent; 1789 else 1790 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent); 1791 } 1792 } 1793 1794 constexpr 1795 common_iterator(common_iterator&& __x) 1796 noexcept(_S_noexcept<_It, _Sent>()) 1797 : _M_valueless(), _M_index(__x._M_index) 1798 { 1799 if (_M_index == 0) 1800 { 1801 if constexpr (is_trivially_default_constructible_v<_It>) 1802 _M_it = std::move(__x._M_it); 1803 else 1804 ::new((void*)std::__addressof(_M_it)) _It(std::move(__x._M_it)); 1805 } 1806 else if (_M_index == 1) 1807 { 1808 if constexpr (is_trivially_default_constructible_v<_Sent>) 1809 _M_sent = std::move(__x._M_sent); 1810 else 1811 ::new((void*)std::__addressof(_M_sent)) 1812 _Sent(std::move(__x._M_sent)); 1813 } 1814 } 1815 1816 constexpr common_iterator& 1817 operator=(const common_iterator&) = default; 1818 1819 common_iterator& 1820 operator=(const common_iterator& __x) 1821 noexcept(is_nothrow_copy_assignable_v<_It> 1822 && is_nothrow_copy_assignable_v<_Sent> 1823 && is_nothrow_copy_constructible_v<_It> 1824 && is_nothrow_copy_constructible_v<_Sent>) 1825 requires (!is_trivially_copy_assignable_v<_It> 1826 || !is_trivially_copy_assignable_v<_Sent>) 1827 { 1828 _M_assign(__x); 1829 return *this; 1830 } 1831 1832 constexpr common_iterator& 1833 operator=(common_iterator&&) = default; 1834 1835 common_iterator& 1836 operator=(common_iterator&& __x) 1837 noexcept(is_nothrow_move_assignable_v<_It> 1838 && is_nothrow_move_assignable_v<_Sent> 1839 && is_nothrow_move_constructible_v<_It> 1840 && is_nothrow_move_constructible_v<_Sent>) 1841 requires (!is_trivially_move_assignable_v<_It> 1842 || !is_trivially_move_assignable_v<_Sent>) 1843 { 1844 _M_assign(std::move(__x)); 1845 return *this; 1846 } 1847 1848 template<typename _It2, typename _Sent2> 1849 requires convertible_to<const _It2&, _It> 1850 && convertible_to<const _Sent2&, _Sent> 1851 && assignable_from<_It&, const _It2&> 1852 && assignable_from<_Sent&, const _Sent2&> 1853 common_iterator& 1854 operator=(const common_iterator<_It2, _Sent2>& __x) 1855 noexcept(is_nothrow_constructible_v<_It, const _It2&> 1856 && is_nothrow_constructible_v<_Sent, const _Sent2&> 1857 && is_nothrow_assignable_v<_It&, const _It2&> 1858 && is_nothrow_assignable_v<_Sent&, const _Sent2&>) 1859 { 1860 __glibcxx_assert(__x._M_has_value()); 1861 _M_assign(__x); 1862 return *this; 1863 } 1864 1865 ~common_iterator() 1866 { 1867 if (_M_index == 0) 1868 _M_it.~_It(); 1869 else if (_M_index == 1) 1870 _M_sent.~_Sent(); 1871 } 1872 1873 decltype(auto) 1874 operator*() 1875 { 1876 __glibcxx_assert(_M_index == 0); 1877 return *_M_it; 1878 } 1879 1880 decltype(auto) 1881 operator*() const requires __detail::__dereferenceable<const _It> 1882 { 1883 __glibcxx_assert(_M_index == 0); 1884 return *_M_it; 1885 } 1886 1887 decltype(auto) 1888 operator->() const requires __detail::__common_iter_has_arrow<_It> 1889 { 1890 __glibcxx_assert(_M_index == 0); 1891 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); }) 1892 return _M_it; 1893 else if constexpr (is_reference_v<iter_reference_t<_It>>) 1894 { 1895 auto&& __tmp = *_M_it; 1896 return std::__addressof(__tmp); 1897 } 1898 else 1899 return __arrow_proxy{*_M_it}; 1900 } 1901 1902 common_iterator& 1903 operator++() 1904 { 1905 __glibcxx_assert(_M_index == 0); 1906 ++_M_it; 1907 return *this; 1908 } 1909 1910 decltype(auto) 1911 operator++(int) 1912 { 1913 __glibcxx_assert(_M_index == 0); 1914 if constexpr (forward_iterator<_It>) 1915 { 1916 common_iterator __tmp = *this; 1917 ++*this; 1918 return __tmp; 1919 } 1920 else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>) 1921 return _M_it++; 1922 else 1923 { 1924 __postfix_proxy __p(**this); 1925 ++*this; 1926 return __p; 1927 } 1928 } 1929 1930 template<typename _It2, sentinel_for<_It> _Sent2> 1931 requires sentinel_for<_Sent, _It2> 1932 friend bool 1933 operator==(const common_iterator& __x, 1934 const common_iterator<_It2, _Sent2>& __y) 1935 { 1936 switch(__x._M_index << 2 | __y._M_index) 1937 { 1938 case 0b0000: 1939 case 0b0101: 1940 return true; 1941 case 0b0001: 1942 return __x._M_it == __y._M_sent; 1943 case 0b0100: 1944 return __x._M_sent == __y._M_it; 1945 default: 1946 __glibcxx_assert(__x._M_has_value()); 1947 __glibcxx_assert(__y._M_has_value()); 1948 __builtin_unreachable(); 1949 } 1950 } 1951 1952 template<typename _It2, sentinel_for<_It> _Sent2> 1953 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2> 1954 friend bool 1955 operator==(const common_iterator& __x, 1956 const common_iterator<_It2, _Sent2>& __y) 1957 { 1958 switch(__x._M_index << 2 | __y._M_index) 1959 { 1960 case 0b0101: 1961 return true; 1962 case 0b0000: 1963 return __x._M_it == __y._M_it; 1964 case 0b0001: 1965 return __x._M_it == __y._M_sent; 1966 case 0b0100: 1967 return __x._M_sent == __y._M_it; 1968 default: 1969 __glibcxx_assert(__x._M_has_value()); 1970 __glibcxx_assert(__y._M_has_value()); 1971 __builtin_unreachable(); 1972 } 1973 } 1974 1975 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2> 1976 requires sized_sentinel_for<_Sent, _It2> 1977 friend iter_difference_t<_It2> 1978 operator-(const common_iterator& __x, 1979 const common_iterator<_It2, _Sent2>& __y) 1980 { 1981 switch(__x._M_index << 2 | __y._M_index) 1982 { 1983 case 0b0101: 1984 return 0; 1985 case 0b0000: 1986 return __x._M_it - __y._M_it; 1987 case 0b0001: 1988 return __x._M_it - __y._M_sent; 1989 case 0b0100: 1990 return __x._M_sent - __y._M_it; 1991 default: 1992 __glibcxx_assert(__x._M_has_value()); 1993 __glibcxx_assert(__y._M_has_value()); 1994 __builtin_unreachable(); 1995 } 1996 } 1997 1998 friend iter_rvalue_reference_t<_It> 1999 iter_move(const common_iterator& __i) 2000 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>()))) 2001 requires input_iterator<_It> 2002 { 2003 __glibcxx_assert(__i._M_index == 0); 2004 return ranges::iter_move(__i._M_it); 2005 } 2006 2007 template<indirectly_swappable<_It> _It2, typename _Sent2> 2008 friend void 2009 iter_swap(const common_iterator& __x, 2010 const common_iterator<_It2, _Sent2>& __y) 2011 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(), 2012 std::declval<const _It2&>()))) 2013 { 2014 __glibcxx_assert(__x._M_index == 0); 2015 __glibcxx_assert(__y._M_index == 0); 2016 return ranges::iter_swap(__x._M_it, __y._M_it); 2017 } 2018 2019 private: 2020 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2> 2021 requires (!same_as<_It2, _Sent2>) && copyable<_It2> 2022 friend class common_iterator; 2023 2024 bool 2025 _M_has_value() const noexcept { return _M_index != _S_valueless; } 2026 2027 template<typename _CIt> 2028 void 2029 _M_assign(_CIt&& __x) 2030 { 2031 if (_M_index == __x._M_index) 2032 { 2033 if (_M_index == 0) 2034 _M_it = std::forward<_CIt>(__x)._M_it; 2035 else if (_M_index == 1) 2036 _M_sent = std::forward<_CIt>(__x)._M_sent; 2037 } 2038 else 2039 { 2040 if (_M_index == 0) 2041 _M_it.~_It(); 2042 else if (_M_index == 1) 2043 _M_sent.~_Sent(); 2044 _M_index = _S_valueless; 2045 2046 if (__x._M_index == 0) 2047 ::new((void*)std::__addressof(_M_it)) 2048 _It(std::forward<_CIt>(__x)._M_it); 2049 else if (__x._M_index == 1) 2050 ::new((void*)std::__addressof(_M_sent)) 2051 _Sent(std::forward<_CIt>(__x)._M_sent); 2052 _M_index = __x._M_index; 2053 } 2054 } 2055 2056 union 2057 { 2058 _It _M_it; 2059 _Sent _M_sent; 2060 unsigned char _M_valueless; 2061 }; 2062 unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless 2063 2064 static constexpr unsigned char _S_valueless{2}; 2065 }; 2066 2067 template<typename _It, typename _Sent> 2068 struct incrementable_traits<common_iterator<_It, _Sent>> 2069 { 2070 using difference_type = iter_difference_t<_It>; 2071 }; 2072 2073 template<input_iterator _It, typename _Sent> 2074 struct iterator_traits<common_iterator<_It, _Sent>> 2075 { 2076 private: 2077 template<typename _Iter> 2078 struct __ptr 2079 { 2080 using type = void; 2081 }; 2082 2083 template<typename _Iter> 2084 requires __detail::__common_iter_has_arrow<_Iter> 2085 struct __ptr<_Iter> 2086 { 2087 using _CIter = common_iterator<_Iter, _Sent>; 2088 using type = decltype(std::declval<const _CIter&>().operator->()); 2089 }; 2090 2091 static auto 2092 _S_iter_cat() 2093 { 2094 using _Traits = iterator_traits<_It>; 2095 if constexpr (requires { requires derived_from<typename _Traits::iterator_category, 2096 forward_iterator_tag>; }) 2097 return forward_iterator_tag{}; 2098 else 2099 return input_iterator_tag{}; 2100 } 2101 2102 public: 2103 using iterator_concept = conditional_t<forward_iterator<_It>, 2104 forward_iterator_tag, input_iterator_tag>; 2105 using iterator_category = decltype(_S_iter_cat()); 2106 using value_type = iter_value_t<_It>; 2107 using difference_type = iter_difference_t<_It>; 2108 using pointer = typename __ptr<_It>::type; 2109 using reference = iter_reference_t<_It>; 2110 }; 2111 2112 // [iterators.counted] Counted iterators 2113 2114 namespace __detail 2115 { 2116 template<typename _It> 2117 struct __counted_iter_value_type 2118 { }; 2119 2120 template<indirectly_readable _It> 2121 struct __counted_iter_value_type<_It> 2122 { using value_type = iter_value_t<_It>; }; 2123 2124 template<typename _It> 2125 struct __counted_iter_concept 2126 { }; 2127 2128 template<typename _It> 2129 requires requires { typename _It::iterator_concept; } 2130 struct __counted_iter_concept<_It> 2131 { using iterator_concept = typename _It::iterator_concept; }; 2132 2133 template<typename _It> 2134 struct __counted_iter_cat 2135 { }; 2136 2137 template<typename _It> 2138 requires requires { typename _It::iterator_category; } 2139 struct __counted_iter_cat<_It> 2140 { using iterator_category = typename _It::iterator_category; }; 2141 } 2142 2143 /// An iterator adaptor that keeps track of the distance to the end. 2144 template<input_or_output_iterator _It> 2145 class counted_iterator 2146 : public __detail::__counted_iter_value_type<_It>, 2147 public __detail::__counted_iter_concept<_It>, 2148 public __detail::__counted_iter_cat<_It> 2149 { 2150 public: 2151 using iterator_type = _It; 2152 // value_type defined in __counted_iter_value_type 2153 using difference_type = iter_difference_t<_It>; 2154 // iterator_concept defined in __counted_iter_concept 2155 // iterator_category defined in __counted_iter_cat 2156 2157 constexpr counted_iterator() requires default_initializable<_It> = default; 2158 2159 constexpr 2160 counted_iterator(_It __i, iter_difference_t<_It> __n) 2161 : _M_current(std::move(__i)), _M_length(__n) 2162 { __glibcxx_assert(__n >= 0); } 2163 2164 template<typename _It2> 2165 requires convertible_to<const _It2&, _It> 2166 constexpr 2167 counted_iterator(const counted_iterator<_It2>& __x) 2168 : _M_current(__x._M_current), _M_length(__x._M_length) 2169 { } 2170 2171 template<typename _It2> 2172 requires assignable_from<_It&, const _It2&> 2173 constexpr counted_iterator& 2174 operator=(const counted_iterator<_It2>& __x) 2175 { 2176 _M_current = __x._M_current; 2177 _M_length = __x._M_length; 2178 return *this; 2179 } 2180 2181 constexpr const _It& 2182 base() const & noexcept 2183 { return _M_current; } 2184 2185 constexpr _It 2186 base() && 2187 noexcept(is_nothrow_move_constructible_v<_It>) 2188 { return std::move(_M_current); } 2189 2190 constexpr iter_difference_t<_It> 2191 count() const noexcept { return _M_length; } 2192 2193 constexpr decltype(auto) 2194 operator*() 2195 noexcept(noexcept(*_M_current)) 2196 { return *_M_current; } 2197 2198 constexpr decltype(auto) 2199 operator*() const 2200 noexcept(noexcept(*_M_current)) 2201 requires __detail::__dereferenceable<const _It> 2202 { return *_M_current; } 2203 2204 constexpr auto 2205 operator->() const noexcept 2206 requires contiguous_iterator<_It> 2207 { return std::to_address(_M_current); } 2208 2209 constexpr counted_iterator& 2210 operator++() 2211 { 2212 __glibcxx_assert(_M_length > 0); 2213 ++_M_current; 2214 --_M_length; 2215 return *this; 2216 } 2217 2218 decltype(auto) 2219 operator++(int) 2220 { 2221 __glibcxx_assert(_M_length > 0); 2222 --_M_length; 2223 __try 2224 { 2225 return _M_current++; 2226 } __catch(...) { 2227 ++_M_length; 2228 __throw_exception_again; 2229 } 2230 2231 } 2232 2233 constexpr counted_iterator 2234 operator++(int) requires forward_iterator<_It> 2235 { 2236 auto __tmp = *this; 2237 ++*this; 2238 return __tmp; 2239 } 2240 2241 constexpr counted_iterator& 2242 operator--() requires bidirectional_iterator<_It> 2243 { 2244 --_M_current; 2245 ++_M_length; 2246 return *this; 2247 } 2248 2249 constexpr counted_iterator 2250 operator--(int) requires bidirectional_iterator<_It> 2251 { 2252 auto __tmp = *this; 2253 --*this; 2254 return __tmp; 2255 } 2256 2257 constexpr counted_iterator 2258 operator+(iter_difference_t<_It> __n) const 2259 requires random_access_iterator<_It> 2260 { return counted_iterator(_M_current + __n, _M_length - __n); } 2261 2262 friend constexpr counted_iterator 2263 operator+(iter_difference_t<_It> __n, const counted_iterator& __x) 2264 requires random_access_iterator<_It> 2265 { return __x + __n; } 2266 2267 constexpr counted_iterator& 2268 operator+=(iter_difference_t<_It> __n) 2269 requires random_access_iterator<_It> 2270 { 2271 __glibcxx_assert(__n <= _M_length); 2272 _M_current += __n; 2273 _M_length -= __n; 2274 return *this; 2275 } 2276 2277 constexpr counted_iterator 2278 operator-(iter_difference_t<_It> __n) const 2279 requires random_access_iterator<_It> 2280 { return counted_iterator(_M_current - __n, _M_length + __n); } 2281 2282 template<common_with<_It> _It2> 2283 friend constexpr iter_difference_t<_It2> 2284 operator-(const counted_iterator& __x, 2285 const counted_iterator<_It2>& __y) 2286 { return __y._M_length - __x._M_length; } 2287 2288 friend constexpr iter_difference_t<_It> 2289 operator-(const counted_iterator& __x, default_sentinel_t) 2290 { return -__x._M_length; } 2291 2292 friend constexpr iter_difference_t<_It> 2293 operator-(default_sentinel_t, const counted_iterator& __y) 2294 { return __y._M_length; } 2295 2296 constexpr counted_iterator& 2297 operator-=(iter_difference_t<_It> __n) 2298 requires random_access_iterator<_It> 2299 { 2300 __glibcxx_assert(-__n <= _M_length); 2301 _M_current -= __n; 2302 _M_length += __n; 2303 return *this; 2304 } 2305 2306 constexpr decltype(auto) 2307 operator[](iter_difference_t<_It> __n) const 2308 noexcept(noexcept(_M_current[__n])) 2309 requires random_access_iterator<_It> 2310 { 2311 __glibcxx_assert(__n < _M_length); 2312 return _M_current[__n]; 2313 } 2314 2315 template<common_with<_It> _It2> 2316 friend constexpr bool 2317 operator==(const counted_iterator& __x, 2318 const counted_iterator<_It2>& __y) 2319 { return __x._M_length == __y._M_length; } 2320 2321 friend constexpr bool 2322 operator==(const counted_iterator& __x, default_sentinel_t) 2323 { return __x._M_length == 0; } 2324 2325 template<common_with<_It> _It2> 2326 friend constexpr strong_ordering 2327 operator<=>(const counted_iterator& __x, 2328 const counted_iterator<_It2>& __y) 2329 { return __y._M_length <=> __x._M_length; } 2330 2331 friend constexpr iter_rvalue_reference_t<_It> 2332 iter_move(const counted_iterator& __i) 2333 noexcept(noexcept(ranges::iter_move(__i._M_current))) 2334 requires input_iterator<_It> 2335 { return ranges::iter_move(__i._M_current); } 2336 2337 template<indirectly_swappable<_It> _It2> 2338 friend constexpr void 2339 iter_swap(const counted_iterator& __x, 2340 const counted_iterator<_It2>& __y) 2341 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) 2342 { ranges::iter_swap(__x._M_current, __y._M_current); } 2343 2344 private: 2345 template<input_or_output_iterator _It2> friend class counted_iterator; 2346 2347 _It _M_current = _It(); 2348 iter_difference_t<_It> _M_length = 0; 2349 }; 2350 2351 template<input_iterator _It> 2352 requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>> 2353 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It> 2354 { 2355 using pointer = conditional_t<contiguous_iterator<_It>, 2356 add_pointer_t<iter_reference_t<_It>>, 2357 void>; 2358 }; 2359 #endif // C++20 2360 2361 /// @} group iterators 2362 2363 template<typename _Iterator> 2364 _GLIBCXX20_CONSTEXPR 2365 auto 2366 __niter_base(move_iterator<_Iterator> __it) 2367 -> decltype(make_move_iterator(__niter_base(__it.base()))) 2368 { return make_move_iterator(__niter_base(__it.base())); } 2369 2370 template<typename _Iterator> 2371 struct __is_move_iterator<move_iterator<_Iterator> > 2372 { 2373 enum { __value = 1 }; 2374 typedef __true_type __type; 2375 }; 2376 2377 template<typename _Iterator> 2378 _GLIBCXX20_CONSTEXPR 2379 auto 2380 __miter_base(move_iterator<_Iterator> __it) 2381 -> decltype(__miter_base(__it.base())) 2382 { return __miter_base(__it.base()); } 2383 2384 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 2385 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 2386 std::__make_move_if_noexcept_iterator(_Iter) 2387 #else 2388 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 2389 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 2390 #endif // C++11 2391 2392 #if __cpp_deduction_guides >= 201606 2393 // These helper traits are used for deduction guides 2394 // of associative containers. 2395 template<typename _InputIterator> 2396 using __iter_key_t = remove_const_t< 2397 typename iterator_traits<_InputIterator>::value_type::first_type>; 2398 2399 template<typename _InputIterator> 2400 using __iter_val_t = 2401 typename iterator_traits<_InputIterator>::value_type::second_type; 2402 2403 template<typename _T1, typename _T2> 2404 struct pair; 2405 2406 template<typename _InputIterator> 2407 using __iter_to_alloc_t = 2408 pair<add_const_t<__iter_key_t<_InputIterator>>, 2409 __iter_val_t<_InputIterator>>; 2410 #endif // __cpp_deduction_guides 2411 2412 _GLIBCXX_END_NAMESPACE_VERSION 2413 } // namespace 2414 2415 #ifdef _GLIBCXX_DEBUG 2416 # include <debug/stl_iterator.h> 2417 #endif 2418 2419 #endif 2420