libstdc++
stl_iterator.h
Go to the documentation of this file.
1 // Iterators -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996-1998
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file bits/stl_iterator.h
53  * This is an internal header file, included by other library headers.
54  * Do not attempt to use it directly. @headername{iterator}
55  *
56  * This file implements reverse_iterator, back_insert_iterator,
57  * front_insert_iterator, insert_iterator, __normal_iterator, and their
58  * supporting functions and overloaded operators.
59  */
60 
61 #ifndef _STL_ITERATOR_H
62 #define _STL_ITERATOR_H 1
63 
64 #include <bits/cpp_type_traits.h>
65 #include <ext/type_traits.h>
66 #include <bits/move.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 default-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 in the normal
137  * fashion.
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 TODO
152  *
153  * @doctodo
154  */
155  reference
156  operator*() const
157  {
158  _Iterator __tmp = current;
159  return *--__tmp;
160  }
161 
162  /**
163  * @return TODO
164  *
165  * @doctodo
166  */
167  pointer
168  operator->() const
169  { return &(operator*()); }
170 
171  /**
172  * @return TODO
173  *
174  * @doctodo
175  */
178  {
179  --current;
180  return *this;
181  }
182 
183  /**
184  * @return TODO
185  *
186  * @doctodo
187  */
190  {
191  reverse_iterator __tmp = *this;
192  --current;
193  return __tmp;
194  }
195 
196  /**
197  * @return TODO
198  *
199  * @doctodo
200  */
203  {
204  ++current;
205  return *this;
206  }
207 
208  /**
209  * @return TODO
210  *
211  * @doctodo
212  */
215  {
216  reverse_iterator __tmp = *this;
217  ++current;
218  return __tmp;
219  }
220 
221  /**
222  * @return TODO
223  *
224  * @doctodo
225  */
227  operator+(difference_type __n) const
228  { return reverse_iterator(current - __n); }
229 
230  /**
231  * @return TODO
232  *
233  * @doctodo
234  */
236  operator+=(difference_type __n)
237  {
238  current -= __n;
239  return *this;
240  }
241 
242  /**
243  * @return TODO
244  *
245  * @doctodo
246  */
248  operator-(difference_type __n) const
249  { return reverse_iterator(current + __n); }
250 
251  /**
252  * @return TODO
253  *
254  * @doctodo
255  */
257  operator-=(difference_type __n)
258  {
259  current += __n;
260  return *this;
261  }
262 
263  /**
264  * @return TODO
265  *
266  * @doctodo
267  */
268  reference
269  operator[](difference_type __n) const
270  { return *(*this + __n); }
271  };
272 
273  //@{
274  /**
275  * @param x A %reverse_iterator.
276  * @param y A %reverse_iterator.
277  * @return A simple bool.
278  *
279  * Reverse iterators forward many operations to their underlying base()
280  * iterators. Others are implemented in terms of one another.
281  *
282  */
283  template<typename _Iterator>
284  inline bool
285  operator==(const reverse_iterator<_Iterator>& __x,
286  const reverse_iterator<_Iterator>& __y)
287  { return __x.base() == __y.base(); }
288 
289  template<typename _Iterator>
290  inline bool
291  operator<(const reverse_iterator<_Iterator>& __x,
292  const reverse_iterator<_Iterator>& __y)
293  { return __y.base() < __x.base(); }
294 
295  template<typename _Iterator>
296  inline bool
297  operator!=(const reverse_iterator<_Iterator>& __x,
298  const reverse_iterator<_Iterator>& __y)
299  { return !(__x == __y); }
300 
301  template<typename _Iterator>
302  inline bool
303  operator>(const reverse_iterator<_Iterator>& __x,
304  const reverse_iterator<_Iterator>& __y)
305  { return __y < __x; }
306 
307  template<typename _Iterator>
308  inline bool
309  operator<=(const reverse_iterator<_Iterator>& __x,
310  const reverse_iterator<_Iterator>& __y)
311  { return !(__y < __x); }
312 
313  template<typename _Iterator>
314  inline bool
315  operator>=(const reverse_iterator<_Iterator>& __x,
316  const reverse_iterator<_Iterator>& __y)
317  { return !(__x < __y); }
318 
319  template<typename _Iterator>
320  inline typename reverse_iterator<_Iterator>::difference_type
321  operator-(const reverse_iterator<_Iterator>& __x,
322  const reverse_iterator<_Iterator>& __y)
323  { return __y.base() - __x.base(); }
324 
325  template<typename _Iterator>
326  inline reverse_iterator<_Iterator>
327  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
328  const reverse_iterator<_Iterator>& __x)
329  { return reverse_iterator<_Iterator>(__x.base() - __n); }
330 
331  // _GLIBCXX_RESOLVE_LIB_DEFECTS
332  // DR 280. Comparison of reverse_iterator to const reverse_iterator.
333  template<typename _IteratorL, typename _IteratorR>
334  inline bool
335  operator==(const reverse_iterator<_IteratorL>& __x,
336  const reverse_iterator<_IteratorR>& __y)
337  { return __x.base() == __y.base(); }
338 
339  template<typename _IteratorL, typename _IteratorR>
340  inline bool
341  operator<(const reverse_iterator<_IteratorL>& __x,
342  const reverse_iterator<_IteratorR>& __y)
343  { return __y.base() < __x.base(); }
344 
345  template<typename _IteratorL, typename _IteratorR>
346  inline bool
347  operator!=(const reverse_iterator<_IteratorL>& __x,
348  const reverse_iterator<_IteratorR>& __y)
349  { return !(__x == __y); }
350 
351  template<typename _IteratorL, typename _IteratorR>
352  inline bool
353  operator>(const reverse_iterator<_IteratorL>& __x,
354  const reverse_iterator<_IteratorR>& __y)
355  { return __y < __x; }
356 
357  template<typename _IteratorL, typename _IteratorR>
358  inline bool
359  operator<=(const reverse_iterator<_IteratorL>& __x,
360  const reverse_iterator<_IteratorR>& __y)
361  { return !(__y < __x); }
362 
363  template<typename _IteratorL, typename _IteratorR>
364  inline bool
365  operator>=(const reverse_iterator<_IteratorL>& __x,
366  const reverse_iterator<_IteratorR>& __y)
367  { return !(__x < __y); }
368 
369  template<typename _IteratorL, typename _IteratorR>
370 #ifdef __GXX_EXPERIMENTAL_CXX0X__
371  // DR 685.
372  inline auto
373  operator-(const reverse_iterator<_IteratorL>& __x,
374  const reverse_iterator<_IteratorR>& __y)
375  -> decltype(__y.base() - __x.base())
376 #else
377  inline typename reverse_iterator<_IteratorL>::difference_type
378  operator-(const reverse_iterator<_IteratorL>& __x,
379  const reverse_iterator<_IteratorR>& __y)
380 #endif
381  { return __y.base() - __x.base(); }
382  //@}
383 
384  // 24.4.2.2.1 back_insert_iterator
385  /**
386  * @brief Turns assignment into insertion.
387  *
388  * These are output iterators, constructed from a container-of-T.
389  * Assigning a T to the iterator appends it to the container using
390  * push_back.
391  *
392  * Tip: Using the back_inserter function to create these iterators can
393  * save typing.
394  */
395  template<typename _Container>
397  : public iterator<output_iterator_tag, void, void, void, void>
398  {
399  protected:
400  _Container* container;
401 
402  public:
403  /// A nested typedef for the type of whatever container you used.
404  typedef _Container container_type;
405 
406  /// The only way to create this %iterator is with a container.
407  explicit
408  back_insert_iterator(_Container& __x) : container(&__x) { }
409 
410  /**
411  * @param value An instance of whatever type
412  * container_type::const_reference is; presumably a
413  * reference-to-const T for container<T>.
414  * @return This %iterator, for chained operations.
415  *
416  * This kind of %iterator doesn't really have a @a position in the
417  * container (you can think of the position as being permanently at
418  * the end, if you like). Assigning a value to the %iterator will
419  * always append the value to the end of the container.
420  */
421 #ifndef __GXX_EXPERIMENTAL_CXX0X__
423  operator=(typename _Container::const_reference __value)
424  {
425  container->push_back(__value);
426  return *this;
427  }
428 #else
430  operator=(const typename _Container::value_type& __value)
431  {
432  container->push_back(__value);
433  return *this;
434  }
435 
437  operator=(typename _Container::value_type&& __value)
438  {
439  container->push_back(std::move(__value));
440  return *this;
441  }
442 #endif
443 
444  /// Simply returns *this.
447  { return *this; }
448 
449  /// Simply returns *this. (This %iterator does not @a move.)
452  { return *this; }
453 
454  /// Simply returns *this. (This %iterator does not @a move.)
457  { return *this; }
458  };
459 
460  /**
461  * @param x A container of arbitrary type.
462  * @return An instance of back_insert_iterator working on @p x.
463  *
464  * This wrapper function helps in creating back_insert_iterator instances.
465  * Typing the name of the %iterator requires knowing the precise full
466  * type of the container, which can be tedious and impedes generic
467  * programming. Using this function lets you take advantage of automatic
468  * template parameter deduction, making the compiler match the correct
469  * types for you.
470  */
471  template<typename _Container>
472  inline back_insert_iterator<_Container>
473  back_inserter(_Container& __x)
474  { return back_insert_iterator<_Container>(__x); }
475 
476  /**
477  * @brief Turns assignment into insertion.
478  *
479  * These are output iterators, constructed from a container-of-T.
480  * Assigning a T to the iterator prepends it to the container using
481  * push_front.
482  *
483  * Tip: Using the front_inserter function to create these iterators can
484  * save typing.
485  */
486  template<typename _Container>
488  : public iterator<output_iterator_tag, void, void, void, void>
489  {
490  protected:
491  _Container* container;
492 
493  public:
494  /// A nested typedef for the type of whatever container you used.
495  typedef _Container container_type;
496 
497  /// The only way to create this %iterator is with a container.
498  explicit front_insert_iterator(_Container& __x) : container(&__x) { }
499 
500  /**
501  * @param value An instance of whatever type
502  * container_type::const_reference is; presumably a
503  * reference-to-const T for container<T>.
504  * @return This %iterator, for chained operations.
505  *
506  * This kind of %iterator doesn't really have a @a position in the
507  * container (you can think of the position as being permanently at
508  * the front, if you like). Assigning a value to the %iterator will
509  * always prepend the value to the front of the container.
510  */
511 #ifndef __GXX_EXPERIMENTAL_CXX0X__
513  operator=(typename _Container::const_reference __value)
514  {
515  container->push_front(__value);
516  return *this;
517  }
518 #else
520  operator=(const typename _Container::value_type& __value)
521  {
522  container->push_front(__value);
523  return *this;
524  }
525 
527  operator=(typename _Container::value_type&& __value)
528  {
529  container->push_front(std::move(__value));
530  return *this;
531  }
532 #endif
533 
534  /// Simply returns *this.
537  { return *this; }
538 
539  /// Simply returns *this. (This %iterator does not @a move.)
542  { return *this; }
543 
544  /// Simply returns *this. (This %iterator does not @a move.)
547  { return *this; }
548  };
549 
550  /**
551  * @param x A container of arbitrary type.
552  * @return An instance of front_insert_iterator working on @p x.
553  *
554  * This wrapper function helps in creating front_insert_iterator instances.
555  * Typing the name of the %iterator requires knowing the precise full
556  * type of the container, which can be tedious and impedes generic
557  * programming. Using this function lets you take advantage of automatic
558  * template parameter deduction, making the compiler match the correct
559  * types for you.
560  */
561  template<typename _Container>
562  inline front_insert_iterator<_Container>
563  front_inserter(_Container& __x)
564  { return front_insert_iterator<_Container>(__x); }
565 
566  /**
567  * @brief Turns assignment into insertion.
568  *
569  * These are output iterators, constructed from a container-of-T.
570  * Assigning a T to the iterator inserts it in the container at the
571  * %iterator's position, rather than overwriting the value at that
572  * position.
573  *
574  * (Sequences will actually insert a @e copy of the value before the
575  * %iterator's position.)
576  *
577  * Tip: Using the inserter function to create these iterators can
578  * save typing.
579  */
580  template<typename _Container>
582  : public iterator<output_iterator_tag, void, void, void, void>
583  {
584  protected:
585  _Container* container;
586  typename _Container::iterator iter;
587 
588  public:
589  /// A nested typedef for the type of whatever container you used.
590  typedef _Container container_type;
591 
592  /**
593  * The only way to create this %iterator is with a container and an
594  * initial position (a normal %iterator into the container).
595  */
596  insert_iterator(_Container& __x, typename _Container::iterator __i)
597  : container(&__x), iter(__i) {}
598 
599  /**
600  * @param value An instance of whatever type
601  * container_type::const_reference is; presumably a
602  * reference-to-const T for container<T>.
603  * @return This %iterator, for chained operations.
604  *
605  * This kind of %iterator maintains its own position in the
606  * container. Assigning a value to the %iterator will insert the
607  * value into the container at the place before the %iterator.
608  *
609  * The position is maintained such that subsequent assignments will
610  * insert values immediately after one another. For example,
611  * @code
612  * // vector v contains A and Z
613  *
614  * insert_iterator i (v, ++v.begin());
615  * i = 1;
616  * i = 2;
617  * i = 3;
618  *
619  * // vector v contains A, 1, 2, 3, and Z
620  * @endcode
621  */
622 #ifndef __GXX_EXPERIMENTAL_CXX0X__
624  operator=(typename _Container::const_reference __value)
625  {
626  iter = container->insert(iter, __value);
627  ++iter;
628  return *this;
629  }
630 #else
632  operator=(const typename _Container::value_type& __value)
633  {
634  iter = container->insert(iter, __value);
635  ++iter;
636  return *this;
637  }
638 
640  operator=(typename _Container::value_type&& __value)
641  {
642  iter = container->insert(iter, std::move(__value));
643  ++iter;
644  return *this;
645  }
646 #endif
647 
648  /// Simply returns *this.
651  { return *this; }
652 
653  /// Simply returns *this. (This %iterator does not @a move.)
656  { return *this; }
657 
658  /// Simply returns *this. (This %iterator does not @a move.)
661  { return *this; }
662  };
663 
664  /**
665  * @param x A container of arbitrary type.
666  * @return An instance of insert_iterator working on @p x.
667  *
668  * This wrapper function helps in creating insert_iterator instances.
669  * Typing the name of the %iterator requires knowing the precise full
670  * type of the container, which can be tedious and impedes generic
671  * programming. Using this function lets you take advantage of automatic
672  * template parameter deduction, making the compiler match the correct
673  * types for you.
674  */
675  template<typename _Container, typename _Iterator>
676  inline insert_iterator<_Container>
677  inserter(_Container& __x, _Iterator __i)
678  {
679  return insert_iterator<_Container>(__x,
680  typename _Container::iterator(__i));
681  }
682 
683  // @} group iterators
684 
685 _GLIBCXX_END_NAMESPACE_VERSION
686 } // namespace
687 
688 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
689 {
690 _GLIBCXX_BEGIN_NAMESPACE_VERSION
691 
692  // This iterator adapter is @a normal in the sense that it does not
693  // change the semantics of any of the operators of its iterator
694  // parameter. Its primary purpose is to convert an iterator that is
695  // not a class, e.g. a pointer, into an iterator that is a class.
696  // The _Container parameter exists solely so that different containers
697  // using this template can instantiate different types, even if the
698  // _Iterator parameter is the same.
699  using std::iterator_traits;
700  using std::iterator;
701  template<typename _Iterator, typename _Container>
702  class __normal_iterator
703  {
704  protected:
705  _Iterator _M_current;
706 
707  typedef iterator_traits<_Iterator> __traits_type;
708 
709  public:
710  typedef _Iterator iterator_type;
711  typedef typename __traits_type::iterator_category iterator_category;
712  typedef typename __traits_type::value_type value_type;
713  typedef typename __traits_type::difference_type difference_type;
714  typedef typename __traits_type::reference reference;
715  typedef typename __traits_type::pointer pointer;
716 
717  _GLIBCXX_CONSTEXPR __normal_iterator() : _M_current(_Iterator()) { }
718 
719  explicit
720  __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
721 
722  // Allow iterator to const_iterator conversion
723  template<typename _Iter>
724  __normal_iterator(const __normal_iterator<_Iter,
725  typename __enable_if<
726  (std::__are_same<_Iter, typename _Container::pointer>::__value),
727  _Container>::__type>& __i)
728  : _M_current(__i.base()) { }
729 
730  // Forward iterator requirements
731  reference
732  operator*() const
733  { return *_M_current; }
734 
735  pointer
736  operator->() const
737  { return _M_current; }
738 
739  __normal_iterator&
740  operator++()
741  {
742  ++_M_current;
743  return *this;
744  }
745 
746  __normal_iterator
747  operator++(int)
748  { return __normal_iterator(_M_current++); }
749 
750  // Bidirectional iterator requirements
751  __normal_iterator&
752  operator--()
753  {
754  --_M_current;
755  return *this;
756  }
757 
758  __normal_iterator
759  operator--(int)
760  { return __normal_iterator(_M_current--); }
761 
762  // Random access iterator requirements
763  reference
764  operator[](const difference_type& __n) const
765  { return _M_current[__n]; }
766 
767  __normal_iterator&
768  operator+=(const difference_type& __n)
769  { _M_current += __n; return *this; }
770 
771  __normal_iterator
772  operator+(const difference_type& __n) const
773  { return __normal_iterator(_M_current + __n); }
774 
775  __normal_iterator&
776  operator-=(const difference_type& __n)
777  { _M_current -= __n; return *this; }
778 
779  __normal_iterator
780  operator-(const difference_type& __n) const
781  { return __normal_iterator(_M_current - __n); }
782 
783  const _Iterator&
784  base() const
785  { return _M_current; }
786  };
787 
788  // Note: In what follows, the left- and right-hand-side iterators are
789  // allowed to vary in types (conceptually in cv-qualification) so that
790  // comparison between cv-qualified and non-cv-qualified iterators be
791  // valid. However, the greedy and unfriendly operators in std::rel_ops
792  // will make overload resolution ambiguous (when in scope) if we don't
793  // provide overloads whose operands are of the same type. Can someone
794  // remind me what generic programming is about? -- Gaby
795 
796  // Forward iterator requirements
797  template<typename _IteratorL, typename _IteratorR, typename _Container>
798  inline bool
799  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
800  const __normal_iterator<_IteratorR, _Container>& __rhs)
801  { return __lhs.base() == __rhs.base(); }
802 
803  template<typename _Iterator, typename _Container>
804  inline bool
805  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
806  const __normal_iterator<_Iterator, _Container>& __rhs)
807  { return __lhs.base() == __rhs.base(); }
808 
809  template<typename _IteratorL, typename _IteratorR, typename _Container>
810  inline bool
811  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
812  const __normal_iterator<_IteratorR, _Container>& __rhs)
813  { return __lhs.base() != __rhs.base(); }
814 
815  template<typename _Iterator, typename _Container>
816  inline bool
817  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
818  const __normal_iterator<_Iterator, _Container>& __rhs)
819  { return __lhs.base() != __rhs.base(); }
820 
821  // Random access iterator requirements
822  template<typename _IteratorL, typename _IteratorR, typename _Container>
823  inline bool
824  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
825  const __normal_iterator<_IteratorR, _Container>& __rhs)
826  { return __lhs.base() < __rhs.base(); }
827 
828  template<typename _Iterator, typename _Container>
829  inline bool
830  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
831  const __normal_iterator<_Iterator, _Container>& __rhs)
832  { return __lhs.base() < __rhs.base(); }
833 
834  template<typename _IteratorL, typename _IteratorR, typename _Container>
835  inline bool
836  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
837  const __normal_iterator<_IteratorR, _Container>& __rhs)
838  { return __lhs.base() > __rhs.base(); }
839 
840  template<typename _Iterator, typename _Container>
841  inline bool
842  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
843  const __normal_iterator<_Iterator, _Container>& __rhs)
844  { return __lhs.base() > __rhs.base(); }
845 
846  template<typename _IteratorL, typename _IteratorR, typename _Container>
847  inline bool
848  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
849  const __normal_iterator<_IteratorR, _Container>& __rhs)
850  { return __lhs.base() <= __rhs.base(); }
851 
852  template<typename _Iterator, typename _Container>
853  inline bool
854  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
855  const __normal_iterator<_Iterator, _Container>& __rhs)
856  { return __lhs.base() <= __rhs.base(); }
857 
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  { 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  { return __lhs.base() >= __rhs.base(); }
869 
870  // _GLIBCXX_RESOLVE_LIB_DEFECTS
871  // According to the resolution of DR179 not only the various comparison
872  // operators but also operator- must accept mixed iterator/const_iterator
873  // parameters.
874  template<typename _IteratorL, typename _IteratorR, typename _Container>
875 #ifdef __GXX_EXPERIMENTAL_CXX0X__
876  // DR 685.
877  inline auto
878  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
879  const __normal_iterator<_IteratorR, _Container>& __rhs)
880  -> decltype(__lhs.base() - __rhs.base())
881 #else
882  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
883  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
884  const __normal_iterator<_IteratorR, _Container>& __rhs)
885 #endif
886  { return __lhs.base() - __rhs.base(); }
887 
888  template<typename _Iterator, typename _Container>
889  inline typename __normal_iterator<_Iterator, _Container>::difference_type
890  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
891  const __normal_iterator<_Iterator, _Container>& __rhs)
892  { return __lhs.base() - __rhs.base(); }
893 
894  template<typename _Iterator, typename _Container>
895  inline __normal_iterator<_Iterator, _Container>
896  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
897  __n, const __normal_iterator<_Iterator, _Container>& __i)
898  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
899 
900 _GLIBCXX_END_NAMESPACE_VERSION
901 } // namespace
902 
903 #ifdef __GXX_EXPERIMENTAL_CXX0X__
904 
905 namespace std _GLIBCXX_VISIBILITY(default)
906 {
907 _GLIBCXX_BEGIN_NAMESPACE_VERSION
908 
909  /**
910  * @addtogroup iterators
911  * @{
912  */
913 
914  // 24.4.3 Move iterators
915  /**
916  * Class template move_iterator is an iterator adapter with the same
917  * behavior as the underlying iterator except that its dereference
918  * operator implicitly converts the value returned by the underlying
919  * iterator's dereference operator to an rvalue reference. Some
920  * generic algorithms can be called with move iterators to replace
921  * copying with moving.
922  */
923  template<typename _Iterator>
924  class move_iterator
925  {
926  protected:
927  _Iterator _M_current;
928 
929  typedef iterator_traits<_Iterator> __traits_type;
930 
931  public:
932  typedef _Iterator iterator_type;
933  typedef typename __traits_type::iterator_category iterator_category;
934  typedef typename __traits_type::value_type value_type;
935  typedef typename __traits_type::difference_type difference_type;
936  // NB: DR 680.
937  typedef _Iterator pointer;
938  typedef value_type&& reference;
939 
940  move_iterator()
941  : _M_current() { }
942 
943  explicit
944  move_iterator(iterator_type __i)
945  : _M_current(__i) { }
946 
947  template<typename _Iter>
948  move_iterator(const move_iterator<_Iter>& __i)
949  : _M_current(__i.base()) { }
950 
951  iterator_type
952  base() const
953  { return _M_current; }
954 
955  reference
956  operator*() const
957  { return std::move(*_M_current); }
958 
959  pointer
960  operator->() const
961  { return _M_current; }
962 
963  move_iterator&
964  operator++()
965  {
966  ++_M_current;
967  return *this;
968  }
969 
970  move_iterator
971  operator++(int)
972  {
973  move_iterator __tmp = *this;
974  ++_M_current;
975  return __tmp;
976  }
977 
978  move_iterator&
979  operator--()
980  {
981  --_M_current;
982  return *this;
983  }
984 
985  move_iterator
986  operator--(int)
987  {
988  move_iterator __tmp = *this;
989  --_M_current;
990  return __tmp;
991  }
992 
993  move_iterator
994  operator+(difference_type __n) const
995  { return move_iterator(_M_current + __n); }
996 
997  move_iterator&
998  operator+=(difference_type __n)
999  {
1000  _M_current += __n;
1001  return *this;
1002  }
1003 
1004  move_iterator
1005  operator-(difference_type __n) const
1006  { return move_iterator(_M_current - __n); }
1007 
1008  move_iterator&
1009  operator-=(difference_type __n)
1010  {
1011  _M_current -= __n;
1012  return *this;
1013  }
1014 
1015  reference
1016  operator[](difference_type __n) const
1017  { return std::move(_M_current[__n]); }
1018  };
1019 
1020  // Note: See __normal_iterator operators note from Gaby to understand
1021  // why there are always 2 versions for most of the move_iterator
1022  // operators.
1023  template<typename _IteratorL, typename _IteratorR>
1024  inline bool
1025  operator==(const move_iterator<_IteratorL>& __x,
1026  const move_iterator<_IteratorR>& __y)
1027  { return __x.base() == __y.base(); }
1028 
1029  template<typename _Iterator>
1030  inline bool
1031  operator==(const move_iterator<_Iterator>& __x,
1032  const move_iterator<_Iterator>& __y)
1033  { return __x.base() == __y.base(); }
1034 
1035  template<typename _IteratorL, typename _IteratorR>
1036  inline bool
1037  operator!=(const move_iterator<_IteratorL>& __x,
1038  const move_iterator<_IteratorR>& __y)
1039  { return !(__x == __y); }
1040 
1041  template<typename _Iterator>
1042  inline bool
1043  operator!=(const move_iterator<_Iterator>& __x,
1044  const move_iterator<_Iterator>& __y)
1045  { return !(__x == __y); }
1046 
1047  template<typename _IteratorL, typename _IteratorR>
1048  inline bool
1049  operator<(const move_iterator<_IteratorL>& __x,
1050  const move_iterator<_IteratorR>& __y)
1051  { return __x.base() < __y.base(); }
1052 
1053  template<typename _Iterator>
1054  inline bool
1055  operator<(const move_iterator<_Iterator>& __x,
1056  const move_iterator<_Iterator>& __y)
1057  { return __x.base() < __y.base(); }
1058 
1059  template<typename _IteratorL, typename _IteratorR>
1060  inline bool
1061  operator<=(const move_iterator<_IteratorL>& __x,
1062  const move_iterator<_IteratorR>& __y)
1063  { return !(__y < __x); }
1064 
1065  template<typename _Iterator>
1066  inline bool
1067  operator<=(const move_iterator<_Iterator>& __x,
1068  const move_iterator<_Iterator>& __y)
1069  { return !(__y < __x); }
1070 
1071  template<typename _IteratorL, typename _IteratorR>
1072  inline bool
1073  operator>(const move_iterator<_IteratorL>& __x,
1074  const move_iterator<_IteratorR>& __y)
1075  { return __y < __x; }
1076 
1077  template<typename _Iterator>
1078  inline bool
1079  operator>(const move_iterator<_Iterator>& __x,
1080  const move_iterator<_Iterator>& __y)
1081  { return __y < __x; }
1082 
1083  template<typename _IteratorL, typename _IteratorR>
1084  inline bool
1085  operator>=(const move_iterator<_IteratorL>& __x,
1086  const move_iterator<_IteratorR>& __y)
1087  { return !(__x < __y); }
1088 
1089  template<typename _Iterator>
1090  inline bool
1091  operator>=(const move_iterator<_Iterator>& __x,
1092  const move_iterator<_Iterator>& __y)
1093  { return !(__x < __y); }
1094 
1095  // DR 685.
1096  template<typename _IteratorL, typename _IteratorR>
1097  inline auto
1098  operator-(const move_iterator<_IteratorL>& __x,
1099  const move_iterator<_IteratorR>& __y)
1100  -> decltype(__x.base() - __y.base())
1101  { return __x.base() - __y.base(); }
1102 
1103  template<typename _Iterator>
1104  inline auto
1105  operator-(const move_iterator<_Iterator>& __x,
1106  const move_iterator<_Iterator>& __y)
1107  -> decltype(__x.base() - __y.base())
1108  { return __x.base() - __y.base(); }
1109 
1110  template<typename _Iterator>
1111  inline move_iterator<_Iterator>
1112  operator+(typename move_iterator<_Iterator>::difference_type __n,
1113  const move_iterator<_Iterator>& __x)
1114  { return __x + __n; }
1115 
1116  template<typename _Iterator>
1117  inline move_iterator<_Iterator>
1118  make_move_iterator(const _Iterator& __i)
1119  { return move_iterator<_Iterator>(__i); }
1120 
1121  // @} group iterators
1122 
1123 _GLIBCXX_END_NAMESPACE_VERSION
1124 } // namespace
1125 
1126 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1127 #else
1128 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1129 #endif // __GXX_EXPERIMENTAL_CXX0X__
1130 
1131 #endif
front_insert_iterator & operator*()
Simply returns *this.
Definition: stl_iterator.h:536
reference operator[](size_t __position)
Array-indexing support.
Definition: bitset:1138
iterator_type base() const
Definition: stl_iterator.h:147
complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:321
insert_iterator & operator++(int)
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:660
pointer operator->() const
Definition: stl_iterator.h:168
reverse_iterator(iterator_type __x)
Definition: stl_iterator.h:127
reverse_iterator & operator-=(difference_type __n)
Definition: stl_iterator.h:257
insert_iterator & operator*()
Simply returns *this.
Definition: stl_iterator.h:650
reverse_iterator operator++(int)
Definition: stl_iterator.h:189
insert_iterator(_Container &__x, typename _Container::iterator __i)
Definition: stl_iterator.h:596
back_insert_iterator< _Container > back_inserter(_Container &__x)
Definition: stl_iterator.h:473
insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: stl_iterator.h:632
reverse_iterator operator+(difference_type __n) const
Definition: stl_iterator.h:227
back_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:451
reverse_iterator & operator++()
Definition: stl_iterator.h:177
front_insert_iterator< _Container > front_inserter(_Container &__x)
Definition: stl_iterator.h:563
back_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
Definition: stl_iterator.h:408
reverse_iterator operator--(int)
Definition: stl_iterator.h:214
reverse_iterator & operator--()
Definition: stl_iterator.h:202
reference operator*() const
Definition: stl_iterator.h:156
insert_iterator< _Container > inserter(_Container &__x, _Iterator __i)
Definition: stl_iterator.h:677
_Container container_type
A nested typedef for the type of whatever container you used.
Definition: stl_iterator.h:590
Turns assignment into insertion.
Definition: stl_iterator.h:396
back_insert_iterator & operator*()
Simply returns *this.
Definition: stl_iterator.h:446
Turns assignment into insertion.
Definition: stl_iterator.h:581
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:655
reverse_iterator & operator+=(difference_type __n)
Definition: stl_iterator.h:236
reference operator[](difference_type __n) const
Definition: stl_iterator.h:269
reverse_iterator(const reverse_iterator &__x)
Definition: stl_iterator.h:132
_Container container_type
A nested typedef for the type of whatever container you used.
Definition: stl_iterator.h:404
complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition: complex:351
reverse_iterator(const reverse_iterator< _Iter > &__x)
Definition: stl_iterator.h:140
Common iterator class.
_Container container_type
A nested typedef for the type of whatever container you used.
Definition: stl_iterator.h:495
front_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:541
front_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:546
back_insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: stl_iterator.h:430
Turns assignment into insertion.
Definition: stl_iterator.h:487
reverse_iterator operator-(difference_type __n) const
Definition: stl_iterator.h:248
back_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:456
front_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
Definition: stl_iterator.h:498
front_insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: stl_iterator.h:520