libstdc++-v3/include/bits/stl_iterator.h

   1 // Iterators -*- C++ -*-
   2
   3 // Copyright (C) 2001-2023 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   // [iterators.common] Common iterators
1833
1834   namespace __detail
1835   {
1836     template<typename _It>
1837       concept __common_iter_has_arrow = indirectly_readable<const _It>
1838         && (requires(const _It& __it) { __it.operator->(); }
1839             || is_reference_v<iter_reference_t<_It>>
1840             || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1841
1842     template<typename _It>
1843       concept __common_iter_use_postfix_proxy
1844         = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1845           && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1846           && move_constructible<iter_value_t<_It>>;
1847   } // namespace __detail
1848
1849   /// An iterator/sentinel adaptor for representing a non-common range.
1850   template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1851     requires (!same_as<_It, _Sent>) && copyable<_It>
1852   class common_iterator
1853   {
1854     template<typename _Tp, typename _Up>
1855       static constexpr bool
1856       _S_noexcept1()
1857       {
1858         if constexpr (is_trivially_default_constructible_v<_Tp>)
1859           return is_nothrow_assignable_v<_Tp&, _Up>;
1860         else
1861           return is_nothrow_constructible_v<_Tp, _Up>;
1862       }
1863
1864     template<typename _It2, typename _Sent2>
1865       static constexpr bool
1866       _S_noexcept()
1867       { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1868
1869     class __arrow_proxy
1870     {
1871       iter_value_t<_It> _M_keep;
1872
1873       constexpr
1874       __arrow_proxy(iter_reference_t<_It>&& __x)
1875       : _M_keep(std::move(__x)) { }
1876
1877       friend class common_iterator;
1878
1879     public:
1880       constexpr const iter_value_t<_It>*
1881       operator->() const noexcept
1882       { return std::__addressof(_M_keep); }
1883     };
1884
1885     class __postfix_proxy
1886     {
1887       iter_value_t<_It> _M_keep;
1888
1889       constexpr
1890       __postfix_proxy(iter_reference_t<_It>&& __x)
1891       : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1892
1893       friend class common_iterator;
1894
1895     public:
1896       constexpr const iter_value_t<_It>&
1897       operator*() const noexcept
1898       { return _M_keep; }
1899     };
1900
1901   public:
1902     constexpr
1903     common_iterator()
1904     noexcept(is_nothrow_default_constructible_v<_It>)
1905     requires default_initializable<_It>
1906     : _M_it(), _M_index(0)
1907     { }
1908
1909     constexpr
1910     common_iterator(_It __i)
1911     noexcept(is_nothrow_move_constructible_v<_It>)
1912     : _M_it(std::move(__i)), _M_index(0)
1913     { }
1914
1915     constexpr
1916     common_iterator(_Sent __s)
1917     noexcept(is_nothrow_move_constructible_v<_Sent>)
1918     : _M_sent(std::move(__s)), _M_index(1)
1919     { }
1920
1921     template<typename _It2, typename _Sent2>
1922       requires convertible_to<const _It2&, _It>
1923         && convertible_to<const _Sent2&, _Sent>
1924       constexpr
1925       common_iterator(const common_iterator<_It2, _Sent2>& __x)
1926       noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1927       : _M_valueless(), _M_index(__x._M_index)
1928       {
1929         __glibcxx_assert(__x._M_has_value());
1930         if (_M_index == 0)
1931           {
1932             if constexpr (is_trivially_default_constructible_v<_It>)
1933               _M_it = std::move(__x._M_it);
1934             else
1935               std::construct_at(std::__addressof(_M_it), __x._M_it);
1936           }
1937         else if (_M_index == 1)
1938           {
1939             if constexpr (is_trivially_default_constructible_v<_Sent>)
1940               _M_sent = std::move(__x._M_sent);
1941             else
1942               std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1943           }
1944       }
1945
1946     common_iterator(const common_iterator&) = default;
1947
1948     constexpr
1949     common_iterator(const common_iterator& __x)
1950     noexcept(_S_noexcept<const _It&, const _Sent&>())
1951     requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
1952     : _M_valueless(), _M_index(__x._M_index)
1953     {
1954       if (_M_index == 0)
1955         {
1956           if constexpr (is_trivially_default_constructible_v<_It>)
1957             _M_it = __x._M_it;
1958           else
1959             std::construct_at(std::__addressof(_M_it), __x._M_it);
1960         }
1961       else if (_M_index == 1)
1962         {
1963           if constexpr (is_trivially_default_constructible_v<_Sent>)
1964             _M_sent = __x._M_sent;
1965           else
1966             std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1967         }
1968     }
1969
1970     common_iterator(common_iterator&&) = default;
1971
1972     constexpr
1973     common_iterator(common_iterator&& __x)
1974     noexcept(_S_noexcept<_It, _Sent>())
1975     requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
1976     : _M_valueless(), _M_index(__x._M_index)
1977     {
1978       if (_M_index == 0)
1979         {
1980           if constexpr (is_trivially_default_constructible_v<_It>)
1981             _M_it = std::move(__x._M_it);
1982           else
1983             std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
1984         }
1985       else if (_M_index == 1)
1986         {
1987           if constexpr (is_trivially_default_constructible_v<_Sent>)
1988             _M_sent = std::move(__x._M_sent);
1989           else
1990             std::construct_at(std::__addressof(_M_sent),
1991                               std::move(__x._M_sent));
1992         }
1993     }
1994
1995     constexpr common_iterator&
1996     operator=(const common_iterator&) = default;
1997
1998     constexpr common_iterator&
1999     operator=(const common_iterator& __x)
2000     noexcept(is_nothrow_copy_assignable_v<_It>
2001              && is_nothrow_copy_assignable_v<_Sent>
2002              && is_nothrow_copy_constructible_v<_It>
2003              && is_nothrow_copy_constructible_v<_Sent>)
2004     requires (!is_trivially_copy_assignable_v<_It>
2005                 || !is_trivially_copy_assignable_v<_Sent>)
2006     {
2007       _M_assign(__x);
2008       return *this;
2009     }
2010
2011     constexpr common_iterator&
2012     operator=(common_iterator&&) = default;
2013
2014     constexpr common_iterator&
2015     operator=(common_iterator&& __x)
2016     noexcept(is_nothrow_move_assignable_v<_It>
2017              && is_nothrow_move_assignable_v<_Sent>
2018              && is_nothrow_move_constructible_v<_It>
2019              && is_nothrow_move_constructible_v<_Sent>)
2020     requires (!is_trivially_move_assignable_v<_It>
2021                 || !is_trivially_move_assignable_v<_Sent>)
2022     {
2023       _M_assign(std::move(__x));
2024       return *this;
2025     }
2026
2027     template<typename _It2, typename _Sent2>
2028       requires convertible_to<const _It2&, _It>
2029         && convertible_to<const _Sent2&, _Sent>
2030         && assignable_from<_It&, const _It2&>
2031         && assignable_from<_Sent&, const _Sent2&>
2032       constexpr common_iterator&
2033       operator=(const common_iterator<_It2, _Sent2>& __x)
2034       noexcept(is_nothrow_constructible_v<_It, const _It2&>
2035                && is_nothrow_constructible_v<_Sent, const _Sent2&>
2036                && is_nothrow_assignable_v<_It&, const _It2&>
2037                && is_nothrow_assignable_v<_Sent&, const _Sent2&>)
2038       {
2039         __glibcxx_assert(__x._M_has_value());
2040         _M_assign(__x);
2041         return *this;
2042       }
2043
2044 #if __cpp_concepts >= 202002L // Constrained special member functions
2045     ~common_iterator() = default;
2046
2047     constexpr
2048     ~common_iterator()
2049       requires (!is_trivially_destructible_v<_It>
2050                   || !is_trivially_destructible_v<_Sent>)
2051 #else
2052     constexpr
2053     ~common_iterator()
2054 #endif
2055     {
2056       if (_M_index == 0)
2057         _M_it.~_It();
2058       else if (_M_index == 1)
2059         _M_sent.~_Sent();
2060     }
2061
2062     [[nodiscard]]
2063     constexpr decltype(auto)
2064     operator*()
2065     {
2066       __glibcxx_assert(_M_index == 0);
2067       return *_M_it;
2068     }
2069
2070     [[nodiscard]]
2071     constexpr decltype(auto)
2072     operator*() const requires __detail::__dereferenceable<const _It>
2073     {
2074       __glibcxx_assert(_M_index == 0);
2075       return *_M_it;
2076     }
2077
2078     [[nodiscard]]
2079     constexpr auto
2080     operator->() const requires __detail::__common_iter_has_arrow<_It>
2081     {
2082       __glibcxx_assert(_M_index == 0);
2083       if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
2084         return _M_it;
2085       else if constexpr (is_reference_v<iter_reference_t<_It>>)
2086         {
2087           auto&& __tmp = *_M_it;
2088           return std::__addressof(__tmp);
2089         }
2090       else
2091         return __arrow_proxy{*_M_it};
2092     }
2093
2094     constexpr common_iterator&
2095     operator++()
2096     {
2097       __glibcxx_assert(_M_index == 0);
2098       ++_M_it;
2099       return *this;
2100     }
2101
2102     constexpr decltype(auto)
2103     operator++(int)
2104     {
2105       __glibcxx_assert(_M_index == 0);
2106       if constexpr (forward_iterator<_It>)
2107         {
2108           common_iterator __tmp = *this;
2109           ++*this;
2110           return __tmp;
2111         }
2112       else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
2113         return _M_it++;
2114       else
2115         {
2116           __postfix_proxy __p(**this);
2117           ++*this;
2118           return __p;
2119         }
2120     }
2121
2122     template<typename _It2, sentinel_for<_It> _Sent2>
2123       requires sentinel_for<_Sent, _It2>
2124       friend constexpr bool
2125       operator== [[nodiscard]] (const common_iterator& __x,
2126                                 const common_iterator<_It2, _Sent2>& __y)
2127       {
2128         switch(__x._M_index << 2 | __y._M_index)
2129           {
2130           case 0b0000:
2131           case 0b0101:
2132             return true;
2133           case 0b0001:
2134             return __x._M_it == __y._M_sent;
2135           case 0b0100:
2136             return __x._M_sent == __y._M_it;
2137           default:
2138             __glibcxx_assert(__x._M_has_value());
2139             __glibcxx_assert(__y._M_has_value());
2140             __builtin_unreachable();
2141           }
2142       }
2143
2144     template<typename _It2, sentinel_for<_It> _Sent2>
2145       requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2146       friend constexpr bool
2147       operator== [[nodiscard]] (const common_iterator& __x,
2148                                 const common_iterator<_It2, _Sent2>& __y)
2149       {
2150         switch(__x._M_index << 2 | __y._M_index)
2151           {
2152           case 0b0101:
2153             return true;
2154           case 0b0000:
2155             return __x._M_it == __y._M_it;
2156           case 0b0001:
2157             return __x._M_it == __y._M_sent;
2158           case 0b0100:
2159             return __x._M_sent == __y._M_it;
2160           default:
2161             __glibcxx_assert(__x._M_has_value());
2162             __glibcxx_assert(__y._M_has_value());
2163             __builtin_unreachable();
2164           }
2165       }
2166
2167     template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2168       requires sized_sentinel_for<_Sent, _It2>
2169       friend constexpr iter_difference_t<_It2>
2170       operator- [[nodiscard]] (const common_iterator& __x,
2171                                const common_iterator<_It2, _Sent2>& __y)
2172       {
2173         switch(__x._M_index << 2 | __y._M_index)
2174           {
2175           case 0b0101:
2176             return 0;
2177           case 0b0000:
2178             return __x._M_it - __y._M_it;
2179           case 0b0001:
2180             return __x._M_it - __y._M_sent;
2181           case 0b0100:
2182             return __x._M_sent - __y._M_it;
2183           default:
2184             __glibcxx_assert(__x._M_has_value());
2185             __glibcxx_assert(__y._M_has_value());
2186             __builtin_unreachable();
2187           }
2188       }
2189
2190     [[nodiscard]]
2191     friend constexpr iter_rvalue_reference_t<_It>
2192     iter_move(const common_iterator& __i)
2193     noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2194     requires input_iterator<_It>
2195     {
2196       __glibcxx_assert(__i._M_index == 0);
2197       return ranges::iter_move(__i._M_it);
2198     }
2199
2200     template<indirectly_swappable<_It> _It2, typename _Sent2>
2201       friend constexpr void
2202       iter_swap(const common_iterator& __x,
2203                 const common_iterator<_It2, _Sent2>& __y)
2204       noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2205                                           std::declval<const _It2&>())))
2206       {
2207         __glibcxx_assert(__x._M_index == 0);
2208         __glibcxx_assert(__y._M_index == 0);
2209         return ranges::iter_swap(__x._M_it, __y._M_it);
2210       }
2211
2212   private:
2213     template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2214       requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2215       friend class common_iterator;
2216
2217     constexpr bool
2218     _M_has_value() const noexcept { return _M_index != _S_valueless; }
2219
2220     template<typename _CIt>
2221       constexpr void
2222       _M_assign(_CIt&& __x)
2223       {
2224         if (_M_index == __x._M_index)
2225           {
2226             if (_M_index == 0)
2227               _M_it = std::forward<_CIt>(__x)._M_it;
2228             else if (_M_index == 1)
2229               _M_sent = std::forward<_CIt>(__x)._M_sent;
2230           }
2231         else
2232           {
2233             if (_M_index == 0)
2234               _M_it.~_It();
2235             else if (_M_index == 1)
2236               _M_sent.~_Sent();
2237             _M_index = _S_valueless;
2238
2239             if (__x._M_index == 0)
2240               std::construct_at(std::__addressof(_M_it),
2241                                 std::forward<_CIt>(__x)._M_it);
2242             else if (__x._M_index == 1)
2243               std::construct_at(std::__addressof(_M_sent),
2244                                 std::forward<_CIt>(__x)._M_sent);
2245             _M_index = __x._M_index;
2246           }
2247       }
2248
2249     union
2250     {
2251       _It _M_it;
2252       _Sent _M_sent;
2253       unsigned char _M_valueless;
2254     };
2255     unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2256
2257     static constexpr unsigned char _S_valueless{2};
2258   };
2259
2260   template<typename _It, typename _Sent>
2261     struct incrementable_traits<common_iterator<_It, _Sent>>
2262     {
2263       using difference_type = iter_difference_t<_It>;
2264     };
2265
2266   template<input_iterator _It, typename _Sent>
2267     struct iterator_traits<common_iterator<_It, _Sent>>
2268     {
2269     private:
2270       template<typename _Iter>
2271         struct __ptr
2272         {
2273           using type = void;
2274         };
2275
2276       template<typename _Iter>
2277         requires __detail::__common_iter_has_arrow<_Iter>
2278         struct __ptr<_Iter>
2279         {
2280           using _CIter = common_iterator<_Iter, _Sent>;
2281           using type = decltype(std::declval<const _CIter&>().operator->());
2282         };
2283
2284       static auto
2285       _S_iter_cat()
2286       {
2287         using _Traits = iterator_traits<_It>;
2288         if constexpr (requires { requires derived_from<typename _Traits::iterator_category,
2289                                                        forward_iterator_tag>; })
2290           return forward_iterator_tag{};
2291         else
2292           return input_iterator_tag{};
2293       }
2294
2295     public:
2296       using iterator_concept = __conditional_t<forward_iterator<_It>,
2297                                                forward_iterator_tag,
2298                                                input_iterator_tag>;
2299       using iterator_category = decltype(_S_iter_cat());
2300       using value_type = iter_value_t<_It>;
2301       using difference_type = iter_difference_t<_It>;
2302       using pointer = typename __ptr<_It>::type;
2303       using reference = iter_reference_t<_It>;
2304     };
2305
2306   // [iterators.counted] Counted iterators
2307
2308   namespace __detail
2309   {
2310     template<typename _It>
2311       struct __counted_iter_value_type
2312       { };
2313
2314     template<indirectly_readable _It>
2315       struct __counted_iter_value_type<_It>
2316       { using value_type = iter_value_t<_It>; };
2317
2318     template<typename _It>
2319       struct __counted_iter_concept
2320       { };
2321
2322     template<typename _It>
2323       requires requires { typename _It::iterator_concept; }
2324       struct __counted_iter_concept<_It>
2325       { using iterator_concept = typename _It::iterator_concept; };
2326
2327     template<typename _It>
2328       struct __counted_iter_cat
2329       { };
2330
2331     template<typename _It>
2332       requires requires { typename _It::iterator_category; }
2333       struct __counted_iter_cat<_It>
2334       { using iterator_category = typename _It::iterator_category; };
2335   }
2336
2337   /// An iterator adaptor that keeps track of the distance to the end.
2338   template<input_or_output_iterator _It>
2339     class counted_iterator
2340       : public __detail::__counted_iter_value_type<_It>,
2341         public __detail::__counted_iter_concept<_It>,
2342         public __detail::__counted_iter_cat<_It>
2343     {
2344     public:
2345       using iterator_type = _It;
2346       // value_type defined in __counted_iter_value_type
2347       using difference_type = iter_difference_t<_It>;
2348       // iterator_concept defined in __counted_iter_concept
2349       // iterator_category defined in __counted_iter_cat
2350
2351       constexpr counted_iterator() requires default_initializable<_It> = default;
2352
2353       constexpr
2354       counted_iterator(_It __i, iter_difference_t<_It> __n)
2355       : _M_current(std::move(__i)), _M_length(__n)
2356       { __glibcxx_assert(__n >= 0); }
2357
2358       template<typename _It2>
2359         requires convertible_to<const _It2&, _It>
2360         constexpr
2361         counted_iterator(const counted_iterator<_It2>& __x)
2362         : _M_current(__x._M_current), _M_length(__x._M_length)
2363         { }
2364
2365       template<typename _It2>
2366         requires assignable_from<_It&, const _It2&>
2367         constexpr counted_iterator&
2368         operator=(const counted_iterator<_It2>& __x)
2369         {
2370           _M_current = __x._M_current;
2371           _M_length = __x._M_length;
2372           return *this;
2373         }
2374
2375       [[nodiscard]]
2376       constexpr const _It&
2377       base() const & noexcept
2378       { return _M_current; }
2379
2380       [[nodiscard]]
2381       constexpr _It
2382       base() &&
2383       noexcept(is_nothrow_move_constructible_v<_It>)
2384       { return std::move(_M_current); }
2385
2386       [[nodiscard]]
2387       constexpr iter_difference_t<_It>
2388       count() const noexcept { return _M_length; }
2389
2390       [[nodiscard]]
2391       constexpr decltype(auto)
2392       operator*()
2393       noexcept(noexcept(*_M_current))
2394       {
2395         __glibcxx_assert( _M_length > 0 );
2396         return *_M_current;
2397       }
2398
2399       [[nodiscard]]
2400       constexpr decltype(auto)
2401       operator*() const
2402       noexcept(noexcept(*_M_current))
2403       requires __detail::__dereferenceable<const _It>
2404       {
2405         __glibcxx_assert( _M_length > 0 );
2406         return *_M_current;
2407       }
2408
2409       [[nodiscard]]
2410       constexpr auto
2411       operator->() const noexcept
2412       requires contiguous_iterator<_It>
2413       { return std::to_address(_M_current); }
2414
2415       constexpr counted_iterator&
2416       operator++()
2417       {
2418         __glibcxx_assert(_M_length > 0);
2419         ++_M_current;
2420         --_M_length;
2421         return *this;
2422       }
2423
2424       constexpr decltype(auto)
2425       operator++(int)
2426       {
2427         __glibcxx_assert(_M_length > 0);
2428         --_M_length;
2429         __try
2430           {
2431             return _M_current++;
2432           } __catch(...) {
2433             ++_M_length;
2434             __throw_exception_again;
2435           }
2436       }
2437
2438       constexpr counted_iterator
2439       operator++(int) requires forward_iterator<_It>
2440       {
2441         auto __tmp = *this;
2442         ++*this;
2443         return __tmp;
2444       }
2445
2446       constexpr counted_iterator&
2447       operator--() requires bidirectional_iterator<_It>
2448       {
2449         --_M_current;
2450         ++_M_length;
2451         return *this;
2452       }
2453
2454       constexpr counted_iterator
2455       operator--(int) requires bidirectional_iterator<_It>
2456       {
2457         auto __tmp = *this;
2458         --*this;
2459         return __tmp;
2460       }
2461
2462       [[nodiscard]]
2463       constexpr counted_iterator
2464       operator+(iter_difference_t<_It> __n) const
2465         requires random_access_iterator<_It>
2466       { return counted_iterator(_M_current + __n, _M_length - __n); }
2467
2468       [[nodiscard]]
2469       friend constexpr counted_iterator
2470       operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2471       requires random_access_iterator<_It>
2472       { return __x + __n; }
2473
2474       constexpr counted_iterator&
2475       operator+=(iter_difference_t<_It> __n)
2476       requires random_access_iterator<_It>
2477       {
2478         __glibcxx_assert(__n <= _M_length);
2479         _M_current += __n;
2480         _M_length -= __n;
2481         return *this;
2482       }
2483
2484       [[nodiscard]]
2485       constexpr counted_iterator
2486       operator-(iter_difference_t<_It> __n) const
2487       requires random_access_iterator<_It>
2488       { return counted_iterator(_M_current - __n, _M_length + __n); }
2489
2490       template<common_with<_It> _It2>
2491         [[nodiscard]]
2492         friend constexpr iter_difference_t<_It2>
2493         operator-(const counted_iterator& __x,
2494                   const counted_iterator<_It2>& __y)
2495         { return __y._M_length - __x._M_length; }
2496
2497       [[nodiscard]]
2498       friend constexpr iter_difference_t<_It>
2499       operator-(const counted_iterator& __x, default_sentinel_t)
2500       { return -__x._M_length; }
2501
2502       [[nodiscard]]
2503       friend constexpr iter_difference_t<_It>
2504       operator-(default_sentinel_t, const counted_iterator& __y)
2505       { return __y._M_length; }
2506
2507       constexpr counted_iterator&
2508       operator-=(iter_difference_t<_It> __n)
2509       requires random_access_iterator<_It>
2510       {
2511         __glibcxx_assert(-__n <= _M_length);
2512         _M_current -= __n;
2513         _M_length += __n;
2514         return *this;
2515       }
2516
2517       [[nodiscard]]
2518       constexpr decltype(auto)
2519       operator[](iter_difference_t<_It> __n) const
2520       noexcept(noexcept(_M_current[__n]))
2521       requires random_access_iterator<_It>
2522       {
2523         __glibcxx_assert(__n < _M_length);
2524         return _M_current[__n];
2525       }
2526
2527       template<common_with<_It> _It2>
2528         [[nodiscard]]
2529         friend constexpr bool
2530         operator==(const counted_iterator& __x,
2531                    const counted_iterator<_It2>& __y)
2532         { return __x._M_length == __y._M_length; }
2533
2534       [[nodiscard]]
2535       friend constexpr bool
2536       operator==(const counted_iterator& __x, default_sentinel_t)
2537       { return __x._M_length == 0; }
2538
2539       template<common_with<_It> _It2>
2540         [[nodiscard]]
2541         friend constexpr strong_ordering
2542         operator<=>(const counted_iterator& __x,
2543                     const counted_iterator<_It2>& __y)
2544         { return __y._M_length <=> __x._M_length; }
2545
2546       [[nodiscard]]
2547       friend constexpr iter_rvalue_reference_t<_It>
2548       iter_move(const counted_iterator& __i)
2549       noexcept(noexcept(ranges::iter_move(__i._M_current)))
2550       requires input_iterator<_It>
2551       {
2552         __glibcxx_assert( __i._M_length > 0 );
2553         return ranges::iter_move(__i._M_current);
2554       }
2555
2556       template<indirectly_swappable<_It> _It2>
2557         friend constexpr void
2558         iter_swap(const counted_iterator& __x,
2559                   const counted_iterator<_It2>& __y)
2560         noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2561         {
2562           __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
2563           ranges::iter_swap(__x._M_current, __y._M_current);
2564         }
2565
2566     private:
2567       template<input_or_output_iterator _It2> friend class counted_iterator;
2568
2569       _It _M_current = _It();
2570       iter_difference_t<_It> _M_length = 0;
2571     };
2572
2573   template<input_iterator _It>
2574     requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2575     struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2576     {
2577       using pointer = __conditional_t<contiguous_iterator<_It>,
2578                                       add_pointer_t<iter_reference_t<_It>>,
2579                                       void>;
2580     };
2581 #endif // C++20
2582
2583   /// @} group iterators
2584
2585   template<typename _Iterator>
2586     _GLIBCXX20_CONSTEXPR
2587     auto
2588     __niter_base(move_iterator<_Iterator> __it)
2589     -> decltype(make_move_iterator(__niter_base(__it.base())))
2590     { return make_move_iterator(__niter_base(__it.base())); }
2591
2592   template<typename _Iterator>
2593     struct __is_move_iterator<move_iterator<_Iterator> >
2594     {
2595       enum { __value = 1 };
2596       typedef __true_type __type;
2597     };
2598
2599   template<typename _Iterator>
2600     _GLIBCXX20_CONSTEXPR
2601     auto
2602     __miter_base(move_iterator<_Iterator> __it)
2603     -> decltype(__miter_base(__it.base()))
2604     { return __miter_base(__it.base()); }
2605
2606 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2607 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2608   std::__make_move_if_noexcept_iterator(_Iter)
2609 #else
2610 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2611 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2612 #endif // C++11
2613
2614 #if __cpp_deduction_guides >= 201606
2615   // These helper traits are used for deduction guides
2616   // of associative containers.
2617   template<typename _InputIterator>
2618     using __iter_key_t = remove_const_t<
2619       typename iterator_traits<_InputIterator>::value_type::first_type>;
2620
2621   template<typename _InputIterator>
2622     using __iter_val_t
2623       = typename iterator_traits<_InputIterator>::value_type::second_type;
2624
2625   template<typename _T1, typename _T2>
2626     struct pair;
2627
2628   template<typename _InputIterator>
2629     using __iter_to_alloc_t
2630       = pair<const __iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>>;
2631 #endif // __cpp_deduction_guides
2632
2633 _GLIBCXX_END_NAMESPACE_VERSION
2634 } // namespace
2635
2636 #ifdef _GLIBCXX_DEBUG
2637 # include <debug/stl_iterator.h>
2638 #endif
2639
2640 #endif