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