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