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