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