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