libstdc++
stl_iterator.h
Go to the documentation of this file.
00001 // Iterators -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2015 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 #if __cplusplus < 201103L
00328     inline typename reverse_iterator<_Iterator>::difference_type
00329     operator-(const reverse_iterator<_Iterator>& __x,
00330               const reverse_iterator<_Iterator>& __y)
00331 #else
00332     inline auto
00333     operator-(const reverse_iterator<_Iterator>& __x,
00334               const reverse_iterator<_Iterator>& __y)
00335     -> decltype(__x.base() - __y.base())
00336 #endif
00337     { return __y.base() - __x.base(); }
00338 
00339   template<typename _Iterator>
00340     inline reverse_iterator<_Iterator>
00341     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00342               const reverse_iterator<_Iterator>& __x)
00343     { return reverse_iterator<_Iterator>(__x.base() - __n); }
00344 
00345   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00346   // DR 280. Comparison of reverse_iterator to const reverse_iterator.
00347   template<typename _IteratorL, typename _IteratorR>
00348     inline bool
00349     operator==(const reverse_iterator<_IteratorL>& __x,
00350                const reverse_iterator<_IteratorR>& __y)
00351     { return __x.base() == __y.base(); }
00352 
00353   template<typename _IteratorL, typename _IteratorR>
00354     inline bool
00355     operator<(const reverse_iterator<_IteratorL>& __x,
00356               const reverse_iterator<_IteratorR>& __y)
00357     { return __y.base() < __x.base(); }
00358 
00359   template<typename _IteratorL, typename _IteratorR>
00360     inline bool
00361     operator!=(const reverse_iterator<_IteratorL>& __x,
00362                const reverse_iterator<_IteratorR>& __y)
00363     { return !(__x == __y); }
00364 
00365   template<typename _IteratorL, typename _IteratorR>
00366     inline bool
00367     operator>(const reverse_iterator<_IteratorL>& __x,
00368               const reverse_iterator<_IteratorR>& __y)
00369     { return __y < __x; }
00370 
00371   template<typename _IteratorL, typename _IteratorR>
00372     inline bool
00373     operator<=(const reverse_iterator<_IteratorL>& __x,
00374                const reverse_iterator<_IteratorR>& __y)
00375     { return !(__y < __x); }
00376 
00377   template<typename _IteratorL, typename _IteratorR>
00378     inline bool
00379     operator>=(const reverse_iterator<_IteratorL>& __x,
00380                const reverse_iterator<_IteratorR>& __y)
00381     { return !(__x < __y); }
00382 
00383   template<typename _IteratorL, typename _IteratorR>
00384 #if __cplusplus >= 201103L
00385     // DR 685.
00386     inline auto
00387     operator-(const reverse_iterator<_IteratorL>& __x,
00388               const reverse_iterator<_IteratorR>& __y)
00389     -> decltype(__y.base() - __x.base())
00390 #else
00391     inline typename reverse_iterator<_IteratorL>::difference_type
00392     operator-(const reverse_iterator<_IteratorL>& __x,
00393               const reverse_iterator<_IteratorR>& __y)
00394 #endif
00395     { return __y.base() - __x.base(); }
00396   //@}
00397 
00398 #if __cplusplus > 201103L
00399 #define __cpp_lib_make_reverse_iterator 201402
00400 
00401   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00402   // DR 2285. make_reverse_iterator
00403   /// Generator function for reverse_iterator.
00404   template<typename _Iterator>
00405     inline reverse_iterator<_Iterator>
00406     make_reverse_iterator(_Iterator __i)
00407     { return reverse_iterator<_Iterator>(__i); }
00408 #endif
00409 
00410   // 24.4.2.2.1 back_insert_iterator
00411   /**
00412    *  @brief  Turns assignment into insertion.
00413    *
00414    *  These are output iterators, constructed from a container-of-T.
00415    *  Assigning a T to the iterator appends it to the container using
00416    *  push_back.
00417    *
00418    *  Tip:  Using the back_inserter function to create these iterators can
00419    *  save typing.
00420   */
00421   template<typename _Container>
00422     class back_insert_iterator
00423     : public iterator<output_iterator_tag, void, void, void, void>
00424     {
00425     protected:
00426       _Container* container;
00427 
00428     public:
00429       /// A nested typedef for the type of whatever container you used.
00430       typedef _Container          container_type;
00431 
00432       /// The only way to create this %iterator is with a container.
00433       explicit
00434       back_insert_iterator(_Container& __x) : container(&__x) { }
00435 
00436       /**
00437        *  @param  __value  An instance of whatever type
00438        *                 container_type::const_reference is; presumably a
00439        *                 reference-to-const T for container<T>.
00440        *  @return  This %iterator, for chained operations.
00441        *
00442        *  This kind of %iterator doesn't really have a @a position in the
00443        *  container (you can think of the position as being permanently at
00444        *  the end, if you like).  Assigning a value to the %iterator will
00445        *  always append the value to the end of the container.
00446       */
00447 #if __cplusplus < 201103L
00448       back_insert_iterator&
00449       operator=(typename _Container::const_reference __value)
00450       {
00451         container->push_back(__value);
00452         return *this;
00453       }
00454 #else
00455       back_insert_iterator&
00456       operator=(const typename _Container::value_type& __value)
00457       {
00458         container->push_back(__value);
00459         return *this;
00460       }
00461 
00462       back_insert_iterator&
00463       operator=(typename _Container::value_type&& __value)
00464       {
00465         container->push_back(std::move(__value));
00466         return *this;
00467       }
00468 #endif
00469 
00470       /// Simply returns *this.
00471       back_insert_iterator&
00472       operator*()
00473       { return *this; }
00474 
00475       /// Simply returns *this.  (This %iterator does not @a move.)
00476       back_insert_iterator&
00477       operator++()
00478       { return *this; }
00479 
00480       /// Simply returns *this.  (This %iterator does not @a move.)
00481       back_insert_iterator
00482       operator++(int)
00483       { return *this; }
00484     };
00485 
00486   /**
00487    *  @param  __x  A container of arbitrary type.
00488    *  @return  An instance of back_insert_iterator working on @p __x.
00489    *
00490    *  This wrapper function helps in creating back_insert_iterator instances.
00491    *  Typing the name of the %iterator requires knowing the precise full
00492    *  type of the container, which can be tedious and impedes generic
00493    *  programming.  Using this function lets you take advantage of automatic
00494    *  template parameter deduction, making the compiler match the correct
00495    *  types for you.
00496   */
00497   template<typename _Container>
00498     inline back_insert_iterator<_Container>
00499     back_inserter(_Container& __x)
00500     { return back_insert_iterator<_Container>(__x); }
00501 
00502   /**
00503    *  @brief  Turns assignment into insertion.
00504    *
00505    *  These are output iterators, constructed from a container-of-T.
00506    *  Assigning a T to the iterator prepends it to the container using
00507    *  push_front.
00508    *
00509    *  Tip:  Using the front_inserter function to create these iterators can
00510    *  save typing.
00511   */
00512   template<typename _Container>
00513     class front_insert_iterator
00514     : public iterator<output_iterator_tag, void, void, void, void>
00515     {
00516     protected:
00517       _Container* container;
00518 
00519     public:
00520       /// A nested typedef for the type of whatever container you used.
00521       typedef _Container          container_type;
00522 
00523       /// The only way to create this %iterator is with a container.
00524       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
00525 
00526       /**
00527        *  @param  __value  An instance of whatever type
00528        *                 container_type::const_reference is; presumably a
00529        *                 reference-to-const T for container<T>.
00530        *  @return  This %iterator, for chained operations.
00531        *
00532        *  This kind of %iterator doesn't really have a @a position in the
00533        *  container (you can think of the position as being permanently at
00534        *  the front, if you like).  Assigning a value to the %iterator will
00535        *  always prepend the value to the front of the container.
00536       */
00537 #if __cplusplus < 201103L
00538       front_insert_iterator&
00539       operator=(typename _Container::const_reference __value)
00540       {
00541         container->push_front(__value);
00542         return *this;
00543       }
00544 #else
00545       front_insert_iterator&
00546       operator=(const typename _Container::value_type& __value)
00547       {
00548         container->push_front(__value);
00549         return *this;
00550       }
00551 
00552       front_insert_iterator&
00553       operator=(typename _Container::value_type&& __value)
00554       {
00555         container->push_front(std::move(__value));
00556         return *this;
00557       }
00558 #endif
00559 
00560       /// Simply returns *this.
00561       front_insert_iterator&
00562       operator*()
00563       { return *this; }
00564 
00565       /// Simply returns *this.  (This %iterator does not @a move.)
00566       front_insert_iterator&
00567       operator++()
00568       { return *this; }
00569 
00570       /// Simply returns *this.  (This %iterator does not @a move.)
00571       front_insert_iterator
00572       operator++(int)
00573       { return *this; }
00574     };
00575 
00576   /**
00577    *  @param  __x  A container of arbitrary type.
00578    *  @return  An instance of front_insert_iterator working on @p x.
00579    *
00580    *  This wrapper function helps in creating front_insert_iterator instances.
00581    *  Typing the name of the %iterator requires knowing the precise full
00582    *  type of the container, which can be tedious and impedes generic
00583    *  programming.  Using this function lets you take advantage of automatic
00584    *  template parameter deduction, making the compiler match the correct
00585    *  types for you.
00586   */
00587   template<typename _Container>
00588     inline front_insert_iterator<_Container>
00589     front_inserter(_Container& __x)
00590     { return front_insert_iterator<_Container>(__x); }
00591 
00592   /**
00593    *  @brief  Turns assignment into insertion.
00594    *
00595    *  These are output iterators, constructed from a container-of-T.
00596    *  Assigning a T to the iterator inserts it in the container at the
00597    *  %iterator's position, rather than overwriting the value at that
00598    *  position.
00599    *
00600    *  (Sequences will actually insert a @e copy of the value before the
00601    *  %iterator's position.)
00602    *
00603    *  Tip:  Using the inserter function to create these iterators can
00604    *  save typing.
00605   */
00606   template<typename _Container>
00607     class insert_iterator
00608     : public iterator<output_iterator_tag, void, void, void, void>
00609     {
00610     protected:
00611       _Container* container;
00612       typename _Container::iterator iter;
00613 
00614     public:
00615       /// A nested typedef for the type of whatever container you used.
00616       typedef _Container          container_type;
00617 
00618       /**
00619        *  The only way to create this %iterator is with a container and an
00620        *  initial position (a normal %iterator into the container).
00621       */
00622       insert_iterator(_Container& __x, typename _Container::iterator __i)
00623       : container(&__x), iter(__i) {}
00624 
00625       /**
00626        *  @param  __value  An instance of whatever type
00627        *                 container_type::const_reference is; presumably a
00628        *                 reference-to-const T for container<T>.
00629        *  @return  This %iterator, for chained operations.
00630        *
00631        *  This kind of %iterator maintains its own position in the
00632        *  container.  Assigning a value to the %iterator will insert the
00633        *  value into the container at the place before the %iterator.
00634        *
00635        *  The position is maintained such that subsequent assignments will
00636        *  insert values immediately after one another.  For example,
00637        *  @code
00638        *     // vector v contains A and Z
00639        *
00640        *     insert_iterator i (v, ++v.begin());
00641        *     i = 1;
00642        *     i = 2;
00643        *     i = 3;
00644        *
00645        *     // vector v contains A, 1, 2, 3, and Z
00646        *  @endcode
00647       */
00648 #if __cplusplus < 201103L
00649       insert_iterator&
00650       operator=(typename _Container::const_reference __value)
00651       {
00652         iter = container->insert(iter, __value);
00653         ++iter;
00654         return *this;
00655       }
00656 #else
00657       insert_iterator&
00658       operator=(const typename _Container::value_type& __value)
00659       {
00660         iter = container->insert(iter, __value);
00661         ++iter;
00662         return *this;
00663       }
00664 
00665       insert_iterator&
00666       operator=(typename _Container::value_type&& __value)
00667       {
00668         iter = container->insert(iter, std::move(__value));
00669         ++iter;
00670         return *this;
00671       }
00672 #endif
00673 
00674       /// Simply returns *this.
00675       insert_iterator&
00676       operator*()
00677       { return *this; }
00678 
00679       /// Simply returns *this.  (This %iterator does not @a move.)
00680       insert_iterator&
00681       operator++()
00682       { return *this; }
00683 
00684       /// Simply returns *this.  (This %iterator does not @a move.)
00685       insert_iterator&
00686       operator++(int)
00687       { return *this; }
00688     };
00689 
00690   /**
00691    *  @param __x  A container of arbitrary type.
00692    *  @return  An instance of insert_iterator working on @p __x.
00693    *
00694    *  This wrapper function helps in creating insert_iterator instances.
00695    *  Typing the name of the %iterator requires knowing the precise full
00696    *  type of the container, which can be tedious and impedes generic
00697    *  programming.  Using this function lets you take advantage of automatic
00698    *  template parameter deduction, making the compiler match the correct
00699    *  types for you.
00700   */
00701   template<typename _Container, typename _Iterator>
00702     inline insert_iterator<_Container>
00703     inserter(_Container& __x, _Iterator __i)
00704     {
00705       return insert_iterator<_Container>(__x,
00706                                          typename _Container::iterator(__i));
00707     }
00708 
00709   // @} group iterators
00710 
00711 _GLIBCXX_END_NAMESPACE_VERSION
00712 } // namespace
00713 
00714 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00715 {
00716 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00717 
00718   // This iterator adapter is @a normal in the sense that it does not
00719   // change the semantics of any of the operators of its iterator
00720   // parameter.  Its primary purpose is to convert an iterator that is
00721   // not a class, e.g. a pointer, into an iterator that is a class.
00722   // The _Container parameter exists solely so that different containers
00723   // using this template can instantiate different types, even if the
00724   // _Iterator parameter is the same.
00725   using std::iterator_traits;
00726   using std::iterator;
00727   template<typename _Iterator, typename _Container>
00728     class __normal_iterator
00729     {
00730     protected:
00731       _Iterator _M_current;
00732 
00733       typedef iterator_traits<_Iterator>                __traits_type;
00734 
00735     public:
00736       typedef _Iterator                                 iterator_type;
00737       typedef typename __traits_type::iterator_category iterator_category;
00738       typedef typename __traits_type::value_type        value_type;
00739       typedef typename __traits_type::difference_type   difference_type;
00740       typedef typename __traits_type::reference         reference;
00741       typedef typename __traits_type::pointer           pointer;
00742 
00743       _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
00744       : _M_current(_Iterator()) { }
00745 
00746       explicit
00747       __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
00748       : _M_current(__i) { }
00749 
00750       // Allow iterator to const_iterator conversion
00751       template<typename _Iter>
00752         __normal_iterator(const __normal_iterator<_Iter,
00753                           typename __enable_if<
00754                (std::__are_same<_Iter, typename _Container::pointer>::__value),
00755                       _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
00756         : _M_current(__i.base()) { }
00757 
00758       // Forward iterator requirements
00759       reference
00760       operator*() const _GLIBCXX_NOEXCEPT
00761       { return *_M_current; }
00762 
00763       pointer
00764       operator->() const _GLIBCXX_NOEXCEPT
00765       { return _M_current; }
00766 
00767       __normal_iterator&
00768       operator++() _GLIBCXX_NOEXCEPT
00769       {
00770         ++_M_current;
00771         return *this;
00772       }
00773 
00774       __normal_iterator
00775       operator++(int) _GLIBCXX_NOEXCEPT
00776       { return __normal_iterator(_M_current++); }
00777 
00778       // Bidirectional iterator requirements
00779       __normal_iterator&
00780       operator--() _GLIBCXX_NOEXCEPT
00781       {
00782         --_M_current;
00783         return *this;
00784       }
00785 
00786       __normal_iterator
00787       operator--(int) _GLIBCXX_NOEXCEPT
00788       { return __normal_iterator(_M_current--); }
00789 
00790       // Random access iterator requirements
00791       reference
00792       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
00793       { return _M_current[__n]; }
00794 
00795       __normal_iterator&
00796       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
00797       { _M_current += __n; return *this; }
00798 
00799       __normal_iterator
00800       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
00801       { return __normal_iterator(_M_current + __n); }
00802 
00803       __normal_iterator&
00804       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
00805       { _M_current -= __n; return *this; }
00806 
00807       __normal_iterator
00808       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
00809       { return __normal_iterator(_M_current - __n); }
00810 
00811       const _Iterator&
00812       base() const _GLIBCXX_NOEXCEPT
00813       { return _M_current; }
00814     };
00815 
00816   // Note: In what follows, the left- and right-hand-side iterators are
00817   // allowed to vary in types (conceptually in cv-qualification) so that
00818   // comparison between cv-qualified and non-cv-qualified iterators be
00819   // valid.  However, the greedy and unfriendly operators in std::rel_ops
00820   // will make overload resolution ambiguous (when in scope) if we don't
00821   // provide overloads whose operands are of the same type.  Can someone
00822   // remind me what generic programming is about? -- Gaby
00823 
00824   // Forward iterator requirements
00825   template<typename _IteratorL, typename _IteratorR, typename _Container>
00826     inline bool
00827     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00828                const __normal_iterator<_IteratorR, _Container>& __rhs)
00829     _GLIBCXX_NOEXCEPT
00830     { return __lhs.base() == __rhs.base(); }
00831 
00832   template<typename _Iterator, typename _Container>
00833     inline bool
00834     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00835                const __normal_iterator<_Iterator, _Container>& __rhs)
00836     _GLIBCXX_NOEXCEPT
00837     { return __lhs.base() == __rhs.base(); }
00838 
00839   template<typename _IteratorL, typename _IteratorR, typename _Container>
00840     inline bool
00841     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00842                const __normal_iterator<_IteratorR, _Container>& __rhs)
00843     _GLIBCXX_NOEXCEPT
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     _GLIBCXX_NOEXCEPT
00851     { return __lhs.base() != __rhs.base(); }
00852 
00853   // Random access iterator requirements
00854   template<typename _IteratorL, typename _IteratorR, typename _Container>
00855     inline bool
00856     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00857               const __normal_iterator<_IteratorR, _Container>& __rhs)
00858     _GLIBCXX_NOEXCEPT
00859     { return __lhs.base() < __rhs.base(); }
00860 
00861   template<typename _Iterator, typename _Container>
00862     inline bool
00863     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00864               const __normal_iterator<_Iterator, _Container>& __rhs)
00865     _GLIBCXX_NOEXCEPT
00866     { return __lhs.base() < __rhs.base(); }
00867 
00868   template<typename _IteratorL, typename _IteratorR, typename _Container>
00869     inline bool
00870     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00871               const __normal_iterator<_IteratorR, _Container>& __rhs)
00872     _GLIBCXX_NOEXCEPT
00873     { return __lhs.base() > __rhs.base(); }
00874 
00875   template<typename _Iterator, typename _Container>
00876     inline bool
00877     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00878               const __normal_iterator<_Iterator, _Container>& __rhs)
00879     _GLIBCXX_NOEXCEPT
00880     { return __lhs.base() > __rhs.base(); }
00881 
00882   template<typename _IteratorL, typename _IteratorR, typename _Container>
00883     inline bool
00884     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00885                const __normal_iterator<_IteratorR, _Container>& __rhs)
00886     _GLIBCXX_NOEXCEPT
00887     { return __lhs.base() <= __rhs.base(); }
00888 
00889   template<typename _Iterator, typename _Container>
00890     inline bool
00891     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00892                const __normal_iterator<_Iterator, _Container>& __rhs)
00893     _GLIBCXX_NOEXCEPT
00894     { return __lhs.base() <= __rhs.base(); }
00895 
00896   template<typename _IteratorL, typename _IteratorR, typename _Container>
00897     inline bool
00898     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00899                const __normal_iterator<_IteratorR, _Container>& __rhs)
00900     _GLIBCXX_NOEXCEPT
00901     { return __lhs.base() >= __rhs.base(); }
00902 
00903   template<typename _Iterator, typename _Container>
00904     inline bool
00905     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00906                const __normal_iterator<_Iterator, _Container>& __rhs)
00907     _GLIBCXX_NOEXCEPT
00908     { return __lhs.base() >= __rhs.base(); }
00909 
00910   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00911   // According to the resolution of DR179 not only the various comparison
00912   // operators but also operator- must accept mixed iterator/const_iterator
00913   // parameters.
00914   template<typename _IteratorL, typename _IteratorR, typename _Container>
00915 #if __cplusplus >= 201103L
00916     // DR 685.
00917     inline auto
00918     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00919               const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
00920     -> decltype(__lhs.base() - __rhs.base())
00921 #else
00922     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00923     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00924               const __normal_iterator<_IteratorR, _Container>& __rhs)
00925 #endif
00926     { return __lhs.base() - __rhs.base(); }
00927 
00928   template<typename _Iterator, typename _Container>
00929     inline typename __normal_iterator<_Iterator, _Container>::difference_type
00930     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
00931               const __normal_iterator<_Iterator, _Container>& __rhs)
00932     _GLIBCXX_NOEXCEPT
00933     { return __lhs.base() - __rhs.base(); }
00934 
00935   template<typename _Iterator, typename _Container>
00936     inline __normal_iterator<_Iterator, _Container>
00937     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
00938               __n, const __normal_iterator<_Iterator, _Container>& __i)
00939     _GLIBCXX_NOEXCEPT
00940     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00941 
00942 _GLIBCXX_END_NAMESPACE_VERSION
00943 } // namespace
00944 
00945 #if __cplusplus >= 201103L
00946 
00947 namespace std _GLIBCXX_VISIBILITY(default)
00948 {
00949 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00950 
00951   /**
00952    * @addtogroup iterators
00953    * @{
00954    */
00955 
00956   // 24.4.3  Move iterators
00957   /**
00958    *  Class template move_iterator is an iterator adapter with the same
00959    *  behavior as the underlying iterator except that its dereference
00960    *  operator implicitly converts the value returned by the underlying
00961    *  iterator's dereference operator to an rvalue reference.  Some
00962    *  generic algorithms can be called with move iterators to replace
00963    *  copying with moving.
00964    */
00965   template<typename _Iterator>
00966     class move_iterator
00967     {
00968     protected:
00969       _Iterator _M_current;
00970 
00971       typedef iterator_traits<_Iterator>                __traits_type;
00972       typedef typename __traits_type::reference         __base_ref;
00973 
00974     public:
00975       typedef _Iterator                                 iterator_type;
00976       typedef typename __traits_type::iterator_category iterator_category;
00977       typedef typename __traits_type::value_type        value_type;
00978       typedef typename __traits_type::difference_type   difference_type;
00979       // NB: DR 680.
00980       typedef _Iterator                                 pointer;
00981       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00982       // 2106. move_iterator wrapping iterators returning prvalues
00983       typedef typename conditional<is_reference<__base_ref>::value,
00984                          typename remove_reference<__base_ref>::type&&,
00985                          __base_ref>::type              reference;
00986 
00987       move_iterator()
00988       : _M_current() { }
00989 
00990       explicit
00991       move_iterator(iterator_type __i)
00992       : _M_current(__i) { }
00993 
00994       template<typename _Iter>
00995         move_iterator(const move_iterator<_Iter>& __i)
00996         : _M_current(__i.base()) { }
00997 
00998       iterator_type
00999       base() const
01000       { return _M_current; }
01001 
01002       reference
01003       operator*() const
01004       { return static_cast<reference>(*_M_current); }
01005 
01006       pointer
01007       operator->() const
01008       { return _M_current; }
01009 
01010       move_iterator&
01011       operator++()
01012       {
01013         ++_M_current;
01014         return *this;
01015       }
01016 
01017       move_iterator
01018       operator++(int)
01019       {
01020         move_iterator __tmp = *this;
01021         ++_M_current;
01022         return __tmp;
01023       }
01024 
01025       move_iterator&
01026       operator--()
01027       {
01028         --_M_current;
01029         return *this;
01030       }
01031 
01032       move_iterator
01033       operator--(int)
01034       {
01035         move_iterator __tmp = *this;
01036         --_M_current;
01037         return __tmp;
01038       }
01039 
01040       move_iterator
01041       operator+(difference_type __n) const
01042       { return move_iterator(_M_current + __n); }
01043 
01044       move_iterator&
01045       operator+=(difference_type __n)
01046       {
01047         _M_current += __n;
01048         return *this;
01049       }
01050 
01051       move_iterator
01052       operator-(difference_type __n) const
01053       { return move_iterator(_M_current - __n); }
01054     
01055       move_iterator&
01056       operator-=(difference_type __n)
01057       { 
01058         _M_current -= __n;
01059         return *this;
01060       }
01061 
01062       reference
01063       operator[](difference_type __n) const
01064       { return std::move(_M_current[__n]); }
01065     };
01066 
01067   // Note: See __normal_iterator operators note from Gaby to understand
01068   // why there are always 2 versions for most of the move_iterator
01069   // operators.
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 !(__x == __y); }
01087 
01088   template<typename _Iterator>
01089     inline bool
01090     operator!=(const move_iterator<_Iterator>& __x,
01091                const move_iterator<_Iterator>& __y)
01092     { return !(__x == __y); }
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 __x.base() < __y.base(); }
01099 
01100   template<typename _Iterator>
01101     inline bool
01102     operator<(const move_iterator<_Iterator>& __x,
01103               const move_iterator<_Iterator>& __y)
01104     { return __x.base() < __y.base(); }
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 !(__y < __x); }
01111 
01112   template<typename _Iterator>
01113     inline bool
01114     operator<=(const move_iterator<_Iterator>& __x,
01115                const move_iterator<_Iterator>& __y)
01116     { return !(__y < __x); }
01117 
01118   template<typename _IteratorL, typename _IteratorR>
01119     inline bool
01120     operator>(const move_iterator<_IteratorL>& __x,
01121               const move_iterator<_IteratorR>& __y)
01122     { return __y < __x; }
01123 
01124   template<typename _Iterator>
01125     inline bool
01126     operator>(const move_iterator<_Iterator>& __x,
01127               const move_iterator<_Iterator>& __y)
01128     { return __y < __x; }
01129 
01130   template<typename _IteratorL, typename _IteratorR>
01131     inline bool
01132     operator>=(const move_iterator<_IteratorL>& __x,
01133                const move_iterator<_IteratorR>& __y)
01134     { return !(__x < __y); }
01135 
01136   template<typename _Iterator>
01137     inline bool
01138     operator>=(const move_iterator<_Iterator>& __x,
01139                const move_iterator<_Iterator>& __y)
01140     { return !(__x < __y); }
01141 
01142   // DR 685.
01143   template<typename _IteratorL, typename _IteratorR>
01144     inline auto
01145     operator-(const move_iterator<_IteratorL>& __x,
01146               const move_iterator<_IteratorR>& __y)
01147     -> decltype(__x.base() - __y.base())
01148     { return __x.base() - __y.base(); }
01149 
01150   template<typename _Iterator>
01151     inline auto
01152     operator-(const move_iterator<_Iterator>& __x,
01153               const move_iterator<_Iterator>& __y)
01154     -> decltype(__x.base() - __y.base())
01155     { return __x.base() - __y.base(); }
01156 
01157   template<typename _Iterator>
01158     inline move_iterator<_Iterator>
01159     operator+(typename move_iterator<_Iterator>::difference_type __n,
01160               const move_iterator<_Iterator>& __x)
01161     { return __x + __n; }
01162 
01163   template<typename _Iterator>
01164     inline move_iterator<_Iterator>
01165     make_move_iterator(_Iterator __i)
01166     { return move_iterator<_Iterator>(__i); }
01167 
01168   template<typename _Iterator, typename _ReturnType
01169     = typename conditional<__move_if_noexcept_cond
01170       <typename iterator_traits<_Iterator>::value_type>::value,
01171                 _Iterator, move_iterator<_Iterator>>::type>
01172     inline _ReturnType
01173     __make_move_if_noexcept_iterator(_Iterator __i)
01174     { return _ReturnType(__i); }
01175 
01176   // @} group iterators
01177 
01178 _GLIBCXX_END_NAMESPACE_VERSION
01179 } // namespace
01180 
01181 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
01182 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
01183   std::__make_move_if_noexcept_iterator(_Iter)
01184 #else
01185 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
01186 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
01187 #endif // C++11
01188 
01189 #endif