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