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>
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 __cplusplus > 201703L && __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>
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 
137 
138  public:
139  typedef _Iterator iterator_type;
140  typedef typename __traits_type::pointer pointer;
141 #if __cplusplus <= 201703L
142  typedef typename __traits_type::difference_type difference_type;
143  typedef typename __traits_type::reference reference;
144 #else
145  using iterator_concept
149  using iterator_category
150  = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
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
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
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&
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
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&
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
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 #endif // C++20
510  ///@}
511 
512 #if __cplusplus < 201103L
513  template<typename _Iterator>
514  inline typename reverse_iterator<_Iterator>::difference_type
515  operator-(const reverse_iterator<_Iterator>& __x,
516  const reverse_iterator<_Iterator>& __y)
517  { return __y.base() - __x.base(); }
518 
519  template<typename _IteratorL, typename _IteratorR>
520  inline typename reverse_iterator<_IteratorL>::difference_type
521  operator-(const reverse_iterator<_IteratorL>& __x,
522  const reverse_iterator<_IteratorR>& __y)
523  { return __y.base() - __x.base(); }
524 #else
525  // _GLIBCXX_RESOLVE_LIB_DEFECTS
526  // DR 685. reverse_iterator/move_iterator difference has invalid signatures
527  template<typename _IteratorL, typename _IteratorR>
528  inline _GLIBCXX17_CONSTEXPR auto
529  operator-(const reverse_iterator<_IteratorL>& __x,
530  const reverse_iterator<_IteratorR>& __y)
531  -> decltype(__y.base() - __x.base())
532  { return __y.base() - __x.base(); }
533 #endif
534 
535  template<typename _Iterator>
536  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
537  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
538  const reverse_iterator<_Iterator>& __x)
539  { return reverse_iterator<_Iterator>(__x.base() - __n); }
540 
541 #if __cplusplus >= 201103L
542  // Same as C++14 make_reverse_iterator but used in C++11 mode too.
543  template<typename _Iterator>
544  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
545  __make_reverse_iterator(_Iterator __i)
546  { return reverse_iterator<_Iterator>(__i); }
547 
548 # if __cplusplus >= 201402L
549 # define __cpp_lib_make_reverse_iterator 201402
550 
551  // _GLIBCXX_RESOLVE_LIB_DEFECTS
552  // DR 2285. make_reverse_iterator
553  /// Generator function for reverse_iterator.
554  template<typename _Iterator>
555  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
556  make_reverse_iterator(_Iterator __i)
557  { return reverse_iterator<_Iterator>(__i); }
558 
559 # if __cplusplus > 201703L && defined __cpp_lib_concepts
560  template<typename _Iterator1, typename _Iterator2>
561  requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
562  inline constexpr bool
563  disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
564  reverse_iterator<_Iterator2>> = true;
565 # endif // C++20
566 # endif // C++14
567 
568  template<typename _Iterator>
569  _GLIBCXX20_CONSTEXPR
570  auto
571  __niter_base(reverse_iterator<_Iterator> __it)
572  -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
573  { return __make_reverse_iterator(__niter_base(__it.base())); }
574 
575  template<typename _Iterator>
576  struct __is_move_iterator<reverse_iterator<_Iterator> >
577  : __is_move_iterator<_Iterator>
578  { };
579 
580  template<typename _Iterator>
581  _GLIBCXX20_CONSTEXPR
582  auto
583  __miter_base(reverse_iterator<_Iterator> __it)
584  -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
585  { return __make_reverse_iterator(__miter_base(__it.base())); }
586 #endif // C++11
587 
588  // 24.4.2.2.1 back_insert_iterator
589  /**
590  * @brief Turns assignment into insertion.
591  *
592  * These are output iterators, constructed from a container-of-T.
593  * Assigning a T to the iterator appends it to the container using
594  * push_back.
595  *
596  * Tip: Using the back_inserter function to create these iterators can
597  * save typing.
598  */
599  template<typename _Container>
601  : public iterator<output_iterator_tag, void, void, void, void>
602  {
603  protected:
604  _Container* container;
605 
606  public:
607  /// A nested typedef for the type of whatever container you used.
608  typedef _Container container_type;
609 #if __cplusplus > 201703L
610  using difference_type = ptrdiff_t;
611 
612  constexpr back_insert_iterator() noexcept : container(nullptr) { }
613 #endif
614 
615  /// The only way to create this %iterator is with a container.
616  explicit _GLIBCXX20_CONSTEXPR
617  back_insert_iterator(_Container& __x)
618  : container(std::__addressof(__x)) { }
619 
620  /**
621  * @param __value An instance of whatever type
622  * container_type::const_reference is; presumably a
623  * reference-to-const T for container<T>.
624  * @return This %iterator, for chained operations.
625  *
626  * This kind of %iterator doesn't really have a @a position in the
627  * container (you can think of the position as being permanently at
628  * the end, if you like). Assigning a value to the %iterator will
629  * always append the value to the end of the container.
630  */
631 #if __cplusplus < 201103L
633  operator=(typename _Container::const_reference __value)
634  {
635  container->push_back(__value);
636  return *this;
637  }
638 #else
639  _GLIBCXX20_CONSTEXPR
641  operator=(const typename _Container::value_type& __value)
642  {
643  container->push_back(__value);
644  return *this;
645  }
646 
647  _GLIBCXX20_CONSTEXPR
649  operator=(typename _Container::value_type&& __value)
650  {
651  container->push_back(std::move(__value));
652  return *this;
653  }
654 #endif
655 
656  /// Simply returns *this.
657  _GLIBCXX20_CONSTEXPR
660  { return *this; }
661 
662  /// Simply returns *this. (This %iterator does not @a move.)
663  _GLIBCXX20_CONSTEXPR
666  { return *this; }
667 
668  /// Simply returns *this. (This %iterator does not @a move.)
669  _GLIBCXX20_CONSTEXPR
672  { return *this; }
673  };
674 
675  /**
676  * @param __x A container of arbitrary type.
677  * @return An instance of back_insert_iterator working on @p __x.
678  *
679  * This wrapper function helps in creating back_insert_iterator instances.
680  * Typing the name of the %iterator requires knowing the precise full
681  * type of the container, which can be tedious and impedes generic
682  * programming. Using this function lets you take advantage of automatic
683  * template parameter deduction, making the compiler match the correct
684  * types for you.
685  */
686  template<typename _Container>
687  _GLIBCXX20_CONSTEXPR
688  inline back_insert_iterator<_Container>
689  back_inserter(_Container& __x)
690  { return back_insert_iterator<_Container>(__x); }
691 
692  /**
693  * @brief Turns assignment into insertion.
694  *
695  * These are output iterators, constructed from a container-of-T.
696  * Assigning a T to the iterator prepends it to the container using
697  * push_front.
698  *
699  * Tip: Using the front_inserter function to create these iterators can
700  * save typing.
701  */
702  template<typename _Container>
704  : public iterator<output_iterator_tag, void, void, void, void>
705  {
706  protected:
707  _Container* container;
708 
709  public:
710  /// A nested typedef for the type of whatever container you used.
711  typedef _Container container_type;
712 #if __cplusplus > 201703L
713  using difference_type = ptrdiff_t;
714 
715  constexpr front_insert_iterator() noexcept : container(nullptr) { }
716 #endif
717 
718  /// The only way to create this %iterator is with a container.
719  explicit _GLIBCXX20_CONSTEXPR
720  front_insert_iterator(_Container& __x)
721  : container(std::__addressof(__x)) { }
722 
723  /**
724  * @param __value An instance of whatever type
725  * container_type::const_reference is; presumably a
726  * reference-to-const T for container<T>.
727  * @return This %iterator, for chained operations.
728  *
729  * This kind of %iterator doesn't really have a @a position in the
730  * container (you can think of the position as being permanently at
731  * the front, if you like). Assigning a value to the %iterator will
732  * always prepend the value to the front of the container.
733  */
734 #if __cplusplus < 201103L
736  operator=(typename _Container::const_reference __value)
737  {
738  container->push_front(__value);
739  return *this;
740  }
741 #else
742  _GLIBCXX20_CONSTEXPR
744  operator=(const typename _Container::value_type& __value)
745  {
746  container->push_front(__value);
747  return *this;
748  }
749 
750  _GLIBCXX20_CONSTEXPR
752  operator=(typename _Container::value_type&& __value)
753  {
754  container->push_front(std::move(__value));
755  return *this;
756  }
757 #endif
758 
759  /// Simply returns *this.
760  _GLIBCXX20_CONSTEXPR
763  { return *this; }
764 
765  /// Simply returns *this. (This %iterator does not @a move.)
766  _GLIBCXX20_CONSTEXPR
769  { return *this; }
770 
771  /// Simply returns *this. (This %iterator does not @a move.)
772  _GLIBCXX20_CONSTEXPR
775  { return *this; }
776  };
777 
778  /**
779  * @param __x A container of arbitrary type.
780  * @return An instance of front_insert_iterator working on @p x.
781  *
782  * This wrapper function helps in creating front_insert_iterator instances.
783  * Typing the name of the %iterator requires knowing the precise full
784  * type of the container, which can be tedious and impedes generic
785  * programming. Using this function lets you take advantage of automatic
786  * template parameter deduction, making the compiler match the correct
787  * types for you.
788  */
789  template<typename _Container>
790  _GLIBCXX20_CONSTEXPR
791  inline front_insert_iterator<_Container>
792  front_inserter(_Container& __x)
793  { return front_insert_iterator<_Container>(__x); }
794 
795  /**
796  * @brief Turns assignment into insertion.
797  *
798  * These are output iterators, constructed from a container-of-T.
799  * Assigning a T to the iterator inserts it in the container at the
800  * %iterator's position, rather than overwriting the value at that
801  * position.
802  *
803  * (Sequences will actually insert a @e copy of the value before the
804  * %iterator's position.)
805  *
806  * Tip: Using the inserter function to create these iterators can
807  * save typing.
808  */
809  template<typename _Container>
811  : public iterator<output_iterator_tag, void, void, void, void>
812  {
813 #if __cplusplus > 201703L && defined __cpp_lib_concepts
814  using _Iter = std::__detail::__range_iter_t<_Container>;
815 
816  protected:
817  _Container* container = nullptr;
818  _Iter iter = _Iter();
819 #else
820  typedef typename _Container::iterator _Iter;
821 
822  protected:
823  _Container* container;
824  _Iter iter;
825 #endif
826 
827  public:
828  /// A nested typedef for the type of whatever container you used.
829  typedef _Container container_type;
830 
831 #if __cplusplus > 201703L && defined __cpp_lib_concepts
832  using difference_type = ptrdiff_t;
833 
834  insert_iterator() = default;
835 #endif
836 
837  /**
838  * The only way to create this %iterator is with a container and an
839  * initial position (a normal %iterator into the container).
840  */
841  _GLIBCXX20_CONSTEXPR
842  insert_iterator(_Container& __x, _Iter __i)
843  : container(std::__addressof(__x)), iter(__i) {}
844 
845  /**
846  * @param __value An instance of whatever type
847  * container_type::const_reference is; presumably a
848  * reference-to-const T for container<T>.
849  * @return This %iterator, for chained operations.
850  *
851  * This kind of %iterator maintains its own position in the
852  * container. Assigning a value to the %iterator will insert the
853  * value into the container at the place before the %iterator.
854  *
855  * The position is maintained such that subsequent assignments will
856  * insert values immediately after one another. For example,
857  * @code
858  * // vector v contains A and Z
859  *
860  * insert_iterator i (v, ++v.begin());
861  * i = 1;
862  * i = 2;
863  * i = 3;
864  *
865  * // vector v contains A, 1, 2, 3, and Z
866  * @endcode
867  */
868 #if __cplusplus < 201103L
870  operator=(typename _Container::const_reference __value)
871  {
872  iter = container->insert(iter, __value);
873  ++iter;
874  return *this;
875  }
876 #else
877  _GLIBCXX20_CONSTEXPR
879  operator=(const typename _Container::value_type& __value)
880  {
881  iter = container->insert(iter, __value);
882  ++iter;
883  return *this;
884  }
885 
886  _GLIBCXX20_CONSTEXPR
888  operator=(typename _Container::value_type&& __value)
889  {
890  iter = container->insert(iter, std::move(__value));
891  ++iter;
892  return *this;
893  }
894 #endif
895 
896  /// Simply returns *this.
897  _GLIBCXX20_CONSTEXPR
900  { return *this; }
901 
902  /// Simply returns *this. (This %iterator does not @a move.)
903  _GLIBCXX20_CONSTEXPR
906  { return *this; }
907 
908  /// Simply returns *this. (This %iterator does not @a move.)
909  _GLIBCXX20_CONSTEXPR
912  { return *this; }
913  };
914 
915  /**
916  * @param __x A container of arbitrary type.
917  * @param __i An iterator into the container.
918  * @return An instance of insert_iterator working on @p __x.
919  *
920  * This wrapper function helps in creating insert_iterator instances.
921  * Typing the name of the %iterator requires knowing the precise full
922  * type of the container, which can be tedious and impedes generic
923  * programming. Using this function lets you take advantage of automatic
924  * template parameter deduction, making the compiler match the correct
925  * types for you.
926  */
927 #if __cplusplus > 201703L && defined __cpp_lib_concepts
928  template<typename _Container>
929  constexpr insert_iterator<_Container>
930  inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
931  { return insert_iterator<_Container>(__x, __i); }
932 #else
933  template<typename _Container>
934  inline insert_iterator<_Container>
935  inserter(_Container& __x, typename _Container::iterator __i)
936  { return insert_iterator<_Container>(__x, __i); }
937 #endif
938 
939  /// @} group iterators
940 
941 _GLIBCXX_END_NAMESPACE_VERSION
942 } // namespace
943 
944 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
945 {
946 _GLIBCXX_BEGIN_NAMESPACE_VERSION
947 
948  // This iterator adapter is @a normal in the sense that it does not
949  // change the semantics of any of the operators of its iterator
950  // parameter. Its primary purpose is to convert an iterator that is
951  // not a class, e.g. a pointer, into an iterator that is a class.
952  // The _Container parameter exists solely so that different containers
953  // using this template can instantiate different types, even if the
954  // _Iterator parameter is the same.
955  template<typename _Iterator, typename _Container>
956  class __normal_iterator
957  {
958  protected:
959  _Iterator _M_current;
960 
961  typedef std::iterator_traits<_Iterator> __traits_type;
962 
963  public:
964  typedef _Iterator iterator_type;
965  typedef typename __traits_type::iterator_category iterator_category;
966  typedef typename __traits_type::value_type value_type;
967  typedef typename __traits_type::difference_type difference_type;
968  typedef typename __traits_type::reference reference;
969  typedef typename __traits_type::pointer pointer;
970 
971 #if __cplusplus > 201703L && __cpp_lib_concepts
972  using iterator_concept = std::__detail::__iter_concept<_Iterator>;
973 #endif
974 
975  _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
976  : _M_current(_Iterator()) { }
977 
978  explicit _GLIBCXX20_CONSTEXPR
979  __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
980  : _M_current(__i) { }
981 
982  // Allow iterator to const_iterator conversion
983  template<typename _Iter>
984  _GLIBCXX20_CONSTEXPR
985  __normal_iterator(const __normal_iterator<_Iter,
986  typename __enable_if<
987  (std::__are_same<_Iter, typename _Container::pointer>::__value),
988  _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
989  : _M_current(__i.base()) { }
990 
991  // Forward iterator requirements
992  _GLIBCXX20_CONSTEXPR
993  reference
994  operator*() const _GLIBCXX_NOEXCEPT
995  { return *_M_current; }
996 
997  _GLIBCXX20_CONSTEXPR
998  pointer
999  operator->() const _GLIBCXX_NOEXCEPT
1000  { return _M_current; }
1001 
1002  _GLIBCXX20_CONSTEXPR
1003  __normal_iterator&
1004  operator++() _GLIBCXX_NOEXCEPT
1005  {
1006  ++_M_current;
1007  return *this;
1008  }
1009 
1010  _GLIBCXX20_CONSTEXPR
1011  __normal_iterator
1012  operator++(int) _GLIBCXX_NOEXCEPT
1013  { return __normal_iterator(_M_current++); }
1014 
1015  // Bidirectional iterator requirements
1016  _GLIBCXX20_CONSTEXPR
1017  __normal_iterator&
1018  operator--() _GLIBCXX_NOEXCEPT
1019  {
1020  --_M_current;
1021  return *this;
1022  }
1023 
1024  _GLIBCXX20_CONSTEXPR
1025  __normal_iterator
1026  operator--(int) _GLIBCXX_NOEXCEPT
1027  { return __normal_iterator(_M_current--); }
1028 
1029  // Random access iterator requirements
1030  _GLIBCXX20_CONSTEXPR
1031  reference
1032  operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
1033  { return _M_current[__n]; }
1034 
1035  _GLIBCXX20_CONSTEXPR
1036  __normal_iterator&
1037  operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1038  { _M_current += __n; return *this; }
1039 
1040  _GLIBCXX20_CONSTEXPR
1041  __normal_iterator
1042  operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
1043  { return __normal_iterator(_M_current + __n); }
1044 
1045  _GLIBCXX20_CONSTEXPR
1046  __normal_iterator&
1047  operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1048  { _M_current -= __n; return *this; }
1049 
1050  _GLIBCXX20_CONSTEXPR
1051  __normal_iterator
1052  operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
1053  { return __normal_iterator(_M_current - __n); }
1054 
1055  _GLIBCXX20_CONSTEXPR
1056  const _Iterator&
1057  base() const _GLIBCXX_NOEXCEPT
1058  { return _M_current; }
1059  };
1060 
1061  // Note: In what follows, the left- and right-hand-side iterators are
1062  // allowed to vary in types (conceptually in cv-qualification) so that
1063  // comparison between cv-qualified and non-cv-qualified iterators be
1064  // valid. However, the greedy and unfriendly operators in std::rel_ops
1065  // will make overload resolution ambiguous (when in scope) if we don't
1066  // provide overloads whose operands are of the same type. Can someone
1067  // remind me what generic programming is about? -- Gaby
1068 
1069 #if __cpp_lib_three_way_comparison
1070  template<typename _IteratorL, typename _IteratorR, typename _Container>
1071  requires requires (_IteratorL __lhs, _IteratorR __rhs)
1072  { { __lhs == __rhs } -> std::convertible_to<bool>; }
1073  constexpr bool
1074  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1075  const __normal_iterator<_IteratorR, _Container>& __rhs)
1076  noexcept(noexcept(__lhs.base() == __rhs.base()))
1077  { return __lhs.base() == __rhs.base(); }
1078 
1079  template<typename _IteratorL, typename _IteratorR, typename _Container>
1080  constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
1081  operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1082  const __normal_iterator<_IteratorR, _Container>& __rhs)
1083  noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1084  { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1085 #else
1086  // Forward iterator requirements
1087  template<typename _IteratorL, typename _IteratorR, typename _Container>
1088  _GLIBCXX20_CONSTEXPR
1089  inline bool
1090  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1091  const __normal_iterator<_IteratorR, _Container>& __rhs)
1092  _GLIBCXX_NOEXCEPT
1093  { return __lhs.base() == __rhs.base(); }
1094 
1095  template<typename _Iterator, typename _Container>
1096  _GLIBCXX20_CONSTEXPR
1097  inline bool
1098  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1099  const __normal_iterator<_Iterator, _Container>& __rhs)
1100  _GLIBCXX_NOEXCEPT
1101  { return __lhs.base() == __rhs.base(); }
1102 
1103  template<typename _IteratorL, typename _IteratorR, typename _Container>
1104  _GLIBCXX20_CONSTEXPR
1105  inline bool
1106  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1107  const __normal_iterator<_IteratorR, _Container>& __rhs)
1108  _GLIBCXX_NOEXCEPT
1109  { return __lhs.base() != __rhs.base(); }
1110 
1111  template<typename _Iterator, typename _Container>
1112  _GLIBCXX20_CONSTEXPR
1113  inline bool
1114  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
1115  const __normal_iterator<_Iterator, _Container>& __rhs)
1116  _GLIBCXX_NOEXCEPT
1117  { return __lhs.base() != __rhs.base(); }
1118 
1119  // Random access iterator requirements
1120  template<typename _IteratorL, typename _IteratorR, typename _Container>
1121  inline bool
1122  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1123  const __normal_iterator<_IteratorR, _Container>& __rhs)
1124  _GLIBCXX_NOEXCEPT
1125  { return __lhs.base() < __rhs.base(); }
1126 
1127  template<typename _Iterator, typename _Container>
1128  _GLIBCXX20_CONSTEXPR
1129  inline bool
1130  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
1131  const __normal_iterator<_Iterator, _Container>& __rhs)
1132  _GLIBCXX_NOEXCEPT
1133  { return __lhs.base() < __rhs.base(); }
1134 
1135  template<typename _IteratorL, typename _IteratorR, typename _Container>
1136  inline bool
1137  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1138  const __normal_iterator<_IteratorR, _Container>& __rhs)
1139  _GLIBCXX_NOEXCEPT
1140  { return __lhs.base() > __rhs.base(); }
1141 
1142  template<typename _Iterator, typename _Container>
1143  _GLIBCXX20_CONSTEXPR
1144  inline bool
1145  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
1146  const __normal_iterator<_Iterator, _Container>& __rhs)
1147  _GLIBCXX_NOEXCEPT
1148  { return __lhs.base() > __rhs.base(); }
1149 
1150  template<typename _IteratorL, typename _IteratorR, typename _Container>
1151  inline bool
1152  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1153  const __normal_iterator<_IteratorR, _Container>& __rhs)
1154  _GLIBCXX_NOEXCEPT
1155  { return __lhs.base() <= __rhs.base(); }
1156 
1157  template<typename _Iterator, typename _Container>
1158  _GLIBCXX20_CONSTEXPR
1159  inline bool
1160  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
1161  const __normal_iterator<_Iterator, _Container>& __rhs)
1162  _GLIBCXX_NOEXCEPT
1163  { return __lhs.base() <= __rhs.base(); }
1164 
1165  template<typename _IteratorL, typename _IteratorR, typename _Container>
1166  inline bool
1167  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1168  const __normal_iterator<_IteratorR, _Container>& __rhs)
1169  _GLIBCXX_NOEXCEPT
1170  { return __lhs.base() >= __rhs.base(); }
1171 
1172  template<typename _Iterator, typename _Container>
1173  _GLIBCXX20_CONSTEXPR
1174  inline bool
1175  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1176  const __normal_iterator<_Iterator, _Container>& __rhs)
1177  _GLIBCXX_NOEXCEPT
1178  { return __lhs.base() >= __rhs.base(); }
1179 #endif // three-way comparison
1180 
1181  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1182  // According to the resolution of DR179 not only the various comparison
1183  // operators but also operator- must accept mixed iterator/const_iterator
1184  // parameters.
1185  template<typename _IteratorL, typename _IteratorR, typename _Container>
1186 #if __cplusplus >= 201103L
1187  // DR 685.
1188  _GLIBCXX20_CONSTEXPR
1189  inline auto
1190  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1191  const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1192  -> decltype(__lhs.base() - __rhs.base())
1193 #else
1194  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1195  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1196  const __normal_iterator<_IteratorR, _Container>& __rhs)
1197 #endif
1198  { return __lhs.base() - __rhs.base(); }
1199 
1200  template<typename _Iterator, typename _Container>
1201  _GLIBCXX20_CONSTEXPR
1202  inline typename __normal_iterator<_Iterator, _Container>::difference_type
1203  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1204  const __normal_iterator<_Iterator, _Container>& __rhs)
1205  _GLIBCXX_NOEXCEPT
1206  { return __lhs.base() - __rhs.base(); }
1207 
1208  template<typename _Iterator, typename _Container>
1209  _GLIBCXX20_CONSTEXPR
1210  inline __normal_iterator<_Iterator, _Container>
1211  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1212  __n, const __normal_iterator<_Iterator, _Container>& __i)
1213  _GLIBCXX_NOEXCEPT
1214  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1215 
1216 _GLIBCXX_END_NAMESPACE_VERSION
1217 } // namespace
1218 
1219 namespace std _GLIBCXX_VISIBILITY(default)
1220 {
1221 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1222 
1223  template<typename _Iterator, typename _Container>
1224  _GLIBCXX20_CONSTEXPR
1225  _Iterator
1226  __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1228  { return __it.base(); }
1229 
1230 #if __cplusplus >= 201103L
1231  /**
1232  * @addtogroup iterators
1233  * @{
1234  */
1235 
1236 #if __cplusplus > 201703L && __cpp_lib_concepts
1237  template<semiregular _Sent>
1238  class move_sentinel
1239  {
1240  public:
1241  constexpr
1242  move_sentinel()
1243  noexcept(is_nothrow_default_constructible_v<_Sent>)
1244  : _M_last() { }
1245 
1246  constexpr explicit
1247  move_sentinel(_Sent __s)
1248  noexcept(is_nothrow_move_constructible_v<_Sent>)
1249  : _M_last(std::move(__s)) { }
1250 
1251  template<typename _S2> requires convertible_to<const _S2&, _Sent>
1252  constexpr
1253  move_sentinel(const move_sentinel<_S2>& __s)
1254  noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1255  : _M_last(__s.base())
1256  { }
1257 
1258  template<typename _S2> requires assignable_from<_Sent&, const _S2&>
1259  constexpr move_sentinel&
1260  operator=(const move_sentinel<_S2>& __s)
1261  noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1262  {
1263  _M_last = __s.base();
1264  return *this;
1265  }
1266 
1267  constexpr _Sent
1268  base() const
1269  noexcept(is_nothrow_copy_constructible_v<_Sent>)
1270  { return _M_last; }
1271 
1272  private:
1273  _Sent _M_last;
1274  };
1275 #endif // C++20
1276 
1277  namespace __detail
1278  {
1279 #if __cplusplus > 201703L && __cpp_lib_concepts
1280  template<typename _Iterator>
1281  struct __move_iter_cat
1282  { };
1283 
1284  template<typename _Iterator>
1285  requires requires { typename iterator_traits<_Iterator>::iterator_category; }
1286  struct __move_iter_cat<_Iterator>
1287  {
1288  using iterator_category
1289  = __clamp_iter_cat<typename iterator_traits<_Iterator>::iterator_category,
1290  random_access_iterator_tag>;
1291  };
1292 #endif
1293  }
1294 
1295  // 24.4.3 Move iterators
1296  /**
1297  * Class template move_iterator is an iterator adapter with the same
1298  * behavior as the underlying iterator except that its dereference
1299  * operator implicitly converts the value returned by the underlying
1300  * iterator's dereference operator to an rvalue reference. Some
1301  * generic algorithms can be called with move iterators to replace
1302  * copying with moving.
1303  */
1304  template<typename _Iterator>
1306 #if __cplusplus > 201703L && __cpp_lib_concepts
1307  : public __detail::__move_iter_cat<_Iterator>
1308 #endif
1309  {
1310  _Iterator _M_current;
1311 
1313 #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1314  using __base_ref = typename __traits_type::reference;
1315 #endif
1316 
1317  public:
1318  using iterator_type = _Iterator;
1319 
1320 #if __cplusplus > 201703L && __cpp_lib_concepts
1321  using iterator_concept = input_iterator_tag;
1322  // iterator_category defined in __move_iter_cat
1323  using value_type = iter_value_t<_Iterator>;
1324  using difference_type = iter_difference_t<_Iterator>;
1325  using pointer = _Iterator;
1326  using reference = iter_rvalue_reference_t<_Iterator>;
1327 #else
1328  typedef typename __traits_type::iterator_category iterator_category;
1329  typedef typename __traits_type::value_type value_type;
1330  typedef typename __traits_type::difference_type difference_type;
1331  // NB: DR 680.
1332  typedef _Iterator pointer;
1333  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1334  // 2106. move_iterator wrapping iterators returning prvalues
1336  typename remove_reference<__base_ref>::type&&,
1337  __base_ref>::type reference;
1338 #endif
1339 
1340  _GLIBCXX17_CONSTEXPR
1341  move_iterator()
1342  : _M_current() { }
1343 
1344  explicit _GLIBCXX17_CONSTEXPR
1345  move_iterator(iterator_type __i)
1346  : _M_current(std::move(__i)) { }
1347 
1348  template<typename _Iter>
1349  _GLIBCXX17_CONSTEXPR
1351  : _M_current(__i.base()) { }
1352 
1353  template<typename _Iter>
1354  _GLIBCXX17_CONSTEXPR
1355  move_iterator& operator=(const move_iterator<_Iter>& __i)
1356  {
1357  _M_current = __i.base();
1358  return *this;
1359  }
1360 
1361 #if __cplusplus <= 201703L
1362  _GLIBCXX17_CONSTEXPR iterator_type
1363  base() const
1364  { return _M_current; }
1365 #else
1366  constexpr const iterator_type&
1367  base() const & noexcept
1368  { return _M_current; }
1369 
1370  constexpr iterator_type
1371  base() &&
1372  { return std::move(_M_current); }
1373 #endif
1374 
1375  _GLIBCXX17_CONSTEXPR reference
1376  operator*() const
1377 #if __cplusplus > 201703L && __cpp_lib_concepts
1378  { return ranges::iter_move(_M_current); }
1379 #else
1380  { return static_cast<reference>(*_M_current); }
1381 #endif
1382 
1383  _GLIBCXX17_CONSTEXPR pointer
1384  operator->() const
1385  { return _M_current; }
1386 
1387  _GLIBCXX17_CONSTEXPR move_iterator&
1388  operator++()
1389  {
1390  ++_M_current;
1391  return *this;
1392  }
1393 
1394  _GLIBCXX17_CONSTEXPR move_iterator
1395  operator++(int)
1396  {
1397  move_iterator __tmp = *this;
1398  ++_M_current;
1399  return __tmp;
1400  }
1401 
1402 #if __cpp_lib_concepts
1403  constexpr void
1404  operator++(int) requires (!forward_iterator<_Iterator>)
1405  { ++_M_current; }
1406 #endif
1407 
1408  _GLIBCXX17_CONSTEXPR move_iterator&
1409  operator--()
1410  {
1411  --_M_current;
1412  return *this;
1413  }
1414 
1415  _GLIBCXX17_CONSTEXPR move_iterator
1416  operator--(int)
1417  {
1418  move_iterator __tmp = *this;
1419  --_M_current;
1420  return __tmp;
1421  }
1422 
1423  _GLIBCXX17_CONSTEXPR move_iterator
1424  operator+(difference_type __n) const
1425  { return move_iterator(_M_current + __n); }
1426 
1427  _GLIBCXX17_CONSTEXPR move_iterator&
1428  operator+=(difference_type __n)
1429  {
1430  _M_current += __n;
1431  return *this;
1432  }
1433 
1434  _GLIBCXX17_CONSTEXPR move_iterator
1435  operator-(difference_type __n) const
1436  { return move_iterator(_M_current - __n); }
1437 
1438  _GLIBCXX17_CONSTEXPR move_iterator&
1439  operator-=(difference_type __n)
1440  {
1441  _M_current -= __n;
1442  return *this;
1443  }
1444 
1445  _GLIBCXX17_CONSTEXPR reference
1446  operator[](difference_type __n) const
1447 #if __cplusplus > 201703L && __cpp_lib_concepts
1448  { return ranges::iter_move(_M_current + __n); }
1449 #else
1450  { return std::move(_M_current[__n]); }
1451 #endif
1452 
1453 #if __cplusplus > 201703L && __cpp_lib_concepts
1454  template<sentinel_for<_Iterator> _Sent>
1455  friend constexpr bool
1456  operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1457  { return __x.base() == __y.base(); }
1458 
1459  template<sized_sentinel_for<_Iterator> _Sent>
1460  friend constexpr iter_difference_t<_Iterator>
1461  operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1462  { return __x.base() - __y.base(); }
1463 
1464  template<sized_sentinel_for<_Iterator> _Sent>
1465  friend constexpr iter_difference_t<_Iterator>
1466  operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1467  { return __x.base() - __y.base(); }
1468 
1469  friend constexpr iter_rvalue_reference_t<_Iterator>
1470  iter_move(const move_iterator& __i)
1471  noexcept(noexcept(ranges::iter_move(__i._M_current)))
1472  { return ranges::iter_move(__i._M_current); }
1473 
1474  template<indirectly_swappable<_Iterator> _Iter2>
1475  friend constexpr void
1476  iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1477  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1478  { return ranges::iter_swap(__x._M_current, __y._M_current); }
1479 #endif // C++20
1480  };
1481 
1482  template<typename _IteratorL, typename _IteratorR>
1483  inline _GLIBCXX17_CONSTEXPR bool
1484  operator==(const move_iterator<_IteratorL>& __x,
1485  const move_iterator<_IteratorR>& __y)
1486 #if __cplusplus > 201703L && __cpp_lib_concepts
1487  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1488 #endif
1489  { return __x.base() == __y.base(); }
1490 
1491 #if __cpp_lib_three_way_comparison
1492  template<typename _IteratorL,
1493  three_way_comparable_with<_IteratorL> _IteratorR>
1494  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1495  operator<=>(const move_iterator<_IteratorL>& __x,
1496  const move_iterator<_IteratorR>& __y)
1497  { return __x.base() <=> __y.base(); }
1498 #else
1499  template<typename _IteratorL, typename _IteratorR>
1500  inline _GLIBCXX17_CONSTEXPR bool
1501  operator!=(const move_iterator<_IteratorL>& __x,
1502  const move_iterator<_IteratorR>& __y)
1503  { return !(__x == __y); }
1504 #endif
1505 
1506  template<typename _IteratorL, typename _IteratorR>
1507  inline _GLIBCXX17_CONSTEXPR bool
1508  operator<(const move_iterator<_IteratorL>& __x,
1509  const move_iterator<_IteratorR>& __y)
1510 #if __cplusplus > 201703L && __cpp_lib_concepts
1511  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1512 #endif
1513  { return __x.base() < __y.base(); }
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 { { __y.base() < __x.base() } -> convertible_to<bool>; }
1521 #endif
1522  { return !(__y < __x); }
1523 
1524  template<typename _IteratorL, typename _IteratorR>
1525  inline _GLIBCXX17_CONSTEXPR bool
1526  operator>(const move_iterator<_IteratorL>& __x,
1527  const move_iterator<_IteratorR>& __y)
1528 #if __cplusplus > 201703L && __cpp_lib_concepts
1529  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1530 #endif
1531  { return __y < __x; }
1532 
1533  template<typename _IteratorL, typename _IteratorR>
1534  inline _GLIBCXX17_CONSTEXPR bool
1535  operator>=(const move_iterator<_IteratorL>& __x,
1536  const move_iterator<_IteratorR>& __y)
1537 #if __cplusplus > 201703L && __cpp_lib_concepts
1538  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1539 #endif
1540  { return !(__x < __y); }
1541 
1542 #if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1543  // Note: See __normal_iterator operators note from Gaby to understand
1544  // why we have these extra overloads for some move_iterator operators.
1545 
1546  // These extra overloads are not needed in C++20, because the ones above
1547  // are constrained with a requires-clause and so overload resolution will
1548  // prefer them to greedy unconstrained function templates.
1549 
1550  template<typename _Iterator>
1551  inline _GLIBCXX17_CONSTEXPR bool
1552  operator==(const move_iterator<_Iterator>& __x,
1553  const move_iterator<_Iterator>& __y)
1554  { return __x.base() == __y.base(); }
1555 
1556  template<typename _Iterator>
1557  inline _GLIBCXX17_CONSTEXPR bool
1558  operator!=(const move_iterator<_Iterator>& __x,
1559  const move_iterator<_Iterator>& __y)
1560  { return !(__x == __y); }
1561 
1562  template<typename _Iterator>
1563  inline _GLIBCXX17_CONSTEXPR bool
1564  operator<(const move_iterator<_Iterator>& __x,
1565  const move_iterator<_Iterator>& __y)
1566  { return __x.base() < __y.base(); }
1567 
1568  template<typename _Iterator>
1569  inline _GLIBCXX17_CONSTEXPR bool
1570  operator<=(const move_iterator<_Iterator>& __x,
1571  const move_iterator<_Iterator>& __y)
1572  { return !(__y < __x); }
1573 
1574  template<typename _Iterator>
1575  inline _GLIBCXX17_CONSTEXPR bool
1576  operator>(const move_iterator<_Iterator>& __x,
1577  const move_iterator<_Iterator>& __y)
1578  { return __y < __x; }
1579 
1580  template<typename _Iterator>
1581  inline _GLIBCXX17_CONSTEXPR bool
1582  operator>=(const move_iterator<_Iterator>& __x,
1583  const move_iterator<_Iterator>& __y)
1584  { return !(__x < __y); }
1585 #endif // ! C++20
1586 
1587  // DR 685.
1588  template<typename _IteratorL, typename _IteratorR>
1589  inline _GLIBCXX17_CONSTEXPR auto
1590  operator-(const move_iterator<_IteratorL>& __x,
1591  const move_iterator<_IteratorR>& __y)
1592  -> decltype(__x.base() - __y.base())
1593  { return __x.base() - __y.base(); }
1594 
1595  template<typename _Iterator>
1596  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1597  operator+(typename move_iterator<_Iterator>::difference_type __n,
1598  const move_iterator<_Iterator>& __x)
1599  { return __x + __n; }
1600 
1601  template<typename _Iterator>
1602  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1603  make_move_iterator(_Iterator __i)
1604  { return move_iterator<_Iterator>(std::move(__i)); }
1605 
1606  template<typename _Iterator, typename _ReturnType
1607  = typename conditional<__move_if_noexcept_cond
1608  <typename iterator_traits<_Iterator>::value_type>::value,
1609  _Iterator, move_iterator<_Iterator>>::type>
1610  inline _GLIBCXX17_CONSTEXPR _ReturnType
1611  __make_move_if_noexcept_iterator(_Iterator __i)
1612  { return _ReturnType(__i); }
1613 
1614  // Overload for pointers that matches std::move_if_noexcept more closely,
1615  // returning a constant iterator when we don't want to move.
1616  template<typename _Tp, typename _ReturnType
1617  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1618  const _Tp*, move_iterator<_Tp*>>::type>
1619  inline _GLIBCXX17_CONSTEXPR _ReturnType
1620  __make_move_if_noexcept_iterator(_Tp* __i)
1621  { return _ReturnType(__i); }
1622 
1623 #if __cplusplus > 201703L && __cpp_lib_concepts
1624  // [iterators.common] Common iterators
1625 
1626  namespace __detail
1627  {
1628  template<typename _It>
1629  concept __common_iter_has_arrow = indirectly_readable<const _It>
1630  && (requires(const _It& __it) { __it.operator->(); }
1631  || is_reference_v<iter_reference_t<_It>>
1632  || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1633 
1634  template<typename _It>
1635  concept __common_iter_use_postfix_proxy
1636  = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1637  && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1638  && move_constructible<iter_value_t<_It>>;
1639  } // namespace __detail
1640 
1641  /// An iterator/sentinel adaptor for representing a non-common range.
1642  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1643  requires (!same_as<_It, _Sent>) && copyable<_It>
1644  class common_iterator
1645  {
1646  template<typename _Tp, typename _Up>
1647  static constexpr bool
1648  _S_noexcept1()
1649  {
1650  if constexpr (is_trivially_default_constructible_v<_Tp>)
1651  return is_nothrow_assignable_v<_Tp, _Up>;
1652  else
1653  return is_nothrow_constructible_v<_Tp, _Up>;
1654  }
1655 
1656  template<typename _It2, typename _Sent2>
1657  static constexpr bool
1658  _S_noexcept()
1659  { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1660 
1661  class __arrow_proxy
1662  {
1663  iter_value_t<_It> _M_keep;
1664 
1665  __arrow_proxy(iter_reference_t<_It>&& __x)
1666  : _M_keep(std::move(__x)) { }
1667 
1668  friend class common_iterator;
1669 
1670  public:
1671  const iter_value_t<_It>*
1672  operator->() const
1673  { return std::__addressof(_M_keep); }
1674  };
1675 
1676  class __postfix_proxy
1677  {
1678  iter_value_t<_It> _M_keep;
1679 
1680  __postfix_proxy(iter_reference_t<_It>&& __x)
1681  : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1682 
1683  friend class common_iterator;
1684 
1685  public:
1686  const iter_value_t<_It>&
1687  operator*() const
1688  { return _M_keep; }
1689  };
1690 
1691  public:
1692  constexpr
1693  common_iterator()
1694  noexcept(is_nothrow_default_constructible_v<_It>)
1695  : _M_it(), _M_index(0)
1696  { }
1697 
1698  constexpr
1699  common_iterator(_It __i)
1700  noexcept(is_nothrow_move_constructible_v<_It>)
1701  : _M_it(std::move(__i)), _M_index(0)
1702  { }
1703 
1704  constexpr
1705  common_iterator(_Sent __s)
1706  noexcept(is_nothrow_move_constructible_v<_Sent>)
1707  : _M_sent(std::move(__s)), _M_index(1)
1708  { }
1709 
1710  template<typename _It2, typename _Sent2>
1711  requires convertible_to<const _It2&, _It>
1712  && convertible_to<const _Sent2&, _Sent>
1713  constexpr
1714  common_iterator(const common_iterator<_It2, _Sent2>& __x)
1715  noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1716  : _M_valueless(), _M_index(__x._M_index)
1717  {
1718  if (_M_index == 0)
1719  {
1720  if constexpr (is_trivially_default_constructible_v<_It>)
1721  _M_it = std::move(__x._M_it);
1722  else
1723  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1724  }
1725  else if (_M_index == 1)
1726  {
1727  if constexpr (is_trivially_default_constructible_v<_Sent>)
1728  _M_sent = std::move(__x._M_sent);
1729  else
1730  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1731  }
1732  }
1733 
1734  constexpr
1735  common_iterator(const common_iterator& __x)
1736  noexcept(_S_noexcept<const _It&, const _Sent&>())
1737  : _M_valueless(), _M_index(__x._M_index)
1738  {
1739  if (_M_index == 0)
1740  {
1741  if constexpr (is_trivially_default_constructible_v<_It>)
1742  _M_it = std::move(__x._M_it);
1743  else
1744  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1745  }
1746  else if (_M_index == 1)
1747  {
1748  if constexpr (is_trivially_default_constructible_v<_Sent>)
1749  _M_sent = std::move(__x._M_sent);
1750  else
1751  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1752  }
1753  }
1754 
1755  common_iterator&
1756  operator=(const common_iterator& __x)
1757  noexcept(is_nothrow_copy_assignable_v<_It>
1758  && is_nothrow_copy_assignable_v<_Sent>
1759  && is_nothrow_copy_constructible_v<_It>
1760  && is_nothrow_copy_constructible_v<_Sent>)
1761  {
1762  return this->operator=<_It, _Sent>(__x);
1763  }
1764 
1765  template<typename _It2, typename _Sent2>
1766  requires convertible_to<const _It2&, _It>
1767  && convertible_to<const _Sent2&, _Sent>
1768  && assignable_from<_It&, const _It2&>
1769  && assignable_from<_Sent&, const _Sent2&>
1770  common_iterator&
1771  operator=(const common_iterator<_It2, _Sent2>& __x)
1772  noexcept(is_nothrow_constructible_v<_It, const _It2&>
1773  && is_nothrow_constructible_v<_Sent, const _Sent2&>
1774  && is_nothrow_assignable_v<_It, const _It2&>
1775  && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1776  {
1777  switch(_M_index << 2 | __x._M_index)
1778  {
1779  case 0b0000:
1780  _M_it = __x._M_it;
1781  break;
1782  case 0b0101:
1783  _M_sent = __x._M_sent;
1784  break;
1785  case 0b0001:
1786  _M_it.~_It();
1787  _M_index = -1;
1788  [[fallthrough]];
1789  case 0b1001:
1790  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1791  _M_index = 1;
1792  break;
1793  case 0b0100:
1794  _M_sent.~_Sent();
1795  _M_index = -1;
1796  [[fallthrough]];
1797  case 0b1000:
1798  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1799  _M_index = 0;
1800  break;
1801  default:
1802  __glibcxx_assert(__x._M_has_value());
1803  __builtin_unreachable();
1804  }
1805  return *this;
1806  }
1807 
1808  ~common_iterator()
1809  {
1810  switch (_M_index)
1811  {
1812  case 0:
1813  _M_it.~_It();
1814  break;
1815  case 1:
1816  _M_sent.~_Sent();
1817  break;
1818  }
1819  }
1820 
1821  decltype(auto)
1822  operator*()
1823  {
1824  __glibcxx_assert(_M_index == 0);
1825  return *_M_it;
1826  }
1827 
1828  decltype(auto)
1829  operator*() const requires __detail::__dereferenceable<const _It>
1830  {
1831  __glibcxx_assert(_M_index == 0);
1832  return *_M_it;
1833  }
1834 
1835  decltype(auto)
1836  operator->() const requires __detail::__common_iter_has_arrow<_It>
1837  {
1838  __glibcxx_assert(_M_index == 0);
1839  if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1840  return _M_it;
1841  else if constexpr (is_reference_v<iter_reference_t<_It>>)
1842  {
1843  auto&& __tmp = *_M_it;
1844  return std::__addressof(__tmp);
1845  }
1846  else
1847  return __arrow_proxy{*_M_it};
1848  }
1849 
1850  common_iterator&
1851  operator++()
1852  {
1853  __glibcxx_assert(_M_index == 0);
1854  ++_M_it;
1855  return *this;
1856  }
1857 
1858  decltype(auto)
1859  operator++(int)
1860  {
1861  __glibcxx_assert(_M_index == 0);
1862  if constexpr (forward_iterator<_It>)
1863  {
1864  common_iterator __tmp = *this;
1865  ++*this;
1866  return __tmp;
1867  }
1868  else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
1869  return _M_it++;
1870  else
1871  {
1872  __postfix_proxy __p(**this);
1873  ++*this;
1874  return __p;
1875  }
1876  }
1877 
1878  template<typename _It2, sentinel_for<_It> _Sent2>
1879  requires sentinel_for<_Sent, _It2>
1880  friend bool
1881  operator==(const common_iterator& __x,
1882  const common_iterator<_It2, _Sent2>& __y)
1883  {
1884  switch(__x._M_index << 2 | __y._M_index)
1885  {
1886  case 0b0000:
1887  case 0b0101:
1888  return true;
1889  case 0b0001:
1890  return __x._M_it == __y._M_sent;
1891  case 0b0100:
1892  return __x._M_sent == __y._M_it;
1893  default:
1894  __glibcxx_assert(__x._M_has_value());
1895  __glibcxx_assert(__y._M_has_value());
1896  __builtin_unreachable();
1897  }
1898  }
1899 
1900  template<typename _It2, sentinel_for<_It> _Sent2>
1901  requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1902  friend bool
1903  operator==(const common_iterator& __x,
1904  const common_iterator<_It2, _Sent2>& __y)
1905  {
1906  switch(__x._M_index << 2 | __y._M_index)
1907  {
1908  case 0b0101:
1909  return true;
1910  case 0b0000:
1911  return __x._M_it == __y._M_it;
1912  case 0b0001:
1913  return __x._M_it == __y._M_sent;
1914  case 0b0100:
1915  return __x._M_sent == __y._M_it;
1916  default:
1917  __glibcxx_assert(__x._M_has_value());
1918  __glibcxx_assert(__y._M_has_value());
1919  __builtin_unreachable();
1920  }
1921  }
1922 
1923  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1924  requires sized_sentinel_for<_Sent, _It2>
1925  friend iter_difference_t<_It2>
1926  operator-(const common_iterator& __x,
1927  const common_iterator<_It2, _Sent2>& __y)
1928  {
1929  switch(__x._M_index << 2 | __y._M_index)
1930  {
1931  case 0b0101:
1932  return 0;
1933  case 0b0000:
1934  return __x._M_it - __y._M_it;
1935  case 0b0001:
1936  return __x._M_it - __y._M_sent;
1937  case 0b0100:
1938  return __x._M_sent - __y._M_it;
1939  default:
1940  __glibcxx_assert(__x._M_has_value());
1941  __glibcxx_assert(__y._M_has_value());
1942  __builtin_unreachable();
1943  }
1944  }
1945 
1946  friend iter_rvalue_reference_t<_It>
1947  iter_move(const common_iterator& __i)
1948  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1949  requires input_iterator<_It>
1950  {
1951  __glibcxx_assert(__i._M_index == 0);
1952  return ranges::iter_move(__i._M_it);
1953  }
1954 
1955  template<indirectly_swappable<_It> _It2, typename _Sent2>
1956  friend void
1957  iter_swap(const common_iterator& __x,
1958  const common_iterator<_It2, _Sent2>& __y)
1959  noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1960  std::declval<const _It2&>())))
1961  {
1962  __glibcxx_assert(__x._M_index == 0);
1963  __glibcxx_assert(__y._M_index == 0);
1964  return ranges::iter_swap(__x._M_it, __y._M_it);
1965  }
1966 
1967  private:
1968  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1969  friend class common_iterator;
1970 
1971  bool _M_has_value() const noexcept { return _M_index < 2; }
1972 
1973  union
1974  {
1975  _It _M_it;
1976  _Sent _M_sent;
1977  unsigned char _M_valueless;
1978  };
1979  unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
1980  };
1981 
1982  template<typename _It, typename _Sent>
1983  struct incrementable_traits<common_iterator<_It, _Sent>>
1984  {
1985  using difference_type = iter_difference_t<_It>;
1986  };
1987 
1988  template<input_iterator _It, typename _Sent>
1989  struct iterator_traits<common_iterator<_It, _Sent>>
1990  {
1991  private:
1992  template<typename _Iter>
1993  struct __ptr
1994  {
1995  using type = void;
1996  };
1997 
1998  template<typename _Iter>
1999  requires __detail::__common_iter_has_arrow<_Iter>
2000  struct __ptr<_Iter>
2001  {
2002  using _CIter = common_iterator<_Iter, _Sent>;
2003  using type = decltype(std::declval<const _CIter&>().operator->());
2004  };
2005 
2006  static auto
2007  _S_iter_cat()
2008  {
2009  using _Traits = iterator_traits<_It>;
2010  if constexpr (requires { requires derived_from<typename _Traits::iterator_category,
2011  forward_iterator_tag>; })
2012  return forward_iterator_tag{};
2013  else
2014  return input_iterator_tag{};
2015  }
2016 
2017  public:
2018  using iterator_concept = conditional_t<forward_iterator<_It>,
2019  forward_iterator_tag, input_iterator_tag>;
2020  using iterator_category = decltype(_S_iter_cat());
2021  using value_type = iter_value_t<_It>;
2022  using difference_type = iter_difference_t<_It>;
2023  using pointer = typename __ptr<_It>::type;
2024  using reference = iter_reference_t<_It>;
2025  };
2026 
2027  // [iterators.counted] Counted iterators
2028 
2029  namespace __detail
2030  {
2031  template<typename _It>
2032  struct __counted_iter_value_type
2033  { };
2034 
2035  template<indirectly_readable _It>
2036  struct __counted_iter_value_type<_It>
2037  { using value_type = iter_value_t<_It>; };
2038 
2039  template<typename _It>
2040  struct __counted_iter_concept
2041  { };
2042 
2043  template<typename _It>
2044  requires requires { typename _It::iterator_concept; }
2045  struct __counted_iter_concept<_It>
2046  { using iterator_concept = typename _It::iterator_concept; };
2047 
2048  template<typename _It>
2049  struct __counted_iter_cat
2050  { };
2051 
2052  template<typename _It>
2053  requires requires { typename _It::iterator_category; }
2054  struct __counted_iter_cat<_It>
2055  { using iterator_category = typename _It::iterator_category; };
2056  }
2057 
2058  /// An iterator adaptor that keeps track of the distance to the end.
2059  template<input_or_output_iterator _It>
2060  class counted_iterator
2061  : public __detail::__counted_iter_value_type<_It>,
2062  public __detail::__counted_iter_concept<_It>,
2063  public __detail::__counted_iter_cat<_It>
2064  {
2065  public:
2066  using iterator_type = _It;
2067  // value_type defined in __counted_iter_value_type
2068  using difference_type = iter_difference_t<_It>;
2069  // iterator_concept defined in __counted_iter_concept
2070  // iterator_category defined in __counted_iter_cat
2071 
2072  constexpr counted_iterator() = default;
2073 
2074  constexpr
2075  counted_iterator(_It __i, iter_difference_t<_It> __n)
2076  : _M_current(std::move(__i)), _M_length(__n)
2077  { __glibcxx_assert(__n >= 0); }
2078 
2079  template<typename _It2>
2080  requires convertible_to<const _It2&, _It>
2081  constexpr
2082  counted_iterator(const counted_iterator<_It2>& __x)
2083  : _M_current(__x._M_current), _M_length(__x._M_length)
2084  { }
2085 
2086  template<typename _It2>
2087  requires assignable_from<_It&, const _It2&>
2088  constexpr counted_iterator&
2089  operator=(const counted_iterator<_It2>& __x)
2090  {
2091  _M_current = __x._M_current;
2092  _M_length = __x._M_length;
2093  return *this;
2094  }
2095 
2096  constexpr const _It&
2097  base() const & noexcept
2098  { return _M_current; }
2099 
2100  constexpr _It
2101  base() &&
2102  noexcept(is_nothrow_move_constructible_v<_It>)
2103  { return std::move(_M_current); }
2104 
2105  constexpr iter_difference_t<_It>
2106  count() const noexcept { return _M_length; }
2107 
2108  constexpr decltype(auto)
2109  operator*()
2110  noexcept(noexcept(*_M_current))
2111  { return *_M_current; }
2112 
2113  constexpr decltype(auto)
2114  operator*() const
2115  noexcept(noexcept(*_M_current))
2116  requires __detail::__dereferenceable<const _It>
2117  { return *_M_current; }
2118 
2119  constexpr auto
2120  operator->() const noexcept
2121  requires contiguous_iterator<_It>
2122  { return std::to_address(_M_current); }
2123 
2124  constexpr counted_iterator&
2125  operator++()
2126  {
2127  __glibcxx_assert(_M_length > 0);
2128  ++_M_current;
2129  --_M_length;
2130  return *this;
2131  }
2132 
2133  decltype(auto)
2134  operator++(int)
2135  {
2136  __glibcxx_assert(_M_length > 0);
2137  --_M_length;
2138  __try
2139  {
2140  return _M_current++;
2141  } __catch(...) {
2142  ++_M_length;
2143  __throw_exception_again;
2144  }
2145 
2146  }
2147 
2148  constexpr counted_iterator
2149  operator++(int) requires forward_iterator<_It>
2150  {
2151  auto __tmp = *this;
2152  ++*this;
2153  return __tmp;
2154  }
2155 
2156  constexpr counted_iterator&
2157  operator--() requires bidirectional_iterator<_It>
2158  {
2159  --_M_current;
2160  ++_M_length;
2161  return *this;
2162  }
2163 
2164  constexpr counted_iterator
2165  operator--(int) requires bidirectional_iterator<_It>
2166  {
2167  auto __tmp = *this;
2168  --*this;
2169  return __tmp;
2170  }
2171 
2172  constexpr counted_iterator
2173  operator+(iter_difference_t<_It> __n) const
2174  requires random_access_iterator<_It>
2175  { return counted_iterator(_M_current + __n, _M_length - __n); }
2176 
2177  friend constexpr counted_iterator
2178  operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2179  requires random_access_iterator<_It>
2180  { return __x + __n; }
2181 
2182  constexpr counted_iterator&
2183  operator+=(iter_difference_t<_It> __n)
2184  requires random_access_iterator<_It>
2185  {
2186  __glibcxx_assert(__n <= _M_length);
2187  _M_current += __n;
2188  _M_length -= __n;
2189  return *this;
2190  }
2191 
2192  constexpr counted_iterator
2193  operator-(iter_difference_t<_It> __n) const
2194  requires random_access_iterator<_It>
2195  { return counted_iterator(_M_current - __n, _M_length + __n); }
2196 
2197  template<common_with<_It> _It2>
2198  friend constexpr iter_difference_t<_It2>
2199  operator-(const counted_iterator& __x,
2200  const counted_iterator<_It2>& __y)
2201  { return __y._M_length - __x._M_length; }
2202 
2203  friend constexpr iter_difference_t<_It>
2204  operator-(const counted_iterator& __x, default_sentinel_t)
2205  { return -__x._M_length; }
2206 
2207  friend constexpr iter_difference_t<_It>
2208  operator-(default_sentinel_t, const counted_iterator& __y)
2209  { return __y._M_length; }
2210 
2211  constexpr counted_iterator&
2212  operator-=(iter_difference_t<_It> __n)
2213  requires random_access_iterator<_It>
2214  {
2215  __glibcxx_assert(-__n <= _M_length);
2216  _M_current -= __n;
2217  _M_length += __n;
2218  return *this;
2219  }
2220 
2221  constexpr decltype(auto)
2222  operator[](iter_difference_t<_It> __n) const
2223  noexcept(noexcept(_M_current[__n]))
2224  requires random_access_iterator<_It>
2225  {
2226  __glibcxx_assert(__n < _M_length);
2227  return _M_current[__n];
2228  }
2229 
2230  template<common_with<_It> _It2>
2231  friend constexpr bool
2232  operator==(const counted_iterator& __x,
2233  const counted_iterator<_It2>& __y)
2234  { return __x._M_length == __y._M_length; }
2235 
2236  friend constexpr bool
2237  operator==(const counted_iterator& __x, default_sentinel_t)
2238  { return __x._M_length == 0; }
2239 
2240  template<common_with<_It> _It2>
2241  friend constexpr strong_ordering
2242  operator<=>(const counted_iterator& __x,
2243  const counted_iterator<_It2>& __y)
2244  { return __y._M_length <=> __x._M_length; }
2245 
2246  friend constexpr iter_rvalue_reference_t<_It>
2247  iter_move(const counted_iterator& __i)
2248  noexcept(noexcept(ranges::iter_move(__i._M_current)))
2249  requires input_iterator<_It>
2250  { return ranges::iter_move(__i._M_current); }
2251 
2252  template<indirectly_swappable<_It> _It2>
2253  friend constexpr void
2254  iter_swap(const counted_iterator& __x,
2255  const counted_iterator<_It2>& __y)
2256  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2257  { ranges::iter_swap(__x._M_current, __y._M_current); }
2258 
2259  private:
2260  template<input_or_output_iterator _It2> friend class counted_iterator;
2261 
2262  _It _M_current = _It();
2263  iter_difference_t<_It> _M_length = 0;
2264  };
2265 
2266  template<input_iterator _It>
2267  requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2268  struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2269  {
2270  using pointer = conditional_t<contiguous_iterator<_It>,
2271  add_pointer_t<iter_reference_t<_It>>,
2272  void>;
2273  };
2274 #endif // C++20
2275 
2276  /// @} group iterators
2277 
2278  template<typename _Iterator>
2279  _GLIBCXX20_CONSTEXPR
2280  auto
2281  __niter_base(move_iterator<_Iterator> __it)
2282  -> decltype(make_move_iterator(__niter_base(__it.base())))
2283  { return make_move_iterator(__niter_base(__it.base())); }
2284 
2285  template<typename _Iterator>
2286  struct __is_move_iterator<move_iterator<_Iterator> >
2287  {
2288  enum { __value = 1 };
2289  typedef __true_type __type;
2290  };
2291 
2292  template<typename _Iterator>
2293  _GLIBCXX20_CONSTEXPR
2294  auto
2295  __miter_base(move_iterator<_Iterator> __it)
2296  -> decltype(__miter_base(__it.base()))
2297  { return __miter_base(__it.base()); }
2298 
2299 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2300 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2301  std::__make_move_if_noexcept_iterator(_Iter)
2302 #else
2303 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2304 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2305 #endif // C++11
2306 
2307 #if __cpp_deduction_guides >= 201606
2308  // These helper traits are used for deduction guides
2309  // of associative containers.
2310  template<typename _InputIterator>
2311  using __iter_key_t = remove_const_t<
2312  typename iterator_traits<_InputIterator>::value_type::first_type>;
2313 
2314  template<typename _InputIterator>
2315  using __iter_val_t =
2316  typename iterator_traits<_InputIterator>::value_type::second_type;
2317 
2318  template<typename _T1, typename _T2>
2319  struct pair;
2320 
2321  template<typename _InputIterator>
2322  using __iter_to_alloc_t =
2323  pair<add_const_t<__iter_key_t<_InputIterator>>,
2324  __iter_val_t<_InputIterator>>;
2325 #endif // __cpp_deduction_guides
2326 
2327 _GLIBCXX_END_NAMESPACE_VERSION
2328 } // namespace
2329 
2330 #ifdef _GLIBCXX_DEBUG
2331 # include <debug/stl_iterator.h>
2332 #endif
2333 
2334 #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.