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 if (_M_index == 0) 1757 { 1758 if constexpr (is_trivially_default_constructible_v<_It>) 1759 _M_it = std::move(__x._M_it); 1760 else 1761 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it); 1762 } 1763 else if (_M_index == 1) 1764 { 1765 if constexpr (is_trivially_default_constructible_v<_Sent>) 1766 _M_sent = std::move(__x._M_sent); 1767 else 1768 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent); 1769 } 1770 } 1771 1772 constexpr 1773 common_iterator(const common_iterator& __x) 1774 noexcept(_S_noexcept<const _It&, const _Sent&>()) 1775 : _M_valueless(), _M_index(__x._M_index) 1776 { 1777 if (_M_index == 0) 1778 { 1779 if constexpr (is_trivially_default_constructible_v<_It>) 1780 _M_it = std::move(__x._M_it); 1781 else 1782 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it); 1783 } 1784 else if (_M_index == 1) 1785 { 1786 if constexpr (is_trivially_default_constructible_v<_Sent>) 1787 _M_sent = std::move(__x._M_sent); 1788 else 1789 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent); 1790 } 1791 } 1792 1793 common_iterator& 1794 operator=(const common_iterator& __x) 1795 noexcept(is_nothrow_copy_assignable_v<_It> 1796 && is_nothrow_copy_assignable_v<_Sent> 1797 && is_nothrow_copy_constructible_v<_It> 1798 && is_nothrow_copy_constructible_v<_Sent>) 1799 { 1800 return this->operator=<_It, _Sent>(__x); 1801 } 1802 1803 template<typename _It2, typename _Sent2> 1804 requires convertible_to<const _It2&, _It> 1805 && convertible_to<const _Sent2&, _Sent> 1806 && assignable_from<_It&, const _It2&> 1807 && assignable_from<_Sent&, const _Sent2&> 1808 common_iterator& 1809 operator=(const common_iterator<_It2, _Sent2>& __x) 1810 noexcept(is_nothrow_constructible_v<_It, const _It2&> 1811 && is_nothrow_constructible_v<_Sent, const _Sent2&> 1812 && is_nothrow_assignable_v<_It, const _It2&> 1813 && is_nothrow_assignable_v<_Sent, const _Sent2&>) 1814 { 1815 switch(_M_index << 2 | __x._M_index) 1816 { 1817 case 0b0000: 1818 _M_it = __x._M_it; 1819 break; 1820 case 0b0101: 1821 _M_sent = __x._M_sent; 1822 break; 1823 case 0b0001: 1824 _M_it.~_It(); 1825 _M_index = -1; 1826 [[fallthrough]]; 1827 case 0b1001: 1828 ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent); 1829 _M_index = 1; 1830 break; 1831 case 0b0100: 1832 _M_sent.~_Sent(); 1833 _M_index = -1; 1834 [[fallthrough]]; 1835 case 0b1000: 1836 ::new((void*)std::__addressof(_M_it)) _It(__x._M_it); 1837 _M_index = 0; 1838 break; 1839 default: 1840 __glibcxx_assert(__x._M_has_value()); 1841 __builtin_unreachable(); 1842 } 1843 return *this; 1844 } 1845 1846 ~common_iterator() 1847 { 1848 switch (_M_index) 1849 { 1850 case 0: 1851 _M_it.~_It(); 1852 break; 1853 case 1: 1854 _M_sent.~_Sent(); 1855 break; 1856 } 1857 } 1858 1859 decltype(auto) 1860 operator*() 1861 { 1862 __glibcxx_assert(_M_index == 0); 1863 return *_M_it; 1864 } 1865 1866 decltype(auto) 1867 operator*() const requires __detail::__dereferenceable<const _It> 1868 { 1869 __glibcxx_assert(_M_index == 0); 1870 return *_M_it; 1871 } 1872 1873 decltype(auto) 1874 operator->() const requires __detail::__common_iter_has_arrow<_It> 1875 { 1876 __glibcxx_assert(_M_index == 0); 1877 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); }) 1878 return _M_it; 1879 else if constexpr (is_reference_v<iter_reference_t<_It>>) 1880 { 1881 auto&& __tmp = *_M_it; 1882 return std::__addressof(__tmp); 1883 } 1884 else 1885 return __arrow_proxy{*_M_it}; 1886 } 1887 1888 common_iterator& 1889 operator++() 1890 { 1891 __glibcxx_assert(_M_index == 0); 1892 ++_M_it; 1893 return *this; 1894 } 1895 1896 decltype(auto) 1897 operator++(int) 1898 { 1899 __glibcxx_assert(_M_index == 0); 1900 if constexpr (forward_iterator<_It>) 1901 { 1902 common_iterator __tmp = *this; 1903 ++*this; 1904 return __tmp; 1905 } 1906 else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>) 1907 return _M_it++; 1908 else 1909 { 1910 __postfix_proxy __p(**this); 1911 ++*this; 1912 return __p; 1913 } 1914 } 1915 1916 template<typename _It2, sentinel_for<_It> _Sent2> 1917 requires sentinel_for<_Sent, _It2> 1918 friend bool 1919 operator==(const common_iterator& __x, 1920 const common_iterator<_It2, _Sent2>& __y) 1921 { 1922 switch(__x._M_index << 2 | __y._M_index) 1923 { 1924 case 0b0000: 1925 case 0b0101: 1926 return true; 1927 case 0b0001: 1928 return __x._M_it == __y._M_sent; 1929 case 0b0100: 1930 return __x._M_sent == __y._M_it; 1931 default: 1932 __glibcxx_assert(__x._M_has_value()); 1933 __glibcxx_assert(__y._M_has_value()); 1934 __builtin_unreachable(); 1935 } 1936 } 1937 1938 template<typename _It2, sentinel_for<_It> _Sent2> 1939 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2> 1940 friend bool 1941 operator==(const common_iterator& __x, 1942 const common_iterator<_It2, _Sent2>& __y) 1943 { 1944 switch(__x._M_index << 2 | __y._M_index) 1945 { 1946 case 0b0101: 1947 return true; 1948 case 0b0000: 1949 return __x._M_it == __y._M_it; 1950 case 0b0001: 1951 return __x._M_it == __y._M_sent; 1952 case 0b0100: 1953 return __x._M_sent == __y._M_it; 1954 default: 1955 __glibcxx_assert(__x._M_has_value()); 1956 __glibcxx_assert(__y._M_has_value()); 1957 __builtin_unreachable(); 1958 } 1959 } 1960 1961 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2> 1962 requires sized_sentinel_for<_Sent, _It2> 1963 friend iter_difference_t<_It2> 1964 operator-(const common_iterator& __x, 1965 const common_iterator<_It2, _Sent2>& __y) 1966 { 1967 switch(__x._M_index << 2 | __y._M_index) 1968 { 1969 case 0b0101: 1970 return 0; 1971 case 0b0000: 1972 return __x._M_it - __y._M_it; 1973 case 0b0001: 1974 return __x._M_it - __y._M_sent; 1975 case 0b0100: 1976 return __x._M_sent - __y._M_it; 1977 default: 1978 __glibcxx_assert(__x._M_has_value()); 1979 __glibcxx_assert(__y._M_has_value()); 1980 __builtin_unreachable(); 1981 } 1982 } 1983 1984 friend iter_rvalue_reference_t<_It> 1985 iter_move(const common_iterator& __i) 1986 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>()))) 1987 requires input_iterator<_It> 1988 { 1989 __glibcxx_assert(__i._M_index == 0); 1990 return ranges::iter_move(__i._M_it); 1991 } 1992 1993 template<indirectly_swappable<_It> _It2, typename _Sent2> 1994 friend void 1995 iter_swap(const common_iterator& __x, 1996 const common_iterator<_It2, _Sent2>& __y) 1997 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(), 1998 std::declval<const _It2&>()))) 1999 { 2000 __glibcxx_assert(__x._M_index == 0); 2001 __glibcxx_assert(__y._M_index == 0); 2002 return ranges::iter_swap(__x._M_it, __y._M_it); 2003 } 2004 2005 private: 2006 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2> 2007 friend class common_iterator; 2008 2009 bool _M_has_value() const noexcept { return _M_index < 2; } 2010 2011 union 2012 { 2013 _It _M_it; 2014 _Sent _M_sent; 2015 unsigned char _M_valueless; 2016 }; 2017 unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless 2018 }; 2019 2020 template<typename _It, typename _Sent> 2021 struct incrementable_traits<common_iterator<_It, _Sent>> 2022 { 2023 using difference_type = iter_difference_t<_It>; 2024 }; 2025 2026 template<input_iterator _It, typename _Sent> 2027 struct iterator_traits<common_iterator<_It, _Sent>> 2028 { 2029 private: 2030 template<typename _Iter> 2031 struct __ptr 2032 { 2033 using type = void; 2034 }; 2035 2036 template<typename _Iter> 2037 requires __detail::__common_iter_has_arrow<_Iter> 2038 struct __ptr<_Iter> 2039 { 2040 using _CIter = common_iterator<_Iter, _Sent>; 2041 using type = decltype(std::declval<const _CIter&>().operator->()); 2042 }; 2043 2044 static auto 2045 _S_iter_cat() 2046 { 2047 using _Traits = iterator_traits<_It>; 2048 if constexpr (requires { requires derived_from<typename _Traits::iterator_category, 2049 forward_iterator_tag>; }) 2050 return forward_iterator_tag{}; 2051 else 2052 return input_iterator_tag{}; 2053 } 2054 2055 public: 2056 using iterator_concept = conditional_t<forward_iterator<_It>, 2057 forward_iterator_tag, input_iterator_tag>; 2058 using iterator_category = decltype(_S_iter_cat()); 2059 using value_type = iter_value_t<_It>; 2060 using difference_type = iter_difference_t<_It>; 2061 using pointer = typename __ptr<_It>::type; 2062 using reference = iter_reference_t<_It>; 2063 }; 2064 2065 // [iterators.counted] Counted iterators 2066 2067 namespace __detail 2068 { 2069 template<typename _It> 2070 struct __counted_iter_value_type 2071 { }; 2072 2073 template<indirectly_readable _It> 2074 struct __counted_iter_value_type<_It> 2075 { using value_type = iter_value_t<_It>; }; 2076 2077 template<typename _It> 2078 struct __counted_iter_concept 2079 { }; 2080 2081 template<typename _It> 2082 requires requires { typename _It::iterator_concept; } 2083 struct __counted_iter_concept<_It> 2084 { using iterator_concept = typename _It::iterator_concept; }; 2085 2086 template<typename _It> 2087 struct __counted_iter_cat 2088 { }; 2089 2090 template<typename _It> 2091 requires requires { typename _It::iterator_category; } 2092 struct __counted_iter_cat<_It> 2093 { using iterator_category = typename _It::iterator_category; }; 2094 } 2095 2096 /// An iterator adaptor that keeps track of the distance to the end. 2097 template<input_or_output_iterator _It> 2098 class counted_iterator 2099 : public __detail::__counted_iter_value_type<_It>, 2100 public __detail::__counted_iter_concept<_It>, 2101 public __detail::__counted_iter_cat<_It> 2102 { 2103 public: 2104 using iterator_type = _It; 2105 // value_type defined in __counted_iter_value_type 2106 using difference_type = iter_difference_t<_It>; 2107 // iterator_concept defined in __counted_iter_concept 2108 // iterator_category defined in __counted_iter_cat 2109 2110 constexpr counted_iterator() requires default_initializable<_It> = default; 2111 2112 constexpr 2113 counted_iterator(_It __i, iter_difference_t<_It> __n) 2114 : _M_current(std::move(__i)), _M_length(__n) 2115 { __glibcxx_assert(__n >= 0); } 2116 2117 template<typename _It2> 2118 requires convertible_to<const _It2&, _It> 2119 constexpr 2120 counted_iterator(const counted_iterator<_It2>& __x) 2121 : _M_current(__x._M_current), _M_length(__x._M_length) 2122 { } 2123 2124 template<typename _It2> 2125 requires assignable_from<_It&, const _It2&> 2126 constexpr counted_iterator& 2127 operator=(const counted_iterator<_It2>& __x) 2128 { 2129 _M_current = __x._M_current; 2130 _M_length = __x._M_length; 2131 return *this; 2132 } 2133 2134 constexpr const _It& 2135 base() const & noexcept 2136 { return _M_current; } 2137 2138 constexpr _It 2139 base() && 2140 noexcept(is_nothrow_move_constructible_v<_It>) 2141 { return std::move(_M_current); } 2142 2143 constexpr iter_difference_t<_It> 2144 count() const noexcept { return _M_length; } 2145 2146 constexpr decltype(auto) 2147 operator*() 2148 noexcept(noexcept(*_M_current)) 2149 { return *_M_current; } 2150 2151 constexpr decltype(auto) 2152 operator*() const 2153 noexcept(noexcept(*_M_current)) 2154 requires __detail::__dereferenceable<const _It> 2155 { return *_M_current; } 2156 2157 constexpr auto 2158 operator->() const noexcept 2159 requires contiguous_iterator<_It> 2160 { return std::to_address(_M_current); } 2161 2162 constexpr counted_iterator& 2163 operator++() 2164 { 2165 __glibcxx_assert(_M_length > 0); 2166 ++_M_current; 2167 --_M_length; 2168 return *this; 2169 } 2170 2171 decltype(auto) 2172 operator++(int) 2173 { 2174 __glibcxx_assert(_M_length > 0); 2175 --_M_length; 2176 __try 2177 { 2178 return _M_current++; 2179 } __catch(...) { 2180 ++_M_length; 2181 __throw_exception_again; 2182 } 2183 2184 } 2185 2186 constexpr counted_iterator 2187 operator++(int) requires forward_iterator<_It> 2188 { 2189 auto __tmp = *this; 2190 ++*this; 2191 return __tmp; 2192 } 2193 2194 constexpr counted_iterator& 2195 operator--() requires bidirectional_iterator<_It> 2196 { 2197 --_M_current; 2198 ++_M_length; 2199 return *this; 2200 } 2201 2202 constexpr counted_iterator 2203 operator--(int) requires bidirectional_iterator<_It> 2204 { 2205 auto __tmp = *this; 2206 --*this; 2207 return __tmp; 2208 } 2209 2210 constexpr counted_iterator 2211 operator+(iter_difference_t<_It> __n) const 2212 requires random_access_iterator<_It> 2213 { return counted_iterator(_M_current + __n, _M_length - __n); } 2214 2215 friend constexpr counted_iterator 2216 operator+(iter_difference_t<_It> __n, const counted_iterator& __x) 2217 requires random_access_iterator<_It> 2218 { return __x + __n; } 2219 2220 constexpr counted_iterator& 2221 operator+=(iter_difference_t<_It> __n) 2222 requires random_access_iterator<_It> 2223 { 2224 __glibcxx_assert(__n <= _M_length); 2225 _M_current += __n; 2226 _M_length -= __n; 2227 return *this; 2228 } 2229 2230 constexpr counted_iterator 2231 operator-(iter_difference_t<_It> __n) const 2232 requires random_access_iterator<_It> 2233 { return counted_iterator(_M_current - __n, _M_length + __n); } 2234 2235 template<common_with<_It> _It2> 2236 friend constexpr iter_difference_t<_It2> 2237 operator-(const counted_iterator& __x, 2238 const counted_iterator<_It2>& __y) 2239 { return __y._M_length - __x._M_length; } 2240 2241 friend constexpr iter_difference_t<_It> 2242 operator-(const counted_iterator& __x, default_sentinel_t) 2243 { return -__x._M_length; } 2244 2245 friend constexpr iter_difference_t<_It> 2246 operator-(default_sentinel_t, const counted_iterator& __y) 2247 { return __y._M_length; } 2248 2249 constexpr counted_iterator& 2250 operator-=(iter_difference_t<_It> __n) 2251 requires random_access_iterator<_It> 2252 { 2253 __glibcxx_assert(-__n <= _M_length); 2254 _M_current -= __n; 2255 _M_length += __n; 2256 return *this; 2257 } 2258 2259 constexpr decltype(auto) 2260 operator[](iter_difference_t<_It> __n) const 2261 noexcept(noexcept(_M_current[__n])) 2262 requires random_access_iterator<_It> 2263 { 2264 __glibcxx_assert(__n < _M_length); 2265 return _M_current[__n]; 2266 } 2267 2268 template<common_with<_It> _It2> 2269 friend constexpr bool 2270 operator==(const counted_iterator& __x, 2271 const counted_iterator<_It2>& __y) 2272 { return __x._M_length == __y._M_length; } 2273 2274 friend constexpr bool 2275 operator==(const counted_iterator& __x, default_sentinel_t) 2276 { return __x._M_length == 0; } 2277 2278 template<common_with<_It> _It2> 2279 friend constexpr strong_ordering 2280 operator<=>(const counted_iterator& __x, 2281 const counted_iterator<_It2>& __y) 2282 { return __y._M_length <=> __x._M_length; } 2283 2284 friend constexpr iter_rvalue_reference_t<_It> 2285 iter_move(const counted_iterator& __i) 2286 noexcept(noexcept(ranges::iter_move(__i._M_current))) 2287 requires input_iterator<_It> 2288 { return ranges::iter_move(__i._M_current); } 2289 2290 template<indirectly_swappable<_It> _It2> 2291 friend constexpr void 2292 iter_swap(const counted_iterator& __x, 2293 const counted_iterator<_It2>& __y) 2294 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) 2295 { ranges::iter_swap(__x._M_current, __y._M_current); } 2296 2297 private: 2298 template<input_or_output_iterator _It2> friend class counted_iterator; 2299 2300 _It _M_current = _It(); 2301 iter_difference_t<_It> _M_length = 0; 2302 }; 2303 2304 template<input_iterator _It> 2305 requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>> 2306 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It> 2307 { 2308 using pointer = conditional_t<contiguous_iterator<_It>, 2309 add_pointer_t<iter_reference_t<_It>>, 2310 void>; 2311 }; 2312 #endif // C++20 2313 2314 /// @} group iterators 2315 2316 template<typename _Iterator> 2317 _GLIBCXX20_CONSTEXPR 2318 auto 2319 __niter_base(move_iterator<_Iterator> __it) 2320 -> decltype(make_move_iterator(__niter_base(__it.base()))) 2321 { return make_move_iterator(__niter_base(__it.base())); } 2322 2323 template<typename _Iterator> 2324 struct __is_move_iterator<move_iterator<_Iterator> > 2325 { 2326 enum { __value = 1 }; 2327 typedef __true_type __type; 2328 }; 2329 2330 template<typename _Iterator> 2331 _GLIBCXX20_CONSTEXPR 2332 auto 2333 __miter_base(move_iterator<_Iterator> __it) 2334 -> decltype(__miter_base(__it.base())) 2335 { return __miter_base(__it.base()); } 2336 2337 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 2338 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 2339 std::__make_move_if_noexcept_iterator(_Iter) 2340 #else 2341 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 2342 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 2343 #endif // C++11 2344 2345 #if __cpp_deduction_guides >= 201606 2346 // These helper traits are used for deduction guides 2347 // of associative containers. 2348 template<typename _InputIterator> 2349 using __iter_key_t = remove_const_t< 2350 typename iterator_traits<_InputIterator>::value_type::first_type>; 2351 2352 template<typename _InputIterator> 2353 using __iter_val_t = 2354 typename iterator_traits<_InputIterator>::value_type::second_type; 2355 2356 template<typename _T1, typename _T2> 2357 struct pair; 2358 2359 template<typename _InputIterator> 2360 using __iter_to_alloc_t = 2361 pair<add_const_t<__iter_key_t<_InputIterator>>, 2362 __iter_val_t<_InputIterator>>; 2363 #endif // __cpp_deduction_guides 2364 2365 _GLIBCXX_END_NAMESPACE_VERSION 2366 } // namespace 2367 2368 #ifdef _GLIBCXX_DEBUG 2369 # include <debug/stl_iterator.h> 2370 #endif 2371 2372 #endif 2373