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