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