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