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

Generated on Thu Jul 23 21:16:20 2009 for libstdc++ by  doxygen 1.5.8