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  { return __x.base() == __y.base(); }
1740 
1741 #if __cpp_lib_three_way_comparison
1742  template<three_way_comparable _Iterator>
1743  [[__nodiscard__]]
1744  constexpr compare_three_way_result_t<_Iterator>
1745  operator<=>(const move_iterator<_Iterator>& __x,
1746  const move_iterator<_Iterator>& __y)
1747  { return __x.base() <=> __y.base(); }
1748 #else
1749  template<typename _Iterator>
1750  [[__nodiscard__]]
1751  inline _GLIBCXX17_CONSTEXPR bool
1752  operator!=(const move_iterator<_Iterator>& __x,
1753  const move_iterator<_Iterator>& __y)
1754  { return !(__x == __y); }
1755 
1756  template<typename _Iterator>
1757  [[__nodiscard__]]
1758  inline _GLIBCXX17_CONSTEXPR bool
1759  operator<(const move_iterator<_Iterator>& __x,
1760  const move_iterator<_Iterator>& __y)
1761  { return __x.base() < __y.base(); }
1762 
1763  template<typename _Iterator>
1764  [[__nodiscard__]]
1765  inline _GLIBCXX17_CONSTEXPR bool
1766  operator<=(const move_iterator<_Iterator>& __x,
1767  const move_iterator<_Iterator>& __y)
1768  { return !(__y < __x); }
1769 
1770  template<typename _Iterator>
1771  [[__nodiscard__]]
1772  inline _GLIBCXX17_CONSTEXPR bool
1773  operator>(const move_iterator<_Iterator>& __x,
1774  const move_iterator<_Iterator>& __y)
1775  { return __y < __x; }
1776 
1777  template<typename _Iterator>
1778  [[__nodiscard__]]
1779  inline _GLIBCXX17_CONSTEXPR bool
1780  operator>=(const move_iterator<_Iterator>& __x,
1781  const move_iterator<_Iterator>& __y)
1782  { return !(__x < __y); }
1783 #endif // ! C++20
1784 
1785  // DR 685.
1786  template<typename _IteratorL, typename _IteratorR>
1787  [[__nodiscard__]]
1788  inline _GLIBCXX17_CONSTEXPR auto
1789  operator-(const move_iterator<_IteratorL>& __x,
1790  const move_iterator<_IteratorR>& __y)
1791  -> decltype(__x.base() - __y.base())
1792  { return __x.base() - __y.base(); }
1793 
1794  template<typename _Iterator>
1795  [[__nodiscard__]]
1796  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1797  operator+(typename move_iterator<_Iterator>::difference_type __n,
1798  const move_iterator<_Iterator>& __x)
1799  { return __x + __n; }
1800 
1801  template<typename _Iterator>
1802  [[__nodiscard__]]
1803  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1804  make_move_iterator(_Iterator __i)
1805  { return move_iterator<_Iterator>(std::move(__i)); }
1806 
1807  template<typename _Iterator, typename _ReturnType
1808  = __conditional_t<__move_if_noexcept_cond
1809  <typename iterator_traits<_Iterator>::value_type>::value,
1810  _Iterator, move_iterator<_Iterator>>>
1811  inline _GLIBCXX17_CONSTEXPR _ReturnType
1812  __make_move_if_noexcept_iterator(_Iterator __i)
1813  { return _ReturnType(__i); }
1814 
1815  // Overload for pointers that matches std::move_if_noexcept more closely,
1816  // returning a constant iterator when we don't want to move.
1817  template<typename _Tp, typename _ReturnType
1818  = __conditional_t<__move_if_noexcept_cond<_Tp>::value,
1819  const _Tp*, move_iterator<_Tp*>>>
1820  inline _GLIBCXX17_CONSTEXPR _ReturnType
1821  __make_move_if_noexcept_iterator(_Tp* __i)
1822  { return _ReturnType(__i); }
1823 
1824 #if __cplusplus > 201703L && __glibcxx_concepts
1825  // [iterators.common] Common iterators
1826 
1827  namespace __detail
1828  {
1829  template<typename _It>
1830  concept __common_iter_has_arrow = indirectly_readable<const _It>
1831  && (requires(const _It& __it) { __it.operator->(); }
1832  || is_reference_v<iter_reference_t<_It>>
1833  || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1834 
1835  template<typename _It>
1836  concept __common_iter_use_postfix_proxy
1837  = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1838  && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1839  && move_constructible<iter_value_t<_It>>;
1840  } // namespace __detail
1841 
1842  /// An iterator/sentinel adaptor for representing a non-common range.
1843  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1844  requires (!same_as<_It, _Sent>) && copyable<_It>
1845  class common_iterator
1846  {
1847  template<typename _Tp, typename _Up>
1848  static constexpr bool
1849  _S_noexcept1()
1850  {
1851  if constexpr (is_trivially_default_constructible_v<_Tp>)
1852  return is_nothrow_assignable_v<_Tp&, _Up>;
1853  else
1854  return is_nothrow_constructible_v<_Tp, _Up>;
1855  }
1856 
1857  template<typename _It2, typename _Sent2>
1858  static constexpr bool
1859  _S_noexcept()
1860  { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1861 
1862  class __arrow_proxy
1863  {
1864  iter_value_t<_It> _M_keep;
1865 
1866  constexpr
1867  __arrow_proxy(iter_reference_t<_It>&& __x)
1868  : _M_keep(std::move(__x)) { }
1869 
1870  friend class common_iterator;
1871 
1872  public:
1873  constexpr const iter_value_t<_It>*
1874  operator->() const noexcept
1875  { return std::__addressof(_M_keep); }
1876  };
1877 
1878  class __postfix_proxy
1879  {
1880  iter_value_t<_It> _M_keep;
1881 
1882  constexpr
1883  __postfix_proxy(iter_reference_t<_It>&& __x)
1884  : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1885 
1886  friend class common_iterator;
1887 
1888  public:
1889  constexpr const iter_value_t<_It>&
1890  operator*() const noexcept
1891  { return _M_keep; }
1892  };
1893 
1894  public:
1895  constexpr
1896  common_iterator()
1897  noexcept(is_nothrow_default_constructible_v<_It>)
1898  requires default_initializable<_It>
1899  : _M_it(), _M_index(0)
1900  { }
1901 
1902  constexpr
1903  common_iterator(_It __i)
1904  noexcept(is_nothrow_move_constructible_v<_It>)
1905  : _M_it(std::move(__i)), _M_index(0)
1906  { }
1907 
1908  constexpr
1909  common_iterator(_Sent __s)
1910  noexcept(is_nothrow_move_constructible_v<_Sent>)
1911  : _M_sent(std::move(__s)), _M_index(1)
1912  { }
1913 
1914  template<typename _It2, typename _Sent2>
1915  requires convertible_to<const _It2&, _It>
1916  && convertible_to<const _Sent2&, _Sent>
1917  constexpr
1918  common_iterator(const common_iterator<_It2, _Sent2>& __x)
1919  noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1920  : _M_valueless(), _M_index(__x._M_index)
1921  {
1922  __glibcxx_assert(__x._M_has_value());
1923  if (_M_index == 0)
1924  {
1925  if constexpr (is_trivially_default_constructible_v<_It>)
1926  _M_it = std::move(__x._M_it);
1927  else
1928  std::construct_at(std::__addressof(_M_it), __x._M_it);
1929  }
1930  else if (_M_index == 1)
1931  {
1932  if constexpr (is_trivially_default_constructible_v<_Sent>)
1933  _M_sent = std::move(__x._M_sent);
1934  else
1935  std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1936  }
1937  }
1938 
1939  common_iterator(const common_iterator&) = default;
1940 
1941  constexpr
1942  common_iterator(const common_iterator& __x)
1943  noexcept(_S_noexcept<const _It&, const _Sent&>())
1944  requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
1945  : _M_valueless(), _M_index(__x._M_index)
1946  {
1947  if (_M_index == 0)
1948  {
1949  if constexpr (is_trivially_default_constructible_v<_It>)
1950  _M_it = __x._M_it;
1951  else
1952  std::construct_at(std::__addressof(_M_it), __x._M_it);
1953  }
1954  else if (_M_index == 1)
1955  {
1956  if constexpr (is_trivially_default_constructible_v<_Sent>)
1957  _M_sent = __x._M_sent;
1958  else
1959  std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1960  }
1961  }
1962 
1963  common_iterator(common_iterator&&) = default;
1964 
1965  constexpr
1966  common_iterator(common_iterator&& __x)
1967  noexcept(_S_noexcept<_It, _Sent>())
1968  requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
1969  : _M_valueless(), _M_index(__x._M_index)
1970  {
1971  if (_M_index == 0)
1972  {
1973  if constexpr (is_trivially_default_constructible_v<_It>)
1974  _M_it = std::move(__x._M_it);
1975  else
1976  std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
1977  }
1978  else if (_M_index == 1)
1979  {
1980  if constexpr (is_trivially_default_constructible_v<_Sent>)
1981  _M_sent = std::move(__x._M_sent);
1982  else
1983  std::construct_at(std::__addressof(_M_sent),
1984  std::move(__x._M_sent));
1985  }
1986  }
1987 
1988  constexpr common_iterator&
1989  operator=(const common_iterator&) = default;
1990 
1991  constexpr common_iterator&
1992  operator=(const common_iterator& __x)
1993  noexcept(is_nothrow_copy_assignable_v<_It>
1994  && is_nothrow_copy_assignable_v<_Sent>
1995  && is_nothrow_copy_constructible_v<_It>
1996  && is_nothrow_copy_constructible_v<_Sent>)
1997  requires (!is_trivially_copy_assignable_v<_It>
1998  || !is_trivially_copy_assignable_v<_Sent>)
1999  {
2000  _M_assign(__x);
2001  return *this;
2002  }
2003 
2004  constexpr common_iterator&
2005  operator=(common_iterator&&) = default;
2006 
2007  constexpr common_iterator&
2008  operator=(common_iterator&& __x)
2009  noexcept(is_nothrow_move_assignable_v<_It>
2010  && is_nothrow_move_assignable_v<_Sent>
2011  && is_nothrow_move_constructible_v<_It>
2012  && is_nothrow_move_constructible_v<_Sent>)
2013  requires (!is_trivially_move_assignable_v<_It>
2014  || !is_trivially_move_assignable_v<_Sent>)
2015  {
2016  _M_assign(std::move(__x));
2017  return *this;
2018  }
2019 
2020  template<typename _It2, typename _Sent2>
2021  requires convertible_to<const _It2&, _It>
2022  && convertible_to<const _Sent2&, _Sent>
2023  && assignable_from<_It&, const _It2&>
2024  && assignable_from<_Sent&, const _Sent2&>
2025  constexpr common_iterator&
2026  operator=(const common_iterator<_It2, _Sent2>& __x)
2027  noexcept(is_nothrow_constructible_v<_It, const _It2&>
2028  && is_nothrow_constructible_v<_Sent, const _Sent2&>
2029  && is_nothrow_assignable_v<_It&, const _It2&>
2030  && is_nothrow_assignable_v<_Sent&, const _Sent2&>)
2031  {
2032  __glibcxx_assert(__x._M_has_value());
2033  _M_assign(__x);
2034  return *this;
2035  }
2036 
2037 #if __cpp_concepts >= 202002L // Constrained special member functions
2038  ~common_iterator() = default;
2039 
2040  constexpr
2041  ~common_iterator()
2042  requires (!is_trivially_destructible_v<_It>
2043  || !is_trivially_destructible_v<_Sent>)
2044 #else
2045  constexpr
2046  ~common_iterator()
2047 #endif
2048  {
2049  if (_M_index == 0)
2050  _M_it.~_It();
2051  else if (_M_index == 1)
2052  _M_sent.~_Sent();
2053  }
2054 
2055  [[nodiscard]]
2056  constexpr decltype(auto)
2057  operator*()
2058  {
2059  __glibcxx_assert(_M_index == 0);
2060  return *_M_it;
2061  }
2062 
2063  [[nodiscard]]
2064  constexpr decltype(auto)
2065  operator*() const requires __detail::__dereferenceable<const _It>
2066  {
2067  __glibcxx_assert(_M_index == 0);
2068  return *_M_it;
2069  }
2070 
2071  [[nodiscard]]
2072  constexpr auto
2073  operator->() const requires __detail::__common_iter_has_arrow<_It>
2074  {
2075  __glibcxx_assert(_M_index == 0);
2076  if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
2077  return _M_it;
2078  else if constexpr (is_reference_v<iter_reference_t<_It>>)
2079  {
2080  auto&& __tmp = *_M_it;
2081  return std::__addressof(__tmp);
2082  }
2083  else
2084  return __arrow_proxy{*_M_it};
2085  }
2086 
2087  constexpr common_iterator&
2088  operator++()
2089  {
2090  __glibcxx_assert(_M_index == 0);
2091  ++_M_it;
2092  return *this;
2093  }
2094 
2095  constexpr decltype(auto)
2096  operator++(int)
2097  {
2098  __glibcxx_assert(_M_index == 0);
2099  if constexpr (forward_iterator<_It>)
2100  {
2101  common_iterator __tmp = *this;
2102  ++*this;
2103  return __tmp;
2104  }
2105  else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
2106  return _M_it++;
2107  else
2108  {
2109  __postfix_proxy __p(**this);
2110  ++*this;
2111  return __p;
2112  }
2113  }
2114 
2115  template<typename _It2, sentinel_for<_It> _Sent2>
2116  requires sentinel_for<_Sent, _It2>
2117  friend constexpr bool
2118  operator== [[nodiscard]] (const common_iterator& __x,
2119  const common_iterator<_It2, _Sent2>& __y)
2120  {
2121  switch(__x._M_index << 2 | __y._M_index)
2122  {
2123  case 0b0000:
2124  case 0b0101:
2125  return true;
2126  case 0b0001:
2127  return __x._M_it == __y._M_sent;
2128  case 0b0100:
2129  return __x._M_sent == __y._M_it;
2130  default:
2131  __glibcxx_assert(__x._M_has_value());
2132  __glibcxx_assert(__y._M_has_value());
2133  __builtin_unreachable();
2134  }
2135  }
2136 
2137  template<typename _It2, sentinel_for<_It> _Sent2>
2138  requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2139  friend constexpr bool
2140  operator== [[nodiscard]] (const common_iterator& __x,
2141  const common_iterator<_It2, _Sent2>& __y)
2142  {
2143  switch(__x._M_index << 2 | __y._M_index)
2144  {
2145  case 0b0101:
2146  return true;
2147  case 0b0000:
2148  return __x._M_it == __y._M_it;
2149  case 0b0001:
2150  return __x._M_it == __y._M_sent;
2151  case 0b0100:
2152  return __x._M_sent == __y._M_it;
2153  default:
2154  __glibcxx_assert(__x._M_has_value());
2155  __glibcxx_assert(__y._M_has_value());
2156  __builtin_unreachable();
2157  }
2158  }
2159 
2160  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2161  requires sized_sentinel_for<_Sent, _It2>
2162  friend constexpr iter_difference_t<_It2>
2163  operator- [[nodiscard]] (const common_iterator& __x,
2164  const common_iterator<_It2, _Sent2>& __y)
2165  {
2166  switch(__x._M_index << 2 | __y._M_index)
2167  {
2168  case 0b0101:
2169  return 0;
2170  case 0b0000:
2171  return __x._M_it - __y._M_it;
2172  case 0b0001:
2173  return __x._M_it - __y._M_sent;
2174  case 0b0100:
2175  return __x._M_sent - __y._M_it;
2176  default:
2177  __glibcxx_assert(__x._M_has_value());
2178  __glibcxx_assert(__y._M_has_value());
2179  __builtin_unreachable();
2180  }
2181  }
2182 
2183  [[nodiscard]]
2184  friend constexpr iter_rvalue_reference_t<_It>
2185  iter_move(const common_iterator& __i)
2186  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2187  requires input_iterator<_It>
2188  {
2189  __glibcxx_assert(__i._M_index == 0);
2190  return ranges::iter_move(__i._M_it);
2191  }
2192 
2193  template<indirectly_swappable<_It> _It2, typename _Sent2>
2194  friend constexpr void
2195  iter_swap(const common_iterator& __x,
2196  const common_iterator<_It2, _Sent2>& __y)
2197  noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2198  std::declval<const _It2&>())))
2199  {
2200  __glibcxx_assert(__x._M_index == 0);
2201  __glibcxx_assert(__y._M_index == 0);
2202  return ranges::iter_swap(__x._M_it, __y._M_it);
2203  }
2204 
2205  private:
2206  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2207  requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2208  friend class common_iterator;
2209 
2210  constexpr bool
2211  _M_has_value() const noexcept { return _M_index != _S_valueless; }
2212 
2213  template<typename _CIt>
2214  constexpr void
2215  _M_assign(_CIt&& __x)
2216  {
2217  if (_M_index == __x._M_index)
2218  {
2219  if (_M_index == 0)
2220  _M_it = std::forward<_CIt>(__x)._M_it;
2221  else if (_M_index == 1)
2222  _M_sent = std::forward<_CIt>(__x)._M_sent;
2223  }
2224  else
2225  {
2226  if (_M_index == 0)
2227  _M_it.~_It();
2228  else if (_M_index == 1)
2229  _M_sent.~_Sent();
2230  _M_index = _S_valueless;
2231 
2232  if (__x._M_index == 0)
2233  std::construct_at(std::__addressof(_M_it),
2234  std::forward<_CIt>(__x)._M_it);
2235  else if (__x._M_index == 1)
2236  std::construct_at(std::__addressof(_M_sent),
2237  std::forward<_CIt>(__x)._M_sent);
2238  _M_index = __x._M_index;
2239  }
2240  }
2241 
2242  union
2243  {
2244  _It _M_it;
2245  _Sent _M_sent;
2246  unsigned char _M_valueless;
2247  };
2248  unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2249 
2250  static constexpr unsigned char _S_valueless{2};
2251  };
2252 
2253  template<typename _It, typename _Sent>
2254  struct incrementable_traits<common_iterator<_It, _Sent>>
2255  {
2256  using difference_type = iter_difference_t<_It>;
2257  };
2258 
2259  template<input_iterator _It, typename _Sent>
2260  struct iterator_traits<common_iterator<_It, _Sent>>
2261  {
2262  private:
2263  template<typename _Iter>
2264  struct __ptr
2265  {
2266  using type = void;
2267  };
2268 
2269  template<typename _Iter>
2270  requires __detail::__common_iter_has_arrow<_Iter>
2271  struct __ptr<_Iter>
2272  {
2273  using _CIter = common_iterator<_Iter, _Sent>;
2274  using type = decltype(std::declval<const _CIter&>().operator->());
2275  };
2276 
2277  static auto
2278  _S_iter_cat()
2279  {
2280  if constexpr (requires { requires derived_from<__iter_category_t<_It>,
2281  forward_iterator_tag>; })
2282  return forward_iterator_tag{};
2283  else
2284  return input_iterator_tag{};
2285  }
2286 
2287  public:
2288  using iterator_concept = __conditional_t<forward_iterator<_It>,
2289  forward_iterator_tag,
2290  input_iterator_tag>;
2291  using iterator_category = decltype(_S_iter_cat());
2292  using value_type = iter_value_t<_It>;
2293  using difference_type = iter_difference_t<_It>;
2294  using pointer = typename __ptr<_It>::type;
2295  using reference = iter_reference_t<_It>;
2296  };
2297 
2298  // [iterators.counted] Counted iterators
2299 
2300  namespace __detail
2301  {
2302  template<typename _It>
2303  struct __counted_iter_value_type
2304  { };
2305 
2306  template<indirectly_readable _It>
2307  struct __counted_iter_value_type<_It>
2308  { using value_type = iter_value_t<_It>; };
2309 
2310  template<typename _It>
2311  struct __counted_iter_concept
2312  { };
2313 
2314  template<typename _It>
2315  requires requires { typename _It::iterator_concept; }
2316  struct __counted_iter_concept<_It>
2317  { using iterator_concept = typename _It::iterator_concept; };
2318 
2319  template<typename _It>
2320  struct __counted_iter_cat
2321  { };
2322 
2323  template<typename _It>
2324  requires requires { typename _It::iterator_category; }
2325  struct __counted_iter_cat<_It>
2326  { using iterator_category = typename _It::iterator_category; };
2327  }
2328 
2329  /// An iterator adaptor that keeps track of the distance to the end.
2330  template<input_or_output_iterator _It>
2332  : public __detail::__counted_iter_value_type<_It>,
2333  public __detail::__counted_iter_concept<_It>,
2334  public __detail::__counted_iter_cat<_It>
2335  {
2336  public:
2337  using iterator_type = _It;
2338  // value_type defined in __counted_iter_value_type
2339  using difference_type = iter_difference_t<_It>;
2340  // iterator_concept defined in __counted_iter_concept
2341  // iterator_category defined in __counted_iter_cat
2342 
2343  constexpr counted_iterator() requires default_initializable<_It> = default;
2344 
2345  constexpr
2346  counted_iterator(_It __i, iter_difference_t<_It> __n)
2347  : _M_current(std::move(__i)), _M_length(__n)
2348  { __glibcxx_assert(__n >= 0); }
2349 
2350  template<typename _It2>
2351  requires convertible_to<const _It2&, _It>
2352  constexpr
2354  : _M_current(__x._M_current), _M_length(__x._M_length)
2355  { }
2356 
2357  template<typename _It2>
2358  requires assignable_from<_It&, const _It2&>
2359  constexpr counted_iterator&
2360  operator=(const counted_iterator<_It2>& __x)
2361  {
2362  _M_current = __x._M_current;
2363  _M_length = __x._M_length;
2364  return *this;
2365  }
2366 
2367  [[nodiscard]]
2368  constexpr const _It&
2369  base() const & noexcept
2370  { return _M_current; }
2371 
2372  [[nodiscard]]
2373  constexpr _It
2374  base() &&
2375  noexcept(is_nothrow_move_constructible_v<_It>)
2376  { return std::move(_M_current); }
2377 
2378  [[nodiscard]]
2379  constexpr iter_difference_t<_It>
2380  count() const noexcept { return _M_length; }
2381 
2382  [[nodiscard]]
2383  constexpr decltype(auto)
2384  operator*()
2385  noexcept(noexcept(*_M_current))
2386  {
2387  __glibcxx_assert( _M_length > 0 );
2388  return *_M_current;
2389  }
2390 
2391  [[nodiscard]]
2392  constexpr decltype(auto)
2393  operator*() const
2394  noexcept(noexcept(*_M_current))
2395  requires __detail::__dereferenceable<const _It>
2396  {
2397  __glibcxx_assert( _M_length > 0 );
2398  return *_M_current;
2399  }
2400 
2401  [[nodiscard]]
2402  constexpr auto
2403  operator->() const noexcept
2404  requires contiguous_iterator<_It>
2405  { return std::to_address(_M_current); }
2406 
2407  constexpr counted_iterator&
2408  operator++()
2409  {
2410  __glibcxx_assert(_M_length > 0);
2411  ++_M_current;
2412  --_M_length;
2413  return *this;
2414  }
2415 
2416  constexpr decltype(auto)
2417  operator++(int)
2418  {
2419  __glibcxx_assert(_M_length > 0);
2420  --_M_length;
2421  __try
2422  {
2423  return _M_current++;
2424  } __catch(...) {
2425  ++_M_length;
2426  __throw_exception_again;
2427  }
2428  }
2429 
2430  constexpr counted_iterator
2431  operator++(int) requires forward_iterator<_It>
2432  {
2433  auto __tmp = *this;
2434  ++*this;
2435  return __tmp;
2436  }
2437 
2438  constexpr counted_iterator&
2439  operator--() requires bidirectional_iterator<_It>
2440  {
2441  --_M_current;
2442  ++_M_length;
2443  return *this;
2444  }
2445 
2446  constexpr counted_iterator
2447  operator--(int) requires bidirectional_iterator<_It>
2448  {
2449  auto __tmp = *this;
2450  --*this;
2451  return __tmp;
2452  }
2453 
2454  [[nodiscard]]
2455  constexpr counted_iterator
2456  operator+(iter_difference_t<_It> __n) const
2457  requires random_access_iterator<_It>
2458  { return counted_iterator(_M_current + __n, _M_length - __n); }
2459 
2460  [[nodiscard]]
2461  friend constexpr counted_iterator
2462  operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2463  requires random_access_iterator<_It>
2464  { return __x + __n; }
2465 
2466  constexpr counted_iterator&
2467  operator+=(iter_difference_t<_It> __n)
2468  requires random_access_iterator<_It>
2469  {
2470  __glibcxx_assert(__n <= _M_length);
2471  _M_current += __n;
2472  _M_length -= __n;
2473  return *this;
2474  }
2475 
2476  [[nodiscard]]
2477  constexpr counted_iterator
2478  operator-(iter_difference_t<_It> __n) const
2479  requires random_access_iterator<_It>
2480  { return counted_iterator(_M_current - __n, _M_length + __n); }
2481 
2482  template<common_with<_It> _It2>
2483  [[nodiscard]]
2484  friend constexpr iter_difference_t<_It2>
2485  operator-(const counted_iterator& __x,
2486  const counted_iterator<_It2>& __y)
2487  { return __y._M_length - __x._M_length; }
2488 
2489  [[nodiscard]]
2490  friend constexpr iter_difference_t<_It>
2491  operator-(const counted_iterator& __x, default_sentinel_t)
2492  { return -__x._M_length; }
2493 
2494  [[nodiscard]]
2495  friend constexpr iter_difference_t<_It>
2496  operator-(default_sentinel_t, const counted_iterator& __y)
2497  { return __y._M_length; }
2498 
2499  constexpr counted_iterator&
2500  operator-=(iter_difference_t<_It> __n)
2501  requires random_access_iterator<_It>
2502  {
2503  __glibcxx_assert(-__n <= _M_length);
2504  _M_current -= __n;
2505  _M_length += __n;
2506  return *this;
2507  }
2508 
2509  [[nodiscard]]
2510  constexpr decltype(auto)
2511  operator[](iter_difference_t<_It> __n) const
2512  noexcept(noexcept(_M_current[__n]))
2513  requires random_access_iterator<_It>
2514  {
2515  __glibcxx_assert(__n < _M_length);
2516  return _M_current[__n];
2517  }
2518 
2519  template<common_with<_It> _It2>
2520  [[nodiscard]]
2521  friend constexpr bool
2522  operator==(const counted_iterator& __x,
2523  const counted_iterator<_It2>& __y)
2524  { return __x._M_length == __y._M_length; }
2525 
2526  [[nodiscard]]
2527  friend constexpr bool
2528  operator==(const counted_iterator& __x, default_sentinel_t)
2529  { return __x._M_length == 0; }
2530 
2531  template<common_with<_It> _It2>
2532  [[nodiscard]]
2533  friend constexpr strong_ordering
2534  operator<=>(const counted_iterator& __x,
2535  const counted_iterator<_It2>& __y)
2536  { return __y._M_length <=> __x._M_length; }
2537 
2538  [[nodiscard]]
2539  friend constexpr iter_rvalue_reference_t<_It>
2540  iter_move(const counted_iterator& __i)
2541  noexcept(noexcept(ranges::iter_move(__i._M_current)))
2542  requires input_iterator<_It>
2543  {
2544  __glibcxx_assert( __i._M_length > 0 );
2545  return ranges::iter_move(__i._M_current);
2546  }
2547 
2548  template<indirectly_swappable<_It> _It2>
2549  friend constexpr void
2550  iter_swap(const counted_iterator& __x,
2551  const counted_iterator<_It2>& __y)
2552  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2553  {
2554  __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
2555  ranges::iter_swap(__x._M_current, __y._M_current);
2556  }
2557 
2558  private:
2559  template<input_or_output_iterator _It2> friend class counted_iterator;
2560 
2561  _It _M_current = _It();
2562  iter_difference_t<_It> _M_length = 0;
2563  };
2564 
2565  template<input_iterator _It>
2566  requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2568  {
2569  using pointer = __conditional_t<contiguous_iterator<_It>,
2571  void>;
2572  };
2573 
2574 #if __glibcxx_ranges_as_const // >= C++23
2575  template<indirectly_readable _It>
2576  using iter_const_reference_t
2577  = common_reference_t<const iter_value_t<_It>&&, iter_reference_t<_It>>;
2578 
2579  template<input_iterator _It> class basic_const_iterator;
2580 
2581  namespace __detail
2582  {
2583  template<typename _It>
2584  concept __constant_iterator = input_iterator<_It>
2585  && same_as<iter_const_reference_t<_It>, iter_reference_t<_It>>;
2586 
2587  template<typename _Tp>
2588  inline constexpr bool __is_const_iterator = false;
2589 
2590  template<typename _It>
2591  inline constexpr bool __is_const_iterator<basic_const_iterator<_It>> = true;
2592 
2593  template<typename _Tp>
2594  concept __not_a_const_iterator = !__is_const_iterator<_Tp>;
2595 
2596  template<indirectly_readable _It>
2597  using __iter_const_rvalue_reference_t
2598  = common_reference_t<const iter_value_t<_It>&&, iter_rvalue_reference_t<_It>>;
2599 
2600  template<typename _It>
2601  struct __basic_const_iterator_iter_cat
2602  { };
2603 
2604  template<forward_iterator _It>
2605  struct __basic_const_iterator_iter_cat<_It>
2606  { using iterator_category = __iter_category_t<_It>; };
2607  } // namespace detail
2608 
2609  template<input_iterator _It>
2610  using const_iterator
2611  = __conditional_t<__detail::__constant_iterator<_It>, _It, basic_const_iterator<_It>>;
2612 
2613  namespace __detail
2614  {
2615  template<typename _Sent>
2616  struct __const_sentinel
2617  { using type = _Sent; };
2618 
2619  template<input_iterator _Sent>
2620  struct __const_sentinel<_Sent>
2621  { using type = const_iterator<_Sent>; };
2622  } // namespace __detail
2623 
2624  template<semiregular _Sent>
2625  using const_sentinel = typename __detail::__const_sentinel<_Sent>::type;
2626 
2627  template<input_iterator _It>
2628  class basic_const_iterator
2629  : public __detail::__basic_const_iterator_iter_cat<_It>
2630  {
2631  _It _M_current = _It();
2632  using __reference = iter_const_reference_t<_It>;
2633  using __rvalue_reference = __detail::__iter_const_rvalue_reference_t<_It>;
2634 
2635  static auto
2636  _S_iter_concept()
2637  {
2638  if constexpr (contiguous_iterator<_It>)
2639  return contiguous_iterator_tag{};
2640  else if constexpr (random_access_iterator<_It>)
2641  return random_access_iterator_tag{};
2642  else if constexpr (bidirectional_iterator<_It>)
2643  return bidirectional_iterator_tag{};
2644  else if constexpr (forward_iterator<_It>)
2645  return forward_iterator_tag{};
2646  else
2647  return input_iterator_tag{};
2648  }
2649 
2650  template<input_iterator _It2> friend class basic_const_iterator;
2651 
2652  public:
2653  using iterator_concept = decltype(_S_iter_concept());
2654  using value_type = iter_value_t<_It>;
2655  using difference_type = iter_difference_t<_It>;
2656 
2657  basic_const_iterator() requires default_initializable<_It> = default;
2658 
2659  constexpr
2660  basic_const_iterator(_It __current)
2661  noexcept(is_nothrow_move_constructible_v<_It>)
2662  : _M_current(std::move(__current))
2663  { }
2664 
2665  template<convertible_to<_It> _It2>
2666  constexpr
2667  basic_const_iterator(basic_const_iterator<_It2> __current)
2668  noexcept(is_nothrow_constructible_v<_It, _It2>)
2669  : _M_current(std::move(__current._M_current))
2670  { }
2671 
2672  template<__detail::__different_from<basic_const_iterator> _Tp>
2673  requires convertible_to<_Tp, _It>
2674  constexpr
2675  basic_const_iterator(_Tp&& __current)
2676  noexcept(is_nothrow_constructible_v<_It, _Tp>)
2677  : _M_current(std::forward<_Tp>(__current))
2678  { }
2679 
2680  constexpr const _It&
2681  base() const & noexcept
2682  { return _M_current; }
2683 
2684  constexpr _It
2685  base() &&
2686  noexcept(is_nothrow_move_constructible_v<_It>)
2687  { return std::move(_M_current); }
2688 
2689  constexpr __reference
2690  operator*() const
2691  noexcept(noexcept(static_cast<__reference>(*_M_current)))
2692  { return static_cast<__reference>(*_M_current); }
2693 
2694  constexpr const auto*
2695  operator->() const
2696  noexcept(contiguous_iterator<_It> || noexcept(*_M_current))
2697  requires is_lvalue_reference_v<iter_reference_t<_It>>
2698  && same_as<remove_cvref_t<iter_reference_t<_It>>, value_type>
2699  {
2700  if constexpr (contiguous_iterator<_It>)
2701  return std::to_address(_M_current);
2702  else
2703  return std::__addressof(*_M_current);
2704  }
2705 
2706  constexpr basic_const_iterator&
2707  operator++()
2708  noexcept(noexcept(++_M_current))
2709  {
2710  ++_M_current;
2711  return *this;
2712  }
2713 
2714  constexpr void
2715  operator++(int)
2716  noexcept(noexcept(++_M_current))
2717  { ++_M_current; }
2718 
2719  constexpr basic_const_iterator
2720  operator++(int)
2721  noexcept(noexcept(++*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2722  requires forward_iterator<_It>
2723  {
2724  auto __tmp = *this;
2725  ++*this;
2726  return __tmp;
2727  }
2728 
2729  constexpr basic_const_iterator&
2730  operator--()
2731  noexcept(noexcept(--_M_current))
2732  requires bidirectional_iterator<_It>
2733  {
2734  --_M_current;
2735  return *this;
2736  }
2737 
2738  constexpr basic_const_iterator
2739  operator--(int)
2740  noexcept(noexcept(--*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2741  requires bidirectional_iterator<_It>
2742  {
2743  auto __tmp = *this;
2744  --*this;
2745  return __tmp;
2746  }
2747 
2748  constexpr basic_const_iterator&
2749  operator+=(difference_type __n)
2750  noexcept(noexcept(_M_current += __n))
2751  requires random_access_iterator<_It>
2752  {
2753  _M_current += __n;
2754  return *this;
2755  }
2756 
2757  constexpr basic_const_iterator&
2758  operator-=(difference_type __n)
2759  noexcept(noexcept(_M_current -= __n))
2760  requires random_access_iterator<_It>
2761  {
2762  _M_current -= __n;
2763  return *this;
2764  }
2765 
2766  constexpr __reference
2767  operator[](difference_type __n) const
2768  noexcept(noexcept(static_cast<__reference>(_M_current[__n])))
2769  requires random_access_iterator<_It>
2770  { return static_cast<__reference>(_M_current[__n]); }
2771 
2772  template<sentinel_for<_It> _Sent>
2773  constexpr bool
2774  operator==(const _Sent& __s) const
2775  noexcept(noexcept(_M_current == __s))
2776  { return _M_current == __s; }
2777 
2778  template<__detail::__not_a_const_iterator _CIt>
2779  requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2780  constexpr
2781  operator _CIt() const&
2782  { return _M_current; }
2783 
2784  template<__detail::__not_a_const_iterator _CIt>
2785  requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2786  constexpr
2787  operator _CIt() &&
2788  { return std::move(_M_current); }
2789 
2790  constexpr bool
2791  operator<(const basic_const_iterator& __y) const
2792  noexcept(noexcept(_M_current < __y._M_current))
2793  requires random_access_iterator<_It>
2794  { return _M_current < __y._M_current; }
2795 
2796  constexpr bool
2797  operator>(const basic_const_iterator& __y) const
2798  noexcept(noexcept(_M_current > __y._M_current))
2799  requires random_access_iterator<_It>
2800  { return _M_current > __y._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 auto
2815  operator<=>(const basic_const_iterator& __y) const
2816  noexcept(noexcept(_M_current <=> __y._M_current))
2817  requires random_access_iterator<_It> && three_way_comparable<_It>
2818  { return _M_current <=> __y._M_current; }
2819 
2820  template<__detail::__different_from<basic_const_iterator> _It2>
2821  constexpr bool
2822  operator<(const _It2& __y) const
2823  noexcept(noexcept(_M_current < __y))
2824  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2825  { return _M_current < __y; }
2826 
2827  template<__detail::__different_from<basic_const_iterator> _It2>
2828  constexpr bool
2829  operator>(const _It2& __y) const
2830  noexcept(noexcept(_M_current > __y))
2831  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2832  { return _M_current > __y; }
2833 
2834  template<__detail::__different_from<basic_const_iterator> _It2>
2835  constexpr bool
2836  operator<=(const _It2& __y) const
2837  noexcept(noexcept(_M_current <= __y))
2838  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2839  { return _M_current <= __y; }
2840 
2841  template<__detail::__different_from<basic_const_iterator> _It2>
2842  constexpr bool
2843  operator>=(const _It2& __y) const
2844  noexcept(noexcept(_M_current >= __y))
2845  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2846  { return _M_current >= __y; }
2847 
2848  template<__detail::__different_from<basic_const_iterator> _It2>
2849  constexpr auto
2850  operator<=>(const _It2& __y) const
2851  noexcept(noexcept(_M_current <=> __y))
2852  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2853  && three_way_comparable_with<_It, _It2>
2854  { return _M_current <=> __y; }
2855 
2856  template<__detail::__not_a_const_iterator _It2>
2857  friend constexpr bool
2858  operator<(const _It2& __x, const basic_const_iterator& __y)
2859  noexcept(noexcept(__x < __y._M_current))
2860  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2861  { return __x < __y._M_current; }
2862 
2863  template<__detail::__not_a_const_iterator _It2>
2864  friend constexpr bool
2865  operator>(const _It2& __x, const basic_const_iterator& __y)
2866  noexcept(noexcept(__x > __y._M_current))
2867  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2868  { return __x > __y._M_current; }
2869 
2870  template<__detail::__not_a_const_iterator _It2>
2871  friend constexpr bool
2872  operator<=(const _It2& __x, const basic_const_iterator& __y)
2873  noexcept(noexcept(__x <= __y._M_current))
2874  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2875  { return __x <= __y._M_current; }
2876 
2877  template<__detail::__not_a_const_iterator _It2>
2878  friend constexpr bool
2879  operator>=(const _It2& __x, const basic_const_iterator& __y)
2880  noexcept(noexcept(__x >= __y._M_current))
2881  requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2882  { return __x >= __y._M_current; }
2883 
2884  friend constexpr basic_const_iterator
2885  operator+(const basic_const_iterator& __i, difference_type __n)
2886  noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2887  requires random_access_iterator<_It>
2888  { return basic_const_iterator(__i._M_current + __n); }
2889 
2890  friend constexpr basic_const_iterator
2891  operator+(difference_type __n, const basic_const_iterator& __i)
2892  noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2893  requires random_access_iterator<_It>
2894  { return basic_const_iterator(__i._M_current + __n); }
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  template<sized_sentinel_for<_It> _Sent>
2903  constexpr difference_type
2904  operator-(const _Sent& __y) const
2905  noexcept(noexcept(_M_current - __y))
2906  { return _M_current - __y; }
2907 
2908  template<__detail::__not_a_const_iterator _Sent>
2909  requires sized_sentinel_for<_Sent, _It>
2910  friend constexpr difference_type
2911  operator-(const _Sent& __x, const basic_const_iterator& __y)
2912  noexcept(noexcept(__x - __y._M_current))
2913  { return __x - __y._M_current; }
2914 
2915  friend constexpr __rvalue_reference
2916  iter_move(const basic_const_iterator& __i)
2917  noexcept(noexcept(static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current))))
2918  { return static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current)); }
2919  };
2920 
2921  template<typename _Tp, common_with<_Tp> _Up>
2922  requires input_iterator<common_type_t<_Tp, _Up>>
2923  struct common_type<basic_const_iterator<_Tp>, _Up>
2924  { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2925 
2926  template<typename _Tp, common_with<_Tp> _Up>
2927  requires input_iterator<common_type_t<_Tp, _Up>>
2928  struct common_type<_Up, basic_const_iterator<_Tp>>
2929  { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2930 
2931  template<typename _Tp, common_with<_Tp> _Up>
2932  requires input_iterator<common_type_t<_Tp, _Up>>
2933  struct common_type<basic_const_iterator<_Tp>, basic_const_iterator<_Up>>
2934  { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2935 
2936  template<input_iterator _It>
2937  constexpr const_iterator<_It>
2938  make_const_iterator(_It __it)
2939  noexcept(is_nothrow_convertible_v<_It, const_iterator<_It>>)
2940  { return __it; }
2941 
2942  template<semiregular _Sent>
2943  constexpr const_sentinel<_Sent>
2944  make_const_sentinel(_Sent __s)
2945  noexcept(is_nothrow_convertible_v<_Sent, const_sentinel<_Sent>>)
2946  { return __s; }
2947 #endif // C++23
2948 #endif // C++20
2949 
2950  /// @} group iterators
2951 
2952  template<typename _Iterator>
2953  _GLIBCXX20_CONSTEXPR
2954  auto
2955  __niter_base(move_iterator<_Iterator> __it)
2956  -> decltype(make_move_iterator(__niter_base(__it.base())))
2957  { return make_move_iterator(__niter_base(__it.base())); }
2958 
2959  template<typename _Iterator>
2960  struct __is_move_iterator<move_iterator<_Iterator> >
2961  {
2962  enum { __value = 1 };
2963  typedef __true_type __type;
2964  };
2965 
2966  template<typename _Iterator>
2967  _GLIBCXX20_CONSTEXPR
2968  auto
2969  __miter_base(move_iterator<_Iterator> __it)
2970  -> decltype(__miter_base(__it.base()))
2971  { return __miter_base(__it.base()); }
2972 
2973 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2974 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2975  std::__make_move_if_noexcept_iterator(_Iter)
2976 #else
2977 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2978 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2979 #endif // C++11
2980 
2981 #if __cpp_deduction_guides >= 201606
2982  // These helper traits are used for deduction guides
2983  // of associative containers.
2984  template<typename _InputIterator>
2985  using __iter_key_t = remove_const_t<
2986 #if __glibcxx_tuple_like // >= C++23
2987  tuple_element_t<0, typename iterator_traits<_InputIterator>::value_type>>;
2988 #else
2989  typename iterator_traits<_InputIterator>::value_type::first_type>;
2990 #endif
2991 
2992  template<typename _InputIterator>
2993  using __iter_val_t
2994 #if __glibcxx_tuple_like // >= C++23
2995  = tuple_element_t<1, typename iterator_traits<_InputIterator>::value_type>;
2996 #else
2997  = typename iterator_traits<_InputIterator>::value_type::second_type;
2998 #endif
2999 
3000  template<typename _T1, typename _T2>
3001  struct pair;
3002 
3003  template<typename _InputIterator>
3004  using __iter_to_alloc_t
3005  = pair<const __iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>>;
3006 #endif // __cpp_deduction_guides
3007 
3008 _GLIBCXX_END_NAMESPACE_VERSION
3009 } // namespace
3010 
3011 #ifdef _GLIBCXX_DEBUG
3012 # include <debug/stl_iterator.h>
3013 #endif
3014 
3015 #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:70
_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:126
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:2153