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