libstdc++-v3/include/bits/stl_iterator.h

   1 // Iterators -*- C++ -*-
   2
   3 // Copyright (C) 2001 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1996-1998
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /* NOTE: This is an internal header file, included by other STL headers.
  57  *   You should not attempt to use it directly.
  58  */
  59
  60 #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  61 #define __SGI_STL_INTERNAL_ITERATOR_H
  62
  63 namespace std
  64 {
  65
  66 template <class _Container>
  67 class back_insert_iterator {
  68 protected:
  69   _Container* container;
  70 public:
  71   typedef _Container          container_type;
  72   typedef output_iterator_tag iterator_category;
  73   typedef void                value_type;
  74   typedef void                difference_type;
  75   typedef void                pointer;
  76   typedef void                reference;
  77
  78   explicit back_insert_iterator(_Container& __x) : container(&__x) {}
  79   back_insert_iterator<_Container>&
  80   operator=(const typename _Container::value_type& __value) {
  81     container->push_back(__value);
  82     return *this;
  83   }
  84   back_insert_iterator<_Container>& operator*() { return *this; }
  85   back_insert_iterator<_Container>& operator++() { return *this; }
  86   back_insert_iterator<_Container>& operator++(int) { return *this; }
  87 };
  88
  89 template <class _Container>
  90 inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
  91   return back_insert_iterator<_Container>(__x);
  92 }
  93
  94 template <class _Container>
  95 class front_insert_iterator {
  96 protected:
  97   _Container* container;
  98 public:
  99   typedef _Container          container_type;
 100   typedef output_iterator_tag iterator_category;
 101   typedef void                value_type;
 102   typedef void                difference_type;
 103   typedef void                pointer;
 104   typedef void                reference;
 105
 106   explicit front_insert_iterator(_Container& __x) : container(&__x) {}
 107   front_insert_iterator<_Container>&
 108   operator=(const typename _Container::value_type& __value) {
 109     container->push_front(__value);
 110     return *this;
 111   }
 112   front_insert_iterator<_Container>& operator*() { return *this; }
 113   front_insert_iterator<_Container>& operator++() { return *this; }
 114   front_insert_iterator<_Container>& operator++(int) { return *this; }
 115 };
 116
 117 template <class _Container>
 118 inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
 119   return front_insert_iterator<_Container>(__x);
 120 }
 121
 122 template <class _Container>
 123 class insert_iterator {
 124 protected:
 125   _Container* container;
 126   typename _Container::iterator iter;
 127 public:
 128   typedef _Container          container_type;
 129   typedef output_iterator_tag iterator_category;
 130   typedef void                value_type;
 131   typedef void                difference_type;
 132   typedef void                pointer;
 133   typedef void                reference;
 134
 135   insert_iterator(_Container& __x, typename _Container::iterator __i)
 136     : container(&__x), iter(__i) {}
 137   insert_iterator<_Container>&
 138   operator=(const typename _Container::value_type& __value) {
 139     iter = container->insert(iter, __value);
 140     ++iter;
 141     return *this;
 142   }
 143   insert_iterator<_Container>& operator*() { return *this; }
 144   insert_iterator<_Container>& operator++() { return *this; }
 145   insert_iterator<_Container>& operator++(int) { return *this; }
 146 };
 147
 148 template <class _Container, class _Iterator>
 149 inline
 150 insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
 151 {
 152   typedef typename _Container::iterator __iter;
 153   return insert_iterator<_Container>(__x, __iter(__i));
 154 }
 155
 156 template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&,
 157           class _Distance = ptrdiff_t>
 158 class reverse_bidirectional_iterator {
 159   typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
 160                                          _Reference, _Distance>  _Self;
 161 protected:
 162   _BidirectionalIterator current;
 163 public:
 164   typedef bidirectional_iterator_tag iterator_category;
 165   typedef _Tp                        value_type;
 166   typedef _Distance                  difference_type;
 167   typedef _Tp*                       pointer;
 168   typedef _Reference                 reference;
 169
 170   reverse_bidirectional_iterator() {}
 171   explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
 172     : current(__x) {}
 173   _BidirectionalIterator base() const { return current; }
 174   _Reference operator*() const {
 175     _BidirectionalIterator __tmp = current;
 176     return *--__tmp;
 177   }
 178   pointer operator->() const { return &(operator*()); }
 179   _Self& operator++() {
 180     --current;
 181     return *this;
 182   }
 183   _Self operator++(int) {
 184     _Self __tmp = *this;
 185     --current;
 186     return __tmp;
 187   }
 188   _Self& operator--() {
 189     ++current;
 190     return *this;
 191   }
 192   _Self operator--(int) {
 193     _Self __tmp = *this;
 194     ++current;
 195     return __tmp;
 196   }
 197 };
 198
 199 template <class _BiIter, class _Tp, class _Ref, class _Distance>
 200 inline bool operator==(
 201     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
 202     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
 203 {
 204   return __x.base() == __y.base();
 205 }
 206
 207 template <class _BiIter, class _Tp, class _Ref, class _Distance>
 208 inline bool operator!=(
 209     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
 210     const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
 211 {
 212   return !(__x == __y);
 213 }
 214
 215
 216 // This is the new version of reverse_iterator, as defined in the
 217 //  draft C++ standard.  It relies on the iterator_traits template,
 218 //  which in turn relies on partial specialization.  The class
 219 //  reverse_bidirectional_iterator is no longer part of the draft
 220 //  standard, but it is retained for backward compatibility.
 221
 222 template <class _Iterator>
 223 class reverse_iterator
 224 {
 225 protected:
 226   _Iterator current;
 227 public:
 228   typedef typename iterator_traits<_Iterator>::iterator_category
 229           iterator_category;
 230   typedef typename iterator_traits<_Iterator>::value_type
 231           value_type;
 232   typedef typename iterator_traits<_Iterator>::difference_type
 233           difference_type;
 234   typedef typename iterator_traits<_Iterator>::pointer
 235           pointer;
 236   typedef typename iterator_traits<_Iterator>::reference
 237           reference;
 238
 239   typedef _Iterator iterator_type;
 240   typedef reverse_iterator<_Iterator> _Self;
 241
 242 public:
 243   reverse_iterator() {}
 244   explicit reverse_iterator(iterator_type __x) : current(__x) {}
 245
 246   reverse_iterator(const _Self& __x) : current(__x.current) {}
 247   template <class _Iter>
 248   reverse_iterator(const reverse_iterator<_Iter>& __x)
 249     : current(__x.base()) {}
 250
 251   iterator_type base() const { return current; }
 252   reference operator*() const {
 253     _Iterator __tmp = current;
 254     return *--__tmp;
 255   }
 256   pointer operator->() const { return &(operator*()); }
 257
 258   _Self& operator++() {
 259     --current;
 260     return *this;
 261   }
 262   _Self operator++(int) {
 263     _Self __tmp = *this;
 264     --current;
 265     return __tmp;
 266   }
 267   _Self& operator--() {
 268     ++current;
 269     return *this;
 270   }
 271   _Self operator--(int) {
 272     _Self __tmp = *this;
 273     ++current;
 274     return __tmp;
 275   }
 276
 277   _Self operator+(difference_type __n) const {
 278     return _Self(current - __n);
 279   }
 280   _Self& operator+=(difference_type __n) {
 281     current -= __n;
 282     return *this;
 283   }
 284   _Self operator-(difference_type __n) const {
 285     return _Self(current + __n);
 286   }
 287   _Self& operator-=(difference_type __n) {
 288     current += __n;
 289     return *this;
 290   }
 291   reference operator[](difference_type __n) const { return *(*this + __n); }
 292 };
 293
 294 template <class _Iterator>
 295 inline bool operator==(const reverse_iterator<_Iterator>& __x,
 296                        const reverse_iterator<_Iterator>& __y) {
 297   return __x.base() == __y.base();
 298 }
 299
 300 template <class _Iterator>
 301 inline bool operator<(const reverse_iterator<_Iterator>& __x,
 302                       const reverse_iterator<_Iterator>& __y) {
 303   return __y.base() < __x.base();
 304 }
 305
 306 template <class _Iterator>
 307 inline bool operator!=(const reverse_iterator<_Iterator>& __x,
 308                        const reverse_iterator<_Iterator>& __y) {
 309   return !(__x == __y);
 310 }
 311
 312 template <class _Iterator>
 313 inline bool operator>(const reverse_iterator<_Iterator>& __x,
 314                       const reverse_iterator<_Iterator>& __y) {
 315   return __y < __x;
 316 }
 317
 318 template <class _Iterator>
 319 inline bool operator<=(const reverse_iterator<_Iterator>& __x,
 320                        const reverse_iterator<_Iterator>& __y) {
 321   return !(__y < __x);
 322 }
 323
 324 template <class _Iterator>
 325 inline bool operator>=(const reverse_iterator<_Iterator>& __x,
 326                       const reverse_iterator<_Iterator>& __y) {
 327   return !(__x < __y);
 328 }
 329
 330 template <class _Iterator>
 331 inline typename reverse_iterator<_Iterator>::difference_type
 332 operator-(const reverse_iterator<_Iterator>& __x,
 333           const reverse_iterator<_Iterator>& __y) {
 334   return __y.base() - __x.base();
 335 }
 336
 337 template <class _Iterator>
 338 inline reverse_iterator<_Iterator>
 339 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
 340           const reverse_iterator<_Iterator>& __x) {
 341   return reverse_iterator<_Iterator>(__x.base() - __n);
 342 }
 343
 344
 345 template <class _Tp,
 346           class _CharT = char, class _Traits = char_traits<_CharT>,
 347           class _Dist = ptrdiff_t>
 348 class istream_iterator {
 349 public:
 350   typedef _CharT                         char_type;
 351   typedef _Traits                        traits_type;
 352   typedef basic_istream<_CharT, _Traits> istream_type;
 353
 354   typedef input_iterator_tag             iterator_category;
 355   typedef _Tp                            value_type;
 356   typedef _Dist                          difference_type;
 357   typedef const _Tp*                     pointer;
 358   typedef const _Tp&                     reference;
 359
 360   istream_iterator() : _M_stream(0), _M_ok(false) {}
 361   istream_iterator(istream_type& __s) : _M_stream(&__s) { _M_read(); }
 362
 363   reference operator*() const { return _M_value; }
 364   pointer operator->() const { return &(operator*()); }
 365
 366   istream_iterator& operator++() {
 367     _M_read();
 368     return *this;
 369   }
 370   istream_iterator operator++(int)  {
 371     istream_iterator __tmp = *this;
 372     _M_read();
 373     return __tmp;
 374   }
 375
 376   bool _M_equal(const istream_iterator& __x) const
 377     { return (_M_ok == __x._M_ok) && (!_M_ok || _M_stream == __x._M_stream); }
 378
 379 private:
 380   istream_type* _M_stream;
 381   _Tp _M_value;
 382   bool _M_ok;
 383
 384   void _M_read() {
 385     _M_ok = (_M_stream && *_M_stream) ? true : false;
 386     if (_M_ok) {
 387       *_M_stream >> _M_value;
 388       _M_ok = *_M_stream ? true : false;
 389     }
 390   }
 391 };
 392
 393 template <class _Tp, class _CharT, class _Traits, class _Dist>
 394 inline bool
 395 operator==(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
 396            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
 397   return __x._M_equal(__y);
 398 }
 399
 400 template <class _Tp, class _CharT, class _Traits, class _Dist>
 401 inline bool
 402 operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
 403            const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
 404   return !__x._M_equal(__y);
 405 }
 406
 407
 408 template <class _Tp,
 409           class _CharT = char, class _Traits = char_traits<_CharT> >
 410 class ostream_iterator {
 411 public:
 412   typedef _CharT                         char_type;
 413   typedef _Traits                        traits_type;
 414   typedef basic_ostream<_CharT, _Traits> ostream_type;
 415
 416   typedef output_iterator_tag            iterator_category;
 417   typedef void                           value_type;
 418   typedef void                           difference_type;
 419   typedef void                           pointer;
 420   typedef void                           reference;
 421
 422   ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
 423   ostream_iterator(ostream_type& __s, const _CharT* __c)
 424     : _M_stream(&__s), _M_string(__c)  {}
 425   ostream_iterator<_Tp>& operator=(const _Tp& __value) {
 426     *_M_stream << __value;
 427     if (_M_string) *_M_stream << _M_string;
 428     return *this;
 429   }
 430   ostream_iterator<_Tp>& operator*() { return *this; }
 431   ostream_iterator<_Tp>& operator++() { return *this; }
 432   ostream_iterator<_Tp>& operator++(int) { return *this; }
 433 private:
 434   ostream_type* _M_stream;
 435   const _CharT* _M_string;
 436 };
 437
 438
 439 // This iterator adapter is 'normal' in the sense that it does not
 440 // change the semantics of any of the operators of its itererator
 441 // parameter.  Its primary purpose is to convert an iterator that is
 442 // not a class, e.g. a pointer, into an iterator that is a class.
 443 // The _Container parameter exists solely so that different containers
 444 // using this template can instantiate different types, even if the
 445 // _Iterator parameter is the same.
 446 template<typename _Iterator, typename _Container>
 447 class __normal_iterator
 448   : public iterator<iterator_traits<_Iterator>::iterator_category,
 449                     iterator_traits<_Iterator>::value_type,
 450                     iterator_traits<_Iterator>::difference_type,
 451                     iterator_traits<_Iterator>::pointer,
 452                     iterator_traits<_Iterator>::reference>
 453 {
 454
 455 protected:
 456   _Iterator _M_current;
 457
 458 public:
 459   typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
 460   typedef iterator_traits<_Iterator>                    __traits_type;
 461   typedef typename __traits_type::iterator_category     iterator_category;
 462   typedef typename __traits_type::value_type            value_type;
 463   typedef typename __traits_type::difference_type       difference_type;
 464   typedef typename __traits_type::pointer               pointer;
 465   typedef typename __traits_type::reference             reference;
 466
 467   __normal_iterator() : _M_current(_Iterator()) { }
 468
 469   explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 470
 471   // Allow iterator to const_iterator conversion
 472   template<typename _Iter>
 473   inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
 474     : _M_current(__i.base()) { }
 475
 476   // Forward iterator requirements
 477   reference
 478   operator*() const { return *_M_current; }
 479
 480   pointer
 481   operator->() const { return _M_current; }
 482
 483   normal_iterator_type&
 484   operator++() { ++_M_current; return *this; }
 485
 486   normal_iterator_type
 487   operator++(int) { return __normal_iterator(_M_current++); }
 488
 489   // Bidirectional iterator requirements
 490   normal_iterator_type&
 491   operator--() { --_M_current; return *this; }
 492
 493   normal_iterator_type
 494   operator--(int) { return __normal_iterator(_M_current--); }
 495
 496   // Random access iterator requirements
 497   reference
 498   operator[](const difference_type& __n) const
 499   { return _M_current[__n]; }
 500
 501   normal_iterator_type&
 502   operator+=(const difference_type& __n)
 503   { _M_current += __n; return *this; }
 504
 505   normal_iterator_type
 506   operator+(const difference_type& __n) const
 507   { return __normal_iterator(_M_current + __n); }
 508
 509   normal_iterator_type&
 510   operator-=(const difference_type& __n)
 511   { _M_current -= __n; return *this; }
 512
 513   normal_iterator_type
 514   operator-(const difference_type& __n) const
 515   { return __normal_iterator(_M_current - __n); }
 516
 517   difference_type
 518   operator-(const normal_iterator_type& __i) const
 519   { return _M_current - __i._M_current; }
 520
 521   const _Iterator&
 522   base() const { return _M_current; }
 523 };
 524
 525 // forward iterator requirements
 526
 527 template<typename _IteratorL, typename _IteratorR, typename _Container>
 528 inline bool
 529 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
 530            const __normal_iterator<_IteratorR, _Container>& __rhs)
 531 { return __lhs.base() == __rhs.base(); }
 532
 533 template<typename _IteratorL, typename _IteratorR, typename _Container>
 534 inline bool
 535 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 536            const __normal_iterator<_IteratorR, _Container>& __rhs)
 537 { return !(__lhs == __rhs); }
 538
 539 // random access iterator requirements
 540
 541 template<typename _IteratorL, typename _IteratorR, typename _Container>
 542 inline bool
 543 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
 544           const __normal_iterator<_IteratorR, _Container>& __rhs)
 545 { return __lhs.base() < __rhs.base(); }
 546
 547 template<typename _IteratorL, typename _IteratorR, typename _Container>
 548 inline bool
 549 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
 550           const __normal_iterator<_IteratorR, _Container>& __rhs)
 551 { return __rhs < __lhs; }
 552
 553 template<typename _IteratorL, typename _IteratorR, typename _Container>
 554 inline bool
 555 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 556            const __normal_iterator<_IteratorR, _Container>& __rhs)
 557 { return !(__rhs < __lhs); }
 558
 559 template<typename _IteratorL, typename _IteratorR, typename _Container>
 560 inline bool
 561 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 562            const __normal_iterator<_IteratorR, _Container>& __rhs)
 563 { return !(__lhs < __rhs); }
 564
 565 template<typename _Iterator, typename _Container>
 566 inline __normal_iterator<_Iterator, _Container>
 567 operator+(__normal_iterator<_Iterator, _Container>::difference_type __n,
 568           const __normal_iterator<_Iterator, _Container>& __i)
 569 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
 570
 571 } // namespace std
 572
 573 #endif /* __SGI_STL_INTERNAL_ITERATOR_H */
 574
 575 // Local Variables:
 576 // mode:C++
 577 // End: