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