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  public:
1394  using iterator_type = _Iterator;
1395 
1396 #if __cplusplus > 201703L && __cpp_lib_concepts
1397  using iterator_concept = input_iterator_tag;
1398  // iterator_category defined in __move_iter_cat
1399  using value_type = iter_value_t<_Iterator>;
1400  using difference_type = iter_difference_t<_Iterator>;
1401  using pointer = _Iterator;
1402  using reference = iter_rvalue_reference_t<_Iterator>;
1403 #else
1404  typedef typename __traits_type::iterator_category iterator_category;
1405  typedef typename __traits_type::value_type value_type;
1406  typedef typename __traits_type::difference_type difference_type;
1407  // NB: DR 680.
1408  typedef _Iterator pointer;
1409  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1410  // 2106. move_iterator wrapping iterators returning prvalues
1412  typename remove_reference<__base_ref>::type&&,
1413  __base_ref>::type reference;
1414 #endif
1415 
1416  _GLIBCXX17_CONSTEXPR
1417  move_iterator()
1418  : _M_current() { }
1419 
1420  explicit _GLIBCXX17_CONSTEXPR
1421  move_iterator(iterator_type __i)
1422  : _M_current(std::move(__i)) { }
1423 
1424  template<typename _Iter>
1425 #if __cpp_lib_concepts
1426  requires __convertible<_Iter>
1427 #endif
1428  _GLIBCXX17_CONSTEXPR
1430  : _M_current(__i._M_current) { }
1431 
1432  template<typename _Iter>
1433 #if __cpp_lib_concepts
1434  requires __convertible<_Iter>
1435  && assignable_from<_Iterator&, const _Iter&>
1436 #endif
1437  _GLIBCXX17_CONSTEXPR
1438  move_iterator& operator=(const move_iterator<_Iter>& __i)
1439  {
1440  _M_current = __i._M_current;
1441  return *this;
1442  }
1443 
1444 #if __cplusplus <= 201703L
1445  _GLIBCXX17_CONSTEXPR iterator_type
1446  base() const
1447  { return _M_current; }
1448 #else
1449  constexpr const iterator_type&
1450  base() const & noexcept
1451  { return _M_current; }
1452 
1453  constexpr iterator_type
1454  base() &&
1455  { return std::move(_M_current); }
1456 #endif
1457 
1458  _GLIBCXX17_CONSTEXPR reference
1459  operator*() const
1460 #if __cplusplus > 201703L && __cpp_lib_concepts
1461  { return ranges::iter_move(_M_current); }
1462 #else
1463  { return static_cast<reference>(*_M_current); }
1464 #endif
1465 
1466  _GLIBCXX17_CONSTEXPR pointer
1467  operator->() const
1468  { return _M_current; }
1469 
1470  _GLIBCXX17_CONSTEXPR move_iterator&
1471  operator++()
1472  {
1473  ++_M_current;
1474  return *this;
1475  }
1476 
1477  _GLIBCXX17_CONSTEXPR move_iterator
1478  operator++(int)
1479  {
1480  move_iterator __tmp = *this;
1481  ++_M_current;
1482  return __tmp;
1483  }
1484 
1485 #if __cpp_lib_concepts
1486  constexpr void
1487  operator++(int) requires (!forward_iterator<_Iterator>)
1488  { ++_M_current; }
1489 #endif
1490 
1491  _GLIBCXX17_CONSTEXPR move_iterator&
1492  operator--()
1493  {
1494  --_M_current;
1495  return *this;
1496  }
1497 
1498  _GLIBCXX17_CONSTEXPR move_iterator
1499  operator--(int)
1500  {
1501  move_iterator __tmp = *this;
1502  --_M_current;
1503  return __tmp;
1504  }
1505 
1506  _GLIBCXX17_CONSTEXPR move_iterator
1507  operator+(difference_type __n) const
1508  { return move_iterator(_M_current + __n); }
1509 
1510  _GLIBCXX17_CONSTEXPR move_iterator&
1511  operator+=(difference_type __n)
1512  {
1513  _M_current += __n;
1514  return *this;
1515  }
1516 
1517  _GLIBCXX17_CONSTEXPR move_iterator
1518  operator-(difference_type __n) const
1519  { return move_iterator(_M_current - __n); }
1520 
1521  _GLIBCXX17_CONSTEXPR move_iterator&
1522  operator-=(difference_type __n)
1523  {
1524  _M_current -= __n;
1525  return *this;
1526  }
1527 
1528  _GLIBCXX17_CONSTEXPR reference
1529  operator[](difference_type __n) const
1530 #if __cplusplus > 201703L && __cpp_lib_concepts
1531  { return ranges::iter_move(_M_current + __n); }
1532 #else
1533  { return std::move(_M_current[__n]); }
1534 #endif
1535 
1536 #if __cplusplus > 201703L && __cpp_lib_concepts
1537  template<sentinel_for<_Iterator> _Sent>
1538  friend constexpr bool
1539  operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1540  { return __x.base() == __y.base(); }
1541 
1542  template<sized_sentinel_for<_Iterator> _Sent>
1543  friend constexpr iter_difference_t<_Iterator>
1544  operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1545  { return __x.base() - __y.base(); }
1546 
1547  template<sized_sentinel_for<_Iterator> _Sent>
1548  friend constexpr iter_difference_t<_Iterator>
1549  operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1550  { return __x.base() - __y.base(); }
1551 
1552  friend constexpr iter_rvalue_reference_t<_Iterator>
1553  iter_move(const move_iterator& __i)
1554  noexcept(noexcept(ranges::iter_move(__i._M_current)))
1555  { return ranges::iter_move(__i._M_current); }
1556 
1557  template<indirectly_swappable<_Iterator> _Iter2>
1558  friend constexpr void
1559  iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1560  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1561  { return ranges::iter_swap(__x._M_current, __y._M_current); }
1562 #endif // C++20
1563  };
1564 
1565  template<typename _IteratorL, typename _IteratorR>
1566  inline _GLIBCXX17_CONSTEXPR bool
1567  operator==(const move_iterator<_IteratorL>& __x,
1568  const move_iterator<_IteratorR>& __y)
1569 #if __cplusplus > 201703L && __cpp_lib_concepts
1570  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1571 #endif
1572  { return __x.base() == __y.base(); }
1573 
1574 #if __cpp_lib_three_way_comparison
1575  template<typename _IteratorL,
1576  three_way_comparable_with<_IteratorL> _IteratorR>
1577  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1578  operator<=>(const move_iterator<_IteratorL>& __x,
1579  const move_iterator<_IteratorR>& __y)
1580  { return __x.base() <=> __y.base(); }
1581 #else
1582  template<typename _IteratorL, typename _IteratorR>
1583  inline _GLIBCXX17_CONSTEXPR bool
1584  operator!=(const move_iterator<_IteratorL>& __x,
1585  const move_iterator<_IteratorR>& __y)
1586  { return !(__x == __y); }
1587 #endif
1588 
1589  template<typename _IteratorL, typename _IteratorR>
1590  inline _GLIBCXX17_CONSTEXPR bool
1591  operator<(const move_iterator<_IteratorL>& __x,
1592  const move_iterator<_IteratorR>& __y)
1593 #if __cplusplus > 201703L && __cpp_lib_concepts
1594  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1595 #endif
1596  { return __x.base() < __y.base(); }
1597 
1598  template<typename _IteratorL, typename _IteratorR>
1599  inline _GLIBCXX17_CONSTEXPR bool
1600  operator<=(const move_iterator<_IteratorL>& __x,
1601  const move_iterator<_IteratorR>& __y)
1602 #if __cplusplus > 201703L && __cpp_lib_concepts
1603  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1604 #endif
1605  { return !(__y < __x); }
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 { { __y.base() < __x.base() } -> convertible_to<bool>; }
1613 #endif
1614  { return __y < __x; }
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 { { __x.base() < __y.base() } -> convertible_to<bool>; }
1622 #endif
1623  { return !(__x < __y); }
1624 
1625  // Note: See __normal_iterator operators note from Gaby to understand
1626  // why we have these extra overloads for some move_iterator operators.
1627 
1628  template<typename _Iterator>
1629  inline _GLIBCXX17_CONSTEXPR bool
1630  operator==(const move_iterator<_Iterator>& __x,
1631  const move_iterator<_Iterator>& __y)
1632  { return __x.base() == __y.base(); }
1633 
1634 #if __cpp_lib_three_way_comparison
1635  template<three_way_comparable _Iterator>
1636  constexpr compare_three_way_result_t<_Iterator>
1637  operator<=>(const move_iterator<_Iterator>& __x,
1638  const move_iterator<_Iterator>& __y)
1639  { return __x.base() <=> __y.base(); }
1640 #else
1641  template<typename _Iterator>
1642  inline _GLIBCXX17_CONSTEXPR bool
1643  operator!=(const move_iterator<_Iterator>& __x,
1644  const move_iterator<_Iterator>& __y)
1645  { return !(__x == __y); }
1646 
1647  template<typename _Iterator>
1648  inline _GLIBCXX17_CONSTEXPR bool
1649  operator<(const move_iterator<_Iterator>& __x,
1650  const move_iterator<_Iterator>& __y)
1651  { return __x.base() < __y.base(); }
1652 
1653  template<typename _Iterator>
1654  inline _GLIBCXX17_CONSTEXPR bool
1655  operator<=(const move_iterator<_Iterator>& __x,
1656  const move_iterator<_Iterator>& __y)
1657  { return !(__y < __x); }
1658 
1659  template<typename _Iterator>
1660  inline _GLIBCXX17_CONSTEXPR bool
1661  operator>(const move_iterator<_Iterator>& __x,
1662  const move_iterator<_Iterator>& __y)
1663  { return __y < __x; }
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 < __y); }
1670 #endif // ! C++20
1671 
1672  // DR 685.
1673  template<typename _IteratorL, typename _IteratorR>
1674  inline _GLIBCXX17_CONSTEXPR auto
1675  operator-(const move_iterator<_IteratorL>& __x,
1676  const move_iterator<_IteratorR>& __y)
1677  -> decltype(__x.base() - __y.base())
1678  { return __x.base() - __y.base(); }
1679 
1680  template<typename _Iterator>
1681  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1682  operator+(typename move_iterator<_Iterator>::difference_type __n,
1683  const move_iterator<_Iterator>& __x)
1684  { return __x + __n; }
1685 
1686  template<typename _Iterator>
1687  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1688  make_move_iterator(_Iterator __i)
1689  { return move_iterator<_Iterator>(std::move(__i)); }
1690 
1691  template<typename _Iterator, typename _ReturnType
1692  = typename conditional<__move_if_noexcept_cond
1693  <typename iterator_traits<_Iterator>::value_type>::value,
1694  _Iterator, move_iterator<_Iterator>>::type>
1695  inline _GLIBCXX17_CONSTEXPR _ReturnType
1696  __make_move_if_noexcept_iterator(_Iterator __i)
1697  { return _ReturnType(__i); }
1698 
1699  // Overload for pointers that matches std::move_if_noexcept more closely,
1700  // returning a constant iterator when we don't want to move.
1701  template<typename _Tp, typename _ReturnType
1702  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1703  const _Tp*, move_iterator<_Tp*>>::type>
1704  inline _GLIBCXX17_CONSTEXPR _ReturnType
1705  __make_move_if_noexcept_iterator(_Tp* __i)
1706  { return _ReturnType(__i); }
1707 
1708 #if __cplusplus > 201703L && __cpp_lib_concepts
1709  // [iterators.common] Common iterators
1710 
1711  namespace __detail
1712  {
1713  template<typename _It>
1714  concept __common_iter_has_arrow = indirectly_readable<const _It>
1715  && (requires(const _It& __it) { __it.operator->(); }
1716  || is_reference_v<iter_reference_t<_It>>
1717  || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1718 
1719  template<typename _It>
1720  concept __common_iter_use_postfix_proxy
1721  = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1722  && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1723  && move_constructible<iter_value_t<_It>>;
1724  } // namespace __detail
1725 
1726  /// An iterator/sentinel adaptor for representing a non-common range.
1727  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1728  requires (!same_as<_It, _Sent>) && copyable<_It>
1729  class common_iterator
1730  {
1731  template<typename _Tp, typename _Up>
1732  static constexpr bool
1733  _S_noexcept1()
1734  {
1735  if constexpr (is_trivially_default_constructible_v<_Tp>)
1736  return is_nothrow_assignable_v<_Tp&, _Up>;
1737  else
1738  return is_nothrow_constructible_v<_Tp, _Up>;
1739  }
1740 
1741  template<typename _It2, typename _Sent2>
1742  static constexpr bool
1743  _S_noexcept()
1744  { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1745 
1746  class __arrow_proxy
1747  {
1748  iter_value_t<_It> _M_keep;
1749 
1750  constexpr
1751  __arrow_proxy(iter_reference_t<_It>&& __x)
1752  : _M_keep(std::move(__x)) { }
1753 
1754  friend class common_iterator;
1755 
1756  public:
1757  constexpr const iter_value_t<_It>*
1758  operator->() const noexcept
1759  { return std::__addressof(_M_keep); }
1760  };
1761 
1762  class __postfix_proxy
1763  {
1764  iter_value_t<_It> _M_keep;
1765 
1766  constexpr
1767  __postfix_proxy(iter_reference_t<_It>&& __x)
1768  : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1769 
1770  friend class common_iterator;
1771 
1772  public:
1773  constexpr const iter_value_t<_It>&
1774  operator*() const noexcept
1775  { return _M_keep; }
1776  };
1777 
1778  public:
1779  constexpr
1780  common_iterator()
1781  noexcept(is_nothrow_default_constructible_v<_It>)
1782  requires default_initializable<_It>
1783  : _M_it(), _M_index(0)
1784  { }
1785 
1786  constexpr
1787  common_iterator(_It __i)
1788  noexcept(is_nothrow_move_constructible_v<_It>)
1789  : _M_it(std::move(__i)), _M_index(0)
1790  { }
1791 
1792  constexpr
1793  common_iterator(_Sent __s)
1794  noexcept(is_nothrow_move_constructible_v<_Sent>)
1795  : _M_sent(std::move(__s)), _M_index(1)
1796  { }
1797 
1798  template<typename _It2, typename _Sent2>
1799  requires convertible_to<const _It2&, _It>
1800  && convertible_to<const _Sent2&, _Sent>
1801  constexpr
1802  common_iterator(const common_iterator<_It2, _Sent2>& __x)
1803  noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1804  : _M_valueless(), _M_index(__x._M_index)
1805  {
1806  __glibcxx_assert(__x._M_has_value());
1807  if (_M_index == 0)
1808  {
1809  if constexpr (is_trivially_default_constructible_v<_It>)
1810  _M_it = std::move(__x._M_it);
1811  else
1812  std::construct_at(std::__addressof(_M_it), __x._M_it);
1813  }
1814  else if (_M_index == 1)
1815  {
1816  if constexpr (is_trivially_default_constructible_v<_Sent>)
1817  _M_sent = std::move(__x._M_sent);
1818  else
1819  std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1820  }
1821  }
1822 
1823  constexpr
1824  common_iterator(const common_iterator& __x)
1825  noexcept(_S_noexcept<const _It&, const _Sent&>())
1826  : _M_valueless(), _M_index(__x._M_index)
1827  {
1828  if (_M_index == 0)
1829  {
1830  if constexpr (is_trivially_default_constructible_v<_It>)
1831  _M_it = __x._M_it;
1832  else
1833  std::construct_at(std::__addressof(_M_it), __x._M_it);
1834  }
1835  else if (_M_index == 1)
1836  {
1837  if constexpr (is_trivially_default_constructible_v<_Sent>)
1838  _M_sent = __x._M_sent;
1839  else
1840  std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1841  }
1842  }
1843 
1844  constexpr
1845  common_iterator(common_iterator&& __x)
1846  noexcept(_S_noexcept<_It, _Sent>())
1847  : _M_valueless(), _M_index(__x._M_index)
1848  {
1849  if (_M_index == 0)
1850  {
1851  if constexpr (is_trivially_default_constructible_v<_It>)
1852  _M_it = std::move(__x._M_it);
1853  else
1854  std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
1855  }
1856  else if (_M_index == 1)
1857  {
1858  if constexpr (is_trivially_default_constructible_v<_Sent>)
1859  _M_sent = std::move(__x._M_sent);
1860  else
1861  std::construct_at(std::__addressof(_M_sent),
1862  std::move(__x._M_sent));
1863  }
1864  }
1865 
1866  constexpr common_iterator&
1867  operator=(const common_iterator&) = default;
1868 
1869  constexpr common_iterator&
1870  operator=(const common_iterator& __x)
1871  noexcept(is_nothrow_copy_assignable_v<_It>
1872  && is_nothrow_copy_assignable_v<_Sent>
1873  && is_nothrow_copy_constructible_v<_It>
1874  && is_nothrow_copy_constructible_v<_Sent>)
1875  requires (!is_trivially_copy_assignable_v<_It>
1876  || !is_trivially_copy_assignable_v<_Sent>)
1877  {
1878  _M_assign(__x);
1879  return *this;
1880  }
1881 
1882  constexpr common_iterator&
1883  operator=(common_iterator&&) = default;
1884 
1885  constexpr common_iterator&
1886  operator=(common_iterator&& __x)
1887  noexcept(is_nothrow_move_assignable_v<_It>
1888  && is_nothrow_move_assignable_v<_Sent>
1889  && is_nothrow_move_constructible_v<_It>
1890  && is_nothrow_move_constructible_v<_Sent>)
1891  requires (!is_trivially_move_assignable_v<_It>
1892  || !is_trivially_move_assignable_v<_Sent>)
1893  {
1894  _M_assign(std::move(__x));
1895  return *this;
1896  }
1897 
1898  template<typename _It2, typename _Sent2>
1899  requires convertible_to<const _It2&, _It>
1900  && convertible_to<const _Sent2&, _Sent>
1901  && assignable_from<_It&, const _It2&>
1902  && assignable_from<_Sent&, const _Sent2&>
1903  constexpr common_iterator&
1904  operator=(const common_iterator<_It2, _Sent2>& __x)
1905  noexcept(is_nothrow_constructible_v<_It, const _It2&>
1906  && is_nothrow_constructible_v<_Sent, const _Sent2&>
1907  && is_nothrow_assignable_v<_It&, const _It2&>
1908  && is_nothrow_assignable_v<_Sent&, const _Sent2&>)
1909  {
1910  __glibcxx_assert(__x._M_has_value());
1911  _M_assign(__x);
1912  return *this;
1913  }
1914 
1915  constexpr
1916  ~common_iterator()
1917  {
1918  if (_M_index == 0)
1919  _M_it.~_It();
1920  else if (_M_index == 1)
1921  _M_sent.~_Sent();
1922  }
1923 
1924  [[nodiscard]]
1925  constexpr decltype(auto)
1926  operator*()
1927  {
1928  __glibcxx_assert(_M_index == 0);
1929  return *_M_it;
1930  }
1931 
1932  [[nodiscard]]
1933  constexpr decltype(auto)
1934  operator*() const requires __detail::__dereferenceable<const _It>
1935  {
1936  __glibcxx_assert(_M_index == 0);
1937  return *_M_it;
1938  }
1939 
1940  [[nodiscard]]
1941  constexpr auto
1942  operator->() const requires __detail::__common_iter_has_arrow<_It>
1943  {
1944  __glibcxx_assert(_M_index == 0);
1945  if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1946  return _M_it;
1947  else if constexpr (is_reference_v<iter_reference_t<_It>>)
1948  {
1949  auto&& __tmp = *_M_it;
1950  return std::__addressof(__tmp);
1951  }
1952  else
1953  return __arrow_proxy{*_M_it};
1954  }
1955 
1956  constexpr common_iterator&
1957  operator++()
1958  {
1959  __glibcxx_assert(_M_index == 0);
1960  ++_M_it;
1961  return *this;
1962  }
1963 
1964  constexpr decltype(auto)
1965  operator++(int)
1966  {
1967  __glibcxx_assert(_M_index == 0);
1968  if constexpr (forward_iterator<_It>)
1969  {
1970  common_iterator __tmp = *this;
1971  ++*this;
1972  return __tmp;
1973  }
1974  else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
1975  return _M_it++;
1976  else
1977  {
1978  __postfix_proxy __p(**this);
1979  ++*this;
1980  return __p;
1981  }
1982  }
1983 
1984  template<typename _It2, sentinel_for<_It> _Sent2>
1985  requires sentinel_for<_Sent, _It2>
1986  friend constexpr bool
1987  operator== [[nodiscard]] (const common_iterator& __x,
1988  const common_iterator<_It2, _Sent2>& __y)
1989  {
1990  switch(__x._M_index << 2 | __y._M_index)
1991  {
1992  case 0b0000:
1993  case 0b0101:
1994  return true;
1995  case 0b0001:
1996  return __x._M_it == __y._M_sent;
1997  case 0b0100:
1998  return __x._M_sent == __y._M_it;
1999  default:
2000  __glibcxx_assert(__x._M_has_value());
2001  __glibcxx_assert(__y._M_has_value());
2002  __builtin_unreachable();
2003  }
2004  }
2005 
2006  template<typename _It2, sentinel_for<_It> _Sent2>
2007  requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2008  friend constexpr bool
2009  operator== [[nodiscard]] (const common_iterator& __x,
2010  const common_iterator<_It2, _Sent2>& __y)
2011  {
2012  switch(__x._M_index << 2 | __y._M_index)
2013  {
2014  case 0b0101:
2015  return true;
2016  case 0b0000:
2017  return __x._M_it == __y._M_it;
2018  case 0b0001:
2019  return __x._M_it == __y._M_sent;
2020  case 0b0100:
2021  return __x._M_sent == __y._M_it;
2022  default:
2023  __glibcxx_assert(__x._M_has_value());
2024  __glibcxx_assert(__y._M_has_value());
2025  __builtin_unreachable();
2026  }
2027  }
2028 
2029  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2030  requires sized_sentinel_for<_Sent, _It2>
2031  friend constexpr iter_difference_t<_It2>
2032  operator- [[nodiscard]] (const common_iterator& __x,
2033  const common_iterator<_It2, _Sent2>& __y)
2034  {
2035  switch(__x._M_index << 2 | __y._M_index)
2036  {
2037  case 0b0101:
2038  return 0;
2039  case 0b0000:
2040  return __x._M_it - __y._M_it;
2041  case 0b0001:
2042  return __x._M_it - __y._M_sent;
2043  case 0b0100:
2044  return __x._M_sent - __y._M_it;
2045  default:
2046  __glibcxx_assert(__x._M_has_value());
2047  __glibcxx_assert(__y._M_has_value());
2048  __builtin_unreachable();
2049  }
2050  }
2051 
2052  [[nodiscard]]
2053  friend constexpr iter_rvalue_reference_t<_It>
2054  iter_move(const common_iterator& __i)
2055  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2056  requires input_iterator<_It>
2057  {
2058  __glibcxx_assert(__i._M_index == 0);
2059  return ranges::iter_move(__i._M_it);
2060  }
2061 
2062  template<indirectly_swappable<_It> _It2, typename _Sent2>
2063  friend constexpr void
2064  iter_swap(const common_iterator& __x,
2065  const common_iterator<_It2, _Sent2>& __y)
2066  noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2067  std::declval<const _It2&>())))
2068  {
2069  __glibcxx_assert(__x._M_index == 0);
2070  __glibcxx_assert(__y._M_index == 0);
2071  return ranges::iter_swap(__x._M_it, __y._M_it);
2072  }
2073 
2074  private:
2075  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2076  requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2077  friend class common_iterator;
2078 
2079  constexpr bool
2080  _M_has_value() const noexcept { return _M_index != _S_valueless; }
2081 
2082  template<typename _CIt>
2083  constexpr void
2084  _M_assign(_CIt&& __x)
2085  {
2086  if (_M_index == __x._M_index)
2087  {
2088  if (_M_index == 0)
2089  _M_it = std::forward<_CIt>(__x)._M_it;
2090  else if (_M_index == 1)
2091  _M_sent = std::forward<_CIt>(__x)._M_sent;
2092  }
2093  else
2094  {
2095  if (_M_index == 0)
2096  _M_it.~_It();
2097  else if (_M_index == 1)
2098  _M_sent.~_Sent();
2099  _M_index = _S_valueless;
2100 
2101  if (__x._M_index == 0)
2102  std::construct_at(std::__addressof(_M_it),
2103  std::forward<_CIt>(__x)._M_it);
2104  else if (__x._M_index == 1)
2105  std::construct_at(std::__addressof(_M_sent),
2106  std::forward<_CIt>(__x)._M_sent);
2107  _M_index = __x._M_index;
2108  }
2109  }
2110 
2111  union
2112  {
2113  _It _M_it;
2114  _Sent _M_sent;
2115  unsigned char _M_valueless;
2116  };
2117  unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2118 
2119  static constexpr unsigned char _S_valueless{2};
2120  };
2121 
2122  template<typename _It, typename _Sent>
2123  struct incrementable_traits<common_iterator<_It, _Sent>>
2124  {
2125  using difference_type = iter_difference_t<_It>;
2126  };
2127 
2128  template<input_iterator _It, typename _Sent>
2129  struct iterator_traits<common_iterator<_It, _Sent>>
2130  {
2131  private:
2132  template<typename _Iter>
2133  struct __ptr
2134  {
2135  using type = void;
2136  };
2137 
2138  template<typename _Iter>
2139  requires __detail::__common_iter_has_arrow<_Iter>
2140  struct __ptr<_Iter>
2141  {
2142  using _CIter = common_iterator<_Iter, _Sent>;
2143  using type = decltype(std::declval<const _CIter&>().operator->());
2144  };
2145 
2146  static auto
2147  _S_iter_cat()
2148  {
2149  using _Traits = iterator_traits<_It>;
2150  if constexpr (requires { requires derived_from<typename _Traits::iterator_category,
2151  forward_iterator_tag>; })
2152  return forward_iterator_tag{};
2153  else
2154  return input_iterator_tag{};
2155  }
2156 
2157  public:
2158  using iterator_concept = conditional_t<forward_iterator<_It>,
2159  forward_iterator_tag, input_iterator_tag>;
2160  using iterator_category = decltype(_S_iter_cat());
2161  using value_type = iter_value_t<_It>;
2162  using difference_type = iter_difference_t<_It>;
2163  using pointer = typename __ptr<_It>::type;
2164  using reference = iter_reference_t<_It>;
2165  };
2166 
2167  // [iterators.counted] Counted iterators
2168 
2169  namespace __detail
2170  {
2171  template<typename _It>
2172  struct __counted_iter_value_type
2173  { };
2174 
2175  template<indirectly_readable _It>
2176  struct __counted_iter_value_type<_It>
2177  { using value_type = iter_value_t<_It>; };
2178 
2179  template<typename _It>
2180  struct __counted_iter_concept
2181  { };
2182 
2183  template<typename _It>
2184  requires requires { typename _It::iterator_concept; }
2185  struct __counted_iter_concept<_It>
2186  { using iterator_concept = typename _It::iterator_concept; };
2187 
2188  template<typename _It>
2189  struct __counted_iter_cat
2190  { };
2191 
2192  template<typename _It>
2193  requires requires { typename _It::iterator_category; }
2194  struct __counted_iter_cat<_It>
2195  { using iterator_category = typename _It::iterator_category; };
2196  }
2197 
2198  /// An iterator adaptor that keeps track of the distance to the end.
2199  template<input_or_output_iterator _It>
2200  class counted_iterator
2201  : public __detail::__counted_iter_value_type<_It>,
2202  public __detail::__counted_iter_concept<_It>,
2203  public __detail::__counted_iter_cat<_It>
2204  {
2205  public:
2206  using iterator_type = _It;
2207  // value_type defined in __counted_iter_value_type
2208  using difference_type = iter_difference_t<_It>;
2209  // iterator_concept defined in __counted_iter_concept
2210  // iterator_category defined in __counted_iter_cat
2211 
2212  constexpr counted_iterator() requires default_initializable<_It> = default;
2213 
2214  constexpr
2215  counted_iterator(_It __i, iter_difference_t<_It> __n)
2216  : _M_current(std::move(__i)), _M_length(__n)
2217  { __glibcxx_assert(__n >= 0); }
2218 
2219  template<typename _It2>
2220  requires convertible_to<const _It2&, _It>
2221  constexpr
2222  counted_iterator(const counted_iterator<_It2>& __x)
2223  : _M_current(__x._M_current), _M_length(__x._M_length)
2224  { }
2225 
2226  template<typename _It2>
2227  requires assignable_from<_It&, const _It2&>
2228  constexpr counted_iterator&
2229  operator=(const counted_iterator<_It2>& __x)
2230  {
2231  _M_current = __x._M_current;
2232  _M_length = __x._M_length;
2233  return *this;
2234  }
2235 
2236  constexpr const _It&
2237  base() const & noexcept
2238  { return _M_current; }
2239 
2240  constexpr _It
2241  base() &&
2242  noexcept(is_nothrow_move_constructible_v<_It>)
2243  { return std::move(_M_current); }
2244 
2245  constexpr iter_difference_t<_It>
2246  count() const noexcept { return _M_length; }
2247 
2248  constexpr decltype(auto)
2249  operator*()
2250  noexcept(noexcept(*_M_current))
2251  {
2252  __glibcxx_assert( _M_length > 0 );
2253  return *_M_current;
2254  }
2255 
2256  constexpr decltype(auto)
2257  operator*() const
2258  noexcept(noexcept(*_M_current))
2259  requires __detail::__dereferenceable<const _It>
2260  {
2261  __glibcxx_assert( _M_length > 0 );
2262  return *_M_current;
2263  }
2264 
2265  constexpr auto
2266  operator->() const noexcept
2267  requires contiguous_iterator<_It>
2268  { return std::to_address(_M_current); }
2269 
2270  constexpr counted_iterator&
2271  operator++()
2272  {
2273  __glibcxx_assert(_M_length > 0);
2274  ++_M_current;
2275  --_M_length;
2276  return *this;
2277  }
2278 
2279  constexpr decltype(auto)
2280  operator++(int)
2281  {
2282  __glibcxx_assert(_M_length > 0);
2283  --_M_length;
2284  __try
2285  {
2286  return _M_current++;
2287  } __catch(...) {
2288  ++_M_length;
2289  __throw_exception_again;
2290  }
2291  }
2292 
2293  constexpr counted_iterator
2294  operator++(int) requires forward_iterator<_It>
2295  {
2296  auto __tmp = *this;
2297  ++*this;
2298  return __tmp;
2299  }
2300 
2301  constexpr counted_iterator&
2302  operator--() requires bidirectional_iterator<_It>
2303  {
2304  --_M_current;
2305  ++_M_length;
2306  return *this;
2307  }
2308 
2309  constexpr counted_iterator
2310  operator--(int) requires bidirectional_iterator<_It>
2311  {
2312  auto __tmp = *this;
2313  --*this;
2314  return __tmp;
2315  }
2316 
2317  constexpr counted_iterator
2318  operator+(iter_difference_t<_It> __n) const
2319  requires random_access_iterator<_It>
2320  { return counted_iterator(_M_current + __n, _M_length - __n); }
2321 
2322  friend constexpr counted_iterator
2323  operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2324  requires random_access_iterator<_It>
2325  { return __x + __n; }
2326 
2327  constexpr counted_iterator&
2328  operator+=(iter_difference_t<_It> __n)
2329  requires random_access_iterator<_It>
2330  {
2331  __glibcxx_assert(__n <= _M_length);
2332  _M_current += __n;
2333  _M_length -= __n;
2334  return *this;
2335  }
2336 
2337  constexpr counted_iterator
2338  operator-(iter_difference_t<_It> __n) const
2339  requires random_access_iterator<_It>
2340  { return counted_iterator(_M_current - __n, _M_length + __n); }
2341 
2342  template<common_with<_It> _It2>
2343  friend constexpr iter_difference_t<_It2>
2344  operator-(const counted_iterator& __x,
2345  const counted_iterator<_It2>& __y)
2346  { return __y._M_length - __x._M_length; }
2347 
2348  friend constexpr iter_difference_t<_It>
2349  operator-(const counted_iterator& __x, default_sentinel_t)
2350  { return -__x._M_length; }
2351 
2352  friend constexpr iter_difference_t<_It>
2353  operator-(default_sentinel_t, const counted_iterator& __y)
2354  { return __y._M_length; }
2355 
2356  constexpr counted_iterator&
2357  operator-=(iter_difference_t<_It> __n)
2358  requires random_access_iterator<_It>
2359  {
2360  __glibcxx_assert(-__n <= _M_length);
2361  _M_current -= __n;
2362  _M_length += __n;
2363  return *this;
2364  }
2365 
2366  constexpr decltype(auto)
2367  operator[](iter_difference_t<_It> __n) const
2368  noexcept(noexcept(_M_current[__n]))
2369  requires random_access_iterator<_It>
2370  {
2371  __glibcxx_assert(__n < _M_length);
2372  return _M_current[__n];
2373  }
2374 
2375  template<common_with<_It> _It2>
2376  friend constexpr bool
2377  operator==(const counted_iterator& __x,
2378  const counted_iterator<_It2>& __y)
2379  { return __x._M_length == __y._M_length; }
2380 
2381  friend constexpr bool
2382  operator==(const counted_iterator& __x, default_sentinel_t)
2383  { return __x._M_length == 0; }
2384 
2385  template<common_with<_It> _It2>
2386  friend constexpr strong_ordering
2387  operator<=>(const counted_iterator& __x,
2388  const counted_iterator<_It2>& __y)
2389  { return __y._M_length <=> __x._M_length; }
2390 
2391  friend constexpr iter_rvalue_reference_t<_It>
2392  iter_move(const counted_iterator& __i)
2393  noexcept(noexcept(ranges::iter_move(__i._M_current)))
2394  requires input_iterator<_It>
2395  {
2396  __glibcxx_assert( __i._M_length > 0 );
2397  return ranges::iter_move(__i._M_current);
2398  }
2399 
2400  template<indirectly_swappable<_It> _It2>
2401  friend constexpr void
2402  iter_swap(const counted_iterator& __x,
2403  const counted_iterator<_It2>& __y)
2404  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2405  {
2406  __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
2407  ranges::iter_swap(__x._M_current, __y._M_current);
2408  }
2409 
2410  private:
2411  template<input_or_output_iterator _It2> friend class counted_iterator;
2412 
2413  _It _M_current = _It();
2414  iter_difference_t<_It> _M_length = 0;
2415  };
2416 
2417  template<input_iterator _It>
2418  requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2419  struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2420  {
2421  using pointer = conditional_t<contiguous_iterator<_It>,
2422  add_pointer_t<iter_reference_t<_It>>,
2423  void>;
2424  };
2425 #endif // C++20
2426 
2427  /// @} group iterators
2428 
2429  template<typename _Iterator>
2430  _GLIBCXX20_CONSTEXPR
2431  auto
2432  __niter_base(move_iterator<_Iterator> __it)
2433  -> decltype(make_move_iterator(__niter_base(__it.base())))
2434  { return make_move_iterator(__niter_base(__it.base())); }
2435 
2436  template<typename _Iterator>
2437  struct __is_move_iterator<move_iterator<_Iterator> >
2438  {
2439  enum { __value = 1 };
2440  typedef __true_type __type;
2441  };
2442 
2443  template<typename _Iterator>
2444  _GLIBCXX20_CONSTEXPR
2445  auto
2446  __miter_base(move_iterator<_Iterator> __it)
2447  -> decltype(__miter_base(__it.base()))
2448  { return __miter_base(__it.base()); }
2449 
2450 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2451 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2452  std::__make_move_if_noexcept_iterator(_Iter)
2453 #else
2454 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2455 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2456 #endif // C++11
2457 
2458 #if __cpp_deduction_guides >= 201606
2459  // These helper traits are used for deduction guides
2460  // of associative containers.
2461  template<typename _InputIterator>
2462  using __iter_key_t = remove_const_t<
2463  typename iterator_traits<_InputIterator>::value_type::first_type>;
2464 
2465  template<typename _InputIterator>
2466  using __iter_val_t =
2467  typename iterator_traits<_InputIterator>::value_type::second_type;
2468 
2469  template<typename _T1, typename _T2>
2470  struct pair;
2471 
2472  template<typename _InputIterator>
2473  using __iter_to_alloc_t =
2474  pair<add_const_t<__iter_key_t<_InputIterator>>,
2475  __iter_val_t<_InputIterator>>;
2476 #endif // __cpp_deduction_guides
2477 
2478 _GLIBCXX_END_NAMESPACE_VERSION
2479 } // namespace
2480 
2481 #ifdef _GLIBCXX_DEBUG
2482 # include <debug/stl_iterator.h>
2483 #endif
2484 
2485 #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:2589
typename remove_const< _Tp >::type remove_const_t
Alias template for remove_const.
Definition: type_traits:1576
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:2227
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.
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