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