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