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