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