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