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