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