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