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