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

   1 // Iterators -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 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 /** @file stl_iterator.h
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  *
  60  *  This file implements reverse_iterator, back_insert_iterator,
  61  *  front_insert_iterator, insert_iterator, __normal_iterator, and their
  62  *  supporting functions and overloaded operators.
  63  */
  64
  65 #ifndef __GLIBCPP_INTERNAL_ITERATOR_H
  66 #define __GLIBCPP_INTERNAL_ITERATOR_H
  67
  68 namespace std
  69 {
  70   // 24.4.1 Reverse iterators
  71   /**
  72    *  "Bidirectional and random access iterators have corresponding reverse
  73    *  %iterator adaptors that iterate through the data structure in the
  74    *  opposite direction.  They have the same signatures as the corresponding
  75    *  iterators.  The fundamental relation between a reverse %iterator and its
  76    *  corresponding %iterator @c i is established by the identity:
  77    *  @code
  78    *      &*(reverse_iterator(i)) == &*(i - 1)
  79    *  @endcode
  80    *
  81    *  This mapping is dictated by the fact that while there is always a
  82    *  pointer past the end of an array, there might not be a valid pointer
  83    *  before the beginning of an array." [24.4.1]/1,2
  84    *
  85    *  Reverse iterators can be tricky and surprising at first.  Their
  86    *  semantics make sense, however, and the trickiness is a side effect of
  87    *  the requirement that the iterators must be safe.
  88   */
  89   template<typename _Iterator>
  90     class reverse_iterator
  91     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
  92                       typename iterator_traits<_Iterator>::value_type,
  93                       typename iterator_traits<_Iterator>::difference_type,
  94                       typename iterator_traits<_Iterator>::pointer,
  95                       typename iterator_traits<_Iterator>::reference>
  96     {
  97     protected:
  98       _Iterator current;
  99
 100     public:
 101       typedef _Iterator                                        iterator_type;
 102       typedef typename iterator_traits<_Iterator>::difference_type
 103                                                                difference_type;
 104       typedef typename iterator_traits<_Iterator>::reference   reference;
 105       typedef typename iterator_traits<_Iterator>::pointer     pointer;
 106
 107     public:
 108       /**
 109        *  The default constructor gives an undefined state to this %iterator.
 110       */
 111       reverse_iterator() { }
 112
 113       /**
 114        *  This %iterator will move in the opposite direction that @p x does.
 115       */
 116       explicit
 117       reverse_iterator(iterator_type __x) : current(__x) { }
 118
 119       /**
 120        *  The copy constructor is normal.
 121       */
 122       reverse_iterator(const reverse_iterator& __x)
 123       : current(__x.current) { }
 124
 125       /**
 126        *  A reverse_iterator across other types can be copied in the normal
 127        *  fashion.
 128       */
 129       template<typename _Iter>
 130         reverse_iterator(const reverse_iterator<_Iter>& __x)
 131         : current(__x.base()) { }
 132
 133       /**
 134        *  @return  @c current, the %iterator used for underlying work.
 135       */
 136       iterator_type
 137       base() const { return current; }
 138
 139       /**
 140        *  @return  TODO
 141        *
 142        *  @doctodo
 143       */
 144       reference
 145       operator*() const
 146       {
 147         _Iterator __tmp = current;
 148         return *--__tmp;
 149       }
 150
 151       /**
 152        *  @return  TODO
 153        *
 154        *  @doctodo
 155       */
 156       pointer
 157       operator->() const { return &(operator*()); }
 158
 159       /**
 160        *  @return  TODO
 161        *
 162        *  @doctodo
 163       */
 164       reverse_iterator&
 165       operator++()
 166       {
 167         --current;
 168         return *this;
 169       }
 170
 171       /**
 172        *  @return  TODO
 173        *
 174        *  @doctodo
 175       */
 176       reverse_iterator
 177       operator++(int)
 178       {
 179         reverse_iterator __tmp = *this;
 180         --current;
 181         return __tmp;
 182       }
 183
 184       /**
 185        *  @return  TODO
 186        *
 187        *  @doctodo
 188       */
 189       reverse_iterator&
 190       operator--()
 191       {
 192         ++current;
 193         return *this;
 194       }
 195
 196       /**
 197        *  @return  TODO
 198        *
 199        *  @doctodo
 200       */
 201       reverse_iterator operator--(int)
 202       {
 203         reverse_iterator __tmp = *this;
 204         ++current;
 205         return __tmp;
 206       }
 207
 208       /**
 209        *  @return  TODO
 210        *
 211        *  @doctodo
 212       */
 213       reverse_iterator
 214       operator+(difference_type __n) const
 215       { return reverse_iterator(current - __n); }
 216
 217       /**
 218        *  @return  TODO
 219        *
 220        *  @doctodo
 221       */
 222       reverse_iterator&
 223       operator+=(difference_type __n)
 224       {
 225         current -= __n;
 226         return *this;
 227       }
 228
 229       /**
 230        *  @return  TODO
 231        *
 232        *  @doctodo
 233       */
 234       reverse_iterator
 235       operator-(difference_type __n) const
 236       { return reverse_iterator(current + __n); }
 237
 238       /**
 239        *  @return  TODO
 240        *
 241        *  @doctodo
 242       */
 243       reverse_iterator&
 244       operator-=(difference_type __n)
 245       {
 246         current += __n;
 247         return *this;
 248       }
 249
 250       /**
 251        *  @return  TODO
 252        *
 253        *  @doctodo
 254       */
 255       reference
 256       operator[](difference_type __n) const { return *(*this + __n); }
 257     };
 258
 259   //@{
 260   /**
 261    *  @param  x  A %reverse_iterator.
 262    *  @param  y  A %reverse_iterator.
 263    *  @return  A simple bool.
 264    *
 265    *  Reverse iterators forward many operations to their underlying base()
 266    *  iterators.  Others are implemented in terms of one another.
 267    *
 268   */
 269   template<typename _Iterator>
 270     inline bool
 271     operator==(const reverse_iterator<_Iterator>& __x,
 272                const reverse_iterator<_Iterator>& __y)
 273     { return __x.base() == __y.base(); }
 274
 275   template<typename _Iterator>
 276     inline bool
 277     operator<(const reverse_iterator<_Iterator>& __x,
 278               const reverse_iterator<_Iterator>& __y)
 279     { return __y.base() < __x.base(); }
 280
 281   template<typename _Iterator>
 282     inline bool
 283     operator!=(const reverse_iterator<_Iterator>& __x,
 284                const reverse_iterator<_Iterator>& __y)
 285     { return !(__x == __y); }
 286
 287   template<typename _Iterator>
 288     inline bool
 289     operator>(const reverse_iterator<_Iterator>& __x,
 290               const reverse_iterator<_Iterator>& __y)
 291     { return __y < __x; }
 292
 293   template<typename _Iterator>
 294     inline bool
 295     operator<=(const reverse_iterator<_Iterator>& __x,
 296                 const reverse_iterator<_Iterator>& __y)
 297     { return !(__y < __x); }
 298
 299   template<typename _Iterator>
 300     inline bool
 301     operator>=(const reverse_iterator<_Iterator>& __x,
 302                const reverse_iterator<_Iterator>& __y)
 303     { return !(__x < __y); }
 304
 305   template<typename _Iterator>
 306     inline typename reverse_iterator<_Iterator>::difference_type
 307     operator-(const reverse_iterator<_Iterator>& __x,
 308               const reverse_iterator<_Iterator>& __y)
 309     { return __y.base() - __x.base(); }
 310
 311   template<typename _Iterator>
 312     inline reverse_iterator<_Iterator>
 313     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
 314               const reverse_iterator<_Iterator>& __x)
 315     { return reverse_iterator<_Iterator>(__x.base() - __n); }
 316   //@}
 317
 318   // 24.4.2.2.1 back_insert_iterator
 319   /**
 320    *  These are output iterators, constructed from a container-of-T.
 321    *  Assigning a T to the iterator appends it to the container using
 322    *  push_back.
 323    *
 324    *  Tip:  Using the back_inserter function to create these iterators can
 325    *  save typing.
 326   */
 327   template<typename _Container>
 328     class back_insert_iterator
 329     : public iterator<output_iterator_tag, void, void, void, void>
 330     {
 331     protected:
 332       _Container* container;
 333
 334     public:
 335       /// A nested typedef for the type of whatever container you used.
 336       typedef _Container          container_type;
 337
 338       /// The only way to create this %iterator is with a container.
 339       explicit
 340       back_insert_iterator(_Container& __x) : container(&__x) { }
 341
 342       /**
 343        *  @param  value  An instance of whatever type
 344        *                 container_type::const_reference is; presumably a
 345        *                 reference-to-const T for container<T>.
 346        *  @return  This %iterator, for chained operations.
 347        *
 348        *  This kind of %iterator doesn't really have a "position" in the
 349        *  container (you can think of the position as being permanently at
 350        *  the end, if you like).  Assigning a value to the %iterator will
 351        *  always append the value to the end of the container.
 352       */
 353       back_insert_iterator&
 354       operator=(typename _Container::const_reference __value)
 355       {
 356         container->push_back(__value);
 357         return *this;
 358       }
 359
 360       /// Simply returns *this.
 361       back_insert_iterator&
 362       operator*() { return *this; }
 363
 364       /// Simply returns *this.  (This %iterator does not "move".)
 365       back_insert_iterator&
 366       operator++() { return *this; }
 367
 368       /// Simply returns *this.  (This %iterator does not "move".)
 369       back_insert_iterator
 370       operator++(int) { return *this; }
 371     };
 372
 373   /**
 374    *  @param  x  A container of arbitrary type.
 375    *  @return  An instance of back_insert_iterator working on @p x.
 376    *
 377    *  This wrapper function helps in creating back_insert_iterator instances.
 378    *  Typing the name of the %iterator requires knowing the precise full
 379    *  type of the container, which can be tedious and impedes generic
 380    *  programming.  Using this function lets you take advantage of automatic
 381    *  template parameter deduction, making the compiler match the correct
 382    *  types for you.
 383   */
 384   template<typename _Container>
 385     inline back_insert_iterator<_Container>
 386     back_inserter(_Container& __x)
 387     { return back_insert_iterator<_Container>(__x); }
 388
 389   /**
 390    *  These are output iterators, constructed from a container-of-T.
 391    *  Assigning a T to the iterator prepends it to the container using
 392    *  push_front.
 393    *
 394    *  Tip:  Using the front_inserter function to create these iterators can
 395    *  save typing.
 396   */
 397   template<typename _Container>
 398     class front_insert_iterator
 399     : public iterator<output_iterator_tag, void, void, void, void>
 400     {
 401     protected:
 402       _Container* container;
 403
 404     public:
 405       /// A nested typedef for the type of whatever container you used.
 406       typedef _Container          container_type;
 407
 408       /// The only way to create this %iterator is with a container.
 409       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
 410
 411       /**
 412        *  @param  value  An instance of whatever type
 413        *                 container_type::const_reference is; presumably a
 414        *                 reference-to-const T for container<T>.
 415        *  @return  This %iterator, for chained operations.
 416        *
 417        *  This kind of %iterator doesn't really have a "position" in the
 418        *  container (you can think of the position as being permanently at
 419        *  the front, if you like).  Assigning a value to the %iterator will
 420        *  always prepend the value to the front of the container.
 421       */
 422       front_insert_iterator&
 423       operator=(typename _Container::const_reference __value)
 424       {
 425         container->push_front(__value);
 426         return *this;
 427       }
 428
 429       /// Simply returns *this.
 430       front_insert_iterator&
 431       operator*() { return *this; }
 432
 433       /// Simply returns *this.  (This %iterator does not "move".)
 434       front_insert_iterator&
 435       operator++() { return *this; }
 436
 437       /// Simply returns *this.  (This %iterator does not "move".)
 438       front_insert_iterator
 439       operator++(int) { return *this; }
 440     };
 441
 442   /**
 443    *  @param  x  A container of arbitrary type.
 444    *  @return  An instance of front_insert_iterator working on @p x.
 445    *
 446    *  This wrapper function helps in creating front_insert_iterator instances.
 447    *  Typing the name of the %iterator requires knowing the precise full
 448    *  type of the container, which can be tedious and impedes generic
 449    *  programming.  Using this function lets you take advantage of automatic
 450    *  template parameter deduction, making the compiler match the correct
 451    *  types for you.
 452   */
 453   template<typename _Container>
 454     inline front_insert_iterator<_Container>
 455     front_inserter(_Container& __x)
 456     { return front_insert_iterator<_Container>(__x); }
 457
 458   /**
 459    *  These are output iterators, constructed from a container-of-T.
 460    *  Assigning a T to the iterator inserts it in the container at the
 461    *  %iterator's position, rather than overwriting the value at that
 462    *  position.
 463    *
 464    *  (Sequences will actually insert a @e copy of the value before the
 465    *  %iterator's position.)
 466    *
 467    *  Tip:  Using the inserter function to create these iterators can
 468    *  save typing.
 469   */
 470   template<typename _Container>
 471     class insert_iterator
 472     : public iterator<output_iterator_tag, void, void, void, void>
 473     {
 474     protected:
 475       _Container* container;
 476       typename _Container::iterator iter;
 477
 478     public:
 479       /// A nested typedef for the type of whatever container you used.
 480       typedef _Container          container_type;
 481
 482       /**
 483        *  The only way to create this %iterator is with a container and an
 484        *  initial position (a normal %iterator into the container).
 485       */
 486       insert_iterator(_Container& __x, typename _Container::iterator __i)
 487       : container(&__x), iter(__i) {}
 488
 489       /**
 490        *  @param  value  An instance of whatever type
 491        *                 container_type::const_reference is; presumably a
 492        *                 reference-to-const T for container<T>.
 493        *  @return  This %iterator, for chained operations.
 494        *
 495        *  This kind of %iterator maintains its own position in the
 496        *  container.  Assigning a value to the %iterator will insert the
 497        *  value into the container at the place before the %iterator.
 498        *
 499        *  The position is maintained such that subsequent assignments will
 500        *  insert values immediately after one another.  For example,
 501        *  @code
 502        *     // vector v contains A and Z
 503        *
 504        *     insert_iterator i (v, ++v.begin());
 505        *     i = 1;
 506        *     i = 2;
 507        *     i = 3;
 508        *
 509        *     // vector v contains A, 1, 2, 3, and Z
 510        *  @endcode
 511       */
 512       insert_iterator&
 513       operator=(const typename _Container::const_reference __value)
 514       {
 515         iter = container->insert(iter, __value);
 516         ++iter;
 517         return *this;
 518       }
 519
 520       /// Simply returns *this.
 521       insert_iterator&
 522       operator*() { return *this; }
 523
 524       /// Simply returns *this.  (This %iterator does not "move".)
 525       insert_iterator&
 526       operator++() { return *this; }
 527
 528       /// Simply returns *this.  (This %iterator does not "move".)
 529       insert_iterator&
 530       operator++(int) { return *this; }
 531     };
 532
 533   /**
 534    *  @param  x  A container of arbitrary type.
 535    *  @return  An instance of insert_iterator working on @p x.
 536    *
 537    *  This wrapper function helps in creating insert_iterator instances.
 538    *  Typing the name of the %iterator requires knowing the precise full
 539    *  type of the container, which can be tedious and impedes generic
 540    *  programming.  Using this function lets you take advantage of automatic
 541    *  template parameter deduction, making the compiler match the correct
 542    *  types for you.
 543   */
 544   template<typename _Container, typename _Iterator>
 545     inline insert_iterator<_Container>
 546     inserter(_Container& __x, _Iterator __i)
 547     {
 548       return insert_iterator<_Container>(__x,
 549                                          typename _Container::iterator(__i));
 550     }
 551
 552   // This iterator adapter is 'normal' in the sense that it does not
 553   // change the semantics of any of the operators of its iterator
 554   // parameter.  Its primary purpose is to convert an iterator that is
 555   // not a class, e.g. a pointer, into an iterator that is a class.
 556   // The _Container parameter exists solely so that different containers
 557   // using this template can instantiate different types, even if the
 558   // _Iterator parameter is the same.
 559   template<typename _Iterator, typename _Container>
 560     class __normal_iterator
 561       : public iterator<typename iterator_traits<_Iterator>::iterator_category,
 562                         typename iterator_traits<_Iterator>::value_type,
 563                         typename iterator_traits<_Iterator>::difference_type,
 564                         typename iterator_traits<_Iterator>::pointer,
 565                         typename iterator_traits<_Iterator>::reference>
 566     {
 567     protected:
 568       _Iterator _M_current;
 569
 570     public:
 571       typedef typename iterator_traits<_Iterator>::difference_type
 572                                                                difference_type;
 573       typedef typename iterator_traits<_Iterator>::reference   reference;
 574       typedef typename iterator_traits<_Iterator>::pointer     pointer;
 575
 576       __normal_iterator() : _M_current(_Iterator()) { }
 577
 578       explicit
 579       __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 580
 581       // Allow iterator to const_iterator conversion
 582       template<typename _Iter>
 583       inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
 584         : _M_current(__i.base()) { }
 585
 586       // Forward iterator requirements
 587       reference
 588       operator*() const { return *_M_current; }
 589
 590       pointer
 591       operator->() const { return _M_current; }
 592
 593       __normal_iterator&
 594       operator++() { ++_M_current; return *this; }
 595
 596       __normal_iterator
 597       operator++(int) { return __normal_iterator(_M_current++); }
 598
 599       // Bidirectional iterator requirements
 600       __normal_iterator&
 601       operator--() { --_M_current; return *this; }
 602
 603       __normal_iterator
 604       operator--(int) { return __normal_iterator(_M_current--); }
 605
 606       // Random access iterator requirements
 607       reference
 608       operator[](const difference_type& __n) const
 609       { return _M_current[__n]; }
 610
 611       __normal_iterator&
 612       operator+=(const difference_type& __n)
 613       { _M_current += __n; return *this; }
 614
 615       __normal_iterator
 616       operator+(const difference_type& __n) const
 617       { return __normal_iterator(_M_current + __n); }
 618
 619       __normal_iterator&
 620       operator-=(const difference_type& __n)
 621       { _M_current -= __n; return *this; }
 622
 623       __normal_iterator
 624       operator-(const difference_type& __n) const
 625       { return __normal_iterator(_M_current - __n); }
 626
 627       difference_type
 628       operator-(const __normal_iterator& __i) const
 629       { return _M_current - __i._M_current; }
 630
 631       const _Iterator&
 632       base() const { return _M_current; }
 633     };
 634
 635   // Forward iterator requirements
 636   template<typename _IteratorL, typename _IteratorR, typename _Container>
 637   inline bool
 638   operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
 639              const __normal_iterator<_IteratorR, _Container>& __rhs)
 640   { return __lhs.base() == __rhs.base(); }
 641
 642   template<typename _IteratorL, typename _IteratorR, typename _Container>
 643   inline bool
 644   operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 645              const __normal_iterator<_IteratorR, _Container>& __rhs)
 646   { return !(__lhs == __rhs); }
 647
 648   // Random access iterator requirements
 649   template<typename _IteratorL, typename _IteratorR, typename _Container>
 650   inline bool
 651   operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
 652             const __normal_iterator<_IteratorR, _Container>& __rhs)
 653   { return __lhs.base() < __rhs.base(); }
 654
 655   template<typename _IteratorL, typename _IteratorR, typename _Container>
 656   inline bool
 657   operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
 658             const __normal_iterator<_IteratorR, _Container>& __rhs)
 659   { return __rhs < __lhs; }
 660
 661   template<typename _IteratorL, typename _IteratorR, typename _Container>
 662   inline bool
 663   operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 664              const __normal_iterator<_IteratorR, _Container>& __rhs)
 665   { return !(__rhs < __lhs); }
 666
 667   template<typename _IteratorL, typename _IteratorR, typename _Container>
 668   inline bool
 669   operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 670              const __normal_iterator<_IteratorR, _Container>& __rhs)
 671   { return !(__lhs < __rhs); }
 672
 673   template<typename _Iterator, typename _Container>
 674   inline __normal_iterator<_Iterator, _Container>
 675   operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n,
 676             const __normal_iterator<_Iterator, _Container>& __i)
 677   { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
 678 } // namespace std
 679
 680 #endif
 681
 682 // Local Variables:
 683 // mode:C++
 684 // End: