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