libstdc++
stl_iterator.h
Go to the documentation of this file.
00001 // Iterators -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996-1998
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_iterator.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{iterator}
00054  *
00055  *  This file implements reverse_iterator, back_insert_iterator,
00056  *  front_insert_iterator, insert_iterator, __normal_iterator, and their
00057  *  supporting functions and overloaded operators.
00058  */
00059 
00060 #ifndef _STL_ITERATOR_H
00061 #define _STL_ITERATOR_H 1
00062 
00063 #include <bits/cpp_type_traits.h>
00064 #include <ext/type_traits.h>
00065 #include <bits/move.h>
00066 
00067 namespace std _GLIBCXX_VISIBILITY(default)
00068 {
00069 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00070 
00071   /**
00072    * @addtogroup iterators
00073    * @{
00074    */
00075 
00076   // 24.4.1 Reverse iterators
00077   /**
00078    *  Bidirectional and random access iterators have corresponding reverse
00079    *  %iterator adaptors that iterate through the data structure in the
00080    *  opposite direction.  They have the same signatures as the corresponding
00081    *  iterators.  The fundamental relation between a reverse %iterator and its
00082    *  corresponding %iterator @c i is established by the identity:
00083    *  @code
00084    *      &*(reverse_iterator(i)) == &*(i - 1)
00085    *  @endcode
00086    *
00087    *  <em>This mapping is dictated by the fact that while there is always a
00088    *  pointer past the end of an array, there might not be a valid pointer
00089    *  before the beginning of an array.</em> [24.4.1]/1,2
00090    *
00091    *  Reverse iterators can be tricky and surprising at first.  Their
00092    *  semantics make sense, however, and the trickiness is a side effect of
00093    *  the requirement that the iterators must be safe.
00094   */
00095   template<typename _Iterator>
00096     class reverse_iterator
00097     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
00098               typename iterator_traits<_Iterator>::value_type,
00099               typename iterator_traits<_Iterator>::difference_type,
00100               typename iterator_traits<_Iterator>::pointer,
00101                       typename iterator_traits<_Iterator>::reference>
00102     {
00103     protected:
00104       _Iterator current;
00105 
00106       typedef iterator_traits<_Iterator>        __traits_type;
00107 
00108     public:
00109       typedef _Iterator                 iterator_type;
00110       typedef typename __traits_type::difference_type   difference_type;
00111       typedef typename __traits_type::pointer       pointer;
00112       typedef typename __traits_type::reference     reference;
00113 
00114       /**
00115        *  The default constructor value-initializes member @p current.
00116        *  If it is a pointer, that means it is zero-initialized.
00117       */
00118       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00119       // 235 No specification of default ctor for reverse_iterator
00120       reverse_iterator() : current() { }
00121 
00122       /**
00123        *  This %iterator will move in the opposite direction that @p x does.
00124       */
00125       explicit
00126       reverse_iterator(iterator_type __x) : current(__x) { }
00127 
00128       /**
00129        *  The copy constructor is normal.
00130       */
00131       reverse_iterator(const reverse_iterator& __x)
00132       : current(__x.current) { }
00133 
00134       /**
00135        *  A %reverse_iterator across other types can be copied if the
00136        *  underlying %iterator can be converted to the type of @c current.
00137       */
00138       template<typename _Iter>
00139         reverse_iterator(const reverse_iterator<_Iter>& __x)
00140     : current(__x.base()) { }
00141 
00142       /**
00143        *  @return  @c current, the %iterator used for underlying work.
00144       */
00145       iterator_type
00146       base() const
00147       { return current; }
00148 
00149       /**
00150        *  @return  A reference to the value at @c --current
00151        *
00152        *  This requires that @c --current is dereferenceable.
00153        *
00154        *  @warning This implementation requires that for an iterator of the
00155        *           underlying iterator type, @c x, a reference obtained by
00156        *           @c *x remains valid after @c x has been modified or
00157        *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
00158       */
00159       reference
00160       operator*() const
00161       {
00162     _Iterator __tmp = current;
00163     return *--__tmp;
00164       }
00165 
00166       /**
00167        *  @return  A pointer to the value at @c --current
00168        *
00169        *  This requires that @c --current is dereferenceable.
00170       */
00171       pointer
00172       operator->() const
00173       { return &(operator*()); }
00174 
00175       /**
00176        *  @return  @c *this
00177        *
00178        *  Decrements the underlying iterator.
00179       */
00180       reverse_iterator&
00181       operator++()
00182       {
00183     --current;
00184     return *this;
00185       }
00186 
00187       /**
00188        *  @return  The original value of @c *this
00189        *
00190        *  Decrements the underlying iterator.
00191       */
00192       reverse_iterator
00193       operator++(int)
00194       {
00195     reverse_iterator __tmp = *this;
00196     --current;
00197     return __tmp;
00198       }
00199 
00200       /**
00201        *  @return  @c *this
00202        *
00203        *  Increments the underlying iterator.
00204       */
00205       reverse_iterator&
00206       operator--()
00207       {
00208     ++current;
00209     return *this;
00210       }
00211 
00212       /**
00213        *  @return  A reverse_iterator with the previous value of @c *this
00214        *
00215        *  Increments the underlying iterator.
00216       */
00217       reverse_iterator
00218       operator--(int)
00219       {
00220     reverse_iterator __tmp = *this;
00221     ++current;
00222     return __tmp;
00223       }
00224 
00225       /**
00226        *  @return  A reverse_iterator that refers to @c current - @a __n
00227        *
00228        *  The underlying iterator must be a Random Access Iterator.
00229       */
00230       reverse_iterator
00231       operator+(difference_type __n) const
00232       { return reverse_iterator(current - __n); }
00233 
00234       /**
00235        *  @return  *this
00236        *
00237        *  Moves the underlying iterator backwards @a __n steps.
00238        *  The underlying iterator must be a Random Access Iterator.
00239       */
00240       reverse_iterator&
00241       operator+=(difference_type __n)
00242       {
00243     current -= __n;
00244     return *this;
00245       }
00246 
00247       /**
00248        *  @return  A reverse_iterator that refers to @c current - @a __n
00249        *
00250        *  The underlying iterator must be a Random Access Iterator.
00251       */
00252       reverse_iterator
00253       operator-(difference_type __n) const
00254       { return reverse_iterator(current + __n); }
00255 
00256       /**
00257        *  @return  *this
00258        *
00259        *  Moves the underlying iterator forwards @a __n steps.
00260        *  The underlying iterator must be a Random Access Iterator.
00261       */
00262       reverse_iterator&
00263       operator-=(difference_type __n)
00264       {
00265     current += __n;
00266     return *this;
00267       }
00268 
00269       /**
00270        *  @return  The value at @c current - @a __n - 1
00271        *
00272        *  The underlying iterator must be a Random Access Iterator.
00273       */
00274       reference
00275       operator[](difference_type __n) const
00276       { return *(*this + __n); }
00277     };
00278 
00279   //@{
00280   /**
00281    *  @param  __x  A %reverse_iterator.
00282    *  @param  __y  A %reverse_iterator.
00283    *  @return  A simple bool.
00284    *
00285    *  Reverse iterators forward many operations to their underlying base()
00286    *  iterators.  Others are implemented in terms of one another.
00287    *
00288   */
00289   template<typename _Iterator>
00290     inline bool
00291     operator==(const reverse_iterator<_Iterator>& __x,
00292            const reverse_iterator<_Iterator>& __y)
00293     { return __x.base() == __y.base(); }
00294 
00295   template<typename _Iterator>
00296     inline bool
00297     operator<(const reverse_iterator<_Iterator>& __x,
00298           const reverse_iterator<_Iterator>& __y)
00299     { return __y.base() < __x.base(); }
00300 
00301   template<typename _Iterator>
00302     inline bool
00303     operator!=(const reverse_iterator<_Iterator>& __x,
00304            const reverse_iterator<_Iterator>& __y)
00305     { return !(__x == __y); }
00306 
00307   template<typename _Iterator>
00308     inline bool
00309     operator>(const reverse_iterator<_Iterator>& __x,
00310           const reverse_iterator<_Iterator>& __y)
00311     { return __y < __x; }
00312 
00313   template<typename _Iterator>
00314     inline bool
00315     operator<=(const reverse_iterator<_Iterator>& __x,
00316            const reverse_iterator<_Iterator>& __y)
00317     { return !(__y < __x); }
00318 
00319   template<typename _Iterator>
00320     inline bool
00321     operator>=(const reverse_iterator<_Iterator>& __x,
00322            const reverse_iterator<_Iterator>& __y)
00323     { return !(__x < __y); }
00324 
00325   template<typename _Iterator>
00326     inline typename reverse_iterator<_Iterator>::difference_type
00327     operator-(const reverse_iterator<_Iterator>& __x,
00328           const reverse_iterator<_Iterator>& __y)
00329     { return __y.base() - __x.base(); }
00330 
00331   template<typename _Iterator>
00332     inline reverse_iterator<_Iterator>
00333     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00334           const reverse_iterator<_Iterator>& __x)
00335     { return reverse_iterator<_Iterator>(__x.base() - __n); }
00336 
00337   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00338   // DR 280. Comparison of reverse_iterator to const reverse_iterator.
00339   template<typename _IteratorL, typename _IteratorR>
00340     inline bool
00341     operator==(const reverse_iterator<_IteratorL>& __x,
00342            const reverse_iterator<_IteratorR>& __y)
00343     { return __x.base() == __y.base(); }
00344 
00345   template<typename _IteratorL, typename _IteratorR>
00346     inline bool
00347     operator<(const reverse_iterator<_IteratorL>& __x,
00348           const reverse_iterator<_IteratorR>& __y)
00349     { return __y.base() < __x.base(); }
00350 
00351   template<typename _IteratorL, typename _IteratorR>
00352     inline bool
00353     operator!=(const reverse_iterator<_IteratorL>& __x,
00354            const reverse_iterator<_IteratorR>& __y)
00355     { return !(__x == __y); }
00356 
00357   template<typename _IteratorL, typename _IteratorR>
00358     inline bool
00359     operator>(const reverse_iterator<_IteratorL>& __x,
00360           const reverse_iterator<_IteratorR>& __y)
00361     { return __y < __x; }
00362 
00363   template<typename _IteratorL, typename _IteratorR>
00364     inline bool
00365     operator<=(const reverse_iterator<_IteratorL>& __x,
00366            const reverse_iterator<_IteratorR>& __y)
00367     { return !(__y < __x); }
00368 
00369   template<typename _IteratorL, typename _IteratorR>
00370     inline bool
00371     operator>=(const reverse_iterator<_IteratorL>& __x,
00372            const reverse_iterator<_IteratorR>& __y)
00373     { return !(__x < __y); }
00374 
00375   template<typename _IteratorL, typename _IteratorR>
00376 #if __cplusplus >= 201103L
00377     // DR 685.
00378     inline auto
00379     operator-(const reverse_iterator<_IteratorL>& __x,
00380           const reverse_iterator<_IteratorR>& __y)
00381     -> decltype(__y.base() - __x.base())
00382 #else
00383     inline typename reverse_iterator<_IteratorL>::difference_type
00384     operator-(const reverse_iterator<_IteratorL>& __x,
00385           const reverse_iterator<_IteratorR>& __y)
00386 #endif
00387     { return __y.base() - __x.base(); }
00388   //@}
00389 
00390   // 24.4.2.2.1 back_insert_iterator
00391   /**
00392    *  @brief  Turns assignment into insertion.
00393    *
00394    *  These are output iterators, constructed from a container-of-T.
00395    *  Assigning a T to the iterator appends it to the container using
00396    *  push_back.
00397    *
00398    *  Tip:  Using the back_inserter function to create these iterators can
00399    *  save typing.
00400   */
00401   template<typename _Container>
00402     class back_insert_iterator
00403     : public iterator<output_iterator_tag, void, void, void, void>
00404     {
00405     protected:
00406       _Container* container;
00407 
00408     public:
00409       /// A nested typedef for the type of whatever container you used.
00410       typedef _Container          container_type;
00411 
00412       /// The only way to create this %iterator is with a container.
00413       explicit
00414       back_insert_iterator(_Container& __x) : container(&__x) { }
00415 
00416       /**
00417        *  @param  __value  An instance of whatever type
00418        *                 container_type::const_reference is; presumably a
00419        *                 reference-to-const T for container<T>.
00420        *  @return  This %iterator, for chained operations.
00421        *
00422        *  This kind of %iterator doesn't really have a @a position in the
00423        *  container (you can think of the position as being permanently at
00424        *  the end, if you like).  Assigning a value to the %iterator will
00425        *  always append the value to the end of the container.
00426       */
00427 #if __cplusplus < 201103L
00428       back_insert_iterator&
00429       operator=(typename _Container::const_reference __value)
00430       {
00431     container->push_back(__value);
00432     return *this;
00433       }
00434 #else
00435       back_insert_iterator&
00436       operator=(const typename _Container::value_type& __value)
00437       {
00438     container->push_back(__value);
00439     return *this;
00440       }
00441 
00442       back_insert_iterator&
00443       operator=(typename _Container::value_type&& __value)
00444       {
00445     container->push_back(std::move(__value));
00446     return *this;
00447       }
00448 #endif
00449 
00450       /// Simply returns *this.
00451       back_insert_iterator&
00452       operator*()
00453       { return *this; }
00454 
00455       /// Simply returns *this.  (This %iterator does not @a move.)
00456       back_insert_iterator&
00457       operator++()
00458       { return *this; }
00459 
00460       /// Simply returns *this.  (This %iterator does not @a move.)
00461       back_insert_iterator
00462       operator++(int)
00463       { return *this; }
00464     };
00465 
00466   /**
00467    *  @param  __x  A container of arbitrary type.
00468    *  @return  An instance of back_insert_iterator working on @p __x.
00469    *
00470    *  This wrapper function helps in creating back_insert_iterator instances.
00471    *  Typing the name of the %iterator requires knowing the precise full
00472    *  type of the container, which can be tedious and impedes generic
00473    *  programming.  Using this function lets you take advantage of automatic
00474    *  template parameter deduction, making the compiler match the correct
00475    *  types for you.
00476   */
00477   template<typename _Container>
00478     inline back_insert_iterator<_Container>
00479     back_inserter(_Container& __x)
00480     { return back_insert_iterator<_Container>(__x); }
00481 
00482   /**
00483    *  @brief  Turns assignment into insertion.
00484    *
00485    *  These are output iterators, constructed from a container-of-T.
00486    *  Assigning a T to the iterator prepends it to the container using
00487    *  push_front.
00488    *
00489    *  Tip:  Using the front_inserter function to create these iterators can
00490    *  save typing.
00491   */
00492   template<typename _Container>
00493     class front_insert_iterator
00494     : public iterator<output_iterator_tag, void, void, void, void>
00495     {
00496     protected:
00497       _Container* container;
00498 
00499     public:
00500       /// A nested typedef for the type of whatever container you used.
00501       typedef _Container          container_type;
00502 
00503       /// The only way to create this %iterator is with a container.
00504       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
00505 
00506       /**
00507        *  @param  __value  An instance of whatever type
00508        *                 container_type::const_reference is; presumably a
00509        *                 reference-to-const T for container<T>.
00510        *  @return  This %iterator, for chained operations.
00511        *
00512        *  This kind of %iterator doesn't really have a @a position in the
00513        *  container (you can think of the position as being permanently at
00514        *  the front, if you like).  Assigning a value to the %iterator will
00515        *  always prepend the value to the front of the container.
00516       */
00517 #if __cplusplus < 201103L
00518       front_insert_iterator&
00519       operator=(typename _Container::const_reference __value)
00520       {
00521     container->push_front(__value);
00522     return *this;
00523       }
00524 #else
00525       front_insert_iterator&
00526       operator=(const typename _Container::value_type& __value)
00527       {
00528     container->push_front(__value);
00529     return *this;
00530       }
00531 
00532       front_insert_iterator&
00533       operator=(typename _Container::value_type&& __value)
00534       {
00535     container->push_front(std::move(__value));
00536     return *this;
00537       }
00538 #endif
00539 
00540       /// Simply returns *this.
00541       front_insert_iterator&
00542       operator*()
00543       { return *this; }
00544 
00545       /// Simply returns *this.  (This %iterator does not @a move.)
00546       front_insert_iterator&
00547       operator++()
00548       { return *this; }
00549 
00550       /// Simply returns *this.  (This %iterator does not @a move.)
00551       front_insert_iterator
00552       operator++(int)
00553       { return *this; }
00554     };
00555 
00556   /**
00557    *  @param  __x  A container of arbitrary type.
00558    *  @return  An instance of front_insert_iterator working on @p x.
00559    *
00560    *  This wrapper function helps in creating front_insert_iterator instances.
00561    *  Typing the name of the %iterator requires knowing the precise full
00562    *  type of the container, which can be tedious and impedes generic
00563    *  programming.  Using this function lets you take advantage of automatic
00564    *  template parameter deduction, making the compiler match the correct
00565    *  types for you.
00566   */
00567   template<typename _Container>
00568     inline front_insert_iterator<_Container>
00569     front_inserter(_Container& __x)
00570     { return front_insert_iterator<_Container>(__x); }
00571 
00572   /**
00573    *  @brief  Turns assignment into insertion.
00574    *
00575    *  These are output iterators, constructed from a container-of-T.
00576    *  Assigning a T to the iterator inserts it in the container at the
00577    *  %iterator's position, rather than overwriting the value at that
00578    *  position.
00579    *
00580    *  (Sequences will actually insert a @e copy of the value before the
00581    *  %iterator's position.)
00582    *
00583    *  Tip:  Using the inserter function to create these iterators can
00584    *  save typing.
00585   */
00586   template<typename _Container>
00587     class insert_iterator
00588     : public iterator<output_iterator_tag, void, void, void, void>
00589     {
00590     protected:
00591       _Container* container;
00592       typename _Container::iterator iter;
00593 
00594     public:
00595       /// A nested typedef for the type of whatever container you used.
00596       typedef _Container          container_type;
00597 
00598       /**
00599        *  The only way to create this %iterator is with a container and an
00600        *  initial position (a normal %iterator into the container).
00601       */
00602       insert_iterator(_Container& __x, typename _Container::iterator __i)
00603       : container(&__x), iter(__i) {}
00604 
00605       /**
00606        *  @param  __value  An instance of whatever type
00607        *                 container_type::const_reference is; presumably a
00608        *                 reference-to-const T for container<T>.
00609        *  @return  This %iterator, for chained operations.
00610        *
00611        *  This kind of %iterator maintains its own position in the
00612        *  container.  Assigning a value to the %iterator will insert the
00613        *  value into the container at the place before the %iterator.
00614        *
00615        *  The position is maintained such that subsequent assignments will
00616        *  insert values immediately after one another.  For example,
00617        *  @code
00618        *     // vector v contains A and Z
00619        *
00620        *     insert_iterator i (v, ++v.begin());
00621        *     i = 1;
00622        *     i = 2;
00623        *     i = 3;
00624        *
00625        *     // vector v contains A, 1, 2, 3, and Z
00626        *  @endcode
00627       */
00628 #if __cplusplus < 201103L
00629       insert_iterator&
00630       operator=(typename _Container::const_reference __value)
00631       {
00632     iter = container->insert(iter, __value);
00633     ++iter;
00634     return *this;
00635       }
00636 #else
00637       insert_iterator&
00638       operator=(const typename _Container::value_type& __value)
00639       {
00640     iter = container->insert(iter, __value);
00641     ++iter;
00642     return *this;
00643       }
00644 
00645       insert_iterator&
00646       operator=(typename _Container::value_type&& __value)
00647       {
00648     iter = container->insert(iter, std::move(__value));
00649     ++iter;
00650     return *this;
00651       }
00652 #endif
00653 
00654       /// Simply returns *this.
00655       insert_iterator&
00656       operator*()
00657       { return *this; }
00658 
00659       /// Simply returns *this.  (This %iterator does not @a move.)
00660       insert_iterator&
00661       operator++()
00662       { return *this; }
00663 
00664       /// Simply returns *this.  (This %iterator does not @a move.)
00665       insert_iterator&
00666       operator++(int)
00667       { return *this; }
00668     };
00669 
00670   /**
00671    *  @param __x  A container of arbitrary type.
00672    *  @return  An instance of insert_iterator working on @p __x.
00673    *
00674    *  This wrapper function helps in creating insert_iterator instances.
00675    *  Typing the name of the %iterator requires knowing the precise full
00676    *  type of the container, which can be tedious and impedes generic
00677    *  programming.  Using this function lets you take advantage of automatic
00678    *  template parameter deduction, making the compiler match the correct
00679    *  types for you.
00680   */
00681   template<typename _Container, typename _Iterator>
00682     inline insert_iterator<_Container>
00683     inserter(_Container& __x, _Iterator __i)
00684     {
00685       return insert_iterator<_Container>(__x,
00686                      typename _Container::iterator(__i));
00687     }
00688 
00689   // @} group iterators
00690 
00691 _GLIBCXX_END_NAMESPACE_VERSION
00692 } // namespace
00693 
00694 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00695 {
00696 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00697 
00698   // This iterator adapter is @a normal in the sense that it does not
00699   // change the semantics of any of the operators of its iterator
00700   // parameter.  Its primary purpose is to convert an iterator that is
00701   // not a class, e.g. a pointer, into an iterator that is a class.
00702   // The _Container parameter exists solely so that different containers
00703   // using this template can instantiate different types, even if the
00704   // _Iterator parameter is the same.
00705   using std::iterator_traits;
00706   using std::iterator;
00707   template<typename _Iterator, typename _Container>
00708     class __normal_iterator
00709     {
00710     protected:
00711       _Iterator _M_current;
00712 
00713       typedef iterator_traits<_Iterator>        __traits_type;
00714 
00715     public:
00716       typedef _Iterator                 iterator_type;
00717       typedef typename __traits_type::iterator_category iterator_category;
00718       typedef typename __traits_type::value_type    value_type;
00719       typedef typename __traits_type::difference_type   difference_type;
00720       typedef typename __traits_type::reference     reference;
00721       typedef typename __traits_type::pointer       pointer;
00722 
00723       _GLIBCXX_CONSTEXPR __normal_iterator() : _M_current(_Iterator()) { }
00724 
00725       explicit
00726       __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
00727 
00728       // Allow iterator to const_iterator conversion
00729       template<typename _Iter>
00730         __normal_iterator(const __normal_iterator<_Iter,
00731               typename __enable_if<
00732                (std::__are_same<_Iter, typename _Container::pointer>::__value),
00733               _Container>::__type>& __i)
00734         : _M_current(__i.base()) { }
00735 
00736       // Forward iterator requirements
00737       reference
00738       operator*() const
00739       { return *_M_current; }
00740 
00741       pointer
00742       operator->() const
00743       { return _M_current; }
00744 
00745       __normal_iterator&
00746       operator++()
00747       {
00748     ++_M_current;
00749     return *this;
00750       }
00751 
00752       __normal_iterator
00753       operator++(int)
00754       { return __normal_iterator(_M_current++); }
00755 
00756       // Bidirectional iterator requirements
00757       __normal_iterator&
00758       operator--()
00759       {
00760     --_M_current;
00761     return *this;
00762       }
00763 
00764       __normal_iterator
00765       operator--(int)
00766       { return __normal_iterator(_M_current--); }
00767 
00768       // Random access iterator requirements
00769       reference
00770       operator[](const difference_type& __n) const
00771       { return _M_current[__n]; }
00772 
00773       __normal_iterator&
00774       operator+=(const difference_type& __n)
00775       { _M_current += __n; return *this; }
00776 
00777       __normal_iterator
00778       operator+(const difference_type& __n) const
00779       { return __normal_iterator(_M_current + __n); }
00780 
00781       __normal_iterator&
00782       operator-=(const difference_type& __n)
00783       { _M_current -= __n; return *this; }
00784 
00785       __normal_iterator
00786       operator-(const difference_type& __n) const
00787       { return __normal_iterator(_M_current - __n); }
00788 
00789       const _Iterator&
00790       base() const
00791       { return _M_current; }
00792     };
00793 
00794   // Note: In what follows, the left- and right-hand-side iterators are
00795   // allowed to vary in types (conceptually in cv-qualification) so that
00796   // comparison between cv-qualified and non-cv-qualified iterators be
00797   // valid.  However, the greedy and unfriendly operators in std::rel_ops
00798   // will make overload resolution ambiguous (when in scope) if we don't
00799   // provide overloads whose operands are of the same type.  Can someone
00800   // remind me what generic programming is about? -- Gaby
00801 
00802   // Forward iterator requirements
00803   template<typename _IteratorL, typename _IteratorR, typename _Container>
00804     inline bool
00805     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00806            const __normal_iterator<_IteratorR, _Container>& __rhs)
00807     { return __lhs.base() == __rhs.base(); }
00808 
00809   template<typename _Iterator, typename _Container>
00810     inline bool
00811     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00812            const __normal_iterator<_Iterator, _Container>& __rhs)
00813     { return __lhs.base() == __rhs.base(); }
00814 
00815   template<typename _IteratorL, typename _IteratorR, typename _Container>
00816     inline bool
00817     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00818            const __normal_iterator<_IteratorR, _Container>& __rhs)
00819     { return __lhs.base() != __rhs.base(); }
00820 
00821   template<typename _Iterator, typename _Container>
00822     inline bool
00823     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
00824            const __normal_iterator<_Iterator, _Container>& __rhs)
00825     { return __lhs.base() != __rhs.base(); }
00826 
00827   // Random access iterator requirements
00828   template<typename _IteratorL, typename _IteratorR, typename _Container>
00829     inline bool
00830     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00831           const __normal_iterator<_IteratorR, _Container>& __rhs)
00832     { return __lhs.base() < __rhs.base(); }
00833 
00834   template<typename _Iterator, typename _Container>
00835     inline bool
00836     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00837           const __normal_iterator<_Iterator, _Container>& __rhs)
00838     { return __lhs.base() < __rhs.base(); }
00839 
00840   template<typename _IteratorL, typename _IteratorR, typename _Container>
00841     inline bool
00842     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00843           const __normal_iterator<_IteratorR, _Container>& __rhs)
00844     { return __lhs.base() > __rhs.base(); }
00845 
00846   template<typename _Iterator, typename _Container>
00847     inline bool
00848     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00849           const __normal_iterator<_Iterator, _Container>& __rhs)
00850     { return __lhs.base() > __rhs.base(); }
00851 
00852   template<typename _IteratorL, typename _IteratorR, typename _Container>
00853     inline bool
00854     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00855            const __normal_iterator<_IteratorR, _Container>& __rhs)
00856     { return __lhs.base() <= __rhs.base(); }
00857 
00858   template<typename _Iterator, typename _Container>
00859     inline bool
00860     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00861            const __normal_iterator<_Iterator, _Container>& __rhs)
00862     { return __lhs.base() <= __rhs.base(); }
00863 
00864   template<typename _IteratorL, typename _IteratorR, typename _Container>
00865     inline bool
00866     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00867            const __normal_iterator<_IteratorR, _Container>& __rhs)
00868     { return __lhs.base() >= __rhs.base(); }
00869 
00870   template<typename _Iterator, typename _Container>
00871     inline bool
00872     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00873            const __normal_iterator<_Iterator, _Container>& __rhs)
00874     { return __lhs.base() >= __rhs.base(); }
00875 
00876   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00877   // According to the resolution of DR179 not only the various comparison
00878   // operators but also operator- must accept mixed iterator/const_iterator
00879   // parameters.
00880   template<typename _IteratorL, typename _IteratorR, typename _Container>
00881 #if __cplusplus >= 201103L
00882     // DR 685.
00883     inline auto
00884     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00885           const __normal_iterator<_IteratorR, _Container>& __rhs)
00886     -> decltype(__lhs.base() - __rhs.base())
00887 #else
00888     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00889     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00890           const __normal_iterator<_IteratorR, _Container>& __rhs)
00891 #endif
00892     { return __lhs.base() - __rhs.base(); }
00893 
00894   template<typename _Iterator, typename _Container>
00895     inline typename __normal_iterator<_Iterator, _Container>::difference_type
00896     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
00897           const __normal_iterator<_Iterator, _Container>& __rhs)
00898     { return __lhs.base() - __rhs.base(); }
00899 
00900   template<typename _Iterator, typename _Container>
00901     inline __normal_iterator<_Iterator, _Container>
00902     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
00903           __n, const __normal_iterator<_Iterator, _Container>& __i)
00904     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00905 
00906 _GLIBCXX_END_NAMESPACE_VERSION
00907 } // namespace
00908 
00909 #if __cplusplus >= 201103L
00910 
00911 namespace std _GLIBCXX_VISIBILITY(default)
00912 {
00913 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00914 
00915   /**
00916    * @addtogroup iterators
00917    * @{
00918    */
00919 
00920   // 24.4.3  Move iterators
00921   /**
00922    *  Class template move_iterator is an iterator adapter with the same
00923    *  behavior as the underlying iterator except that its dereference
00924    *  operator implicitly converts the value returned by the underlying
00925    *  iterator's dereference operator to an rvalue reference.  Some
00926    *  generic algorithms can be called with move iterators to replace
00927    *  copying with moving.
00928    */
00929   template<typename _Iterator>
00930     class move_iterator
00931     {
00932     protected:
00933       _Iterator _M_current;
00934 
00935       typedef iterator_traits<_Iterator>        __traits_type;
00936 
00937     public:
00938       typedef _Iterator                 iterator_type;
00939       typedef typename __traits_type::iterator_category iterator_category;
00940       typedef typename __traits_type::value_type    value_type;
00941       typedef typename __traits_type::difference_type   difference_type;
00942       // NB: DR 680.
00943       typedef _Iterator                 pointer;
00944       typedef value_type&&              reference;
00945 
00946       move_iterator()
00947       : _M_current() { }
00948 
00949       explicit
00950       move_iterator(iterator_type __i)
00951       : _M_current(__i) { }
00952 
00953       template<typename _Iter>
00954     move_iterator(const move_iterator<_Iter>& __i)
00955     : _M_current(__i.base()) { }
00956 
00957       iterator_type
00958       base() const
00959       { return _M_current; }
00960 
00961       reference
00962       operator*() const
00963       { return std::move(*_M_current); }
00964 
00965       pointer
00966       operator->() const
00967       { return _M_current; }
00968 
00969       move_iterator&
00970       operator++()
00971       {
00972     ++_M_current;
00973     return *this;
00974       }
00975 
00976       move_iterator
00977       operator++(int)
00978       {
00979     move_iterator __tmp = *this;
00980     ++_M_current;
00981     return __tmp;
00982       }
00983 
00984       move_iterator&
00985       operator--()
00986       {
00987     --_M_current;
00988     return *this;
00989       }
00990 
00991       move_iterator
00992       operator--(int)
00993       {
00994     move_iterator __tmp = *this;
00995     --_M_current;
00996     return __tmp;
00997       }
00998 
00999       move_iterator
01000       operator+(difference_type __n) const
01001       { return move_iterator(_M_current + __n); }
01002 
01003       move_iterator&
01004       operator+=(difference_type __n)
01005       {
01006     _M_current += __n;
01007     return *this;
01008       }
01009 
01010       move_iterator
01011       operator-(difference_type __n) const
01012       { return move_iterator(_M_current - __n); }
01013     
01014       move_iterator&
01015       operator-=(difference_type __n)
01016       { 
01017     _M_current -= __n;
01018     return *this;
01019       }
01020 
01021       reference
01022       operator[](difference_type __n) const
01023       { return std::move(_M_current[__n]); }
01024     };
01025 
01026   // Note: See __normal_iterator operators note from Gaby to understand
01027   // why there are always 2 versions for most of the move_iterator
01028   // operators.
01029   template<typename _IteratorL, typename _IteratorR>
01030     inline bool
01031     operator==(const move_iterator<_IteratorL>& __x,
01032            const move_iterator<_IteratorR>& __y)
01033     { return __x.base() == __y.base(); }
01034 
01035   template<typename _Iterator>
01036     inline bool
01037     operator==(const move_iterator<_Iterator>& __x,
01038            const move_iterator<_Iterator>& __y)
01039     { return __x.base() == __y.base(); }
01040 
01041   template<typename _IteratorL, typename _IteratorR>
01042     inline bool
01043     operator!=(const move_iterator<_IteratorL>& __x,
01044            const move_iterator<_IteratorR>& __y)
01045     { return !(__x == __y); }
01046 
01047   template<typename _Iterator>
01048     inline bool
01049     operator!=(const move_iterator<_Iterator>& __x,
01050            const move_iterator<_Iterator>& __y)
01051     { return !(__x == __y); }
01052 
01053   template<typename _IteratorL, typename _IteratorR>
01054     inline bool
01055     operator<(const move_iterator<_IteratorL>& __x,
01056           const move_iterator<_IteratorR>& __y)
01057     { return __x.base() < __y.base(); }
01058 
01059   template<typename _Iterator>
01060     inline bool
01061     operator<(const move_iterator<_Iterator>& __x,
01062           const move_iterator<_Iterator>& __y)
01063     { return __x.base() < __y.base(); }
01064 
01065   template<typename _IteratorL, typename _IteratorR>
01066     inline bool
01067     operator<=(const move_iterator<_IteratorL>& __x,
01068            const move_iterator<_IteratorR>& __y)
01069     { return !(__y < __x); }
01070 
01071   template<typename _Iterator>
01072     inline bool
01073     operator<=(const move_iterator<_Iterator>& __x,
01074            const move_iterator<_Iterator>& __y)
01075     { return !(__y < __x); }
01076 
01077   template<typename _IteratorL, typename _IteratorR>
01078     inline bool
01079     operator>(const move_iterator<_IteratorL>& __x,
01080           const move_iterator<_IteratorR>& __y)
01081     { return __y < __x; }
01082 
01083   template<typename _Iterator>
01084     inline bool
01085     operator>(const move_iterator<_Iterator>& __x,
01086           const move_iterator<_Iterator>& __y)
01087     { return __y < __x; }
01088 
01089   template<typename _IteratorL, typename _IteratorR>
01090     inline bool
01091     operator>=(const move_iterator<_IteratorL>& __x,
01092            const move_iterator<_IteratorR>& __y)
01093     { return !(__x < __y); }
01094 
01095   template<typename _Iterator>
01096     inline bool
01097     operator>=(const move_iterator<_Iterator>& __x,
01098            const move_iterator<_Iterator>& __y)
01099     { return !(__x < __y); }
01100 
01101   // DR 685.
01102   template<typename _IteratorL, typename _IteratorR>
01103     inline auto
01104     operator-(const move_iterator<_IteratorL>& __x,
01105           const move_iterator<_IteratorR>& __y)
01106     -> decltype(__x.base() - __y.base())
01107     { return __x.base() - __y.base(); }
01108 
01109   template<typename _Iterator>
01110     inline auto
01111     operator-(const move_iterator<_Iterator>& __x,
01112           const move_iterator<_Iterator>& __y)
01113     -> decltype(__x.base() - __y.base())
01114     { return __x.base() - __y.base(); }
01115 
01116   template<typename _Iterator>
01117     inline move_iterator<_Iterator>
01118     operator+(typename move_iterator<_Iterator>::difference_type __n,
01119           const move_iterator<_Iterator>& __x)
01120     { return __x + __n; }
01121 
01122   template<typename _Iterator>
01123     inline move_iterator<_Iterator>
01124     make_move_iterator(_Iterator __i)
01125     { return move_iterator<_Iterator>(__i); }
01126 
01127   template<typename _Iterator, typename _ReturnType
01128     = typename conditional<__move_if_noexcept_cond
01129       <typename iterator_traits<_Iterator>::value_type>::value,
01130                 _Iterator, move_iterator<_Iterator>>::type>
01131     inline _ReturnType
01132     __make_move_if_noexcept_iterator(_Iterator __i)
01133     { return _ReturnType(__i); }
01134 
01135   // @} group iterators
01136 
01137 _GLIBCXX_END_NAMESPACE_VERSION
01138 } // namespace
01139 
01140 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
01141 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
01142   std::__make_move_if_noexcept_iterator(_Iter)
01143 #else
01144 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
01145 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
01146 #endif // C++11
01147 
01148 #endif