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