stl_iterator.h

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