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, typename _Iterator>
930  inline insert_iterator<_Container>
931  inserter(_Container& __x, _Iterator __i)
932  {
933  return insert_iterator<_Container>(__x,
934  typename _Container::iterator(__i));
935  }
936 #endif
937 
938  // @} group iterators
939 
940 _GLIBCXX_END_NAMESPACE_VERSION
941 } // namespace
942 
943 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
944 {
945 _GLIBCXX_BEGIN_NAMESPACE_VERSION
946 
947  // This iterator adapter is @a normal in the sense that it does not
948  // change the semantics of any of the operators of its iterator
949  // parameter. Its primary purpose is to convert an iterator that is
950  // not a class, e.g. a pointer, into an iterator that is a class.
951  // The _Container parameter exists solely so that different containers
952  // using this template can instantiate different types, even if the
953  // _Iterator parameter is the same.
954  template<typename _Iterator, typename _Container>
955  class __normal_iterator
956  {
957  protected:
958  _Iterator _M_current;
959 
960  typedef std::iterator_traits<_Iterator> __traits_type;
961 
962  public:
963  typedef _Iterator iterator_type;
964  typedef typename __traits_type::iterator_category iterator_category;
965  typedef typename __traits_type::value_type value_type;
966  typedef typename __traits_type::difference_type difference_type;
967  typedef typename __traits_type::reference reference;
968  typedef typename __traits_type::pointer pointer;
969 
970 #if __cplusplus > 201703L && __cpp_lib_concepts
971  using iterator_concept = std::__detail::__iter_concept<_Iterator>;
972 #endif
973 
974  _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
975  : _M_current(_Iterator()) { }
976 
977  explicit _GLIBCXX20_CONSTEXPR
978  __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
979  : _M_current(__i) { }
980 
981  // Allow iterator to const_iterator conversion
982  template<typename _Iter>
983  _GLIBCXX20_CONSTEXPR
984  __normal_iterator(const __normal_iterator<_Iter,
985  typename __enable_if<
986  (std::__are_same<_Iter, typename _Container::pointer>::__value),
987  _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
988  : _M_current(__i.base()) { }
989 
990  // Forward iterator requirements
991  _GLIBCXX20_CONSTEXPR
992  reference
993  operator*() const _GLIBCXX_NOEXCEPT
994  { return *_M_current; }
995 
996  _GLIBCXX20_CONSTEXPR
997  pointer
998  operator->() const _GLIBCXX_NOEXCEPT
999  { return _M_current; }
1000 
1001  _GLIBCXX20_CONSTEXPR
1002  __normal_iterator&
1003  operator++() _GLIBCXX_NOEXCEPT
1004  {
1005  ++_M_current;
1006  return *this;
1007  }
1008 
1009  _GLIBCXX20_CONSTEXPR
1010  __normal_iterator
1011  operator++(int) _GLIBCXX_NOEXCEPT
1012  { return __normal_iterator(_M_current++); }
1013 
1014  // Bidirectional iterator requirements
1015  _GLIBCXX20_CONSTEXPR
1016  __normal_iterator&
1017  operator--() _GLIBCXX_NOEXCEPT
1018  {
1019  --_M_current;
1020  return *this;
1021  }
1022 
1023  _GLIBCXX20_CONSTEXPR
1024  __normal_iterator
1025  operator--(int) _GLIBCXX_NOEXCEPT
1026  { return __normal_iterator(_M_current--); }
1027 
1028  // Random access iterator requirements
1029  _GLIBCXX20_CONSTEXPR
1030  reference
1031  operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
1032  { return _M_current[__n]; }
1033 
1034  _GLIBCXX20_CONSTEXPR
1035  __normal_iterator&
1036  operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1037  { _M_current += __n; return *this; }
1038 
1039  _GLIBCXX20_CONSTEXPR
1040  __normal_iterator
1041  operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
1042  { return __normal_iterator(_M_current + __n); }
1043 
1044  _GLIBCXX20_CONSTEXPR
1045  __normal_iterator&
1046  operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1047  { _M_current -= __n; return *this; }
1048 
1049  _GLIBCXX20_CONSTEXPR
1050  __normal_iterator
1051  operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
1052  { return __normal_iterator(_M_current - __n); }
1053 
1054  _GLIBCXX20_CONSTEXPR
1055  const _Iterator&
1056  base() const _GLIBCXX_NOEXCEPT
1057  { return _M_current; }
1058  };
1059 
1060  // Note: In what follows, the left- and right-hand-side iterators are
1061  // allowed to vary in types (conceptually in cv-qualification) so that
1062  // comparison between cv-qualified and non-cv-qualified iterators be
1063  // valid. However, the greedy and unfriendly operators in std::rel_ops
1064  // will make overload resolution ambiguous (when in scope) if we don't
1065  // provide overloads whose operands are of the same type. Can someone
1066  // remind me what generic programming is about? -- Gaby
1067 
1068 #if __cpp_lib_three_way_comparison
1069  template<typename _IteratorL, typename _IteratorR, typename _Container>
1070  requires requires (_IteratorL __lhs, _IteratorR __rhs)
1071  { { __lhs == __rhs } -> std::convertible_to<bool>; }
1072  constexpr bool
1073  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1074  const __normal_iterator<_IteratorR, _Container>& __rhs)
1075  noexcept(noexcept(__lhs.base() == __rhs.base()))
1076  { return __lhs.base() == __rhs.base(); }
1077 
1078  template<typename _IteratorL, typename _IteratorR, typename _Container>
1079  constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
1080  operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1081  const __normal_iterator<_IteratorR, _Container>& __rhs)
1082  noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1083  { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1084 #else
1085  // Forward iterator requirements
1086  template<typename _IteratorL, typename _IteratorR, typename _Container>
1087  _GLIBCXX20_CONSTEXPR
1088  inline bool
1089  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1090  const __normal_iterator<_IteratorR, _Container>& __rhs)
1091  _GLIBCXX_NOEXCEPT
1092  { return __lhs.base() == __rhs.base(); }
1093 
1094  template<typename _Iterator, typename _Container>
1095  _GLIBCXX20_CONSTEXPR
1096  inline bool
1097  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1098  const __normal_iterator<_Iterator, _Container>& __rhs)
1099  _GLIBCXX_NOEXCEPT
1100  { return __lhs.base() == __rhs.base(); }
1101 
1102  template<typename _IteratorL, typename _IteratorR, typename _Container>
1103  _GLIBCXX20_CONSTEXPR
1104  inline bool
1105  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1106  const __normal_iterator<_IteratorR, _Container>& __rhs)
1107  _GLIBCXX_NOEXCEPT
1108  { return __lhs.base() != __rhs.base(); }
1109 
1110  template<typename _Iterator, typename _Container>
1111  _GLIBCXX20_CONSTEXPR
1112  inline bool
1113  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
1114  const __normal_iterator<_Iterator, _Container>& __rhs)
1115  _GLIBCXX_NOEXCEPT
1116  { return __lhs.base() != __rhs.base(); }
1117 
1118  // Random access iterator requirements
1119  template<typename _IteratorL, typename _IteratorR, typename _Container>
1120  inline bool
1121  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1122  const __normal_iterator<_IteratorR, _Container>& __rhs)
1123  _GLIBCXX_NOEXCEPT
1124  { return __lhs.base() < __rhs.base(); }
1125 
1126  template<typename _Iterator, typename _Container>
1127  _GLIBCXX20_CONSTEXPR
1128  inline bool
1129  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
1130  const __normal_iterator<_Iterator, _Container>& __rhs)
1131  _GLIBCXX_NOEXCEPT
1132  { return __lhs.base() < __rhs.base(); }
1133 
1134  template<typename _IteratorL, typename _IteratorR, typename _Container>
1135  inline bool
1136  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1137  const __normal_iterator<_IteratorR, _Container>& __rhs)
1138  _GLIBCXX_NOEXCEPT
1139  { return __lhs.base() > __rhs.base(); }
1140 
1141  template<typename _Iterator, typename _Container>
1142  _GLIBCXX20_CONSTEXPR
1143  inline bool
1144  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
1145  const __normal_iterator<_Iterator, _Container>& __rhs)
1146  _GLIBCXX_NOEXCEPT
1147  { return __lhs.base() > __rhs.base(); }
1148 
1149  template<typename _IteratorL, typename _IteratorR, typename _Container>
1150  inline bool
1151  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1152  const __normal_iterator<_IteratorR, _Container>& __rhs)
1153  _GLIBCXX_NOEXCEPT
1154  { return __lhs.base() <= __rhs.base(); }
1155 
1156  template<typename _Iterator, typename _Container>
1157  _GLIBCXX20_CONSTEXPR
1158  inline bool
1159  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
1160  const __normal_iterator<_Iterator, _Container>& __rhs)
1161  _GLIBCXX_NOEXCEPT
1162  { return __lhs.base() <= __rhs.base(); }
1163 
1164  template<typename _IteratorL, typename _IteratorR, typename _Container>
1165  inline bool
1166  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1167  const __normal_iterator<_IteratorR, _Container>& __rhs)
1168  _GLIBCXX_NOEXCEPT
1169  { return __lhs.base() >= __rhs.base(); }
1170 
1171  template<typename _Iterator, typename _Container>
1172  _GLIBCXX20_CONSTEXPR
1173  inline bool
1174  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1175  const __normal_iterator<_Iterator, _Container>& __rhs)
1176  _GLIBCXX_NOEXCEPT
1177  { return __lhs.base() >= __rhs.base(); }
1178 #endif // three-way comparison
1179 
1180  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1181  // According to the resolution of DR179 not only the various comparison
1182  // operators but also operator- must accept mixed iterator/const_iterator
1183  // parameters.
1184  template<typename _IteratorL, typename _IteratorR, typename _Container>
1185 #if __cplusplus >= 201103L
1186  // DR 685.
1187  _GLIBCXX20_CONSTEXPR
1188  inline auto
1189  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1190  const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1191  -> decltype(__lhs.base() - __rhs.base())
1192 #else
1193  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1194  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1195  const __normal_iterator<_IteratorR, _Container>& __rhs)
1196 #endif
1197  { return __lhs.base() - __rhs.base(); }
1198 
1199  template<typename _Iterator, typename _Container>
1200  _GLIBCXX20_CONSTEXPR
1201  inline typename __normal_iterator<_Iterator, _Container>::difference_type
1202  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1203  const __normal_iterator<_Iterator, _Container>& __rhs)
1204  _GLIBCXX_NOEXCEPT
1205  { return __lhs.base() - __rhs.base(); }
1206 
1207  template<typename _Iterator, typename _Container>
1208  _GLIBCXX20_CONSTEXPR
1209  inline __normal_iterator<_Iterator, _Container>
1210  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1211  __n, const __normal_iterator<_Iterator, _Container>& __i)
1212  _GLIBCXX_NOEXCEPT
1213  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1214 
1215 _GLIBCXX_END_NAMESPACE_VERSION
1216 } // namespace
1217 
1218 namespace std _GLIBCXX_VISIBILITY(default)
1219 {
1220 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1221 
1222  template<typename _Iterator, typename _Container>
1223  _GLIBCXX20_CONSTEXPR
1224  _Iterator
1225  __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1227  { return __it.base(); }
1228 
1229 #if __cplusplus >= 201103L
1230  /**
1231  * @addtogroup iterators
1232  * @{
1233  */
1234 
1235 #if __cplusplus > 201703L && __cpp_lib_concepts
1236  template<semiregular _Sent>
1237  class move_sentinel
1238  {
1239  public:
1240  constexpr
1241  move_sentinel()
1242  noexcept(is_nothrow_default_constructible_v<_Sent>)
1243  : _M_last() { }
1244 
1245  constexpr explicit
1246  move_sentinel(_Sent __s)
1247  noexcept(is_nothrow_move_constructible_v<_Sent>)
1248  : _M_last(std::move(__s)) { }
1249 
1250  template<typename _S2> requires convertible_to<const _S2&, _Sent>
1251  constexpr
1252  move_sentinel(const move_sentinel<_S2>& __s)
1253  noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1254  : _M_last(__s.base())
1255  { }
1256 
1257  template<typename _S2> requires assignable_from<_Sent&, const _S2&>
1258  constexpr move_sentinel&
1259  operator=(const move_sentinel<_S2>& __s)
1260  noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1261  {
1262  _M_last = __s.base();
1263  return *this;
1264  }
1265 
1266  constexpr _Sent
1267  base() const
1268  noexcept(is_nothrow_copy_constructible_v<_Sent>)
1269  { return _M_last; }
1270 
1271  private:
1272  _Sent _M_last;
1273  };
1274 #endif // C++20
1275 
1276  // 24.4.3 Move iterators
1277  /**
1278  * Class template move_iterator is an iterator adapter with the same
1279  * behavior as the underlying iterator except that its dereference
1280  * operator implicitly converts the value returned by the underlying
1281  * iterator's dereference operator to an rvalue reference. Some
1282  * generic algorithms can be called with move iterators to replace
1283  * copying with moving.
1284  */
1285  template<typename _Iterator>
1287  {
1288  _Iterator _M_current;
1289 
1291 #if __cplusplus > 201703L && __cpp_lib_concepts
1292  using __base_cat = typename __traits_type::iterator_category;
1293 #else
1294  using __base_ref = typename __traits_type::reference;
1295 #endif
1296 
1297  public:
1298  using iterator_type = _Iterator;
1299 
1300 #if __cplusplus > 201703L && __cpp_lib_concepts
1301  using iterator_concept = input_iterator_tag;
1302  using iterator_category
1303  = __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
1304  using value_type = iter_value_t<_Iterator>;
1305  using difference_type = iter_difference_t<_Iterator>;
1306  using pointer = _Iterator;
1307  using reference = iter_rvalue_reference_t<_Iterator>;
1308 #else
1309  typedef typename __traits_type::iterator_category iterator_category;
1310  typedef typename __traits_type::value_type value_type;
1311  typedef typename __traits_type::difference_type difference_type;
1312  // NB: DR 680.
1313  typedef _Iterator pointer;
1314  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1315  // 2106. move_iterator wrapping iterators returning prvalues
1317  typename remove_reference<__base_ref>::type&&,
1318  __base_ref>::type reference;
1319 #endif
1320 
1321  _GLIBCXX17_CONSTEXPR
1322  move_iterator()
1323  : _M_current() { }
1324 
1325  explicit _GLIBCXX17_CONSTEXPR
1326  move_iterator(iterator_type __i)
1327  : _M_current(std::move(__i)) { }
1328 
1329  template<typename _Iter>
1330  _GLIBCXX17_CONSTEXPR
1331  move_iterator(const move_iterator<_Iter>& __i)
1332  : _M_current(__i.base()) { }
1333 
1334 #if __cplusplus <= 201703L
1335  _GLIBCXX17_CONSTEXPR iterator_type
1336  base() const
1337  { return _M_current; }
1338 #else
1339  constexpr iterator_type
1340  base() const &
1341 #if __cpp_lib_concepts
1342  requires copy_constructible<iterator_type>
1343 #endif
1344  { return _M_current; }
1345 
1346  constexpr iterator_type
1347  base() &&
1348  { return std::move(_M_current); }
1349 #endif
1350 
1351  _GLIBCXX17_CONSTEXPR reference
1352  operator*() const
1353 #if __cplusplus > 201703L && __cpp_lib_concepts
1354  { return ranges::iter_move(_M_current); }
1355 #else
1356  { return static_cast<reference>(*_M_current); }
1357 #endif
1358 
1359  _GLIBCXX17_CONSTEXPR pointer
1360  operator->() const
1361  { return _M_current; }
1362 
1363  _GLIBCXX17_CONSTEXPR move_iterator&
1364  operator++()
1365  {
1366  ++_M_current;
1367  return *this;
1368  }
1369 
1370  _GLIBCXX17_CONSTEXPR move_iterator
1371  operator++(int)
1372  {
1373  move_iterator __tmp = *this;
1374  ++_M_current;
1375  return __tmp;
1376  }
1377 
1378 #if __cpp_lib_concepts
1379  constexpr void
1380  operator++(int) requires (!forward_iterator<_Iterator>)
1381  { ++_M_current; }
1382 #endif
1383 
1384  _GLIBCXX17_CONSTEXPR move_iterator&
1385  operator--()
1386  {
1387  --_M_current;
1388  return *this;
1389  }
1390 
1391  _GLIBCXX17_CONSTEXPR move_iterator
1392  operator--(int)
1393  {
1394  move_iterator __tmp = *this;
1395  --_M_current;
1396  return __tmp;
1397  }
1398 
1399  _GLIBCXX17_CONSTEXPR move_iterator
1400  operator+(difference_type __n) const
1401  { return move_iterator(_M_current + __n); }
1402 
1403  _GLIBCXX17_CONSTEXPR move_iterator&
1404  operator+=(difference_type __n)
1405  {
1406  _M_current += __n;
1407  return *this;
1408  }
1409 
1410  _GLIBCXX17_CONSTEXPR move_iterator
1411  operator-(difference_type __n) const
1412  { return move_iterator(_M_current - __n); }
1413 
1414  _GLIBCXX17_CONSTEXPR move_iterator&
1415  operator-=(difference_type __n)
1416  {
1417  _M_current -= __n;
1418  return *this;
1419  }
1420 
1421  _GLIBCXX17_CONSTEXPR reference
1422  operator[](difference_type __n) const
1423 #if __cplusplus > 201703L && __cpp_lib_concepts
1424  { return ranges::iter_move(_M_current + __n); }
1425 #else
1426  { return std::move(_M_current[__n]); }
1427 #endif
1428 
1429 #if __cplusplus > 201703L && __cpp_lib_concepts
1430  template<sentinel_for<_Iterator> _Sent>
1431  friend constexpr bool
1432  operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1433  { return __x.base() == __y.base(); }
1434 
1435  template<sized_sentinel_for<_Iterator> _Sent>
1436  friend constexpr iter_difference_t<_Iterator>
1437  operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1438  { return __x.base() - __y.base(); }
1439 
1440  template<sized_sentinel_for<_Iterator> _Sent>
1441  friend constexpr iter_difference_t<_Iterator>
1442  operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1443  { return __x.base() - __y.base(); }
1444 
1445  friend constexpr iter_rvalue_reference_t<_Iterator>
1446  iter_move(const move_iterator& __i)
1447  noexcept(noexcept(ranges::iter_move(__i._M_current)))
1448  { return ranges::iter_move(__i._M_current); }
1449 
1450  template<indirectly_swappable<_Iterator> _Iter2>
1451  friend constexpr void
1452  iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1453  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1454  { return ranges::iter_swap(__x._M_current, __y._M_current); }
1455 #endif // C++20
1456  };
1457 
1458  template<typename _IteratorL, typename _IteratorR>
1459  inline _GLIBCXX17_CONSTEXPR bool
1460  operator==(const move_iterator<_IteratorL>& __x,
1461  const move_iterator<_IteratorR>& __y)
1462 #if __cplusplus > 201703L && __cpp_lib_concepts
1463  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1464 #endif
1465  { return __x.base() == __y.base(); }
1466 
1467 #if __cpp_lib_three_way_comparison
1468  template<typename _IteratorL,
1469  three_way_comparable_with<_IteratorL> _IteratorR>
1470  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1471  operator<=>(const move_iterator<_IteratorL>& __x,
1472  const move_iterator<_IteratorR>& __y)
1473  { return __x.base() <=> __y.base(); }
1474 #else
1475  template<typename _IteratorL, typename _IteratorR>
1476  inline _GLIBCXX17_CONSTEXPR bool
1477  operator!=(const move_iterator<_IteratorL>& __x,
1478  const move_iterator<_IteratorR>& __y)
1479  { return !(__x == __y); }
1480 #endif
1481 
1482  template<typename _IteratorL, typename _IteratorR>
1483  inline _GLIBCXX17_CONSTEXPR bool
1484  operator<(const move_iterator<_IteratorL>& __x,
1485  const move_iterator<_IteratorR>& __y)
1486 #if __cplusplus > 201703L && __cpp_lib_concepts
1487  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1488 #endif
1489  { return __x.base() < __y.base(); }
1490 
1491  template<typename _IteratorL, typename _IteratorR>
1492  inline _GLIBCXX17_CONSTEXPR bool
1493  operator<=(const move_iterator<_IteratorL>& __x,
1494  const move_iterator<_IteratorR>& __y)
1495 #if __cplusplus > 201703L && __cpp_lib_concepts
1496  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1497 #endif
1498  { return !(__y < __x); }
1499 
1500  template<typename _IteratorL, typename _IteratorR>
1501  inline _GLIBCXX17_CONSTEXPR bool
1502  operator>(const move_iterator<_IteratorL>& __x,
1503  const move_iterator<_IteratorR>& __y)
1504 #if __cplusplus > 201703L && __cpp_lib_concepts
1505  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1506 #endif
1507  { return __y < __x; }
1508 
1509  template<typename _IteratorL, typename _IteratorR>
1510  inline _GLIBCXX17_CONSTEXPR bool
1511  operator>=(const move_iterator<_IteratorL>& __x,
1512  const move_iterator<_IteratorR>& __y)
1513 #if __cplusplus > 201703L && __cpp_lib_concepts
1514  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1515 #endif
1516  { return !(__x < __y); }
1517 
1518 #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1519  // Note: See __normal_iterator operators note from Gaby to understand
1520  // why we have these extra overloads for some move_iterator operators.
1521 
1522  // These extra overloads are not needed in C++20, because the ones above
1523  // are constrained with a requires-clause and so overload resolution will
1524  // prefer them to greedy unconstrained function templates.
1525 
1526  template<typename _Iterator>
1527  inline _GLIBCXX17_CONSTEXPR bool
1528  operator==(const move_iterator<_Iterator>& __x,
1529  const move_iterator<_Iterator>& __y)
1530  { return __x.base() == __y.base(); }
1531 
1532  template<typename _Iterator>
1533  inline _GLIBCXX17_CONSTEXPR bool
1534  operator!=(const move_iterator<_Iterator>& __x,
1535  const move_iterator<_Iterator>& __y)
1536  { return !(__x == __y); }
1537 
1538  template<typename _Iterator>
1539  inline _GLIBCXX17_CONSTEXPR bool
1540  operator<(const move_iterator<_Iterator>& __x,
1541  const move_iterator<_Iterator>& __y)
1542  { return __x.base() < __y.base(); }
1543 
1544  template<typename _Iterator>
1545  inline _GLIBCXX17_CONSTEXPR bool
1546  operator<=(const move_iterator<_Iterator>& __x,
1547  const move_iterator<_Iterator>& __y)
1548  { return !(__y < __x); }
1549 
1550  template<typename _Iterator>
1551  inline _GLIBCXX17_CONSTEXPR bool
1552  operator>(const move_iterator<_Iterator>& __x,
1553  const move_iterator<_Iterator>& __y)
1554  { return __y < __x; }
1555 
1556  template<typename _Iterator>
1557  inline _GLIBCXX17_CONSTEXPR bool
1558  operator>=(const move_iterator<_Iterator>& __x,
1559  const move_iterator<_Iterator>& __y)
1560  { return !(__x < __y); }
1561 #endif // ! C++20
1562 
1563  // DR 685.
1564  template<typename _IteratorL, typename _IteratorR>
1565  inline _GLIBCXX17_CONSTEXPR auto
1566  operator-(const move_iterator<_IteratorL>& __x,
1567  const move_iterator<_IteratorR>& __y)
1568  -> decltype(__x.base() - __y.base())
1569  { return __x.base() - __y.base(); }
1570 
1571  template<typename _Iterator>
1572  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1573  operator+(typename move_iterator<_Iterator>::difference_type __n,
1574  const move_iterator<_Iterator>& __x)
1575  { return __x + __n; }
1576 
1577  template<typename _Iterator>
1578  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1579  make_move_iterator(_Iterator __i)
1580  { return move_iterator<_Iterator>(std::move(__i)); }
1581 
1582  template<typename _Iterator, typename _ReturnType
1583  = typename conditional<__move_if_noexcept_cond
1584  <typename iterator_traits<_Iterator>::value_type>::value,
1585  _Iterator, move_iterator<_Iterator>>::type>
1586  inline _GLIBCXX17_CONSTEXPR _ReturnType
1587  __make_move_if_noexcept_iterator(_Iterator __i)
1588  { return _ReturnType(__i); }
1589 
1590  // Overload for pointers that matches std::move_if_noexcept more closely,
1591  // returning a constant iterator when we don't want to move.
1592  template<typename _Tp, typename _ReturnType
1593  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1594  const _Tp*, move_iterator<_Tp*>>::type>
1595  inline _GLIBCXX17_CONSTEXPR _ReturnType
1596  __make_move_if_noexcept_iterator(_Tp* __i)
1597  { return _ReturnType(__i); }
1598 
1599 #if __cplusplus > 201703L && __cpp_lib_concepts
1600  // [iterators.common] Common iterators
1601 
1602  namespace __detail
1603  {
1604  template<typename _It>
1605  concept __common_iter_has_arrow = indirectly_readable<const _It>
1606  && (requires(const _It& __it) { __it.operator->(); }
1607  || is_reference_v<iter_reference_t<_It>>
1608  || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1609 
1610  } // namespace __detail
1611 
1612  /// An iterator/sentinel adaptor for representing a non-common range.
1613  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1614  requires (!same_as<_It, _Sent>) && copyable<_It>
1615  class common_iterator
1616  {
1617  template<typename _Tp, typename _Up>
1618  static constexpr bool
1619  _S_noexcept1()
1620  {
1621  if constexpr (is_trivially_default_constructible_v<_Tp>)
1622  return is_nothrow_assignable_v<_Tp, _Up>;
1623  else
1624  return is_nothrow_constructible_v<_Tp, _Up>;
1625  }
1626 
1627  template<typename _It2, typename _Sent2>
1628  static constexpr bool
1629  _S_noexcept()
1630  { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1631 
1632  class _Proxy
1633  {
1634  iter_value_t<_It> _M_keep;
1635 
1636  _Proxy(iter_reference_t<_It>&& __x)
1637  : _M_keep(std::move(__x)) { }
1638 
1639  friend class common_iterator;
1640 
1641  public:
1642  const iter_value_t<_It>*
1643  operator->() const
1644  { return std::__addressof(_M_keep); }
1645  };
1646 
1647  public:
1648  constexpr
1649  common_iterator()
1650  noexcept(is_nothrow_default_constructible_v<_It>)
1651  : _M_it(), _M_index(0)
1652  { }
1653 
1654  constexpr
1655  common_iterator(_It __i)
1656  noexcept(is_nothrow_move_constructible_v<_It>)
1657  : _M_it(std::move(__i)), _M_index(0)
1658  { }
1659 
1660  constexpr
1661  common_iterator(_Sent __s)
1662  noexcept(is_nothrow_move_constructible_v<_Sent>)
1663  : _M_sent(std::move(__s)), _M_index(1)
1664  { }
1665 
1666  template<typename _It2, typename _Sent2>
1667  requires convertible_to<const _It2&, _It>
1668  && convertible_to<const _Sent2&, _Sent>
1669  constexpr
1670  common_iterator(const common_iterator<_It2, _Sent2>& __x)
1671  noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1672  : _M_valueless(), _M_index(__x._M_index)
1673  {
1674  if (_M_index == 0)
1675  {
1676  if constexpr (is_trivially_default_constructible_v<_It>)
1677  _M_it = std::move(__x._M_it);
1678  else
1679  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1680  }
1681  else if (_M_index == 1)
1682  {
1683  if constexpr (is_trivially_default_constructible_v<_Sent>)
1684  _M_sent = std::move(__x._M_sent);
1685  else
1686  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1687  }
1688  }
1689 
1690  constexpr
1691  common_iterator(const common_iterator& __x)
1692  noexcept(_S_noexcept<const _It&, const _Sent&>())
1693  : _M_valueless(), _M_index(__x._M_index)
1694  {
1695  if (_M_index == 0)
1696  {
1697  if constexpr (is_trivially_default_constructible_v<_It>)
1698  _M_it = std::move(__x._M_it);
1699  else
1700  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1701  }
1702  else if (_M_index == 1)
1703  {
1704  if constexpr (is_trivially_default_constructible_v<_Sent>)
1705  _M_sent = std::move(__x._M_sent);
1706  else
1707  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1708  }
1709  }
1710 
1711  common_iterator&
1712  operator=(const common_iterator& __x)
1713  noexcept(is_nothrow_copy_assignable_v<_It>
1714  && is_nothrow_copy_assignable_v<_Sent>
1715  && is_nothrow_copy_constructible_v<_It>
1716  && is_nothrow_copy_constructible_v<_Sent>)
1717  {
1718  return this->operator=<_It, _Sent>(__x);
1719  }
1720 
1721  template<typename _It2, typename _Sent2>
1722  requires convertible_to<const _It2&, _It>
1723  && convertible_to<const _Sent2&, _Sent>
1724  && assignable_from<_It&, const _It2&>
1725  && assignable_from<_Sent&, const _Sent2&>
1726  common_iterator&
1727  operator=(const common_iterator<_It2, _Sent2>& __x)
1728  noexcept(is_nothrow_constructible_v<_It, const _It2&>
1729  && is_nothrow_constructible_v<_Sent, const _Sent2&>
1730  && is_nothrow_assignable_v<_It, const _It2&>
1731  && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1732  {
1733  switch(_M_index << 2 | __x._M_index)
1734  {
1735  case 0b0000:
1736  _M_it = __x._M_it;
1737  break;
1738  case 0b0101:
1739  _M_sent = __x._M_sent;
1740  break;
1741  case 0b0001:
1742  _M_it.~_It();
1743  _M_index = -1;
1744  [[fallthrough]];
1745  case 0b1001:
1746  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1747  _M_index = 1;
1748  break;
1749  case 0b0100:
1750  _M_sent.~_Sent();
1751  _M_index = -1;
1752  [[fallthrough]];
1753  case 0b1000:
1754  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1755  _M_index = 0;
1756  break;
1757  default:
1758  __glibcxx_assert(__x._M_has_value());
1759  __builtin_unreachable();
1760  }
1761  return *this;
1762  }
1763 
1764  ~common_iterator()
1765  {
1766  switch (_M_index)
1767  {
1768  case 0:
1769  _M_it.~_It();
1770  break;
1771  case 1:
1772  _M_sent.~_Sent();
1773  break;
1774  }
1775  }
1776 
1777  decltype(auto)
1778  operator*()
1779  {
1780  __glibcxx_assert(_M_index == 0);
1781  return *_M_it;
1782  }
1783 
1784  decltype(auto)
1785  operator*() const requires __detail::__dereferenceable<const _It>
1786  {
1787  __glibcxx_assert(_M_index == 0);
1788  return *_M_it;
1789  }
1790 
1791  decltype(auto)
1792  operator->() const requires __detail::__common_iter_has_arrow<_It>
1793  {
1794  __glibcxx_assert(_M_index == 0);
1795  if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1796  return _M_it;
1797  else if constexpr (is_reference_v<iter_reference_t<_It>>)
1798  {
1799  auto&& __tmp = *_M_it;
1800  return std::__addressof(__tmp);
1801  }
1802  else
1803  return _Proxy{*_M_it};
1804  }
1805 
1806  common_iterator&
1807  operator++()
1808  {
1809  __glibcxx_assert(_M_index == 0);
1810  ++_M_it;
1811  return *this;
1812  }
1813 
1814  decltype(auto)
1815  operator++(int)
1816  {
1817  __glibcxx_assert(_M_index == 0);
1818  if constexpr (forward_iterator<_It>)
1819  {
1820  common_iterator __tmp = *this;
1821  ++*this;
1822  return __tmp;
1823  }
1824  else
1825  return _M_it++;
1826  }
1827 
1828  template<typename _It2, sentinel_for<_It> _Sent2>
1829  requires sentinel_for<_Sent, _It2>
1830  friend bool
1831  operator==(const common_iterator& __x,
1832  const common_iterator<_It2, _Sent2>& __y)
1833  {
1834  switch(__x._M_index << 2 | __y._M_index)
1835  {
1836  case 0b0000:
1837  case 0b0101:
1838  return true;
1839  case 0b0001:
1840  return __x._M_it == __y._M_sent;
1841  case 0b0100:
1842  return __x._M_sent == __y._M_it;
1843  default:
1844  __glibcxx_assert(__x._M_has_value());
1845  __glibcxx_assert(__y._M_has_value());
1846  __builtin_unreachable();
1847  }
1848  }
1849 
1850  template<typename _It2, sentinel_for<_It> _Sent2>
1851  requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1852  friend bool
1853  operator==(const common_iterator& __x,
1854  const common_iterator<_It2, _Sent2>& __y)
1855  {
1856  switch(__x._M_index << 2 | __y._M_index)
1857  {
1858  case 0b0101:
1859  return true;
1860  case 0b0000:
1861  return __x._M_it == __y._M_it;
1862  case 0b0001:
1863  return __x._M_it == __y._M_sent;
1864  case 0b0100:
1865  return __x._M_sent == __y._M_it;
1866  default:
1867  __glibcxx_assert(__x._M_has_value());
1868  __glibcxx_assert(__y._M_has_value());
1869  __builtin_unreachable();
1870  }
1871  }
1872 
1873  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1874  requires sized_sentinel_for<_Sent, _It2>
1875  friend iter_difference_t<_It2>
1876  operator-(const common_iterator& __x,
1877  const common_iterator<_It2, _Sent2>& __y)
1878  {
1879  switch(__x._M_index << 2 | __y._M_index)
1880  {
1881  case 0b0101:
1882  return 0;
1883  case 0b0000:
1884  return __x._M_it - __y._M_it;
1885  case 0b0001:
1886  return __x._M_it - __y._M_sent;
1887  case 0b0100:
1888  return __x._M_sent - __y._M_it;
1889  default:
1890  __glibcxx_assert(__x._M_has_value());
1891  __glibcxx_assert(__y._M_has_value());
1892  __builtin_unreachable();
1893  }
1894  }
1895 
1896  friend iter_rvalue_reference_t<_It>
1897  iter_move(const common_iterator& __i)
1898  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1899  requires input_iterator<_It>
1900  {
1901  __glibcxx_assert(__i._M_index == 0);
1902  return ranges::iter_move(__i._M_it);
1903  }
1904 
1905  template<indirectly_swappable<_It> _It2, typename _Sent2>
1906  friend void
1907  iter_swap(const common_iterator& __x,
1908  const common_iterator<_It2, _Sent2>& __y)
1909  noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1910  std::declval<const _It2&>())))
1911  {
1912  __glibcxx_assert(__x._M_index == 0);
1913  __glibcxx_assert(__y._M_index == 0);
1914  return ranges::iter_swap(__x._M_it, __y._M_it);
1915  }
1916 
1917  private:
1918  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1919  friend class common_iterator;
1920 
1921  bool _M_has_value() const noexcept { return _M_index < 2; }
1922 
1923  union
1924  {
1925  _It _M_it;
1926  _Sent _M_sent;
1927  unsigned char _M_valueless;
1928  };
1929  unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
1930  };
1931 
1932  template<typename _It, typename _Sent>
1933  struct incrementable_traits<common_iterator<_It, _Sent>>
1934  {
1935  using difference_type = iter_difference_t<_It>;
1936  };
1937 
1938  template<input_iterator _It, typename _Sent>
1939  struct iterator_traits<common_iterator<_It, _Sent>>
1940  {
1941  private:
1942  template<typename _Iter>
1943  struct __ptr
1944  {
1945  using type = void;
1946  };
1947 
1948  template<typename _Iter>
1949  requires __detail::__common_iter_has_arrow<_Iter>
1950  struct __ptr<_Iter>
1951  {
1952  using _CIter = common_iterator<_Iter, _Sent>;
1953  using type = decltype(std::declval<const _CIter&>().operator->());
1954  };
1955 
1956  public:
1957  using iterator_concept = conditional_t<forward_iterator<_It>,
1958  forward_iterator_tag, input_iterator_tag>;
1959  using iterator_category = __detail::__clamp_iter_cat<
1960  typename iterator_traits<_It>::iterator_category,
1961  forward_iterator_tag, input_iterator_tag>;
1962  using value_type = iter_value_t<_It>;
1963  using difference_type = iter_difference_t<_It>;
1964  using pointer = typename __ptr<_It>::type;
1965  using reference = iter_reference_t<_It>;
1966  };
1967 
1968  // [iterators.counted] Counted iterators
1969 
1970  /// An iterator adaptor that keeps track of the distance to the end.
1971  template<input_or_output_iterator _It>
1972  class counted_iterator
1973  {
1974  public:
1975  using iterator_type = _It;
1976 
1977  constexpr counted_iterator() = default;
1978 
1979  constexpr
1980  counted_iterator(_It __i, iter_difference_t<_It> __n)
1981  : _M_current(std::move(__i)), _M_length(__n)
1982  { __glibcxx_assert(__n >= 0); }
1983 
1984  template<typename _It2>
1985  requires convertible_to<const _It2&, _It>
1986  constexpr
1987  counted_iterator(const counted_iterator<_It2>& __x)
1988  : _M_current(__x._M_current), _M_length(__x._M_length)
1989  { }
1990 
1991  template<typename _It2>
1992  requires assignable_from<_It&, const _It2&>
1993  constexpr counted_iterator&
1994  operator=(const counted_iterator<_It2>& __x)
1995  {
1996  _M_current = __x._M_current;
1997  _M_length = __x._M_length;
1998  return *this;
1999  }
2000 
2001  constexpr _It
2002  base() const &
2003  noexcept(is_nothrow_copy_constructible_v<_It>)
2004  requires copy_constructible<_It>
2005  { return _M_current; }
2006 
2007  constexpr _It
2008  base() &&
2009  noexcept(is_nothrow_move_constructible_v<_It>)
2010  { return std::move(_M_current); }
2011 
2012  constexpr iter_difference_t<_It>
2013  count() const noexcept { return _M_length; }
2014 
2015  constexpr decltype(auto)
2016  operator*()
2017  noexcept(noexcept(*_M_current))
2018  { return *_M_current; }
2019 
2020  constexpr decltype(auto)
2021  operator*() const
2022  noexcept(noexcept(*_M_current))
2023  requires __detail::__dereferenceable<const _It>
2024  { return *_M_current; }
2025 
2026  constexpr counted_iterator&
2027  operator++()
2028  {
2029  __glibcxx_assert(_M_length > 0);
2030  ++_M_current;
2031  --_M_length;
2032  return *this;
2033  }
2034 
2035  decltype(auto)
2036  operator++(int)
2037  {
2038  __glibcxx_assert(_M_length > 0);
2039  --_M_length;
2040  __try
2041  {
2042  return _M_current++;
2043  } __catch(...) {
2044  ++_M_length;
2045  __throw_exception_again;
2046  }
2047 
2048  }
2049 
2050  constexpr counted_iterator
2051  operator++(int) requires forward_iterator<_It>
2052  {
2053  auto __tmp = *this;
2054  ++*this;
2055  return __tmp;
2056  }
2057 
2058  constexpr counted_iterator&
2059  operator--() requires bidirectional_iterator<_It>
2060  {
2061  --_M_current;
2062  ++_M_length;
2063  return *this;
2064  }
2065 
2066  constexpr counted_iterator
2067  operator--(int) requires bidirectional_iterator<_It>
2068  {
2069  auto __tmp = *this;
2070  --*this;
2071  return __tmp;
2072  }
2073 
2074  constexpr counted_iterator
2075  operator+(iter_difference_t<_It> __n) const
2076  requires random_access_iterator<_It>
2077  { return counted_iterator(_M_current + __n, _M_length - __n); }
2078 
2079  friend constexpr counted_iterator
2080  operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2081  requires random_access_iterator<_It>
2082  { return __x + __n; }
2083 
2084  constexpr counted_iterator&
2085  operator+=(iter_difference_t<_It> __n)
2086  requires random_access_iterator<_It>
2087  {
2088  __glibcxx_assert(__n <= _M_length);
2089  _M_current += __n;
2090  _M_length -= __n;
2091  return *this;
2092  }
2093 
2094  constexpr counted_iterator
2095  operator-(iter_difference_t<_It> __n) const
2096  requires random_access_iterator<_It>
2097  { return counted_iterator(_M_current - __n, _M_length + __n); }
2098 
2099  template<common_with<_It> _It2>
2100  friend constexpr iter_difference_t<_It2>
2101  operator-(const counted_iterator& __x,
2102  const counted_iterator<_It2>& __y)
2103  { return __y._M_length - __x._M_length; }
2104 
2105  friend constexpr iter_difference_t<_It>
2106  operator-(const counted_iterator& __x, default_sentinel_t)
2107  { return -__x._M_length; }
2108 
2109  friend constexpr iter_difference_t<_It>
2110  operator-(default_sentinel_t, const counted_iterator& __y)
2111  { return __y._M_length; }
2112 
2113  constexpr counted_iterator&
2114  operator-=(iter_difference_t<_It> __n)
2115  requires random_access_iterator<_It>
2116  {
2117  __glibcxx_assert(-__n <= _M_length);
2118  _M_current -= __n;
2119  _M_length += __n;
2120  return *this;
2121  }
2122 
2123  constexpr decltype(auto)
2124  operator[](iter_difference_t<_It> __n) const
2125  noexcept(noexcept(_M_current[__n]))
2126  requires random_access_iterator<_It>
2127  {
2128  __glibcxx_assert(__n < _M_length);
2129  return _M_current[__n];
2130  }
2131 
2132  template<common_with<_It> _It2>
2133  friend constexpr bool
2134  operator==(const counted_iterator& __x,
2135  const counted_iterator<_It2>& __y)
2136  { return __x._M_length == __y._M_length; }
2137 
2138  friend constexpr bool
2139  operator==(const counted_iterator& __x, default_sentinel_t)
2140  { return __x._M_length == 0; }
2141 
2142  template<common_with<_It> _It2>
2143  friend constexpr strong_ordering
2144  operator<=>(const counted_iterator& __x,
2145  const counted_iterator<_It2>& __y)
2146  { return __y._M_length <=> __x._M_length; }
2147 
2148  friend constexpr iter_rvalue_reference_t<_It>
2149  iter_move(const counted_iterator& __i)
2150  noexcept(noexcept(ranges::iter_move(__i._M_current)))
2151  requires input_iterator<_It>
2152  { return ranges::iter_move(__i._M_current); }
2153 
2154  template<indirectly_swappable<_It> _It2>
2155  friend constexpr void
2156  iter_swap(const counted_iterator& __x,
2157  const counted_iterator<_It2>& __y)
2158  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2159  { ranges::iter_swap(__x._M_current, __y._M_current); }
2160 
2161  private:
2162  template<input_or_output_iterator _It2> friend class counted_iterator;
2163 
2164  _It _M_current = _It();
2165  iter_difference_t<_It> _M_length = 0;
2166  };
2167 
2168  template<typename _It>
2169  struct incrementable_traits<counted_iterator<_It>>
2170  {
2171  using difference_type = iter_difference_t<_It>;
2172  };
2173 
2174  template<input_iterator _It>
2175  struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2176  {
2177  using pointer = void;
2178  };
2179 #endif // C++20
2180 
2181  // @} group iterators
2182 
2183  template<typename _Iterator>
2184  auto
2185  __niter_base(move_iterator<_Iterator> __it)
2186  -> decltype(make_move_iterator(__niter_base(__it.base())))
2187  { return make_move_iterator(__niter_base(__it.base())); }
2188 
2189  template<typename _Iterator>
2190  struct __is_move_iterator<move_iterator<_Iterator> >
2191  {
2192  enum { __value = 1 };
2193  typedef __true_type __type;
2194  };
2195 
2196  template<typename _Iterator>
2197  auto
2198  __miter_base(move_iterator<_Iterator> __it)
2199  -> decltype(__miter_base(__it.base()))
2200  { return __miter_base(__it.base()); }
2201 
2202 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2203 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2204  std::__make_move_if_noexcept_iterator(_Iter)
2205 #else
2206 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2207 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2208 #endif // C++11
2209 
2210 #if __cpp_deduction_guides >= 201606
2211  // These helper traits are used for deduction guides
2212  // of associative containers.
2213  template<typename _InputIterator>
2214  using __iter_key_t = remove_const_t<
2215  typename iterator_traits<_InputIterator>::value_type::first_type>;
2216 
2217  template<typename _InputIterator>
2218  using __iter_val_t =
2219  typename iterator_traits<_InputIterator>::value_type::second_type;
2220 
2221  template<typename _T1, typename _T2>
2222  struct pair;
2223 
2224  template<typename _InputIterator>
2225  using __iter_to_alloc_t =
2226  pair<add_const_t<__iter_key_t<_InputIterator>>,
2227  __iter_val_t<_InputIterator>>;
2228 #endif // __cpp_deduction_guides
2229 
2230 _GLIBCXX_END_NAMESPACE_VERSION
2231 } // namespace
2232 
2233 #ifdef _GLIBCXX_DEBUG
2234 # include <debug/stl_iterator.h>
2235 #endif
2236 
2237 #endif
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition: complex:361
constexpr front_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
_Container container_type
A nested typedef for the type of whatever container you used.
constexpr insert_iterator(_Container &__x, _Iter __i)
is_nothrow_copy_constructible
Definition: type_traits:1039
constexpr reverse_iterator & operator++()
_Container container_type
A nested typedef for the type of whatever container you used.
constexpr reverse_iterator operator-(difference_type __n) const
_Container container_type
A nested typedef for the type of whatever container you used.
constexpr reverse_iterator(iterator_type __x)
Turns assignment into insertion.
insert_iterator< _Container > inserter(_Container &__x, _Iterator __i)
constexpr back_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
constexpr reference operator*() const
constexpr front_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
constexpr insert_iterator & operator*()
Simply returns *this.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
Common iterator class.
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
constexpr front_insert_iterator & operator*()
Simply returns *this.
typename conditional< _Cond, _Iftrue, _Iffalse >::type conditional_t
Alias template for conditional.
Definition: type_traits:2558
constexpr front_insert_iterator< _Container > front_inserter(_Container &__x)
constexpr back_insert_iterator< _Container > back_inserter(_Container &__x)
constexpr reverse_iterator operator++(int)
constexpr reverse_iterator & operator-=(difference_type __n)
constexpr pointer operator->() const
constexpr reverse_iterator(const reverse_iterator< _Iter > &__x)
constexpr reference operator[](difference_type __n) const
constexpr reverse_iterator operator+(difference_type __n) const
Bidirectional iterators support a superset of forward iterator operations.
void difference_type
Distance between iterators is represented as this type.
constexpr back_insert_iterator & operator=(const typename _Container::value_type &__value)
constexpr reverse_iterator & operator+=(difference_type __n)
constexpr back_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
constexpr reverse_iterator(const reverse_iterator &__x)
constexpr back_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
constexpr insert_iterator & operator++(int)
Simply returns *this. (This iterator does not move.)
constexpr reverse_iterator & operator--()
constexpr iterator_type base() const
Random-access iterators support a superset of bidirectional iterator operations.
Turns assignment into insertion.
Define a member typedef type to one of two argument types.
Definition: type_traits:92
Marking input iterators.
constexpr insert_iterator & operator=(const typename _Container::value_type &__value)
constexpr reverse_iterator operator--(int)
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:331
Turns assignment into insertion.
typename remove_const< _Tp >::type remove_const_t
Alias template for remove_const.
Definition: type_traits:1566
constexpr insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
constexpr back_insert_iterator & operator*()
Simply returns *this.
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:391
constexpr front_insert_iterator & operator=(const typename _Container::value_type &__value)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
constexpr front_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)