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