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