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