libstdc++
bits/stl_iterator.h
Go to the documentation of this file.
1 // Iterators -*- C++ -*-
2 
3 // Copyright (C) 2001-2018 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 > 201402L
69 # define __cpp_lib_array_constexpr 201603
70 #endif
71 
72 namespace std _GLIBCXX_VISIBILITY(default)
73 {
74 _GLIBCXX_BEGIN_NAMESPACE_VERSION
75 
76  /**
77  * @addtogroup iterators
78  * @{
79  */
80 
81  // 24.4.1 Reverse iterators
82  /**
83  * Bidirectional and random access iterators have corresponding reverse
84  * %iterator adaptors that iterate through the data structure in the
85  * opposite direction. They have the same signatures as the corresponding
86  * iterators. The fundamental relation between a reverse %iterator and its
87  * corresponding %iterator @c i is established by the identity:
88  * @code
89  * &*(reverse_iterator(i)) == &*(i - 1)
90  * @endcode
91  *
92  * <em>This mapping is dictated by the fact that while there is always a
93  * pointer past the end of an array, there might not be a valid pointer
94  * before the beginning of an array.</em> [24.4.1]/1,2
95  *
96  * Reverse iterators can be tricky and surprising at first. Their
97  * semantics make sense, however, and the trickiness is a side effect of
98  * the requirement that the iterators must be safe.
99  */
100  template<typename _Iterator>
102  : public iterator<typename iterator_traits<_Iterator>::iterator_category,
103  typename iterator_traits<_Iterator>::value_type,
104  typename iterator_traits<_Iterator>::difference_type,
105  typename iterator_traits<_Iterator>::pointer,
106  typename iterator_traits<_Iterator>::reference>
107  {
108  protected:
109  _Iterator current;
110 
111  typedef iterator_traits<_Iterator> __traits_type;
112 
113  public:
114  typedef _Iterator iterator_type;
115  typedef typename __traits_type::difference_type difference_type;
116  typedef typename __traits_type::pointer pointer;
117  typedef typename __traits_type::reference reference;
118 
119  /**
120  * The default constructor value-initializes member @p current.
121  * If it is a pointer, that means it is zero-initialized.
122  */
123  // _GLIBCXX_RESOLVE_LIB_DEFECTS
124  // 235 No specification of default ctor for reverse_iterator
125  _GLIBCXX17_CONSTEXPR
126  reverse_iterator() : current() { }
127 
128  /**
129  * This %iterator will move in the opposite direction that @p x does.
130  */
131  explicit _GLIBCXX17_CONSTEXPR
132  reverse_iterator(iterator_type __x) : current(__x) { }
133 
134  /**
135  * The copy constructor is normal.
136  */
137  _GLIBCXX17_CONSTEXPR
139  : current(__x.current) { }
140 
141  /**
142  * A %reverse_iterator across other types can be copied if the
143  * underlying %iterator can be converted to the type of @c current.
144  */
145  template<typename _Iter>
146  _GLIBCXX17_CONSTEXPR
148  : current(__x.base()) { }
149 
150  /**
151  * @return @c current, the %iterator used for underlying work.
152  */
153  _GLIBCXX17_CONSTEXPR iterator_type
154  base() const
155  { return current; }
156 
157  /**
158  * @return A reference to the value at @c --current
159  *
160  * This requires that @c --current is dereferenceable.
161  *
162  * @warning This implementation requires that for an iterator of the
163  * underlying iterator type, @c x, a reference obtained by
164  * @c *x remains valid after @c x has been modified or
165  * destroyed. This is a bug: http://gcc.gnu.org/PR51823
166  */
167  _GLIBCXX17_CONSTEXPR reference
168  operator*() const
169  {
170  _Iterator __tmp = current;
171  return *--__tmp;
172  }
173 
174  /**
175  * @return A pointer to the value at @c --current
176  *
177  * This requires that @c --current is dereferenceable.
178  */
179  _GLIBCXX17_CONSTEXPR pointer
180  operator->() const
181  { return &(operator*()); }
182 
183  /**
184  * @return @c *this
185  *
186  * Decrements the underlying iterator.
187  */
188  _GLIBCXX17_CONSTEXPR reverse_iterator&
190  {
191  --current;
192  return *this;
193  }
194 
195  /**
196  * @return The original value of @c *this
197  *
198  * Decrements the underlying iterator.
199  */
200  _GLIBCXX17_CONSTEXPR reverse_iterator
202  {
203  reverse_iterator __tmp = *this;
204  --current;
205  return __tmp;
206  }
207 
208  /**
209  * @return @c *this
210  *
211  * Increments the underlying iterator.
212  */
213  _GLIBCXX17_CONSTEXPR reverse_iterator&
215  {
216  ++current;
217  return *this;
218  }
219 
220  /**
221  * @return A reverse_iterator with the previous value of @c *this
222  *
223  * Increments the underlying iterator.
224  */
225  _GLIBCXX17_CONSTEXPR reverse_iterator
227  {
228  reverse_iterator __tmp = *this;
229  ++current;
230  return __tmp;
231  }
232 
233  /**
234  * @return A reverse_iterator that refers to @c current - @a __n
235  *
236  * The underlying iterator must be a Random Access Iterator.
237  */
238  _GLIBCXX17_CONSTEXPR reverse_iterator
239  operator+(difference_type __n) const
240  { return reverse_iterator(current - __n); }
241 
242  /**
243  * @return *this
244  *
245  * Moves the underlying iterator backwards @a __n steps.
246  * The underlying iterator must be a Random Access Iterator.
247  */
248  _GLIBCXX17_CONSTEXPR reverse_iterator&
249  operator+=(difference_type __n)
250  {
251  current -= __n;
252  return *this;
253  }
254 
255  /**
256  * @return A reverse_iterator that refers to @c current - @a __n
257  *
258  * The underlying iterator must be a Random Access Iterator.
259  */
260  _GLIBCXX17_CONSTEXPR reverse_iterator
261  operator-(difference_type __n) const
262  { return reverse_iterator(current + __n); }
263 
264  /**
265  * @return *this
266  *
267  * Moves the underlying iterator forwards @a __n steps.
268  * The underlying iterator must be a Random Access Iterator.
269  */
270  _GLIBCXX17_CONSTEXPR reverse_iterator&
271  operator-=(difference_type __n)
272  {
273  current += __n;
274  return *this;
275  }
276 
277  /**
278  * @return The value at @c current - @a __n - 1
279  *
280  * The underlying iterator must be a Random Access Iterator.
281  */
282  _GLIBCXX17_CONSTEXPR reference
283  operator[](difference_type __n) const
284  { return *(*this + __n); }
285  };
286 
287  //@{
288  /**
289  * @param __x A %reverse_iterator.
290  * @param __y A %reverse_iterator.
291  * @return A simple bool.
292  *
293  * Reverse iterators forward many operations to their underlying base()
294  * iterators. Others are implemented in terms of one another.
295  *
296  */
297  template<typename _Iterator>
298  inline _GLIBCXX17_CONSTEXPR bool
299  operator==(const reverse_iterator<_Iterator>& __x,
300  const reverse_iterator<_Iterator>& __y)
301  { return __x.base() == __y.base(); }
302 
303  template<typename _Iterator>
304  inline _GLIBCXX17_CONSTEXPR bool
305  operator<(const reverse_iterator<_Iterator>& __x,
306  const reverse_iterator<_Iterator>& __y)
307  { return __y.base() < __x.base(); }
308 
309  template<typename _Iterator>
310  inline _GLIBCXX17_CONSTEXPR bool
311  operator!=(const reverse_iterator<_Iterator>& __x,
312  const reverse_iterator<_Iterator>& __y)
313  { return !(__x == __y); }
314 
315  template<typename _Iterator>
316  inline _GLIBCXX17_CONSTEXPR bool
317  operator>(const reverse_iterator<_Iterator>& __x,
318  const reverse_iterator<_Iterator>& __y)
319  { return __y < __x; }
320 
321  template<typename _Iterator>
322  inline _GLIBCXX17_CONSTEXPR bool
323  operator<=(const reverse_iterator<_Iterator>& __x,
324  const reverse_iterator<_Iterator>& __y)
325  { return !(__y < __x); }
326 
327  template<typename _Iterator>
328  inline _GLIBCXX17_CONSTEXPR bool
329  operator>=(const reverse_iterator<_Iterator>& __x,
330  const reverse_iterator<_Iterator>& __y)
331  { return !(__x < __y); }
332 
333  // _GLIBCXX_RESOLVE_LIB_DEFECTS
334  // DR 280. Comparison of reverse_iterator to const reverse_iterator.
335  template<typename _IteratorL, typename _IteratorR>
336  inline _GLIBCXX17_CONSTEXPR bool
337  operator==(const reverse_iterator<_IteratorL>& __x,
338  const reverse_iterator<_IteratorR>& __y)
339  { return __x.base() == __y.base(); }
340 
341  template<typename _IteratorL, typename _IteratorR>
342  inline _GLIBCXX17_CONSTEXPR bool
343  operator<(const reverse_iterator<_IteratorL>& __x,
344  const reverse_iterator<_IteratorR>& __y)
345  { return __y.base() < __x.base(); }
346 
347  template<typename _IteratorL, typename _IteratorR>
348  inline _GLIBCXX17_CONSTEXPR bool
349  operator!=(const reverse_iterator<_IteratorL>& __x,
350  const reverse_iterator<_IteratorR>& __y)
351  { return !(__x == __y); }
352 
353  template<typename _IteratorL, typename _IteratorR>
354  inline _GLIBCXX17_CONSTEXPR bool
355  operator>(const reverse_iterator<_IteratorL>& __x,
356  const reverse_iterator<_IteratorR>& __y)
357  { return __y < __x; }
358 
359  template<typename _IteratorL, typename _IteratorR>
360  inline _GLIBCXX17_CONSTEXPR bool
361  operator<=(const reverse_iterator<_IteratorL>& __x,
362  const reverse_iterator<_IteratorR>& __y)
363  { return !(__y < __x); }
364 
365  template<typename _IteratorL, typename _IteratorR>
366  inline _GLIBCXX17_CONSTEXPR bool
367  operator>=(const reverse_iterator<_IteratorL>& __x,
368  const reverse_iterator<_IteratorR>& __y)
369  { return !(__x < __y); }
370  //@}
371 
372 #if __cplusplus < 201103L
373  template<typename _Iterator>
374  inline typename reverse_iterator<_Iterator>::difference_type
375  operator-(const reverse_iterator<_Iterator>& __x,
376  const reverse_iterator<_Iterator>& __y)
377  { return __y.base() - __x.base(); }
378 
379  template<typename _IteratorL, typename _IteratorR>
380  inline typename reverse_iterator<_IteratorL>::difference_type
381  operator-(const reverse_iterator<_IteratorL>& __x,
382  const reverse_iterator<_IteratorR>& __y)
383  { return __y.base() - __x.base(); }
384 #else
385  // _GLIBCXX_RESOLVE_LIB_DEFECTS
386  // DR 685. reverse_iterator/move_iterator difference has invalid signatures
387  template<typename _IteratorL, typename _IteratorR>
388  inline _GLIBCXX17_CONSTEXPR auto
389  operator-(const reverse_iterator<_IteratorL>& __x,
390  const reverse_iterator<_IteratorR>& __y)
391  -> decltype(__y.base() - __x.base())
392  { return __y.base() - __x.base(); }
393 #endif
394 
395  template<typename _Iterator>
396  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
397  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
398  const reverse_iterator<_Iterator>& __x)
399  { return reverse_iterator<_Iterator>(__x.base() - __n); }
400 
401 #if __cplusplus >= 201103L
402  // Same as C++14 make_reverse_iterator but used in C++03 mode too.
403  template<typename _Iterator>
404  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
405  __make_reverse_iterator(_Iterator __i)
406  { return reverse_iterator<_Iterator>(__i); }
407 
408 # if __cplusplus > 201103L
409 # define __cpp_lib_make_reverse_iterator 201402
410 
411  // _GLIBCXX_RESOLVE_LIB_DEFECTS
412  // DR 2285. make_reverse_iterator
413  /// Generator function for reverse_iterator.
414  template<typename _Iterator>
415  inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
416  make_reverse_iterator(_Iterator __i)
417  { return reverse_iterator<_Iterator>(__i); }
418 # endif
419 #endif
420 
421 #if __cplusplus >= 201103L
422  template<typename _Iterator>
423  auto
424  __niter_base(reverse_iterator<_Iterator> __it)
425  -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
426  { return __make_reverse_iterator(__niter_base(__it.base())); }
427 
428  template<typename _Iterator>
429  struct __is_move_iterator<reverse_iterator<_Iterator> >
430  : __is_move_iterator<_Iterator>
431  { };
432 
433  template<typename _Iterator>
434  auto
435  __miter_base(reverse_iterator<_Iterator> __it)
436  -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
437  { return __make_reverse_iterator(__miter_base(__it.base())); }
438 #endif
439 
440  // 24.4.2.2.1 back_insert_iterator
441  /**
442  * @brief Turns assignment into insertion.
443  *
444  * These are output iterators, constructed from a container-of-T.
445  * Assigning a T to the iterator appends it to the container using
446  * push_back.
447  *
448  * Tip: Using the back_inserter function to create these iterators can
449  * save typing.
450  */
451  template<typename _Container>
453  : public iterator<output_iterator_tag, void, void, void, void>
454  {
455  protected:
456  _Container* container;
457 
458  public:
459  /// A nested typedef for the type of whatever container you used.
460  typedef _Container container_type;
461 
462  /// The only way to create this %iterator is with a container.
463  explicit
464  back_insert_iterator(_Container& __x)
465  : container(std::__addressof(__x)) { }
466 
467  /**
468  * @param __value An instance of whatever type
469  * container_type::const_reference is; presumably a
470  * reference-to-const T for container<T>.
471  * @return This %iterator, for chained operations.
472  *
473  * This kind of %iterator doesn't really have a @a position in the
474  * container (you can think of the position as being permanently at
475  * the end, if you like). Assigning a value to the %iterator will
476  * always append the value to the end of the container.
477  */
478 #if __cplusplus < 201103L
480  operator=(typename _Container::const_reference __value)
481  {
482  container->push_back(__value);
483  return *this;
484  }
485 #else
487  operator=(const typename _Container::value_type& __value)
488  {
489  container->push_back(__value);
490  return *this;
491  }
492 
494  operator=(typename _Container::value_type&& __value)
495  {
496  container->push_back(std::move(__value));
497  return *this;
498  }
499 #endif
500 
501  /// Simply returns *this.
504  { return *this; }
505 
506  /// Simply returns *this. (This %iterator does not @a move.)
509  { return *this; }
510 
511  /// Simply returns *this. (This %iterator does not @a move.)
514  { return *this; }
515  };
516 
517  /**
518  * @param __x A container of arbitrary type.
519  * @return An instance of back_insert_iterator working on @p __x.
520  *
521  * This wrapper function helps in creating back_insert_iterator instances.
522  * Typing the name of the %iterator requires knowing the precise full
523  * type of the container, which can be tedious and impedes generic
524  * programming. Using this function lets you take advantage of automatic
525  * template parameter deduction, making the compiler match the correct
526  * types for you.
527  */
528  template<typename _Container>
529  inline back_insert_iterator<_Container>
530  back_inserter(_Container& __x)
531  { return back_insert_iterator<_Container>(__x); }
532 
533  /**
534  * @brief Turns assignment into insertion.
535  *
536  * These are output iterators, constructed from a container-of-T.
537  * Assigning a T to the iterator prepends it to the container using
538  * push_front.
539  *
540  * Tip: Using the front_inserter function to create these iterators can
541  * save typing.
542  */
543  template<typename _Container>
545  : public iterator<output_iterator_tag, void, void, void, void>
546  {
547  protected:
548  _Container* container;
549 
550  public:
551  /// A nested typedef for the type of whatever container you used.
552  typedef _Container container_type;
553 
554  /// The only way to create this %iterator is with a container.
555  explicit front_insert_iterator(_Container& __x)
556  : container(std::__addressof(__x)) { }
557 
558  /**
559  * @param __value An instance of whatever type
560  * container_type::const_reference is; presumably a
561  * reference-to-const T for container<T>.
562  * @return This %iterator, for chained operations.
563  *
564  * This kind of %iterator doesn't really have a @a position in the
565  * container (you can think of the position as being permanently at
566  * the front, if you like). Assigning a value to the %iterator will
567  * always prepend the value to the front of the container.
568  */
569 #if __cplusplus < 201103L
571  operator=(typename _Container::const_reference __value)
572  {
573  container->push_front(__value);
574  return *this;
575  }
576 #else
578  operator=(const typename _Container::value_type& __value)
579  {
580  container->push_front(__value);
581  return *this;
582  }
583 
585  operator=(typename _Container::value_type&& __value)
586  {
587  container->push_front(std::move(__value));
588  return *this;
589  }
590 #endif
591 
592  /// Simply returns *this.
595  { return *this; }
596 
597  /// Simply returns *this. (This %iterator does not @a move.)
600  { return *this; }
601 
602  /// Simply returns *this. (This %iterator does not @a move.)
605  { return *this; }
606  };
607 
608  /**
609  * @param __x A container of arbitrary type.
610  * @return An instance of front_insert_iterator working on @p x.
611  *
612  * This wrapper function helps in creating front_insert_iterator instances.
613  * Typing the name of the %iterator requires knowing the precise full
614  * type of the container, which can be tedious and impedes generic
615  * programming. Using this function lets you take advantage of automatic
616  * template parameter deduction, making the compiler match the correct
617  * types for you.
618  */
619  template<typename _Container>
620  inline front_insert_iterator<_Container>
621  front_inserter(_Container& __x)
622  { return front_insert_iterator<_Container>(__x); }
623 
624  /**
625  * @brief Turns assignment into insertion.
626  *
627  * These are output iterators, constructed from a container-of-T.
628  * Assigning a T to the iterator inserts it in the container at the
629  * %iterator's position, rather than overwriting the value at that
630  * position.
631  *
632  * (Sequences will actually insert a @e copy of the value before the
633  * %iterator's position.)
634  *
635  * Tip: Using the inserter function to create these iterators can
636  * save typing.
637  */
638  template<typename _Container>
640  : public iterator<output_iterator_tag, void, void, void, void>
641  {
642  protected:
643  _Container* container;
644  typename _Container::iterator iter;
645 
646  public:
647  /// A nested typedef for the type of whatever container you used.
648  typedef _Container container_type;
649 
650  /**
651  * The only way to create this %iterator is with a container and an
652  * initial position (a normal %iterator into the container).
653  */
654  insert_iterator(_Container& __x, typename _Container::iterator __i)
655  : container(std::__addressof(__x)), iter(__i) {}
656 
657  /**
658  * @param __value An instance of whatever type
659  * container_type::const_reference is; presumably a
660  * reference-to-const T for container<T>.
661  * @return This %iterator, for chained operations.
662  *
663  * This kind of %iterator maintains its own position in the
664  * container. Assigning a value to the %iterator will insert the
665  * value into the container at the place before the %iterator.
666  *
667  * The position is maintained such that subsequent assignments will
668  * insert values immediately after one another. For example,
669  * @code
670  * // vector v contains A and Z
671  *
672  * insert_iterator i (v, ++v.begin());
673  * i = 1;
674  * i = 2;
675  * i = 3;
676  *
677  * // vector v contains A, 1, 2, 3, and Z
678  * @endcode
679  */
680 #if __cplusplus < 201103L
682  operator=(typename _Container::const_reference __value)
683  {
684  iter = container->insert(iter, __value);
685  ++iter;
686  return *this;
687  }
688 #else
690  operator=(const typename _Container::value_type& __value)
691  {
692  iter = container->insert(iter, __value);
693  ++iter;
694  return *this;
695  }
696 
698  operator=(typename _Container::value_type&& __value)
699  {
700  iter = container->insert(iter, std::move(__value));
701  ++iter;
702  return *this;
703  }
704 #endif
705 
706  /// Simply returns *this.
709  { return *this; }
710 
711  /// Simply returns *this. (This %iterator does not @a move.)
714  { return *this; }
715 
716  /// Simply returns *this. (This %iterator does not @a move.)
719  { return *this; }
720  };
721 
722  /**
723  * @param __x A container of arbitrary type.
724  * @param __i An iterator into the container.
725  * @return An instance of insert_iterator working on @p __x.
726  *
727  * This wrapper function helps in creating insert_iterator instances.
728  * Typing the name of the %iterator requires knowing the precise full
729  * type of the container, which can be tedious and impedes generic
730  * programming. Using this function lets you take advantage of automatic
731  * template parameter deduction, making the compiler match the correct
732  * types for you.
733  */
734  template<typename _Container, typename _Iterator>
735  inline insert_iterator<_Container>
736  inserter(_Container& __x, _Iterator __i)
737  {
738  return insert_iterator<_Container>(__x,
739  typename _Container::iterator(__i));
740  }
741 
742  // @} group iterators
743 
744 _GLIBCXX_END_NAMESPACE_VERSION
745 } // namespace
746 
747 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
748 {
749 _GLIBCXX_BEGIN_NAMESPACE_VERSION
750 
751  // This iterator adapter is @a normal in the sense that it does not
752  // change the semantics of any of the operators of its iterator
753  // parameter. Its primary purpose is to convert an iterator that is
754  // not a class, e.g. a pointer, into an iterator that is a class.
755  // The _Container parameter exists solely so that different containers
756  // using this template can instantiate different types, even if the
757  // _Iterator parameter is the same.
758  using std::iterator_traits;
759  using std::iterator;
760  template<typename _Iterator, typename _Container>
761  class __normal_iterator
762  {
763  protected:
764  _Iterator _M_current;
765 
766  typedef iterator_traits<_Iterator> __traits_type;
767 
768  public:
769  typedef _Iterator iterator_type;
770  typedef typename __traits_type::iterator_category iterator_category;
771  typedef typename __traits_type::value_type value_type;
772  typedef typename __traits_type::difference_type difference_type;
773  typedef typename __traits_type::reference reference;
774  typedef typename __traits_type::pointer pointer;
775 
776  _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
777  : _M_current(_Iterator()) { }
778 
779  explicit
780  __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
781  : _M_current(__i) { }
782 
783  // Allow iterator to const_iterator conversion
784  template<typename _Iter>
785  __normal_iterator(const __normal_iterator<_Iter,
786  typename __enable_if<
787  (std::__are_same<_Iter, typename _Container::pointer>::__value),
788  _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
789  : _M_current(__i.base()) { }
790 
791  // Forward iterator requirements
792  reference
793  operator*() const _GLIBCXX_NOEXCEPT
794  { return *_M_current; }
795 
796  pointer
797  operator->() const _GLIBCXX_NOEXCEPT
798  { return _M_current; }
799 
800  __normal_iterator&
801  operator++() _GLIBCXX_NOEXCEPT
802  {
803  ++_M_current;
804  return *this;
805  }
806 
807  __normal_iterator
808  operator++(int) _GLIBCXX_NOEXCEPT
809  { return __normal_iterator(_M_current++); }
810 
811  // Bidirectional iterator requirements
812  __normal_iterator&
813  operator--() _GLIBCXX_NOEXCEPT
814  {
815  --_M_current;
816  return *this;
817  }
818 
819  __normal_iterator
820  operator--(int) _GLIBCXX_NOEXCEPT
821  { return __normal_iterator(_M_current--); }
822 
823  // Random access iterator requirements
824  reference
825  operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
826  { return _M_current[__n]; }
827 
828  __normal_iterator&
829  operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
830  { _M_current += __n; return *this; }
831 
832  __normal_iterator
833  operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
834  { return __normal_iterator(_M_current + __n); }
835 
836  __normal_iterator&
837  operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
838  { _M_current -= __n; return *this; }
839 
840  __normal_iterator
841  operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
842  { return __normal_iterator(_M_current - __n); }
843 
844  const _Iterator&
845  base() const _GLIBCXX_NOEXCEPT
846  { return _M_current; }
847  };
848 
849  // Note: In what follows, the left- and right-hand-side iterators are
850  // allowed to vary in types (conceptually in cv-qualification) so that
851  // comparison between cv-qualified and non-cv-qualified iterators be
852  // valid. However, the greedy and unfriendly operators in std::rel_ops
853  // will make overload resolution ambiguous (when in scope) if we don't
854  // provide overloads whose operands are of the same type. Can someone
855  // remind me what generic programming is about? -- Gaby
856 
857  // Forward iterator requirements
858  template<typename _IteratorL, typename _IteratorR, typename _Container>
859  inline bool
860  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
861  const __normal_iterator<_IteratorR, _Container>& __rhs)
862  _GLIBCXX_NOEXCEPT
863  { return __lhs.base() == __rhs.base(); }
864 
865  template<typename _Iterator, typename _Container>
866  inline bool
867  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
868  const __normal_iterator<_Iterator, _Container>& __rhs)
869  _GLIBCXX_NOEXCEPT
870  { return __lhs.base() == __rhs.base(); }
871 
872  template<typename _IteratorL, typename _IteratorR, typename _Container>
873  inline bool
874  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
875  const __normal_iterator<_IteratorR, _Container>& __rhs)
876  _GLIBCXX_NOEXCEPT
877  { return __lhs.base() != __rhs.base(); }
878 
879  template<typename _Iterator, typename _Container>
880  inline bool
881  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
882  const __normal_iterator<_Iterator, _Container>& __rhs)
883  _GLIBCXX_NOEXCEPT
884  { return __lhs.base() != __rhs.base(); }
885 
886  // Random access iterator requirements
887  template<typename _IteratorL, typename _IteratorR, typename _Container>
888  inline bool
889  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
890  const __normal_iterator<_IteratorR, _Container>& __rhs)
891  _GLIBCXX_NOEXCEPT
892  { return __lhs.base() < __rhs.base(); }
893 
894  template<typename _Iterator, typename _Container>
895  inline bool
896  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
897  const __normal_iterator<_Iterator, _Container>& __rhs)
898  _GLIBCXX_NOEXCEPT
899  { return __lhs.base() < __rhs.base(); }
900 
901  template<typename _IteratorL, typename _IteratorR, typename _Container>
902  inline bool
903  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
904  const __normal_iterator<_IteratorR, _Container>& __rhs)
905  _GLIBCXX_NOEXCEPT
906  { return __lhs.base() > __rhs.base(); }
907 
908  template<typename _Iterator, typename _Container>
909  inline bool
910  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
911  const __normal_iterator<_Iterator, _Container>& __rhs)
912  _GLIBCXX_NOEXCEPT
913  { return __lhs.base() > __rhs.base(); }
914 
915  template<typename _IteratorL, typename _IteratorR, typename _Container>
916  inline bool
917  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
918  const __normal_iterator<_IteratorR, _Container>& __rhs)
919  _GLIBCXX_NOEXCEPT
920  { return __lhs.base() <= __rhs.base(); }
921 
922  template<typename _Iterator, typename _Container>
923  inline bool
924  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
925  const __normal_iterator<_Iterator, _Container>& __rhs)
926  _GLIBCXX_NOEXCEPT
927  { return __lhs.base() <= __rhs.base(); }
928 
929  template<typename _IteratorL, typename _IteratorR, typename _Container>
930  inline bool
931  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
932  const __normal_iterator<_IteratorR, _Container>& __rhs)
933  _GLIBCXX_NOEXCEPT
934  { return __lhs.base() >= __rhs.base(); }
935 
936  template<typename _Iterator, typename _Container>
937  inline bool
938  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
939  const __normal_iterator<_Iterator, _Container>& __rhs)
940  _GLIBCXX_NOEXCEPT
941  { return __lhs.base() >= __rhs.base(); }
942 
943  // _GLIBCXX_RESOLVE_LIB_DEFECTS
944  // According to the resolution of DR179 not only the various comparison
945  // operators but also operator- must accept mixed iterator/const_iterator
946  // parameters.
947  template<typename _IteratorL, typename _IteratorR, typename _Container>
948 #if __cplusplus >= 201103L
949  // DR 685.
950  inline auto
951  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
952  const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
953  -> decltype(__lhs.base() - __rhs.base())
954 #else
955  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
956  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
957  const __normal_iterator<_IteratorR, _Container>& __rhs)
958 #endif
959  { return __lhs.base() - __rhs.base(); }
960 
961  template<typename _Iterator, typename _Container>
962  inline typename __normal_iterator<_Iterator, _Container>::difference_type
963  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
964  const __normal_iterator<_Iterator, _Container>& __rhs)
965  _GLIBCXX_NOEXCEPT
966  { return __lhs.base() - __rhs.base(); }
967 
968  template<typename _Iterator, typename _Container>
969  inline __normal_iterator<_Iterator, _Container>
970  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
971  __n, const __normal_iterator<_Iterator, _Container>& __i)
972  _GLIBCXX_NOEXCEPT
973  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
974 
975 _GLIBCXX_END_NAMESPACE_VERSION
976 } // namespace
977 
978 namespace std _GLIBCXX_VISIBILITY(default)
979 {
980 _GLIBCXX_BEGIN_NAMESPACE_VERSION
981 
982  template<typename _Iterator, typename _Container>
983  _Iterator
984  __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
985  { return __it.base(); }
986 
987 #if __cplusplus >= 201103L
988 
989  /**
990  * @addtogroup iterators
991  * @{
992  */
993 
994  // 24.4.3 Move iterators
995  /**
996  * Class template move_iterator is an iterator adapter with the same
997  * behavior as the underlying iterator except that its dereference
998  * operator implicitly converts the value returned by the underlying
999  * iterator's dereference operator to an rvalue reference. Some
1000  * generic algorithms can be called with move iterators to replace
1001  * copying with moving.
1002  */
1003  template<typename _Iterator>
1005  {
1006  protected:
1007  _Iterator _M_current;
1008 
1009  typedef iterator_traits<_Iterator> __traits_type;
1010  typedef typename __traits_type::reference __base_ref;
1011 
1012  public:
1013  typedef _Iterator iterator_type;
1014  typedef typename __traits_type::iterator_category iterator_category;
1015  typedef typename __traits_type::value_type value_type;
1016  typedef typename __traits_type::difference_type difference_type;
1017  // NB: DR 680.
1018  typedef _Iterator pointer;
1019  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1020  // 2106. move_iterator wrapping iterators returning prvalues
1022  typename remove_reference<__base_ref>::type&&,
1023  __base_ref>::type reference;
1024 
1025  _GLIBCXX17_CONSTEXPR
1026  move_iterator()
1027  : _M_current() { }
1028 
1029  explicit _GLIBCXX17_CONSTEXPR
1030  move_iterator(iterator_type __i)
1031  : _M_current(__i) { }
1032 
1033  template<typename _Iter>
1034  _GLIBCXX17_CONSTEXPR
1036  : _M_current(__i.base()) { }
1037 
1038  _GLIBCXX17_CONSTEXPR iterator_type
1039  base() const
1040  { return _M_current; }
1041 
1042  _GLIBCXX17_CONSTEXPR reference
1043  operator*() const
1044  { return static_cast<reference>(*_M_current); }
1045 
1046  _GLIBCXX17_CONSTEXPR pointer
1047  operator->() const
1048  { return _M_current; }
1049 
1050  _GLIBCXX17_CONSTEXPR move_iterator&
1051  operator++()
1052  {
1053  ++_M_current;
1054  return *this;
1055  }
1056 
1057  _GLIBCXX17_CONSTEXPR move_iterator
1058  operator++(int)
1059  {
1060  move_iterator __tmp = *this;
1061  ++_M_current;
1062  return __tmp;
1063  }
1064 
1065  _GLIBCXX17_CONSTEXPR move_iterator&
1066  operator--()
1067  {
1068  --_M_current;
1069  return *this;
1070  }
1071 
1072  _GLIBCXX17_CONSTEXPR move_iterator
1073  operator--(int)
1074  {
1075  move_iterator __tmp = *this;
1076  --_M_current;
1077  return __tmp;
1078  }
1079 
1080  _GLIBCXX17_CONSTEXPR move_iterator
1081  operator+(difference_type __n) const
1082  { return move_iterator(_M_current + __n); }
1083 
1084  _GLIBCXX17_CONSTEXPR move_iterator&
1085  operator+=(difference_type __n)
1086  {
1087  _M_current += __n;
1088  return *this;
1089  }
1090 
1091  _GLIBCXX17_CONSTEXPR move_iterator
1092  operator-(difference_type __n) const
1093  { return move_iterator(_M_current - __n); }
1094 
1095  _GLIBCXX17_CONSTEXPR move_iterator&
1096  operator-=(difference_type __n)
1097  {
1098  _M_current -= __n;
1099  return *this;
1100  }
1101 
1102  _GLIBCXX17_CONSTEXPR reference
1103  operator[](difference_type __n) const
1104  { return std::move(_M_current[__n]); }
1105  };
1106 
1107  // Note: See __normal_iterator operators note from Gaby to understand
1108  // why there are always 2 versions for most of the move_iterator
1109  // operators.
1110  template<typename _IteratorL, typename _IteratorR>
1111  inline _GLIBCXX17_CONSTEXPR bool
1112  operator==(const move_iterator<_IteratorL>& __x,
1113  const move_iterator<_IteratorR>& __y)
1114  { return __x.base() == __y.base(); }
1115 
1116  template<typename _Iterator>
1117  inline _GLIBCXX17_CONSTEXPR bool
1118  operator==(const move_iterator<_Iterator>& __x,
1119  const move_iterator<_Iterator>& __y)
1120  { return __x.base() == __y.base(); }
1121 
1122  template<typename _IteratorL, typename _IteratorR>
1123  inline _GLIBCXX17_CONSTEXPR bool
1124  operator!=(const move_iterator<_IteratorL>& __x,
1125  const move_iterator<_IteratorR>& __y)
1126  { return !(__x == __y); }
1127 
1128  template<typename _Iterator>
1129  inline _GLIBCXX17_CONSTEXPR bool
1130  operator!=(const move_iterator<_Iterator>& __x,
1131  const move_iterator<_Iterator>& __y)
1132  { return !(__x == __y); }
1133 
1134  template<typename _IteratorL, typename _IteratorR>
1135  inline _GLIBCXX17_CONSTEXPR bool
1136  operator<(const move_iterator<_IteratorL>& __x,
1137  const move_iterator<_IteratorR>& __y)
1138  { return __x.base() < __y.base(); }
1139 
1140  template<typename _Iterator>
1141  inline _GLIBCXX17_CONSTEXPR bool
1142  operator<(const move_iterator<_Iterator>& __x,
1143  const move_iterator<_Iterator>& __y)
1144  { return __x.base() < __y.base(); }
1145 
1146  template<typename _IteratorL, typename _IteratorR>
1147  inline _GLIBCXX17_CONSTEXPR bool
1148  operator<=(const move_iterator<_IteratorL>& __x,
1149  const move_iterator<_IteratorR>& __y)
1150  { return !(__y < __x); }
1151 
1152  template<typename _Iterator>
1153  inline _GLIBCXX17_CONSTEXPR bool
1154  operator<=(const move_iterator<_Iterator>& __x,
1155  const move_iterator<_Iterator>& __y)
1156  { return !(__y < __x); }
1157 
1158  template<typename _IteratorL, typename _IteratorR>
1159  inline _GLIBCXX17_CONSTEXPR bool
1160  operator>(const move_iterator<_IteratorL>& __x,
1161  const move_iterator<_IteratorR>& __y)
1162  { return __y < __x; }
1163 
1164  template<typename _Iterator>
1165  inline _GLIBCXX17_CONSTEXPR bool
1166  operator>(const move_iterator<_Iterator>& __x,
1167  const move_iterator<_Iterator>& __y)
1168  { return __y < __x; }
1169 
1170  template<typename _IteratorL, typename _IteratorR>
1171  inline _GLIBCXX17_CONSTEXPR bool
1172  operator>=(const move_iterator<_IteratorL>& __x,
1173  const move_iterator<_IteratorR>& __y)
1174  { return !(__x < __y); }
1175 
1176  template<typename _Iterator>
1177  inline _GLIBCXX17_CONSTEXPR bool
1178  operator>=(const move_iterator<_Iterator>& __x,
1179  const move_iterator<_Iterator>& __y)
1180  { return !(__x < __y); }
1181 
1182  // DR 685.
1183  template<typename _IteratorL, typename _IteratorR>
1184  inline _GLIBCXX17_CONSTEXPR auto
1185  operator-(const move_iterator<_IteratorL>& __x,
1186  const move_iterator<_IteratorR>& __y)
1187  -> decltype(__x.base() - __y.base())
1188  { return __x.base() - __y.base(); }
1189 
1190  template<typename _Iterator>
1191  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1192  operator+(typename move_iterator<_Iterator>::difference_type __n,
1193  const move_iterator<_Iterator>& __x)
1194  { return __x + __n; }
1195 
1196  template<typename _Iterator>
1197  inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1198  make_move_iterator(_Iterator __i)
1199  { return move_iterator<_Iterator>(__i); }
1200 
1201  template<typename _Iterator, typename _ReturnType
1202  = typename conditional<__move_if_noexcept_cond
1203  <typename iterator_traits<_Iterator>::value_type>::value,
1204  _Iterator, move_iterator<_Iterator>>::type>
1205  inline _GLIBCXX17_CONSTEXPR _ReturnType
1206  __make_move_if_noexcept_iterator(_Iterator __i)
1207  { return _ReturnType(__i); }
1208 
1209  // Overload for pointers that matches std::move_if_noexcept more closely,
1210  // returning a constant iterator when we don't want to move.
1211  template<typename _Tp, typename _ReturnType
1212  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1213  const _Tp*, move_iterator<_Tp*>>::type>
1214  inline _GLIBCXX17_CONSTEXPR _ReturnType
1215  __make_move_if_noexcept_iterator(_Tp* __i)
1216  { return _ReturnType(__i); }
1217 
1218  // @} group iterators
1219 
1220  template<typename _Iterator>
1221  auto
1222  __niter_base(move_iterator<_Iterator> __it)
1223  -> decltype(make_move_iterator(__niter_base(__it.base())))
1224  { return make_move_iterator(__niter_base(__it.base())); }
1225 
1226  template<typename _Iterator>
1227  struct __is_move_iterator<move_iterator<_Iterator> >
1228  {
1229  enum { __value = 1 };
1230  typedef __true_type __type;
1231  };
1232 
1233  template<typename _Iterator>
1234  auto
1235  __miter_base(move_iterator<_Iterator> __it)
1236  -> decltype(__miter_base(__it.base()))
1237  { return __miter_base(__it.base()); }
1238 
1239 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1240 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1241  std::__make_move_if_noexcept_iterator(_Iter)
1242 #else
1243 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1244 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1245 #endif // C++11
1246 
1247 #if __cpp_deduction_guides >= 201606
1248  // These helper traits are used for deduction guides
1249  // of associative containers.
1250  template<typename _InputIterator>
1251  using __iter_key_t = remove_const_t<
1252  typename iterator_traits<_InputIterator>::value_type::first_type>;
1253 
1254  template<typename _InputIterator>
1255  using __iter_val_t =
1256  typename iterator_traits<_InputIterator>::value_type::second_type;
1257 
1258  template<typename _T1, typename _T2>
1259  struct pair;
1260 
1261  template<typename _InputIterator>
1262  using __iter_to_alloc_t =
1263  pair<add_const_t<__iter_key_t<_InputIterator>>,
1264  __iter_val_t<_InputIterator>>;
1265 
1266 #endif
1267 
1268 _GLIBCXX_END_NAMESPACE_VERSION
1269 } // namespace
1270 
1271 #ifdef _GLIBCXX_DEBUG
1272 # include <debug/stl_iterator.h>
1273 #endif
1274 
1275 #endif
insert_iterator(_Container &__x, typename _Container::iterator __i)
_GLIBCXX17_CONSTEXPR reference operator*() const
_GLIBCXX17_CONSTEXPR reverse_iterator(iterator_type __x)
front_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
Define a member typedef type to one of two argument types.
Definition: type_traits:104
_Container container_type
A nested typedef for the type of whatever container you used.
_GLIBCXX17_CONSTEXPR reverse_iterator(const reverse_iterator &__x)
complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition: complex:356
_Container container_type
A nested typedef for the type of whatever container you used.
GNU extensions for public use.
_GLIBCXX17_CONSTEXPR pointer operator->() const
insert_iterator< _Container > inserter(_Container &__x, _Iterator __i)
front_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
_GLIBCXX17_CONSTEXPR reference operator[](difference_type __n) const
_Container container_type
A nested typedef for the type of whatever container you used.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:326
Turns assignment into insertion.
_GLIBCXX17_CONSTEXPR reverse_iterator operator-(difference_type __n) const
back_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
_GLIBCXX17_CONSTEXPR reverse_iterator & operator+=(difference_type __n)
_GLIBCXX17_CONSTEXPR reverse_iterator & operator--()
front_insert_iterator< _Container > front_inserter(_Container &__x)
back_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
ISO C++ entities toplevel namespace is std.
back_insert_iterator< _Container > back_inserter(_Container &__x)
_GLIBCXX17_CONSTEXPR reverse_iterator(const reverse_iterator< _Iter > &__x)
_GLIBCXX17_CONSTEXPR reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
_GLIBCXX17_CONSTEXPR reverse_iterator operator--(int)
_GLIBCXX17_CONSTEXPR reverse_iterator operator+(difference_type __n) const
_GLIBCXX17_CONSTEXPR reverse_iterator & operator-=(difference_type __n)
insert_iterator & operator*()
Simply returns *this.
_GLIBCXX17_CONSTEXPR iterator_type base() const
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
insert_iterator & operator=(const typename _Container::value_type &__value)
Turns assignment into insertion.
typename remove_const< _Tp >::type remove_const_t
Alias template for remove_const.
Definition: type_traits:1437
_GLIBCXX17_CONSTEXPR reverse_iterator operator++(int)
back_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
_GLIBCXX17_CONSTEXPR reverse_iterator()
Turns assignment into insertion.
back_insert_iterator & operator*()
Simply returns *this.
_GLIBCXX17_CONSTEXPR reverse_iterator & operator++()
front_insert_iterator & operator=(const typename _Container::value_type &__value)
Common iterator class.
back_insert_iterator & operator=(const typename _Container::value_type &__value)
front_insert_iterator & operator*()
Simply returns *this.
front_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
insert_iterator & operator++(int)
Simply returns *this. (This iterator does not move.)