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(std::move(__i)) { }
1170 
1171  template<typename _Iter>
1172  _GLIBCXX17_CONSTEXPR
1174  : _M_current(__i.base()) { }
1175 
1176 #if __cplusplus <= 201703L
1177  _GLIBCXX17_CONSTEXPR iterator_type
1178  base() const
1179  { return _M_current; }
1180 #else
1181  constexpr iterator_type
1182  base() const &
1183 #if __cpp_lib_concepts
1184  requires copy_constructible<iterator_type>
1185 #endif
1186  { return _M_current; }
1187 
1188  constexpr iterator_type
1189  base() &&
1190  { return std::move(_M_current); }
1191 #endif
1192 
1193  _GLIBCXX17_CONSTEXPR reference
1194  operator*() const
1195  { return static_cast<reference>(*_M_current); }
1196 
1197  _GLIBCXX17_CONSTEXPR pointer
1198  operator->() const
1199  { return _M_current; }
1200 
1201  _GLIBCXX17_CONSTEXPR move_iterator&
1202  operator++()
1203  {
1204  ++_M_current;
1205  return *this;
1206  }
1207 
1208  _GLIBCXX17_CONSTEXPR move_iterator
1209  operator++(int)
1210  {
1211  move_iterator __tmp = *this;
1212  ++_M_current;
1213  return __tmp;
1214  }
1215 
1216  _GLIBCXX17_CONSTEXPR move_iterator&
1217  operator--()
1218  {
1219  --_M_current;
1220  return *this;
1221  }
1222 
1223  _GLIBCXX17_CONSTEXPR move_iterator
1224  operator--(int)
1225  {
1226  move_iterator __tmp = *this;
1227  --_M_current;
1228  return __tmp;
1229  }
1230 
1231  _GLIBCXX17_CONSTEXPR move_iterator
1232  operator+(difference_type __n) const
1233  { return move_iterator(_M_current + __n); }
1234 
1235  _GLIBCXX17_CONSTEXPR move_iterator&
1236  operator+=(difference_type __n)
1237  {
1238  _M_current += __n;
1239  return *this;
1240  }
1241 
1242  _GLIBCXX17_CONSTEXPR move_iterator
1243  operator-(difference_type __n) const
1244  { return move_iterator(_M_current - __n); }
1245 
1246  _GLIBCXX17_CONSTEXPR move_iterator&
1247  operator-=(difference_type __n)
1248  {
1249  _M_current -= __n;
1250  return *this;
1251  }
1252 
1253  _GLIBCXX17_CONSTEXPR reference
1254  operator[](difference_type __n) const
1255  { return std::move(_M_current[__n]); }
1256 
1257 #if __cplusplus > 201703L && __cpp_lib_concepts
1258  template<sentinel_for<_Iterator> _Sent>
1259  friend constexpr bool
1260  operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1261  { return __x.base() == __y.base(); }
1262 
1263  template<sized_sentinel_for<_Iterator> _Sent>
1264  friend constexpr iter_difference_t<_Iterator>
1265  operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1266  { return __x.base() - __y.base(); }
1267 
1268  template<sized_sentinel_for<_Iterator> _Sent>
1269  friend constexpr iter_difference_t<_Iterator>
1270  operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1271  { return __x.base() - __y.base(); }
1272 
1273  friend constexpr iter_rvalue_reference_t<_Iterator>
1274  iter_move(const move_iterator& __i)
1275  noexcept(noexcept(ranges::iter_move(__i._M_current)))
1276  { return ranges::iter_move(__i._M_current); }
1277 
1278  template<indirectly_swappable<_Iterator> _Iter2>
1279  friend constexpr void
1280  iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1281  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1282  { return ranges::iter_swap(__x._M_current, __y._M_current); }
1283 #endif // C++20
1284  };
1285 
1286  // Note: See __normal_iterator operators note from Gaby to understand
1287  // why there are always 2 versions for most of the move_iterator
1288  // operators.
1289  template<typename _IteratorL, typename _IteratorR>
1290  inline _GLIBCXX17_CONSTEXPR bool
1291  operator==(const move_iterator<_IteratorL>& __x,
1292  const move_iterator<_IteratorR>& __y)
1293  { return __x.base() == __y.base(); }
1294 
1295  template<typename _Iterator>
1296  inline _GLIBCXX17_CONSTEXPR bool
1297  operator==(const move_iterator<_Iterator>& __x,
1298  const move_iterator<_Iterator>& __y)
1299  { return __x.base() == __y.base(); }
1300 
1301  template<typename _IteratorL, typename _IteratorR>
1302  inline _GLIBCXX17_CONSTEXPR bool
1303  operator!=(const move_iterator<_IteratorL>& __x,
1304  const move_iterator<_IteratorR>& __y)
1305  { return !(__x == __y); }
1306 
1307  template<typename _Iterator>
1308  inline _GLIBCXX17_CONSTEXPR bool
1309  operator!=(const move_iterator<_Iterator>& __x,
1310  const move_iterator<_Iterator>& __y)
1311  { return !(__x == __y); }
1312 
1313  template<typename _IteratorL, typename _IteratorR>
1314  inline _GLIBCXX17_CONSTEXPR bool
1315  operator<(const move_iterator<_IteratorL>& __x,
1316  const move_iterator<_IteratorR>& __y)
1317  { return __x.base() < __y.base(); }
1318 
1319  template<typename _Iterator>
1320  inline _GLIBCXX17_CONSTEXPR bool
1321  operator<(const move_iterator<_Iterator>& __x,
1322  const move_iterator<_Iterator>& __y)
1323  { return __x.base() < __y.base(); }
1324 
1325  template<typename _IteratorL, typename _IteratorR>
1326  inline _GLIBCXX17_CONSTEXPR bool
1327  operator<=(const move_iterator<_IteratorL>& __x,
1328  const move_iterator<_IteratorR>& __y)
1329  { return !(__y < __x); }
1330 
1331  template<typename _Iterator>
1332  inline _GLIBCXX17_CONSTEXPR bool
1333  operator<=(const move_iterator<_Iterator>& __x,
1334  const move_iterator<_Iterator>& __y)
1335  { return !(__y < __x); }
1336 
1337  template<typename _IteratorL, typename _IteratorR>
1338  inline _GLIBCXX17_CONSTEXPR bool
1339  operator>(const move_iterator<_IteratorL>& __x,
1340  const move_iterator<_IteratorR>& __y)
1341  { return __y < __x; }
1342 
1343  template<typename _Iterator>
1344  inline _GLIBCXX17_CONSTEXPR bool
1345  operator>(const move_iterator<_Iterator>& __x,
1346  const move_iterator<_Iterator>& __y)
1347  { return __y < __x; }
1348 
1349  template<typename _IteratorL, typename _IteratorR>
1350  inline _GLIBCXX17_CONSTEXPR bool
1351  operator>=(const move_iterator<_IteratorL>& __x,
1352  const move_iterator<_IteratorR>& __y)
1353  { return !(__x < __y); }
1354 
1355  template<typename _Iterator>
1356  inline _GLIBCXX17_CONSTEXPR bool
1357  operator>=(const move_iterator<_Iterator>& __x,
1358  const move_iterator<_Iterator>& __y)
1359  { return !(__x < __y); }
1360 
1361  // DR 685.
1362  template<typename _IteratorL, typename _IteratorR>
1363  inline _GLIBCXX17_CONSTEXPR auto
1364  operator-(const move_iterator<_IteratorL>& __x,
1365  const move_iterator<_IteratorR>& __y)
1366  -> decltype(__x.base() - __y.base())
1367  { return __x.base() - __y.base(); }
1368 
1369  template<typename _Iterator>
1370  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1371  operator+(typename move_iterator<_Iterator>::difference_type __n,
1372  const move_iterator<_Iterator>& __x)
1373  { return __x + __n; }
1374 
1375  template<typename _Iterator>
1376  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1377  make_move_iterator(_Iterator __i)
1378  { return move_iterator<_Iterator>(__i); }
1379 
1380  template<typename _Iterator, typename _ReturnType
1381  = typename conditional<__move_if_noexcept_cond
1382  <typename iterator_traits<_Iterator>::value_type>::value,
1383  _Iterator, move_iterator<_Iterator>>::type>
1384  inline _GLIBCXX17_CONSTEXPR _ReturnType
1385  __make_move_if_noexcept_iterator(_Iterator __i)
1386  { return _ReturnType(__i); }
1387 
1388  // Overload for pointers that matches std::move_if_noexcept more closely,
1389  // returning a constant iterator when we don't want to move.
1390  template<typename _Tp, typename _ReturnType
1391  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1392  const _Tp*, move_iterator<_Tp*>>::type>
1393  inline _GLIBCXX17_CONSTEXPR _ReturnType
1394  __make_move_if_noexcept_iterator(_Tp* __i)
1395  { return _ReturnType(__i); }
1396 
1397 #if __cplusplus > 201703L && __cpp_lib_concepts
1398  // [iterators.common] Common iterators
1399 
1400  namespace __detail
1401  {
1402  template<input_or_output_iterator _It>
1403  class _Common_iter_proxy
1404  {
1405  iter_value_t<_It> _M_keep;
1406 
1407  _Common_iter_proxy(iter_reference_t<_It>&& __x)
1408  : _M_keep(std::move(__x)) { }
1409 
1410  template<typename _Iter, typename _Sent>
1411  friend class common_iterator;
1412 
1413  public:
1414  const iter_value_t<_It>*
1415  operator->() const
1416  { return std::__addressof(_M_keep); }
1417  };
1418 
1419  template<typename _It>
1420  concept __common_iter_has_arrow = indirectly_readable<const _It>
1421  && (requires(const _It& __it) { __it.operator->(); }
1422  || is_reference_v<iter_reference_t<_It>>
1423  || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1424 
1425  } // namespace __detail
1426 
1427  /// An iterator/sentinel adaptor for representing a non-common range.
1428  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1429  requires (!same_as<_It, _Sent>)
1430  class common_iterator
1431  {
1432  template<typename _Tp, typename _Up>
1433  static constexpr bool
1434  _S_noexcept1()
1435  {
1436  if constexpr (is_trivially_default_constructible_v<_Tp>)
1437  return is_nothrow_assignable_v<_Tp, _Up>;
1438  else
1439  return is_nothrow_constructible_v<_Tp, _Up>;
1440  }
1441 
1442  template<typename _It2, typename _Sent2>
1443  static constexpr bool
1444  _S_noexcept()
1445  { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1446 
1447  public:
1448  constexpr
1449  common_iterator()
1450  noexcept(is_nothrow_default_constructible_v<_It>)
1451  : _M_it(), _M_index(0)
1452  { }
1453 
1454  constexpr
1455  common_iterator(_It __i)
1456  noexcept(is_nothrow_move_constructible_v<_It>)
1457  : _M_it(std::move(__i)), _M_index(0)
1458  { }
1459 
1460  constexpr
1461  common_iterator(_Sent __s)
1462  noexcept(is_nothrow_move_constructible_v<_Sent>)
1463  : _M_sent(std::move(__s)), _M_index(1)
1464  { }
1465 
1466  template<typename _It2, typename _Sent2>
1467  requires convertible_to<const _It2&, _It>
1468  && convertible_to<const _Sent2&, _Sent>
1469  constexpr
1470  common_iterator(const common_iterator<_It2, _Sent2>& __x)
1471  noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1472  : _M_valueless(), _M_index(__x._M_index)
1473  {
1474  if (_M_index == 0)
1475  {
1476  if constexpr (is_trivially_default_constructible_v<_It>)
1477  _M_it = std::move(__x._M_it);
1478  else
1479  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1480  }
1481  else if (_M_index == 1)
1482  {
1483  if constexpr (is_trivially_default_constructible_v<_Sent>)
1484  _M_sent = std::move(__x._M_sent);
1485  else
1486  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1487  }
1488  }
1489 
1490  constexpr
1491  common_iterator(const common_iterator& __x)
1492  noexcept(_S_noexcept<const _It&, const _Sent&>())
1493  : _M_valueless(), _M_index(__x._M_index)
1494  {
1495  if (_M_index == 0)
1496  {
1497  if constexpr (is_trivially_default_constructible_v<_It>)
1498  _M_it = std::move(__x._M_it);
1499  else
1500  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1501  }
1502  else if (_M_index == 1)
1503  {
1504  if constexpr (is_trivially_default_constructible_v<_Sent>)
1505  _M_sent = std::move(__x._M_sent);
1506  else
1507  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1508  }
1509  }
1510 
1511  common_iterator&
1512  operator=(const common_iterator& __x)
1513  noexcept(is_nothrow_copy_assignable_v<_It>
1514  && is_nothrow_copy_assignable_v<_Sent>
1515  && is_nothrow_copy_constructible_v<_It>
1516  && is_nothrow_copy_constructible_v<_Sent>)
1517  {
1518  return this->operator=<_It, _Sent>(__x);
1519  }
1520 
1521  template<typename _It2, typename _Sent2>
1522  requires convertible_to<const _It2&, _It>
1523  && convertible_to<const _Sent2&, _Sent>
1524  && assignable_from<_It&, const _It2&>
1525  && assignable_from<_Sent&, const _Sent2&>
1526  common_iterator&
1527  operator=(const common_iterator<_It2, _Sent2>& __x)
1528  noexcept(is_nothrow_constructible_v<_It, const _It2&>
1529  && is_nothrow_constructible_v<_Sent, const _Sent2&>
1530  && is_nothrow_assignable_v<_It, const _It2&>
1531  && is_nothrow_assignable_v<_Sent, const _Sent2&>)
1532  {
1533  switch(_M_index << 2 | __x._M_index)
1534  {
1535  case 0b0000:
1536  _M_it = __x._M_it;
1537  break;
1538  case 0b0101:
1539  _M_sent = __x._M_sent;
1540  break;
1541  case 0b0001:
1542  _M_it.~_It();
1543  _M_index = -1;
1544  [[fallthrough]];
1545  case 0b1001:
1546  ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
1547  _M_index = 1;
1548  break;
1549  case 0b0100:
1550  _M_sent.~_Sent();
1551  _M_index = -1;
1552  [[fallthrough]];
1553  case 0b1000:
1554  ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
1555  _M_index = 0;
1556  break;
1557  default:
1558  __glibcxx_assert(__x._M_has_value());
1559  __builtin_unreachable();
1560  }
1561  return *this;
1562  }
1563 
1564  ~common_iterator()
1565  {
1566  switch (_M_index)
1567  {
1568  case 0:
1569  _M_it.~_It();
1570  break;
1571  case 1:
1572  _M_sent.~_Sent();
1573  break;
1574  }
1575  }
1576 
1577  decltype(auto)
1578  operator*()
1579  {
1580  __glibcxx_assert(_M_index == 0);
1581  return *_M_it;
1582  }
1583 
1584  decltype(auto)
1585  operator*() const requires __detail::__dereferenceable<const _It>
1586  {
1587  __glibcxx_assert(_M_index == 0);
1588  return *_M_it;
1589  }
1590 
1591  decltype(auto)
1592  operator->() const requires __detail::__common_iter_has_arrow<_It>
1593  {
1594  __glibcxx_assert(_M_index == 0);
1595  if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1596  return _M_it;
1597  else if constexpr (is_reference_v<iter_reference_t<_It>>)
1598  {
1599  auto&& __tmp = *_M_it;
1600  return std::__addressof(__tmp);
1601  }
1602  else
1603  return _Common_iter_proxy(*_M_it);
1604  }
1605 
1606  common_iterator&
1607  operator++()
1608  {
1609  __glibcxx_assert(_M_index == 0);
1610  ++_M_it;
1611  return *this;
1612  }
1613 
1614  decltype(auto)
1615  operator++(int)
1616  {
1617  __glibcxx_assert(_M_index == 0);
1618  if constexpr (forward_iterator<_It>)
1619  {
1620  common_iterator __tmp = *this;
1621  ++*this;
1622  return __tmp;
1623  }
1624  else
1625  return _M_it++;
1626  }
1627 
1628  template<typename _It2, sentinel_for<_It> _Sent2>
1629  requires sentinel_for<_Sent, _It2>
1630  friend bool
1631  operator==(const common_iterator& __x,
1632  const common_iterator<_It2, _Sent2>& __y)
1633  {
1634  switch(__x._M_index << 2 | __y._M_index)
1635  {
1636  case 0b0000:
1637  case 0b0101:
1638  return true;
1639  case 0b0001:
1640  return __x._M_it == __y._M_sent;
1641  case 0b0100:
1642  return __x._M_sent == __y._M_it;
1643  default:
1644  __glibcxx_assert(__x._M_has_value());
1645  __glibcxx_assert(__y._M_has_value());
1646  __builtin_unreachable();
1647  }
1648  }
1649 
1650  template<typename _It2, sentinel_for<_It> _Sent2>
1651  requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
1652  friend bool
1653  operator==(const common_iterator& __x,
1654  const common_iterator<_It2, _Sent2>& __y)
1655  {
1656  switch(__x._M_index << 2 | __y._M_index)
1657  {
1658  case 0b0101:
1659  return true;
1660  case 0b0000:
1661  return __x._M_it == __y._M_it;
1662  case 0b0001:
1663  return __x._M_it == __y._M_sent;
1664  case 0b0100:
1665  return __x._M_sent == __y._M_it;
1666  default:
1667  __glibcxx_assert(__x._M_has_value());
1668  __glibcxx_assert(__y._M_has_value());
1669  __builtin_unreachable();
1670  }
1671  }
1672 
1673  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
1674  requires sized_sentinel_for<_Sent, _It2>
1675  friend iter_difference_t<_It2>
1676  operator-(const common_iterator& __x,
1677  const common_iterator<_It2, _Sent2>& __y)
1678  {
1679  switch(__x._M_index << 2 | __y._M_index)
1680  {
1681  case 0b0101:
1682  return 0;
1683  case 0b0000:
1684  return __x._M_it - __y._M_it;
1685  case 0b0001:
1686  return __x._M_it - __y._M_sent;
1687  case 0b0100:
1688  return __x._M_sent - __y._M_it;
1689  default:
1690  __glibcxx_assert(__x._M_has_value());
1691  __glibcxx_assert(__y._M_has_value());
1692  __builtin_unreachable();
1693  }
1694  }
1695 
1696  friend iter_rvalue_reference_t<_It>
1697  iter_move(const common_iterator& __i)
1698  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
1699  requires input_iterator<_It>
1700  {
1701  __glibcxx_assert(__i._M_index == 0);
1702  return ranges::iter_move(__i._M_it);
1703  }
1704 
1705  template<indirectly_swappable<_It> _It2, typename _Sent2>
1706  friend void
1707  iter_swap(const common_iterator& __x,
1708  const common_iterator<_It2, _Sent2>& __y)
1709  noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
1710  std::declval<const _It2&>())))
1711  {
1712  __glibcxx_assert(__x._M_index == 0);
1713  __glibcxx_assert(__y._M_index == 0);
1714  return ranges::iter_swap(__x._M_it, __y._M_it);
1715  }
1716 
1717  private:
1718  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
1719  friend class common_iterator;
1720 
1721  bool _M_has_value() const noexcept { return _M_index < 2; }
1722 
1723  union
1724  {
1725  _It _M_it;
1726  _Sent _M_sent;
1727  unsigned char _M_valueless;
1728  };
1729  unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
1730  };
1731 
1732  template<typename _It, typename _Sent>
1733  struct incrementable_traits<common_iterator<_It, _Sent>>
1734  {
1735  using difference_type = iter_difference_t<_It>;
1736  };
1737 
1738  namespace __detail
1739  {
1740  // FIXME: This has to be at namespace-scope because of PR 92103.
1741  template<typename _It, typename _Sent>
1742  struct __common_iter_ptr
1743  {
1744  using type = void;
1745  };
1746 
1747  template<typename _It, typename _Sent>
1748  requires __detail::__common_iter_has_arrow<_It>
1749  struct __common_iter_ptr<_It, _Sent>
1750  {
1751  using common_iterator = std::common_iterator<_It, _Sent>;
1752 
1753  using type
1754  = decltype(std::declval<const common_iterator&>().operator->());
1755  };
1756  } // namespace __detail
1757 
1758  template<input_iterator _It, typename _Sent>
1759  struct iterator_traits<common_iterator<_It, _Sent>>
1760  {
1761  using iterator_concept = conditional_t<forward_iterator<_It>,
1762  forward_iterator_tag, input_iterator_tag>;
1763  using iterator_category = __detail::__clamp_iter_cat<
1764  typename iterator_traits<_It>::iterator_category,
1765  forward_iterator_tag, input_iterator_tag>;
1766  using value_type = iter_value_t<_It>;
1767  using difference_type = iter_difference_t<_It>;
1768  using pointer = typename __detail::__common_iter_ptr<_It, _Sent>::type;
1769  using reference = iter_reference_t<_It>;
1770  };
1771 
1772  // [iterators.counted] Counted iterators
1773 
1774  /// An iterator adaptor that keeps track of the distance to the end.
1775  template<input_or_output_iterator _It>
1776  class counted_iterator
1777  {
1778  public:
1779  using iterator_type = _It;
1780 
1781  constexpr counted_iterator() = default;
1782 
1783  constexpr
1784  counted_iterator(_It __i, iter_difference_t<_It> __n)
1785  : _M_current(__i), _M_length(__n)
1786  { __glibcxx_assert(__n >= 0); }
1787 
1788  template<typename _It2>
1789  requires convertible_to<const _It2&, _It>
1790  constexpr
1791  counted_iterator(const counted_iterator<_It2>& __x)
1792  : _M_current(__x._M_current), _M_length(__x._M_length)
1793  { }
1794 
1795  template<typename _It2>
1796  requires assignable_from<_It&, const _It2&>
1797  constexpr counted_iterator&
1798  operator=(const counted_iterator<_It2>& __x)
1799  {
1800  _M_current = __x._M_current;
1801  _M_length = __x._M_length;
1802  return *this;
1803  }
1804 
1805  constexpr _It
1806  base() const &
1807  noexcept(is_nothrow_copy_constructible_v<_It>)
1808  requires copy_constructible<_It>
1809  { return _M_current; }
1810 
1811  constexpr _It
1812  base() &&
1813  noexcept(is_nothrow_move_constructible_v<_It>)
1814  { return std::move(_M_current); }
1815 
1816  constexpr iter_difference_t<_It>
1817  count() const noexcept { return _M_length; }
1818 
1819  constexpr decltype(auto)
1820  operator*()
1821  noexcept(noexcept(*_M_current))
1822  { return *_M_current; }
1823 
1824  constexpr decltype(auto)
1825  operator*() const
1826  noexcept(noexcept(*_M_current))
1827  requires __detail::__dereferenceable<const _It>
1828  { return *_M_current; }
1829 
1830  constexpr counted_iterator&
1831  operator++()
1832  {
1833  __glibcxx_assert(_M_length > 0);
1834  ++_M_current;
1835  --_M_length;
1836  return *this;
1837  }
1838 
1839  decltype(auto)
1840  operator++(int)
1841  {
1842  __glibcxx_assert(_M_length > 0);
1843  --_M_length;
1844  __try
1845  {
1846  return _M_current++;
1847  } __catch(...) {
1848  ++_M_length;
1849  throw;
1850  }
1851 
1852  }
1853 
1854  constexpr counted_iterator
1855  operator++(int) requires forward_iterator<_It>
1856  {
1857  auto __tmp = *this;
1858  ++*this;
1859  return __tmp;
1860  }
1861 
1862  constexpr counted_iterator&
1863  operator--() requires bidirectional_iterator<_It>
1864  {
1865  --_M_current;
1866  ++_M_length;
1867  return *this;
1868  }
1869 
1870  constexpr counted_iterator
1871  operator--(int) requires bidirectional_iterator<_It>
1872  {
1873  auto __tmp = *this;
1874  --*this;
1875  return __tmp;
1876  }
1877 
1878  constexpr counted_iterator
1879  operator+(iter_difference_t<_It> __n) const
1880  requires random_access_iterator<_It>
1881  { return counted_iterator(_M_current + __n, _M_length - __n); }
1882 
1883  friend constexpr counted_iterator
1884  operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
1885  requires random_access_iterator<_It>
1886  { return __x + __n; }
1887 
1888  constexpr counted_iterator&
1889  operator+=(iter_difference_t<_It> __n)
1890  requires random_access_iterator<_It>
1891  {
1892  __glibcxx_assert(__n <= _M_length);
1893  _M_current += __n;
1894  _M_length -= __n;
1895  return *this;
1896  }
1897 
1898  constexpr counted_iterator
1899  operator-(iter_difference_t<_It> __n) const
1900  requires random_access_iterator<_It>
1901  { return counted_iterator(_M_current - __n, _M_length + __n); }
1902 
1903  template<common_with<_It> _It2>
1904  friend constexpr iter_difference_t<_It2>
1905  operator-(const counted_iterator& __x,
1906  const counted_iterator<_It2>& __y)
1907  { return __y._M_length - __x._M_length; }
1908 
1909  friend constexpr iter_difference_t<_It>
1910  operator-(const counted_iterator& __x, default_sentinel_t)
1911  { return -__x._M_length; }
1912 
1913  friend constexpr iter_difference_t<_It>
1914  operator-(default_sentinel_t, const counted_iterator& __y)
1915  { return __y._M_length; }
1916 
1917  constexpr counted_iterator&
1918  operator-=(iter_difference_t<_It> __n)
1919  requires random_access_iterator<_It>
1920  {
1921  __glibcxx_assert(-__n <= _M_length);
1922  _M_current -= __n;
1923  _M_length += __n;
1924  return *this;
1925  }
1926 
1927  constexpr decltype(auto)
1928  operator[](iter_difference_t<_It> __n) const
1929  noexcept(noexcept(_M_current[__n]))
1930  requires random_access_iterator<_It>
1931  {
1932  __glibcxx_assert(__n < _M_length);
1933  return _M_current[__n];
1934  }
1935 
1936  template<common_with<_It> _It2>
1937  friend constexpr bool
1938  operator==(const counted_iterator& __x,
1939  const counted_iterator<_It2>& __y)
1940  { return __x._M_length == __y._M_length; }
1941 
1942  friend constexpr bool
1943  operator==(const counted_iterator& __x, default_sentinel_t)
1944  { return __x._M_length == 0; }
1945 
1946  template<common_with<_It> _It2>
1947  friend constexpr strong_ordering
1948  operator<=>(const counted_iterator& __x,
1949  const counted_iterator<_It2>& __y)
1950  { return __y._M_length <=> __x._M_length; }
1951 
1952  friend constexpr iter_rvalue_reference_t<_It>
1953  iter_move(const counted_iterator& __i)
1954  noexcept(noexcept(ranges::iter_move(__i._M_current)))
1955  requires input_iterator<_It>
1956  { return ranges::iter_move(__i._M_current); }
1957 
1958  template<indirectly_swappable<_It> _It2>
1959  friend constexpr void
1960  iter_swap(const counted_iterator& __x,
1961  const counted_iterator<_It2>& __y)
1962  noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1963  { ranges::iter_swap(__x._M_current, __y._M_current); }
1964 
1965  private:
1966  template<input_or_output_iterator _It2> friend class counted_iterator;
1967 
1968  _It _M_current = _It();
1969  iter_difference_t<_It> _M_length = 0;
1970  };
1971 
1972  template<typename _It>
1973  struct incrementable_traits<counted_iterator<_It>>
1974  {
1975  using difference_type = iter_difference_t<_It>;
1976  };
1977 
1978  template<input_iterator _It>
1979  struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
1980  {
1981  using pointer = void;
1982  };
1983 #endif // C++20
1984 
1985  // @} group iterators
1986 
1987  template<typename _Iterator>
1988  auto
1989  __niter_base(move_iterator<_Iterator> __it)
1990  -> decltype(make_move_iterator(__niter_base(__it.base())))
1991  { return make_move_iterator(__niter_base(__it.base())); }
1992 
1993  template<typename _Iterator>
1994  struct __is_move_iterator<move_iterator<_Iterator> >
1995  {
1996  enum { __value = 1 };
1997  typedef __true_type __type;
1998  };
1999 
2000  template<typename _Iterator>
2001  auto
2002  __miter_base(move_iterator<_Iterator> __it)
2003  -> decltype(__miter_base(__it.base()))
2004  { return __miter_base(__it.base()); }
2005 
2006 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2007 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2008  std::__make_move_if_noexcept_iterator(_Iter)
2009 #else
2010 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2011 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2012 #endif // C++11
2013 
2014 #if __cpp_deduction_guides >= 201606
2015  // These helper traits are used for deduction guides
2016  // of associative containers.
2017  template<typename _InputIterator>
2018  using __iter_key_t = remove_const_t<
2019  typename iterator_traits<_InputIterator>::value_type::first_type>;
2020 
2021  template<typename _InputIterator>
2022  using __iter_val_t =
2023  typename iterator_traits<_InputIterator>::value_type::second_type;
2024 
2025  template<typename _T1, typename _T2>
2026  struct pair;
2027 
2028  template<typename _InputIterator>
2029  using __iter_to_alloc_t =
2030  pair<add_const_t<__iter_key_t<_InputIterator>>,
2031  __iter_val_t<_InputIterator>>;
2032 #endif // __cpp_deduction_guides
2033 
2034 _GLIBCXX_END_NAMESPACE_VERSION
2035 } // namespace
2036 
2037 #ifdef _GLIBCXX_DEBUG
2038 # include <debug/stl_iterator.h>
2039 #endif
2040 
2041 #endif
std::conditional
Define a member typedef type to one of two argument types.
Definition: type_traits:92
std::front_insert_iterator::operator++
front_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: bits/stl_iterator.h:642
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::reverse_iterator::operator[]
constexpr reference operator[](difference_type __n) const
Definition: bits/stl_iterator.h:307
std::back_insert_iterator::operator*
back_insert_iterator & operator*()
Simply returns *this.
Definition: bits/stl_iterator.h:546
std::front_insert_iterator::operator*
front_insert_iterator & operator*()
Simply returns *this.
Definition: bits/stl_iterator.h:637
std::insert_iterator::operator*
insert_iterator & operator*()
Simply returns *this.
Definition: bits/stl_iterator.h:751
std::reverse_iterator::operator+=
constexpr reverse_iterator & operator+=(difference_type __n)
Definition: bits/stl_iterator.h:273
std::reverse_iterator::operator*
constexpr reference operator*() const
Definition: bits/stl_iterator.h:182
std::input_iterator_tag
Marking input iterators.
Definition: stl_iterator_base_types.h:93
std::insert_iterator::operator++
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: bits/stl_iterator.h:756
std::iterator_traits
Traits class for iterators.
Definition: stl_iterator_base_types.h:150
std::reverse_iterator::operator+
constexpr reverse_iterator operator+(difference_type __n) const
Definition: bits/stl_iterator.h:263
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
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::back_insert_iterator::operator=
back_insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: bits/stl_iterator.h:530
std::reverse_iterator::reverse_iterator
constexpr reverse_iterator(const reverse_iterator &__x)
Definition: bits/stl_iterator.h:148
std::front_insert_iterator::operator=
front_insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: bits/stl_iterator.h:621
std::reverse_iterator::operator--
constexpr reverse_iterator operator--(int)
Definition: bits/stl_iterator.h:250
std::reverse_iterator::operator-
constexpr reverse_iterator operator-(difference_type __n) const
Definition: bits/stl_iterator.h:285
std::reverse_iterator::reverse_iterator
constexpr reverse_iterator(iterator_type __x)
Definition: bits/stl_iterator.h:142
std::reverse_iterator::operator++
constexpr reverse_iterator & operator++()
Definition: bits/stl_iterator.h:213
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::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::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::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::is_nothrow_copy_constructible
is_nothrow_copy_constructible
Definition: type_traits:1039
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 pointer operator->() const
Definition: bits/stl_iterator.h:194
std::reverse_iterator::operator++
constexpr reverse_iterator operator++(int)
Definition: bits/stl_iterator.h:225
std::insert_iterator
Turns assignment into insertion.
Definition: bits/stl_iterator.h:682
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
std::reverse_iterator::base
constexpr iterator_type base() const
Definition: bits/stl_iterator.h:168
std::reverse_iterator::reverse_iterator
constexpr reverse_iterator()
Definition: bits/stl_iterator.h:136
cpp_type_traits.h
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::remove_const_t
typename remove_const< _Tp >::type remove_const_t
Alias template for remove_const.
Definition: type_traits:1565
__gnu_cxx
GNU extensions for public use.
std::reverse_iterator
Definition: bits/stl_iterator.h:110
ptr_traits.h
std::insert_iterator::insert_iterator
insert_iterator(_Container &__x, typename _Container::iterator __i)
Definition: bits/stl_iterator.h:697
std::make_reverse_iterator
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
Definition: bits/stl_iterator.h:451
std::operator*
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:391
type_traits
std::move_iterator
Definition: bits/stl_iterator.h:1128
new
std::front_insert_iterator
Turns assignment into insertion.
Definition: bits/stl_iterator.h:587
std::inserter
insert_iterator< _Container > inserter(_Container &__x, _Iterator __i)
Definition: bits/stl_iterator.h:779
std
ISO C++ entities toplevel namespace is std.
std::front_inserter
front_insert_iterator< _Container > front_inserter(_Container &__x)
Definition: bits/stl_iterator.h:664
std::back_insert_iterator::operator++
back_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: bits/stl_iterator.h:551
std::reverse_iterator::operator--
constexpr reverse_iterator & operator--()
Definition: bits/stl_iterator.h:238
std::iterator
Common iterator class.
Definition: stl_iterator_base_types.h:127
stl_iterator.h
move.h
std::back_inserter
back_insert_iterator< _Container > back_inserter(_Container &__x)
Definition: bits/stl_iterator.h:573
std::back_insert_iterator
Turns assignment into insertion.
Definition: bits/stl_iterator.h:495
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(const reverse_iterator< _Iter > &__x)
Definition: bits/stl_iterator.h:161
compare
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
type_traits.h
std::insert_iterator::operator++
insert_iterator & operator++(int)
Simply returns *this. (This iterator does not move.)
Definition: bits/stl_iterator.h:761