Whole document tree
    

Whole document tree

stl_iterator.h Source File
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

stl_iterator.h

Go to the documentation of this file.
00001 // Iterators -*- C++ -*-
00002 
00003 // Copyright (C) 2001 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996-1998
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /* NOTE: This is an internal header file, included by other STL headers.
00057  *   You should not attempt to use it directly.
00058  */
00059 
00060 #ifndef __SGI_STL_INTERNAL_ITERATOR_H
00061 #define __SGI_STL_INTERNAL_ITERATOR_H
00062 
00063 namespace std
00064 {
00065 
00066 template <class _Container>
00067 class back_insert_iterator {
00068 protected:
00069   _Container* container;
00070 public:
00071   typedef _Container          container_type;
00072   typedef output_iterator_tag iterator_category;
00073   typedef void                value_type;
00074   typedef void                difference_type;
00075   typedef void                pointer;
00076   typedef void                reference;
00077 
00078   explicit back_insert_iterator(_Container& __x) : container(&__x) {}
00079   back_insert_iterator<_Container>&
00080   operator=(const typename _Container::value_type& __value) { 
00081     container->push_back(__value);
00082     return *this;
00083   }
00084   back_insert_iterator<_Container>& operator*() { return *this; }
00085   back_insert_iterator<_Container>& operator++() { return *this; }
00086   back_insert_iterator<_Container>& operator++(int) { return *this; }
00087 };
00088 
00089 template <class _Container>
00090 inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
00091   return back_insert_iterator<_Container>(__x);
00092 }
00093 
00094 template <class _Container>
00095 class front_insert_iterator {
00096 protected:
00097   _Container* container;
00098 public:
00099   typedef _Container          container_type;
00100   typedef output_iterator_tag iterator_category;
00101   typedef void                value_type;
00102   typedef void                difference_type;
00103   typedef void                pointer;
00104   typedef void                reference;
00105 
00106   explicit front_insert_iterator(_Container& __x) : container(&__x) {}
00107   front_insert_iterator<_Container>&
00108   operator=(const typename _Container::value_type& __value) { 
00109     container->push_front(__value);
00110     return *this;
00111   }
00112   front_insert_iterator<_Container>& operator*() { return *this; }
00113   front_insert_iterator<_Container>& operator++() { return *this; }
00114   front_insert_iterator<_Container>& operator++(int) { return *this; }
00115 };
00116 
00117 template <class _Container>
00118 inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
00119   return front_insert_iterator<_Container>(__x);
00120 }
00121 
00122 template <class _Container>
00123 class insert_iterator {
00124 protected:
00125   _Container* container;
00126   typename _Container::iterator iter;
00127 public:
00128   typedef _Container          container_type;
00129   typedef output_iterator_tag iterator_category;
00130   typedef void                value_type;
00131   typedef void                difference_type;
00132   typedef void                pointer;
00133   typedef void                reference;
00134 
00135   insert_iterator(_Container& __x, typename _Container::iterator __i) 
00136     : container(&__x), iter(__i) {}
00137   insert_iterator<_Container>&
00138   operator=(const typename _Container::value_type& __value) { 
00139     iter = container->insert(iter, __value);
00140     ++iter;
00141     return *this;
00142   }
00143   insert_iterator<_Container>& operator*() { return *this; }
00144   insert_iterator<_Container>& operator++() { return *this; }
00145   insert_iterator<_Container>& operator++(int) { return *this; }
00146 };
00147 
00148 template <class _Container, class _Iterator>
00149 inline 
00150 insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
00151 {
00152   typedef typename _Container::iterator __iter;
00153   return insert_iterator<_Container>(__x, __iter(__i));
00154 }
00155 
00156 template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&, 
00157           class _Distance = ptrdiff_t> 
00158 class reverse_bidirectional_iterator {
00159   typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp, 
00160                                          _Reference, _Distance>  _Self;
00161 protected:
00162   _BidirectionalIterator current;
00163 public:
00164   typedef bidirectional_iterator_tag iterator_category;
00165   typedef _Tp                        value_type;
00166   typedef _Distance                  difference_type;
00167   typedef _Tp*                       pointer;
00168   typedef _Reference                 reference;
00169 
00170   reverse_bidirectional_iterator() {}
00171   explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
00172     : current(__x) {}
00173   _BidirectionalIterator base() const { return current; }
00174   _Reference operator*() const {
00175     _BidirectionalIterator __tmp = current;
00176     return *--__tmp;
00177   }
00178   pointer operator->() const { return &(operator*()); }
00179   _Self& operator++() {
00180     --current;
00181     return *this;
00182   }
00183   _Self operator++(int) {
00184     _Self __tmp = *this;
00185     --current;
00186     return __tmp;
00187   }
00188   _Self& operator--() {
00189     ++current;
00190     return *this;
00191   }
00192   _Self operator--(int) {
00193     _Self __tmp = *this;
00194     ++current;
00195     return __tmp;
00196   }
00197 };
00198 
00199 template <class _BiIter, class _Tp, class _Ref, class _Distance>
00200 inline bool operator==(
00201     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x, 
00202     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
00203 {
00204   return __x.base() == __y.base();
00205 }
00206 
00207 template <class _BiIter, class _Tp, class _Ref, class _Distance>
00208 inline bool operator!=(
00209     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x, 
00210     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
00211 {
00212   return !(__x == __y);
00213 }
00214 
00215 
00216 // This is the new version of reverse_iterator, as defined in the
00217 //  draft C++ standard.  It relies on the iterator_traits template,
00218 //  which in turn relies on partial specialization.  The class
00219 //  reverse_bidirectional_iterator is no longer part of the draft
00220 //  standard, but it is retained for backward compatibility.
00221 
00222 template <class _Iterator>
00223 class reverse_iterator 
00224 {
00225 protected:
00226   _Iterator current;
00227 public:
00228   typedef typename iterator_traits<_Iterator>::iterator_category
00229           iterator_category;
00230   typedef typename iterator_traits<_Iterator>::value_type
00231           value_type;
00232   typedef typename iterator_traits<_Iterator>::difference_type
00233           difference_type;
00234   typedef typename iterator_traits<_Iterator>::pointer
00235           pointer;
00236   typedef typename iterator_traits<_Iterator>::reference
00237           reference;
00238 
00239   typedef _Iterator iterator_type;
00240   typedef reverse_iterator<_Iterator> _Self;
00241 
00242 public:
00243   reverse_iterator() {}
00244   explicit reverse_iterator(iterator_type __x) : current(__x) {}
00245 
00246   reverse_iterator(const _Self& __x) : current(__x.current) {}
00247   template <class _Iter>
00248   reverse_iterator(const reverse_iterator<_Iter>& __x)
00249     : current(__x.base()) {}
00250     
00251   iterator_type base() const { return current; }
00252   reference operator*() const {
00253     _Iterator __tmp = current;
00254     return *--__tmp;
00255   }
00256   pointer operator->() const { return &(operator*()); }
00257 
00258   _Self& operator++() {
00259     --current;
00260     return *this;
00261   }
00262   _Self operator++(int) {
00263     _Self __tmp = *this;
00264     --current;
00265     return __tmp;
00266   }
00267   _Self& operator--() {
00268     ++current;
00269     return *this;
00270   }
00271   _Self operator--(int) {
00272     _Self __tmp = *this;
00273     ++current;
00274     return __tmp;
00275   }
00276 
00277   _Self operator+(difference_type __n) const {
00278     return _Self(current - __n);
00279   }
00280   _Self& operator+=(difference_type __n) {
00281     current -= __n;
00282     return *this;
00283   }
00284   _Self operator-(difference_type __n) const {
00285     return _Self(current + __n);
00286   }
00287   _Self& operator-=(difference_type __n) {
00288     current += __n;
00289     return *this;
00290   }
00291   reference operator[](difference_type __n) const { return *(*this + __n); }  
00292 }; 
00293  
00294 template <class _Iterator>
00295 inline bool operator==(const reverse_iterator<_Iterator>& __x, 
00296                        const reverse_iterator<_Iterator>& __y) {
00297   return __x.base() == __y.base();
00298 }
00299 
00300 template <class _Iterator>
00301 inline bool operator<(const reverse_iterator<_Iterator>& __x, 
00302                       const reverse_iterator<_Iterator>& __y) {
00303   return __y.base() < __x.base();
00304 }
00305 
00306 template <class _Iterator>
00307 inline bool operator!=(const reverse_iterator<_Iterator>& __x, 
00308                        const reverse_iterator<_Iterator>& __y) {
00309   return !(__x == __y);
00310 }
00311 
00312 template <class _Iterator>
00313 inline bool operator>(const reverse_iterator<_Iterator>& __x, 
00314                       const reverse_iterator<_Iterator>& __y) {
00315   return __y < __x;
00316 }
00317 
00318 template <class _Iterator>
00319 inline bool operator<=(const reverse_iterator<_Iterator>& __x, 
00320                        const reverse_iterator<_Iterator>& __y) {
00321   return !(__y < __x);
00322 }
00323 
00324 template <class _Iterator>
00325 inline bool operator>=(const reverse_iterator<_Iterator>& __x, 
00326                       const reverse_iterator<_Iterator>& __y) {
00327   return !(__x < __y);
00328 }
00329 
00330 template <class _Iterator>
00331 inline typename reverse_iterator<_Iterator>::difference_type
00332 operator-(const reverse_iterator<_Iterator>& __x, 
00333           const reverse_iterator<_Iterator>& __y) {
00334   return __y.base() - __x.base();
00335 }
00336 
00337 template <class _Iterator>
00338 inline reverse_iterator<_Iterator> 
00339 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00340           const reverse_iterator<_Iterator>& __x) {
00341   return reverse_iterator<_Iterator>(__x.base() - __n);
00342 }
00343 
00344 
00345 template <class _Tp, 
00346           class _CharT = char, class _Traits = char_traits<_CharT>,
00347           class _Dist = ptrdiff_t> 
00348 class istream_iterator {
00349 public:
00350   typedef _CharT                         char_type;
00351   typedef _Traits                        traits_type;
00352   typedef basic_istream<_CharT, _Traits> istream_type;
00353 
00354   typedef input_iterator_tag             iterator_category;
00355   typedef _Tp                            value_type;
00356   typedef _Dist                          difference_type;
00357   typedef const _Tp*                     pointer;
00358   typedef const _Tp&                     reference;
00359 
00360   istream_iterator() : _M_stream(0), _M_ok(false) {}
00361   istream_iterator(istream_type& __s) : _M_stream(&__s) { _M_read(); }
00362 
00363   reference operator*() const { return _M_value; }
00364   pointer operator->() const { return &(operator*()); }
00365 
00366   istream_iterator& operator++() { 
00367     _M_read(); 
00368     return *this;
00369   }
00370   istream_iterator operator++(int)  {
00371     istream_iterator __tmp = *this;
00372     _M_read();
00373     return __tmp;
00374   }
00375 
00376   bool _M_equal(const istream_iterator& __x) const
00377     { return (_M_ok == __x._M_ok) && (!_M_ok || _M_stream == __x._M_stream); }
00378 
00379 private:
00380   istream_type* _M_stream;
00381   _Tp _M_value;
00382   bool _M_ok;
00383 
00384   void _M_read() {
00385     _M_ok = (_M_stream && *_M_stream) ? true : false;
00386     if (_M_ok) {
00387       *_M_stream >> _M_value;
00388       _M_ok = *_M_stream ? true : false;
00389     }
00390   }
00391 };
00392 
00393 template <class _Tp, class _CharT, class _Traits, class _Dist>
00394 inline bool 
00395 operator==(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
00396            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
00397   return __x._M_equal(__y);
00398 }
00399 
00400 template <class _Tp, class _CharT, class _Traits, class _Dist>
00401 inline bool 
00402 operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
00403            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
00404   return !__x._M_equal(__y);
00405 }
00406 
00407 
00408 template <class _Tp,
00409           class _CharT = char, class _Traits = char_traits<_CharT> >
00410 class ostream_iterator {
00411 public:
00412   typedef _CharT                         char_type;
00413   typedef _Traits                        traits_type;
00414   typedef basic_ostream<_CharT, _Traits> ostream_type;
00415 
00416   typedef output_iterator_tag            iterator_category;
00417   typedef void                           value_type;
00418   typedef void                           difference_type;
00419   typedef void                           pointer;
00420   typedef void                           reference;
00421 
00422   ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
00423   ostream_iterator(ostream_type& __s, const _CharT* __c) 
00424     : _M_stream(&__s), _M_string(__c)  {}
00425   ostream_iterator<_Tp>& operator=(const _Tp& __value) { 
00426     *_M_stream << __value;
00427     if (_M_string) *_M_stream << _M_string;
00428     return *this;
00429   }
00430   ostream_iterator<_Tp>& operator*() { return *this; }
00431   ostream_iterator<_Tp>& operator++() { return *this; } 
00432   ostream_iterator<_Tp>& operator++(int) { return *this; } 
00433 private:
00434   ostream_type* _M_stream;
00435   const _CharT* _M_string;
00436 };
00437 
00438 
00439 // This iterator adapter is 'normal' in the sense that it does not
00440 // change the semantics of any of the operators of its iterator
00441 // parameter.  Its primary purpose is to convert an iterator that is
00442 // not a class, e.g. a pointer, into an iterator that is a class.
00443 // The _Container parameter exists solely so that different containers
00444 // using this template can instantiate different types, even if the
00445 // _Iterator parameter is the same.
00446 template<typename _Iterator, typename _Container>
00447 class __normal_iterator
00448   : public iterator<iterator_traits<_Iterator>::iterator_category,
00449                     iterator_traits<_Iterator>::value_type,
00450                     iterator_traits<_Iterator>::difference_type,
00451                     iterator_traits<_Iterator>::pointer,
00452                     iterator_traits<_Iterator>::reference>
00453 {
00454 
00455 protected:
00456   _Iterator _M_current;
00457 
00458 public:
00459   typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
00460   typedef iterator_traits<_Iterator>            __traits_type;
00461   typedef typename __traits_type::iterator_category     iterator_category;
00462   typedef typename __traits_type::value_type        value_type;
00463   typedef typename __traits_type::difference_type   difference_type;
00464   typedef typename __traits_type::pointer           pointer;
00465   typedef typename __traits_type::reference         reference;
00466 
00467   __normal_iterator() : _M_current(_Iterator()) { }
00468 
00469   explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
00470 
00471   // Allow iterator to const_iterator conversion
00472   template<typename _Iter>
00473   inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
00474     : _M_current(__i.base()) { }
00475 
00476   // Forward iterator requirements
00477   reference
00478   operator*() const { return *_M_current; }
00479 
00480   pointer
00481   operator->() const { return _M_current; }
00482 
00483   normal_iterator_type&
00484   operator++() { ++_M_current; return *this; }
00485 
00486   normal_iterator_type
00487   operator++(int) { return __normal_iterator(_M_current++); }
00488 
00489   // Bidirectional iterator requirements
00490   normal_iterator_type&
00491   operator--() { --_M_current; return *this; }
00492 
00493   normal_iterator_type
00494   operator--(int) { return __normal_iterator(_M_current--); }
00495 
00496   // Random access iterator requirements
00497   reference
00498   operator[](const difference_type& __n) const
00499   { return _M_current[__n]; }
00500 
00501   normal_iterator_type&
00502   operator+=(const difference_type& __n)
00503   { _M_current += __n; return *this; }
00504 
00505   normal_iterator_type
00506   operator+(const difference_type& __n) const
00507   { return __normal_iterator(_M_current + __n); }
00508 
00509   normal_iterator_type&
00510   operator-=(const difference_type& __n)
00511   { _M_current -= __n; return *this; }
00512 
00513   normal_iterator_type
00514   operator-(const difference_type& __n) const
00515   { return __normal_iterator(_M_current - __n); }
00516 
00517   difference_type
00518   operator-(const normal_iterator_type& __i) const
00519   { return _M_current - __i._M_current; }
00520 
00521   const _Iterator& 
00522   base() const { return _M_current; }
00523 };
00524 
00525 // forward iterator requirements
00526 
00527 template<typename _IteratorL, typename _IteratorR, typename _Container>
00528 inline bool
00529 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00530        const __normal_iterator<_IteratorR, _Container>& __rhs)
00531 { return __lhs.base() == __rhs.base(); }
00532 
00533 template<typename _IteratorL, typename _IteratorR, typename _Container>
00534 inline bool
00535 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00536        const __normal_iterator<_IteratorR, _Container>& __rhs)
00537 { return !(__lhs == __rhs); }
00538 
00539 // random access iterator requirements
00540 
00541 template<typename _IteratorL, typename _IteratorR, typename _Container>
00542 inline bool 
00543 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00544       const __normal_iterator<_IteratorR, _Container>& __rhs)
00545 { return __lhs.base() < __rhs.base(); }
00546 
00547 template<typename _IteratorL, typename _IteratorR, typename _Container>
00548 inline bool
00549 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00550       const __normal_iterator<_IteratorR, _Container>& __rhs)
00551 { return __rhs < __lhs; }
00552 
00553 template<typename _IteratorL, typename _IteratorR, typename _Container>
00554 inline bool
00555 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00556        const __normal_iterator<_IteratorR, _Container>& __rhs)
00557 { return !(__rhs < __lhs); }
00558 
00559 template<typename _IteratorL, typename _IteratorR, typename _Container>
00560 inline bool
00561 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00562        const __normal_iterator<_IteratorR, _Container>& __rhs)
00563 { return !(__lhs < __rhs); }
00564 
00565 template<typename _Iterator, typename _Container>
00566 inline __normal_iterator<_Iterator, _Container>
00567 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n,
00568           const __normal_iterator<_Iterator, _Container>& __i)
00569 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00570 
00571 } // namespace std
00572 
00573 #endif /* __SGI_STL_INTERNAL_ITERATOR_H */
00574 
00575 // Local Variables:
00576 // mode:C++
00577 // End:

Generated on Mon Apr 8 03:11:41 2002 for libstdc++-v3 Source by doxygen1.2.15