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