libstdc++
bits/stl_iterator.h
Go to the documentation of this file.
1 // Iterators -*- C++ -*-
2 
3 // Copyright (C) 2001-2016 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 namespace std _GLIBCXX_VISIBILITY(default)
69 {
70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
71 
72  /**
73  * @addtogroup iterators
74  * @{
75  */
76 
77  // 24.4.1 Reverse iterators
78  /**
79  * Bidirectional and random access iterators have corresponding reverse
80  * %iterator adaptors that iterate through the data structure in the
81  * opposite direction. They have the same signatures as the corresponding
82  * iterators. The fundamental relation between a reverse %iterator and its
83  * corresponding %iterator @c i is established by the identity:
84  * @code
85  * &*(reverse_iterator(i)) == &*(i - 1)
86  * @endcode
87  *
88  * <em>This mapping is dictated by the fact that while there is always a
89  * pointer past the end of an array, there might not be a valid pointer
90  * before the beginning of an array.</em> [24.4.1]/1,2
91  *
92  * Reverse iterators can be tricky and surprising at first. Their
93  * semantics make sense, however, and the trickiness is a side effect of
94  * the requirement that the iterators must be safe.
95  */
96  template<typename _Iterator>
98  : public iterator<typename iterator_traits<_Iterator>::iterator_category,
99  typename iterator_traits<_Iterator>::value_type,
100  typename iterator_traits<_Iterator>::difference_type,
101  typename iterator_traits<_Iterator>::pointer,
102  typename iterator_traits<_Iterator>::reference>
103  {
104  protected:
105  _Iterator current;
106 
107  typedef iterator_traits<_Iterator> __traits_type;
108 
109  public:
110  typedef _Iterator iterator_type;
111  typedef typename __traits_type::difference_type difference_type;
112  typedef typename __traits_type::pointer pointer;
113  typedef typename __traits_type::reference reference;
114 
115  /**
116  * The default constructor value-initializes member @p current.
117  * If it is a pointer, that means it is zero-initialized.
118  */
119  // _GLIBCXX_RESOLVE_LIB_DEFECTS
120  // 235 No specification of default ctor for reverse_iterator
121  // 1012. reverse_iterator default ctor should value initialize
122  reverse_iterator() : current() { }
123 
124  /**
125  * This %iterator will move in the opposite direction that @p x does.
126  */
127  explicit
128  reverse_iterator(iterator_type __x) : current(__x) { }
129 
130  /**
131  * The copy constructor is normal.
132  */
134  : current(__x.current) { }
135 
136  /**
137  * A %reverse_iterator across other types can be copied if the
138  * underlying %iterator can be converted to the type of @c current.
139  */
140  template<typename _Iter>
142  : current(__x.base()) { }
143 
144  /**
145  * @return @c current, the %iterator used for underlying work.
146  */
147  iterator_type
148  base() const
149  { return current; }
150 
151  /**
152  * @return A reference to the value at @c --current
153  *
154  * This requires that @c --current is dereferenceable.
155  *
156  * @warning This implementation requires that for an iterator of the
157  * underlying iterator type, @c x, a reference obtained by
158  * @c *x remains valid after @c x has been modified or
159  * destroyed. This is a bug: http://gcc.gnu.org/PR51823
160  */
161  reference
162  operator*() const
163  {
164  _Iterator __tmp = current;
165  return *--__tmp;
166  }
167 
168  /**
169  * @return A pointer to the value at @c --current
170  *
171  * This requires that @c --current is dereferenceable.
172  */
173  // _GLIBCXX_RESOLVE_LIB_DEFECTS
174  // 2188. Reverse iterator does not fully support targets that overload &
175  pointer
176  operator->() const
177  { return std::__addressof(operator*()); }
178 
179  /**
180  * @return @c *this
181  *
182  * Decrements the underlying iterator.
183  */
186  {
187  --current;
188  return *this;
189  }
190 
191  /**
192  * @return The original value of @c *this
193  *
194  * Decrements the underlying iterator.
195  */
198  {
199  reverse_iterator __tmp = *this;
200  --current;
201  return __tmp;
202  }
203 
204  /**
205  * @return @c *this
206  *
207  * Increments the underlying iterator.
208  */
211  {
212  ++current;
213  return *this;
214  }
215 
216  /**
217  * @return A reverse_iterator with the previous value of @c *this
218  *
219  * Increments the underlying iterator.
220  */
223  {
224  reverse_iterator __tmp = *this;
225  ++current;
226  return __tmp;
227  }
228 
229  /**
230  * @return A reverse_iterator that refers to @c current - @a __n
231  *
232  * The underlying iterator must be a Random Access Iterator.
233  */
235  operator+(difference_type __n) const
236  { return reverse_iterator(current - __n); }
237 
238  /**
239  * @return *this
240  *
241  * Moves the underlying iterator backwards @a __n steps.
242  * The underlying iterator must be a Random Access Iterator.
243  */
245  operator+=(difference_type __n)
246  {
247  current -= __n;
248  return *this;
249  }
250 
251  /**
252  * @return A reverse_iterator that refers to @c current - @a __n
253  *
254  * The underlying iterator must be a Random Access Iterator.
255  */
257  operator-(difference_type __n) const
258  { return reverse_iterator(current + __n); }
259 
260  /**
261  * @return *this
262  *
263  * Moves the underlying iterator forwards @a __n steps.
264  * The underlying iterator must be a Random Access Iterator.
265  */
267  operator-=(difference_type __n)
268  {
269  current += __n;
270  return *this;
271  }
272 
273  /**
274  * @return The value at @c current - @a __n - 1
275  *
276  * The underlying iterator must be a Random Access Iterator.
277  */
278  reference
279  operator[](difference_type __n) const
280  { return *(*this + __n); }
281  };
282 
283  //@{
284  /**
285  * @param __x A %reverse_iterator.
286  * @param __y A %reverse_iterator.
287  * @return A simple bool.
288  *
289  * Reverse iterators forward many operations to their underlying base()
290  * iterators. Others are implemented in terms of one another.
291  *
292  */
293  template<typename _Iterator>
294  inline bool
295  operator==(const reverse_iterator<_Iterator>& __x,
296  const reverse_iterator<_Iterator>& __y)
297  { return __x.base() == __y.base(); }
298 
299  template<typename _Iterator>
300  inline bool
301  operator<(const reverse_iterator<_Iterator>& __x,
302  const reverse_iterator<_Iterator>& __y)
303  { return __y.base() < __x.base(); }
304 
305  template<typename _Iterator>
306  inline bool
307  operator!=(const reverse_iterator<_Iterator>& __x,
308  const reverse_iterator<_Iterator>& __y)
309  { return !(__x == __y); }
310 
311  template<typename _Iterator>
312  inline bool
313  operator>(const reverse_iterator<_Iterator>& __x,
314  const reverse_iterator<_Iterator>& __y)
315  { return __y < __x; }
316 
317  template<typename _Iterator>
318  inline bool
319  operator<=(const reverse_iterator<_Iterator>& __x,
320  const reverse_iterator<_Iterator>& __y)
321  { return !(__y < __x); }
322 
323  template<typename _Iterator>
324  inline bool
325  operator>=(const reverse_iterator<_Iterator>& __x,
326  const reverse_iterator<_Iterator>& __y)
327  { return !(__x < __y); }
328 
329  template<typename _Iterator>
330 #if __cplusplus < 201103L
331  inline typename reverse_iterator<_Iterator>::difference_type
333  const reverse_iterator<_Iterator>& __y)
334 #else
335  inline auto
337  const reverse_iterator<_Iterator>& __y)
338  -> decltype(__x.base() - __y.base())
339 #endif
340  { return __y.base() - __x.base(); }
341 
342  template<typename _Iterator>
344  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
345  const reverse_iterator<_Iterator>& __x)
346  { return reverse_iterator<_Iterator>(__x.base() - __n); }
347 
348  // _GLIBCXX_RESOLVE_LIB_DEFECTS
349  // DR 280. Comparison of reverse_iterator to const reverse_iterator.
350  template<typename _IteratorL, typename _IteratorR>
351  inline bool
352  operator==(const reverse_iterator<_IteratorL>& __x,
353  const reverse_iterator<_IteratorR>& __y)
354  { return __x.base() == __y.base(); }
355 
356  template<typename _IteratorL, typename _IteratorR>
357  inline bool
358  operator<(const reverse_iterator<_IteratorL>& __x,
359  const reverse_iterator<_IteratorR>& __y)
360  { return __y.base() < __x.base(); }
361 
362  template<typename _IteratorL, typename _IteratorR>
363  inline bool
364  operator!=(const reverse_iterator<_IteratorL>& __x,
365  const reverse_iterator<_IteratorR>& __y)
366  { return !(__x == __y); }
367 
368  template<typename _IteratorL, typename _IteratorR>
369  inline bool
370  operator>(const reverse_iterator<_IteratorL>& __x,
371  const reverse_iterator<_IteratorR>& __y)
372  { return __y < __x; }
373 
374  template<typename _IteratorL, typename _IteratorR>
375  inline bool
376  operator<=(const reverse_iterator<_IteratorL>& __x,
377  const reverse_iterator<_IteratorR>& __y)
378  { return !(__y < __x); }
379 
380  template<typename _IteratorL, typename _IteratorR>
381  inline bool
382  operator>=(const reverse_iterator<_IteratorL>& __x,
383  const reverse_iterator<_IteratorR>& __y)
384  { return !(__x < __y); }
385 
386  template<typename _IteratorL, typename _IteratorR>
387 #if __cplusplus >= 201103L
388  // DR 685.
389  inline auto
391  const reverse_iterator<_IteratorR>& __y)
392  -> decltype(__y.base() - __x.base())
393 #else
394  inline typename reverse_iterator<_IteratorL>::difference_type
395  operator-(const reverse_iterator<_IteratorL>& __x,
396  const reverse_iterator<_IteratorR>& __y)
397 #endif
398  { return __y.base() - __x.base(); }
399  //@}
400 
401 #if __cplusplus >= 201103L
402  // Same as C++14 make_reverse_iterator but used in C++03 mode too.
403  template<typename _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>
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>
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>
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  * @return An instance of insert_iterator working on @p __x.
725  *
726  * This wrapper function helps in creating insert_iterator instances.
727  * Typing the name of the %iterator requires knowing the precise full
728  * type of the container, which can be tedious and impedes generic
729  * programming. Using this function lets you take advantage of automatic
730  * template parameter deduction, making the compiler match the correct
731  * types for you.
732  */
733  template<typename _Container, typename _Iterator>
735  inserter(_Container& __x, _Iterator __i)
736  {
737  return insert_iterator<_Container>(__x,
738  typename _Container::iterator(__i));
739  }
740 
741  // @} group iterators
742 
743 _GLIBCXX_END_NAMESPACE_VERSION
744 } // namespace
745 
746 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
747 {
748 _GLIBCXX_BEGIN_NAMESPACE_VERSION
749 
750  // This iterator adapter is @a normal in the sense that it does not
751  // change the semantics of any of the operators of its iterator
752  // parameter. Its primary purpose is to convert an iterator that is
753  // not a class, e.g. a pointer, into an iterator that is a class.
754  // The _Container parameter exists solely so that different containers
755  // using this template can instantiate different types, even if the
756  // _Iterator parameter is the same.
757  using std::iterator_traits;
758  using std::iterator;
759  template<typename _Iterator, typename _Container>
760  class __normal_iterator
761  {
762  protected:
763  _Iterator _M_current;
764 
765  typedef iterator_traits<_Iterator> __traits_type;
766 
767  public:
768  typedef _Iterator iterator_type;
769  typedef typename __traits_type::iterator_category iterator_category;
770  typedef typename __traits_type::value_type value_type;
771  typedef typename __traits_type::difference_type difference_type;
772  typedef typename __traits_type::reference reference;
773  typedef typename __traits_type::pointer pointer;
774 
775  _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
776  : _M_current(_Iterator()) { }
777 
778  explicit
779  __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
780  : _M_current(__i) { }
781 
782  // Allow iterator to const_iterator conversion
783  template<typename _Iter>
784  __normal_iterator(const __normal_iterator<_Iter,
785  typename __enable_if<
786  (std::__are_same<_Iter, typename _Container::pointer>::__value),
787  _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
788  : _M_current(__i.base()) { }
789 
790  // Forward iterator requirements
791  reference
792  operator*() const _GLIBCXX_NOEXCEPT
793  { return *_M_current; }
794 
795  pointer
796  operator->() const _GLIBCXX_NOEXCEPT
797  { return _M_current; }
798 
799  __normal_iterator&
800  operator++() _GLIBCXX_NOEXCEPT
801  {
802  ++_M_current;
803  return *this;
804  }
805 
806  __normal_iterator
807  operator++(int) _GLIBCXX_NOEXCEPT
808  { return __normal_iterator(_M_current++); }
809 
810  // Bidirectional iterator requirements
811  __normal_iterator&
812  operator--() _GLIBCXX_NOEXCEPT
813  {
814  --_M_current;
815  return *this;
816  }
817 
818  __normal_iterator
819  operator--(int) _GLIBCXX_NOEXCEPT
820  { return __normal_iterator(_M_current--); }
821 
822  // Random access iterator requirements
823  reference
824  operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
825  { return _M_current[__n]; }
826 
827  __normal_iterator&
828  operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
829  { _M_current += __n; return *this; }
830 
831  __normal_iterator
832  operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
833  { return __normal_iterator(_M_current + __n); }
834 
835  __normal_iterator&
836  operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
837  { _M_current -= __n; return *this; }
838 
839  __normal_iterator
840  operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
841  { return __normal_iterator(_M_current - __n); }
842 
843  const _Iterator&
844  base() const _GLIBCXX_NOEXCEPT
845  { return _M_current; }
846  };
847 
848  // Note: In what follows, the left- and right-hand-side iterators are
849  // allowed to vary in types (conceptually in cv-qualification) so that
850  // comparison between cv-qualified and non-cv-qualified iterators be
851  // valid. However, the greedy and unfriendly operators in std::rel_ops
852  // will make overload resolution ambiguous (when in scope) if we don't
853  // provide overloads whose operands are of the same type. Can someone
854  // remind me what generic programming is about? -- Gaby
855 
856  // Forward iterator requirements
857  template<typename _IteratorL, typename _IteratorR, typename _Container>
858  inline bool
859  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
860  const __normal_iterator<_IteratorR, _Container>& __rhs)
861  _GLIBCXX_NOEXCEPT
862  { return __lhs.base() == __rhs.base(); }
863 
864  template<typename _Iterator, typename _Container>
865  inline bool
866  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
867  const __normal_iterator<_Iterator, _Container>& __rhs)
868  _GLIBCXX_NOEXCEPT
869  { return __lhs.base() == __rhs.base(); }
870 
871  template<typename _IteratorL, typename _IteratorR, typename _Container>
872  inline bool
873  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
874  const __normal_iterator<_IteratorR, _Container>& __rhs)
875  _GLIBCXX_NOEXCEPT
876  { return __lhs.base() != __rhs.base(); }
877 
878  template<typename _Iterator, typename _Container>
879  inline bool
880  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
881  const __normal_iterator<_Iterator, _Container>& __rhs)
882  _GLIBCXX_NOEXCEPT
883  { return __lhs.base() != __rhs.base(); }
884 
885  // Random access iterator requirements
886  template<typename _IteratorL, typename _IteratorR, typename _Container>
887  inline bool
888  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
889  const __normal_iterator<_IteratorR, _Container>& __rhs)
890  _GLIBCXX_NOEXCEPT
891  { return __lhs.base() < __rhs.base(); }
892 
893  template<typename _Iterator, typename _Container>
894  inline bool
895  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
896  const __normal_iterator<_Iterator, _Container>& __rhs)
897  _GLIBCXX_NOEXCEPT
898  { return __lhs.base() < __rhs.base(); }
899 
900  template<typename _IteratorL, typename _IteratorR, typename _Container>
901  inline bool
902  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
903  const __normal_iterator<_IteratorR, _Container>& __rhs)
904  _GLIBCXX_NOEXCEPT
905  { return __lhs.base() > __rhs.base(); }
906 
907  template<typename _Iterator, typename _Container>
908  inline bool
909  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
910  const __normal_iterator<_Iterator, _Container>& __rhs)
911  _GLIBCXX_NOEXCEPT
912  { return __lhs.base() > __rhs.base(); }
913 
914  template<typename _IteratorL, typename _IteratorR, typename _Container>
915  inline bool
916  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
917  const __normal_iterator<_IteratorR, _Container>& __rhs)
918  _GLIBCXX_NOEXCEPT
919  { return __lhs.base() <= __rhs.base(); }
920 
921  template<typename _Iterator, typename _Container>
922  inline bool
923  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
924  const __normal_iterator<_Iterator, _Container>& __rhs)
925  _GLIBCXX_NOEXCEPT
926  { return __lhs.base() <= __rhs.base(); }
927 
928  template<typename _IteratorL, typename _IteratorR, typename _Container>
929  inline bool
930  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
931  const __normal_iterator<_IteratorR, _Container>& __rhs)
932  _GLIBCXX_NOEXCEPT
933  { return __lhs.base() >= __rhs.base(); }
934 
935  template<typename _Iterator, typename _Container>
936  inline bool
937  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
938  const __normal_iterator<_Iterator, _Container>& __rhs)
939  _GLIBCXX_NOEXCEPT
940  { return __lhs.base() >= __rhs.base(); }
941 
942  // _GLIBCXX_RESOLVE_LIB_DEFECTS
943  // According to the resolution of DR179 not only the various comparison
944  // operators but also operator- must accept mixed iterator/const_iterator
945  // parameters.
946  template<typename _IteratorL, typename _IteratorR, typename _Container>
947 #if __cplusplus >= 201103L
948  // DR 685.
949  inline auto
950  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
951  const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
952  -> decltype(__lhs.base() - __rhs.base())
953 #else
954  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
955  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
956  const __normal_iterator<_IteratorR, _Container>& __rhs)
957 #endif
958  { return __lhs.base() - __rhs.base(); }
959 
960  template<typename _Iterator, typename _Container>
961  inline typename __normal_iterator<_Iterator, _Container>::difference_type
962  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
963  const __normal_iterator<_Iterator, _Container>& __rhs)
964  _GLIBCXX_NOEXCEPT
965  { return __lhs.base() - __rhs.base(); }
966 
967  template<typename _Iterator, typename _Container>
968  inline __normal_iterator<_Iterator, _Container>
969  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
970  __n, const __normal_iterator<_Iterator, _Container>& __i)
971  _GLIBCXX_NOEXCEPT
972  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
973 
974 _GLIBCXX_END_NAMESPACE_VERSION
975 } // namespace
976 
977 namespace std _GLIBCXX_VISIBILITY(default)
978 {
979 _GLIBCXX_BEGIN_NAMESPACE_VERSION
980 
981  template<typename _Iterator, typename _Container>
982  _Iterator
983  __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
984  { return __it.base(); }
985 
986 _GLIBCXX_END_NAMESPACE_VERSION
987 } // namespace
988 
989 #if __cplusplus >= 201103L
990 
991 namespace std _GLIBCXX_VISIBILITY(default)
992 {
993 _GLIBCXX_BEGIN_NAMESPACE_VERSION
994 
995  /**
996  * @addtogroup iterators
997  * @{
998  */
999 
1000  // 24.4.3 Move iterators
1001  /**
1002  * Class template move_iterator is an iterator adapter with the same
1003  * behavior as the underlying iterator except that its dereference
1004  * operator implicitly converts the value returned by the underlying
1005  * iterator's dereference operator to an rvalue reference. Some
1006  * generic algorithms can be called with move iterators to replace
1007  * copying with moving.
1008  */
1009  template<typename _Iterator>
1011  {
1012  protected:
1013  _Iterator _M_current;
1014 
1015  typedef iterator_traits<_Iterator> __traits_type;
1016  typedef typename __traits_type::reference __base_ref;
1017 
1018  public:
1019  typedef _Iterator iterator_type;
1020  typedef typename __traits_type::iterator_category iterator_category;
1021  typedef typename __traits_type::value_type value_type;
1022  typedef typename __traits_type::difference_type difference_type;
1023  // NB: DR 680.
1024  typedef _Iterator pointer;
1025  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1026  // 2106. move_iterator wrapping iterators returning prvalues
1027  typedef typename conditional<is_reference<__base_ref>::value,
1028  typename remove_reference<__base_ref>::type&&,
1029  __base_ref>::type reference;
1030 
1031  move_iterator()
1032  : _M_current() { }
1033 
1034  explicit
1035  move_iterator(iterator_type __i)
1036  : _M_current(__i) { }
1037 
1038  template<typename _Iter>
1040  : _M_current(__i.base()) { }
1041 
1042  iterator_type
1043  base() const
1044  { return _M_current; }
1045 
1046  reference
1047  operator*() const
1048  { return static_cast<reference>(*_M_current); }
1049 
1050  pointer
1051  operator->() const
1052  { return _M_current; }
1053 
1054  move_iterator&
1055  operator++()
1056  {
1057  ++_M_current;
1058  return *this;
1059  }
1060 
1062  operator++(int)
1063  {
1064  move_iterator __tmp = *this;
1065  ++_M_current;
1066  return __tmp;
1067  }
1068 
1069  move_iterator&
1070  operator--()
1071  {
1072  --_M_current;
1073  return *this;
1074  }
1075 
1077  operator--(int)
1078  {
1079  move_iterator __tmp = *this;
1080  --_M_current;
1081  return __tmp;
1082  }
1083 
1085  operator+(difference_type __n) const
1086  { return move_iterator(_M_current + __n); }
1087 
1088  move_iterator&
1089  operator+=(difference_type __n)
1090  {
1091  _M_current += __n;
1092  return *this;
1093  }
1094 
1096  operator-(difference_type __n) const
1097  { return move_iterator(_M_current - __n); }
1098 
1099  move_iterator&
1100  operator-=(difference_type __n)
1101  {
1102  _M_current -= __n;
1103  return *this;
1104  }
1105 
1106  reference
1107  operator[](difference_type __n) const
1108  { return std::move(_M_current[__n]); }
1109  };
1110 
1111  // Note: See __normal_iterator operators note from Gaby to understand
1112  // why there are always 2 versions for most of the move_iterator
1113  // operators.
1114  template<typename _IteratorL, typename _IteratorR>
1115  inline bool
1116  operator==(const move_iterator<_IteratorL>& __x,
1117  const move_iterator<_IteratorR>& __y)
1118  { return __x.base() == __y.base(); }
1119 
1120  template<typename _Iterator>
1121  inline bool
1122  operator==(const move_iterator<_Iterator>& __x,
1123  const move_iterator<_Iterator>& __y)
1124  { return __x.base() == __y.base(); }
1125 
1126  template<typename _IteratorL, typename _IteratorR>
1127  inline bool
1128  operator!=(const move_iterator<_IteratorL>& __x,
1129  const move_iterator<_IteratorR>& __y)
1130  { return !(__x == __y); }
1131 
1132  template<typename _Iterator>
1133  inline bool
1134  operator!=(const move_iterator<_Iterator>& __x,
1135  const move_iterator<_Iterator>& __y)
1136  { return !(__x == __y); }
1137 
1138  template<typename _IteratorL, typename _IteratorR>
1139  inline bool
1140  operator<(const move_iterator<_IteratorL>& __x,
1141  const move_iterator<_IteratorR>& __y)
1142  { return __x.base() < __y.base(); }
1143 
1144  template<typename _Iterator>
1145  inline bool
1146  operator<(const move_iterator<_Iterator>& __x,
1147  const move_iterator<_Iterator>& __y)
1148  { return __x.base() < __y.base(); }
1149 
1150  template<typename _IteratorL, typename _IteratorR>
1151  inline bool
1152  operator<=(const move_iterator<_IteratorL>& __x,
1153  const move_iterator<_IteratorR>& __y)
1154  { return !(__y < __x); }
1155 
1156  template<typename _Iterator>
1157  inline bool
1158  operator<=(const move_iterator<_Iterator>& __x,
1159  const move_iterator<_Iterator>& __y)
1160  { return !(__y < __x); }
1161 
1162  template<typename _IteratorL, typename _IteratorR>
1163  inline bool
1164  operator>(const move_iterator<_IteratorL>& __x,
1165  const move_iterator<_IteratorR>& __y)
1166  { return __y < __x; }
1167 
1168  template<typename _Iterator>
1169  inline bool
1170  operator>(const move_iterator<_Iterator>& __x,
1171  const move_iterator<_Iterator>& __y)
1172  { return __y < __x; }
1173 
1174  template<typename _IteratorL, typename _IteratorR>
1175  inline bool
1176  operator>=(const move_iterator<_IteratorL>& __x,
1177  const move_iterator<_IteratorR>& __y)
1178  { return !(__x < __y); }
1179 
1180  template<typename _Iterator>
1181  inline bool
1182  operator>=(const move_iterator<_Iterator>& __x,
1183  const move_iterator<_Iterator>& __y)
1184  { return !(__x < __y); }
1185 
1186  // DR 685.
1187  template<typename _IteratorL, typename _IteratorR>
1188  inline auto
1190  const move_iterator<_IteratorR>& __y)
1191  -> decltype(__x.base() - __y.base())
1192  { return __x.base() - __y.base(); }
1193 
1194  template<typename _Iterator>
1195  inline auto
1197  const move_iterator<_Iterator>& __y)
1198  -> decltype(__x.base() - __y.base())
1199  { return __x.base() - __y.base(); }
1200 
1201  template<typename _Iterator>
1203  operator+(typename move_iterator<_Iterator>::difference_type __n,
1204  const move_iterator<_Iterator>& __x)
1205  { return __x + __n; }
1206 
1207  template<typename _Iterator>
1209  make_move_iterator(_Iterator __i)
1210  { return move_iterator<_Iterator>(__i); }
1211 
1212  template<typename _Iterator, typename _ReturnType
1213  = typename conditional<__move_if_noexcept_cond
1214  <typename iterator_traits<_Iterator>::value_type>::value,
1215  _Iterator, move_iterator<_Iterator>>::type>
1216  inline _ReturnType
1217  __make_move_if_noexcept_iterator(_Iterator __i)
1218  { return _ReturnType(__i); }
1219 
1220  // Overload for pointers that matches std::move_if_noexcept more closely,
1221  // returning a constant iterator when we don't want to move.
1222  template<typename _Tp, typename _ReturnType
1223  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1224  const _Tp*, move_iterator<_Tp*>>::type>
1225  inline _ReturnType
1226  __make_move_if_noexcept_iterator(_Tp* __i)
1227  { return _ReturnType(__i); }
1228 
1229  // @} group iterators
1230 
1231  template<typename _Iterator>
1232  auto
1233  __niter_base(move_iterator<_Iterator> __it)
1234  -> decltype(make_move_iterator(__niter_base(__it.base())))
1235  { return make_move_iterator(__niter_base(__it.base())); }
1236 
1237  template<typename _Iterator>
1238  struct __is_move_iterator<move_iterator<_Iterator> >
1239  {
1240  enum { __value = 1 };
1241  typedef __true_type __type;
1242  };
1243 
1244  template<typename _Iterator>
1245  auto
1246  __miter_base(move_iterator<_Iterator> __it)
1247  -> decltype(__miter_base(__it.base()))
1248  { return __miter_base(__it.base()); }
1249 
1250 _GLIBCXX_END_NAMESPACE_VERSION
1251 } // namespace
1252 
1253 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1254 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1255  std::__make_move_if_noexcept_iterator(_Iter)
1256 #else
1257 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1258 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1259 #endif // C++11
1260 
1261 #ifdef _GLIBCXX_DEBUG
1262 # include <debug/stl_iterator.h>
1263 #endif
1264 
1265 #endif
back_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
front_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
_Container container_type
A nested typedef for the type of whatever container you used.
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
front_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
back_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
reverse_iterator(const reverse_iterator< _Iter > &__x)
front_insert_iterator< _Container > front_inserter(_Container &__x)
reverse_iterator & operator+=(difference_type __n)
reverse_iterator operator++(int)
GNU extensions for public use.
reverse_iterator(iterator_type __x)
reverse_iterator operator+(difference_type __n) const
back_insert_iterator< _Container > back_inserter(_Container &__x)
reverse_iterator & operator-=(difference_type __n)
reference operator*() const
reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
back_insert_iterator & operator*()
Simply returns *this.
insert_iterator< _Container > inserter(_Container &__x, _Iterator __i)
insert_iterator(_Container &__x, typename _Container::iterator __i)
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
front_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
front_insert_iterator & operator=(const typename _Container::value_type &__value)
insert_iterator & operator=(const typename _Container::value_type &__value)
front_insert_iterator & operator*()
Simply returns *this.
reverse_iterator(const reverse_iterator &__x)
Turns assignment into insertion.
Common iterator class.
reverse_iterator & operator--()
pointer operator->() const
_Container container_type
A nested typedef for the type of whatever container you used.
back_insert_iterator & operator=(const typename _Container::value_type &__value)
Turns assignment into insertion.
ISO C++ entities toplevel namespace is std.
reverse_iterator & operator++()
reference operator[](difference_type __n) const
back_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
insert_iterator & operator*()
Simply returns *this.
iterator_type base() const
insert_iterator & operator++(int)
Simply returns *this. (This iterator does not move.)
_Container container_type
A nested typedef for the type of whatever container you used.
reverse_iterator operator--(int)
reverse_iterator operator-(difference_type __n) const
Turns assignment into insertion.