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