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
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 2, 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 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /*
00032  *
00033  * Copyright (c) 1994
00034  * Hewlett-Packard Company
00035  *
00036  * Permission to use, copy, modify, distribute and sell this software
00037  * and its documentation for any purpose is hereby granted without fee,
00038  * provided that the above copyright notice appear in all copies and
00039  * that both that copyright notice and this permission notice appear
00040  * in supporting documentation.  Hewlett-Packard Company makes no
00041  * representations about the suitability of this software for any
00042  * purpose.  It is provided "as is" without express or implied warranty.
00043  *
00044  *
00045  * Copyright (c) 1996-1998
00046  * Silicon Graphics Computer Systems, Inc.
00047  *
00048  * Permission to use, copy, modify, distribute and sell this software
00049  * and its documentation for any purpose is hereby granted without fee,
00050  * provided that the above copyright notice appear in all copies and
00051  * that both that copyright notice and this permission notice appear
00052  * in supporting documentation.  Silicon Graphics makes no
00053  * representations about the suitability of this software for any
00054  * purpose.  It is provided "as is" without express or implied warranty.
00055  */
00056 
00057 /** @file stl_iterator.h
00058  *  This is an internal header file, included by other library headers.
00059  *  You should not attempt to use it directly.
00060  *
00061  *  This file implements reverse_iterator, back_insert_iterator,
00062  *  front_insert_iterator, insert_iterator, __normal_iterator, and their
00063  *  supporting functions and overloaded operators.
00064  */
00065 
00066 #ifndef _STL_ITERATOR_H
00067 #define _STL_ITERATOR_H 1
00068 
00069 #include <bits/cpp_type_traits.h>
00070 #include <ext/type_traits.h>
00071 #include <bits/stl_move.h>
00072 
00073 _GLIBCXX_BEGIN_NAMESPACE(std)
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    *  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." [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     public:
00106       typedef _Iterator                        iterator_type;
00107       typedef typename iterator_traits<_Iterator>::difference_type
00108                                    difference_type;
00109       typedef typename iterator_traits<_Iterator>::reference   reference;
00110       typedef typename iterator_traits<_Iterator>::pointer     pointer;
00111 
00112     public:
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     inline typename reverse_iterator<_IteratorL>::difference_type
00369     operator-(const reverse_iterator<_IteratorL>& __x,
00370           const reverse_iterator<_IteratorR>& __y)
00371     { return __y.base() - __x.base(); }
00372   //@}
00373 
00374   // 24.4.2.2.1 back_insert_iterator
00375   /**
00376    *  @brief  Turns assignment into insertion.
00377    *
00378    *  These are output iterators, constructed from a container-of-T.
00379    *  Assigning a T to the iterator appends it to the container using
00380    *  push_back.
00381    *
00382    *  Tip:  Using the back_inserter function to create these iterators can
00383    *  save typing.
00384   */
00385   template<typename _Container>
00386     class back_insert_iterator
00387     : public iterator<output_iterator_tag, void, void, void, void>
00388     {
00389     protected:
00390       _Container* container;
00391 
00392     public:
00393       /// A nested typedef for the type of whatever container you used.
00394       typedef _Container          container_type;
00395 
00396       /// The only way to create this %iterator is with a container.
00397       explicit
00398       back_insert_iterator(_Container& __x) : container(&__x) { }
00399 
00400       /**
00401        *  @param  value  An instance of whatever type
00402        *                 container_type::const_reference is; presumably a
00403        *                 reference-to-const T for container<T>.
00404        *  @return  This %iterator, for chained operations.
00405        *
00406        *  This kind of %iterator doesn't really have a "position" in the
00407        *  container (you can think of the position as being permanently at
00408        *  the end, if you like).  Assigning a value to the %iterator will
00409        *  always append the value to the end of the container.
00410       */
00411       back_insert_iterator&
00412       operator=(typename _Container::const_reference __value)
00413       {
00414     container->push_back(__value);
00415     return *this;
00416       }
00417 
00418 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00419       back_insert_iterator&
00420       operator=(typename _Container::value_type&& __value)
00421       {
00422     container->push_back(std::move(__value));
00423     return *this;
00424       }
00425 #endif
00426 
00427       /// Simply returns *this.
00428       back_insert_iterator&
00429       operator*()
00430       { return *this; }
00431 
00432       /// Simply returns *this.  (This %iterator does not "move".)
00433       back_insert_iterator&
00434       operator++()
00435       { return *this; }
00436 
00437       /// Simply returns *this.  (This %iterator does not "move".)
00438       back_insert_iterator
00439       operator++(int)
00440       { return *this; }
00441     };
00442 
00443   /**
00444    *  @param  x  A container of arbitrary type.
00445    *  @return  An instance of back_insert_iterator working on @p x.
00446    *
00447    *  This wrapper function helps in creating back_insert_iterator instances.
00448    *  Typing the name of the %iterator requires knowing the precise full
00449    *  type of the container, which can be tedious and impedes generic
00450    *  programming.  Using this function lets you take advantage of automatic
00451    *  template parameter deduction, making the compiler match the correct
00452    *  types for you.
00453   */
00454   template<typename _Container>
00455     inline back_insert_iterator<_Container>
00456     back_inserter(_Container& __x)
00457     { return back_insert_iterator<_Container>(__x); }
00458 
00459   /**
00460    *  @brief  Turns assignment into insertion.
00461    *
00462    *  These are output iterators, constructed from a container-of-T.
00463    *  Assigning a T to the iterator prepends it to the container using
00464    *  push_front.
00465    *
00466    *  Tip:  Using the front_inserter function to create these iterators can
00467    *  save typing.
00468   */
00469   template<typename _Container>
00470     class front_insert_iterator
00471     : public iterator<output_iterator_tag, void, void, void, void>
00472     {
00473     protected:
00474       _Container* container;
00475 
00476     public:
00477       /// A nested typedef for the type of whatever container you used.
00478       typedef _Container          container_type;
00479 
00480       /// The only way to create this %iterator is with a container.
00481       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
00482 
00483       /**
00484        *  @param  value  An instance of whatever type
00485        *                 container_type::const_reference is; presumably a
00486        *                 reference-to-const T for container<T>.
00487        *  @return  This %iterator, for chained operations.
00488        *
00489        *  This kind of %iterator doesn't really have a "position" in the
00490        *  container (you can think of the position as being permanently at
00491        *  the front, if you like).  Assigning a value to the %iterator will
00492        *  always prepend the value to the front of the container.
00493       */
00494       front_insert_iterator&
00495       operator=(typename _Container::const_reference __value)
00496       {
00497     container->push_front(__value);
00498     return *this;
00499       }
00500 
00501 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00502       front_insert_iterator&
00503       operator=(typename _Container::value_type&& __value)
00504       {
00505     container->push_front(std::move(__value));
00506     return *this;
00507       }
00508 #endif
00509 
00510       /// Simply returns *this.
00511       front_insert_iterator&
00512       operator*()
00513       { return *this; }
00514 
00515       /// Simply returns *this.  (This %iterator does not "move".)
00516       front_insert_iterator&
00517       operator++()
00518       { return *this; }
00519 
00520       /// Simply returns *this.  (This %iterator does not "move".)
00521       front_insert_iterator
00522       operator++(int)
00523       { return *this; }
00524     };
00525 
00526   /**
00527    *  @param  x  A container of arbitrary type.
00528    *  @return  An instance of front_insert_iterator working on @p x.
00529    *
00530    *  This wrapper function helps in creating front_insert_iterator instances.
00531    *  Typing the name of the %iterator requires knowing the precise full
00532    *  type of the container, which can be tedious and impedes generic
00533    *  programming.  Using this function lets you take advantage of automatic
00534    *  template parameter deduction, making the compiler match the correct
00535    *  types for you.
00536   */
00537   template<typename _Container>
00538     inline front_insert_iterator<_Container>
00539     front_inserter(_Container& __x)
00540     { return front_insert_iterator<_Container>(__x); }
00541 
00542   /**
00543    *  @brief  Turns assignment into insertion.
00544    *
00545    *  These are output iterators, constructed from a container-of-T.
00546    *  Assigning a T to the iterator inserts it in the container at the
00547    *  %iterator's position, rather than overwriting the value at that
00548    *  position.
00549    *
00550    *  (Sequences will actually insert a @e copy of the value before the
00551    *  %iterator's position.)
00552    *
00553    *  Tip:  Using the inserter function to create these iterators can
00554    *  save typing.
00555   */
00556   template<typename _Container>
00557     class insert_iterator
00558     : public iterator<output_iterator_tag, void, void, void, void>
00559     {
00560     protected:
00561       _Container* container;
00562       typename _Container::iterator iter;
00563 
00564     public:
00565       /// A nested typedef for the type of whatever container you used.
00566       typedef _Container          container_type;
00567 
00568       /**
00569        *  The only way to create this %iterator is with a container and an
00570        *  initial position (a normal %iterator into the container).
00571       */
00572       insert_iterator(_Container& __x, typename _Container::iterator __i)
00573       : container(&__x), iter(__i) {}
00574 
00575       /**
00576        *  @param  value  An instance of whatever type
00577        *                 container_type::const_reference is; presumably a
00578        *                 reference-to-const T for container<T>.
00579        *  @return  This %iterator, for chained operations.
00580        *
00581        *  This kind of %iterator maintains its own position in the
00582        *  container.  Assigning a value to the %iterator will insert the
00583        *  value into the container at the place before the %iterator.
00584        *
00585        *  The position is maintained such that subsequent assignments will
00586        *  insert values immediately after one another.  For example,
00587        *  @code
00588        *     // vector v contains A and Z
00589        *
00590        *     insert_iterator i (v, ++v.begin());
00591        *     i = 1;
00592        *     i = 2;
00593        *     i = 3;
00594        *
00595        *     // vector v contains A, 1, 2, 3, and Z
00596        *  @endcode
00597       */
00598       insert_iterator&
00599       operator=(typename _Container::const_reference __value)
00600       {
00601     iter = container->insert(iter, __value);
00602     ++iter;
00603     return *this;
00604       }
00605 
00606 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00607       insert_iterator&
00608       operator=(typename _Container::value_type&& __value)
00609       {
00610     iter = container->insert(iter, std::move(__value));
00611     ++iter;
00612     return *this;
00613       }
00614 #endif
00615 
00616       /// Simply returns *this.
00617       insert_iterator&
00618       operator*()
00619       { return *this; }
00620 
00621       /// Simply returns *this.  (This %iterator does not "move".)
00622       insert_iterator&
00623       operator++()
00624       { return *this; }
00625 
00626       /// Simply returns *this.  (This %iterator does not "move".)
00627       insert_iterator&
00628       operator++(int)
00629       { return *this; }
00630     };
00631 
00632   /**
00633    *  @param  x  A container of arbitrary type.
00634    *  @return  An instance of insert_iterator working on @p x.
00635    *
00636    *  This wrapper function helps in creating insert_iterator instances.
00637    *  Typing the name of the %iterator requires knowing the precise full
00638    *  type of the container, which can be tedious and impedes generic
00639    *  programming.  Using this function lets you take advantage of automatic
00640    *  template parameter deduction, making the compiler match the correct
00641    *  types for you.
00642   */
00643   template<typename _Container, typename _Iterator>
00644     inline insert_iterator<_Container>
00645     inserter(_Container& __x, _Iterator __i)
00646     {
00647       return insert_iterator<_Container>(__x,
00648                      typename _Container::iterator(__i));
00649     }
00650 
00651 _GLIBCXX_END_NAMESPACE
00652 
00653 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00654 
00655   // This iterator adapter is 'normal' in the sense that it does not
00656   // change the semantics of any of the operators of its iterator
00657   // parameter.  Its primary purpose is to convert an iterator that is
00658   // not a class, e.g. a pointer, into an iterator that is a class.
00659   // The _Container parameter exists solely so that different containers
00660   // using this template can instantiate different types, even if the
00661   // _Iterator parameter is the same.
00662   using std::iterator_traits;
00663   using std::iterator;
00664   template<typename _Iterator, typename _Container>
00665     class __normal_iterator
00666     {
00667     protected:
00668       _Iterator _M_current;
00669 
00670     public:
00671       typedef _Iterator                      iterator_type;
00672       typedef typename iterator_traits<_Iterator>::iterator_category
00673                                                              iterator_category;
00674       typedef typename iterator_traits<_Iterator>::value_type  value_type;
00675       typedef typename iterator_traits<_Iterator>::difference_type
00676                                                              difference_type;
00677       typedef typename iterator_traits<_Iterator>::reference reference;
00678       typedef typename iterator_traits<_Iterator>::pointer   pointer;
00679 
00680       __normal_iterator() : _M_current(_Iterator()) { }
00681 
00682       explicit
00683       __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
00684 
00685       // Allow iterator to const_iterator conversion
00686       template<typename _Iter>
00687         __normal_iterator(const __normal_iterator<_Iter,
00688               typename __enable_if<
00689                (std::__are_same<_Iter, typename _Container::pointer>::__value),
00690               _Container>::__type>& __i)
00691         : _M_current(__i.base()) { }
00692 
00693       // Forward iterator requirements
00694       reference
00695       operator*() const
00696       { return *_M_current; }
00697 
00698       pointer
00699       operator->() const
00700       { return _M_current; }
00701 
00702       __normal_iterator&
00703       operator++()
00704       {
00705     ++_M_current;
00706     return *this;
00707       }
00708 
00709       __normal_iterator
00710       operator++(int)
00711       { return __normal_iterator(_M_current++); }
00712 
00713       // Bidirectional iterator requirements
00714       __normal_iterator&
00715       operator--()
00716       {
00717     --_M_current;
00718     return *this;
00719       }
00720 
00721       __normal_iterator
00722       operator--(int)
00723       { return __normal_iterator(_M_current--); }
00724 
00725       // Random access iterator requirements
00726       reference
00727       operator[](const difference_type& __n) const
00728       { return _M_current[__n]; }
00729 
00730       __normal_iterator&
00731       operator+=(const difference_type& __n)
00732       { _M_current += __n; return *this; }
00733 
00734       __normal_iterator
00735       operator+(const difference_type& __n) const
00736       { return __normal_iterator(_M_current + __n); }
00737 
00738       __normal_iterator&
00739       operator-=(const difference_type& __n)
00740       { _M_current -= __n; return *this; }
00741 
00742       __normal_iterator
00743       operator-(const difference_type& __n) const
00744       { return __normal_iterator(_M_current - __n); }
00745 
00746       const _Iterator&
00747       base() const
00748       { return _M_current; }
00749     };
00750 
00751   // Note: In what follows, the left- and right-hand-side iterators are
00752   // allowed to vary in types (conceptually in cv-qualification) so that
00753   // comparison between cv-qualified and non-cv-qualified iterators be
00754   // valid.  However, the greedy and unfriendly operators in std::rel_ops
00755   // will make overload resolution ambiguous (when in scope) if we don't
00756   // provide overloads whose operands are of the same type.  Can someone
00757   // remind me what generic programming is about? -- Gaby
00758 
00759   // Forward iterator requirements
00760   template<typename _IteratorL, typename _IteratorR, typename _Container>
00761     inline bool
00762     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00763            const __normal_iterator<_IteratorR, _Container>& __rhs)
00764     { return __lhs.base() == __rhs.base(); }
00765 
00766   template<typename _Iterator, typename _Container>
00767     inline bool
00768     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00769            const __normal_iterator<_Iterator, _Container>& __rhs)
00770     { return __lhs.base() == __rhs.base(); }
00771 
00772   template<typename _IteratorL, typename _IteratorR, typename _Container>
00773     inline bool
00774     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00775            const __normal_iterator<_IteratorR, _Container>& __rhs)
00776     { return __lhs.base() != __rhs.base(); }
00777 
00778   template<typename _Iterator, typename _Container>
00779     inline bool
00780     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
00781            const __normal_iterator<_Iterator, _Container>& __rhs)
00782     { return __lhs.base() != __rhs.base(); }
00783 
00784   // Random access iterator requirements
00785   template<typename _IteratorL, typename _IteratorR, typename _Container>
00786     inline bool
00787     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00788           const __normal_iterator<_IteratorR, _Container>& __rhs)
00789     { return __lhs.base() < __rhs.base(); }
00790 
00791   template<typename _Iterator, typename _Container>
00792     inline bool
00793     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00794           const __normal_iterator<_Iterator, _Container>& __rhs)
00795     { return __lhs.base() < __rhs.base(); }
00796 
00797   template<typename _IteratorL, typename _IteratorR, typename _Container>
00798     inline bool
00799     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00800           const __normal_iterator<_IteratorR, _Container>& __rhs)
00801     { return __lhs.base() > __rhs.base(); }
00802 
00803   template<typename _Iterator, typename _Container>
00804     inline bool
00805     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00806           const __normal_iterator<_Iterator, _Container>& __rhs)
00807     { return __lhs.base() > __rhs.base(); }
00808 
00809   template<typename _IteratorL, typename _IteratorR, typename _Container>
00810     inline bool
00811     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00812            const __normal_iterator<_IteratorR, _Container>& __rhs)
00813     { return __lhs.base() <= __rhs.base(); }
00814 
00815   template<typename _Iterator, typename _Container>
00816     inline bool
00817     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00818            const __normal_iterator<_Iterator, _Container>& __rhs)
00819     { return __lhs.base() <= __rhs.base(); }
00820 
00821   template<typename _IteratorL, typename _IteratorR, typename _Container>
00822     inline bool
00823     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00824            const __normal_iterator<_IteratorR, _Container>& __rhs)
00825     { return __lhs.base() >= __rhs.base(); }
00826 
00827   template<typename _Iterator, typename _Container>
00828     inline bool
00829     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00830            const __normal_iterator<_Iterator, _Container>& __rhs)
00831     { return __lhs.base() >= __rhs.base(); }
00832 
00833   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00834   // According to the resolution of DR179 not only the various comparison
00835   // operators but also operator- must accept mixed iterator/const_iterator
00836   // parameters.
00837   template<typename _IteratorL, typename _IteratorR, typename _Container>
00838     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00839     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00840           const __normal_iterator<_IteratorR, _Container>& __rhs)
00841     { return __lhs.base() - __rhs.base(); }
00842 
00843   template<typename _Iterator, typename _Container>
00844     inline typename __normal_iterator<_Iterator, _Container>::difference_type
00845     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
00846           const __normal_iterator<_Iterator, _Container>& __rhs)
00847     { return __lhs.base() - __rhs.base(); }
00848 
00849   template<typename _Iterator, typename _Container>
00850     inline __normal_iterator<_Iterator, _Container>
00851     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
00852           __n, const __normal_iterator<_Iterator, _Container>& __i)
00853     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00854 
00855 _GLIBCXX_END_NAMESPACE
00856 
00857 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00858 
00859 _GLIBCXX_BEGIN_NAMESPACE(std)
00860 
00861   // 24.4.3  Move iterators
00862   /**
00863    *  Class template move_iterator is an iterator adapter with the same
00864    *  behavior as the underlying iterator except that its dereference
00865    *  operator implicitly converts the value returned by the underlying
00866    *  iterator's dereference operator to an rvalue reference.  Some
00867    *  generic algorithms can be called with move iterators to replace
00868    *  copying with moving.
00869    */
00870   template<typename _Iterator>
00871     class move_iterator
00872     {
00873     protected:
00874       _Iterator _M_current;
00875 
00876     public:
00877       typedef _Iterator                                        iterator_type;
00878       typedef typename iterator_traits<_Iterator>::difference_type
00879                                                                difference_type;
00880       // NB: DR 680.
00881       typedef _Iterator                                        pointer;
00882       typedef typename iterator_traits<_Iterator>::value_type  value_type;
00883       typedef typename iterator_traits<_Iterator>::iterator_category
00884                                                                iterator_category;
00885       typedef value_type&&                                     reference;
00886 
00887     public:
00888       move_iterator()
00889       : _M_current() { }
00890 
00891       explicit
00892       move_iterator(iterator_type __i)
00893       : _M_current(__i) { }
00894 
00895       template<typename _Iter>
00896     move_iterator(const move_iterator<_Iter>& __i)
00897     : _M_current(__i.base()) { }
00898 
00899       iterator_type
00900       base() const
00901       { return _M_current; }
00902 
00903       reference
00904       operator*() const
00905       { return *_M_current; }
00906 
00907       pointer
00908       operator->() const
00909       { return _M_current; }
00910 
00911       move_iterator&
00912       operator++()
00913       {
00914     ++_M_current;
00915     return *this;
00916       }
00917 
00918       move_iterator
00919       operator++(int)
00920       {
00921     move_iterator __tmp = *this;
00922     ++_M_current;
00923     return __tmp;
00924       }
00925 
00926       move_iterator&
00927       operator--()
00928       {
00929     --_M_current;
00930     return *this;
00931       }
00932 
00933       move_iterator
00934       operator--(int)
00935       {
00936     move_iterator __tmp = *this;
00937     --_M_current;
00938     return __tmp;
00939       }
00940 
00941       move_iterator
00942       operator+(difference_type __n) const
00943       { return move_iterator(_M_current + __n); }
00944 
00945       move_iterator&
00946       operator+=(difference_type __n)
00947       {
00948     _M_current += __n;
00949     return *this;
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       reference
00964       operator[](difference_type __n) const
00965       { return _M_current[__n]; }
00966     };
00967 
00968   template<typename _IteratorL, typename _IteratorR>
00969     inline bool
00970     operator==(const move_iterator<_IteratorL>& __x,
00971            const move_iterator<_IteratorR>& __y)
00972     { return __x.base() == __y.base(); }
00973 
00974   template<typename _IteratorL, typename _IteratorR>
00975     inline bool
00976     operator!=(const move_iterator<_IteratorL>& __x,
00977            const move_iterator<_IteratorR>& __y)
00978     { return !(__x == __y); }
00979 
00980   template<typename _IteratorL, typename _IteratorR>
00981     inline bool
00982     operator<(const move_iterator<_IteratorL>& __x,
00983           const move_iterator<_IteratorR>& __y)
00984     { return __x.base() < __y.base(); }
00985 
00986   template<typename _IteratorL, typename _IteratorR>
00987     inline bool
00988     operator<=(const move_iterator<_IteratorL>& __x,
00989            const move_iterator<_IteratorR>& __y)
00990     { return !(__y < __x); }
00991 
00992   template<typename _IteratorL, typename _IteratorR>
00993     inline bool
00994     operator>(const move_iterator<_IteratorL>& __x,
00995           const move_iterator<_IteratorR>& __y)
00996     { return __y < __x; }
00997 
00998   template<typename _IteratorL, typename _IteratorR>
00999     inline bool
01000     operator>=(const move_iterator<_IteratorL>& __x,
01001            const move_iterator<_IteratorR>& __y)
01002     { return !(__x < __y); }
01003 
01004   template<typename _IteratorL, typename _IteratorR>
01005     inline typename move_iterator<_IteratorL>::difference_type
01006     operator-(const move_iterator<_IteratorL>& __x,
01007           const move_iterator<_IteratorR>& __y)
01008     { return __x.base() - __y.base(); }
01009 
01010   template<typename _Iterator>
01011     inline move_iterator<_Iterator>
01012     operator+(typename move_iterator<_Iterator>::difference_type __n,
01013           const move_iterator<_Iterator>& __x)
01014     { return __x + __n; }
01015 
01016   template<typename _Iterator>
01017     inline move_iterator<_Iterator>
01018     make_move_iterator(const _Iterator& __i)
01019     { return move_iterator<_Iterator>(__i); }
01020 
01021 _GLIBCXX_END_NAMESPACE
01022 
01023 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
01024 #else
01025 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
01026 #endif // __GXX_EXPERIMENTAL_CXX0X__
01027 
01028 #endif

Generated on Wed Mar 26 00:43:14 2008 for libstdc++ by  doxygen 1.5.1