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