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 } // namespace std 552 553 namespace __gnu_cxx 554 { 555 // This iterator adapter is 'normal' in the sense that it does not 556 // change the semantics of any of the operators of its iterator 557 // parameter. Its primary purpose is to convert an iterator that is 558 // not a class, e.g. a pointer, into an iterator that is a class. 559 // The _Container parameter exists solely so that different containers 560 // using this template can instantiate different types, even if the 561 // _Iterator parameter is the same. 562 using std::iterator_traits; 563 using std::iterator; 564 template<typename _Iterator, typename _Container> 565 class __normal_iterator 566 : public iterator<typename iterator_traits<_Iterator>::iterator_category, 567 typename iterator_traits<_Iterator>::value_type, 568 typename iterator_traits<_Iterator>::difference_type, 569 typename iterator_traits<_Iterator>::pointer, 570 typename iterator_traits<_Iterator>::reference> 571 { 572 protected: 573 _Iterator _M_current; 574 575 public: 576 typedef typename iterator_traits<_Iterator>::difference_type 577 difference_type; 578 typedef typename iterator_traits<_Iterator>::reference reference; 579 typedef typename iterator_traits<_Iterator>::pointer pointer; 580 581 __normal_iterator() : _M_current(_Iterator()) { } 582 583 explicit 584 __normal_iterator(const _Iterator& __i) : _M_current(__i) { } 585 586 // Allow iterator to const_iterator conversion 587 template<typename _Iter> 588 inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i) 589 : _M_current(__i.base()) { } 590 591 // Forward iterator requirements 592 reference 593 operator*() const { return *_M_current; } 594 595 pointer 596 operator->() const { return _M_current; } 597 598 __normal_iterator& 599 operator++() { ++_M_current; return *this; } 600 601 __normal_iterator 602 operator++(int) { return __normal_iterator(_M_current++); } 603 604 // Bidirectional iterator requirements 605 __normal_iterator& 606 operator--() { --_M_current; return *this; } 607 608 __normal_iterator 609 operator--(int) { return __normal_iterator(_M_current--); } 610 611 // Random access iterator requirements 612 reference 613 operator[](const difference_type& __n) const 614 { return _M_current[__n]; } 615 616 __normal_iterator& 617 operator+=(const difference_type& __n) 618 { _M_current += __n; return *this; } 619 620 __normal_iterator 621 operator+(const difference_type& __n) const 622 { return __normal_iterator(_M_current + __n); } 623 624 __normal_iterator& 625 operator-=(const difference_type& __n) 626 { _M_current -= __n; return *this; } 627 628 __normal_iterator 629 operator-(const difference_type& __n) const 630 { return __normal_iterator(_M_current - __n); } 631 632 const _Iterator& 633 base() const { return _M_current; } 634 }; 635 636 // Note: In what follows, the left- and right-hand-side iterators are 637 // allowed to vary in types (conceptually in cv-qualification) so that 638 // comparaison between cv-qualified and non-cv-qualified iterators be 639 // valid. However, the greedy and unfriendly operators in std::rel_ops 640 // will make overload resolution ambiguous (when in scope) if we don't 641 // provide overloads whose operands are of the same type. Can someone 642 // remind me what generic programming is about? -- Gaby 643 644 // Forward iterator requirements 645 template<typename _IteratorL, typename _IteratorR, typename _Container> 646 inline bool 647 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 648 const __normal_iterator<_IteratorR, _Container>& __rhs) 649 { return __lhs.base() == __rhs.base(); } 650 651 template<typename _Iterator, typename _Container> 652 inline bool 653 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 654 const __normal_iterator<_Iterator, _Container>& __rhs) 655 { return __lhs.base() == __rhs.base(); } 656 657 template<typename _IteratorL, typename _IteratorR, typename _Container> 658 inline bool 659 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 660 const __normal_iterator<_IteratorR, _Container>& __rhs) 661 { return __lhs.base() != __rhs.base(); } 662 663 template<typename _Iterator, typename _Container> 664 inline bool 665 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 666 const __normal_iterator<_Iterator, _Container>& __rhs) 667 { return __lhs.base() != __rhs.base(); } 668 669 // Random access iterator requirements 670 template<typename _IteratorL, typename _IteratorR, typename _Container> 671 inline bool 672 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 673 const __normal_iterator<_IteratorR, _Container>& __rhs) 674 { return __lhs.base() < __rhs.base(); } 675 676 template<typename _Iterator, typename _Container> 677 inline bool 678 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 679 const __normal_iterator<_Iterator, _Container>& __rhs) 680 { return __lhs.base() < __rhs.base(); } 681 682 template<typename _IteratorL, typename _IteratorR, typename _Container> 683 inline bool 684 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 685 const __normal_iterator<_IteratorR, _Container>& __rhs) 686 { return __lhs.base() > __rhs.base(); } 687 688 template<typename _Iterator, typename _Container> 689 inline bool 690 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 691 const __normal_iterator<_Iterator, _Container>& __rhs) 692 { return __lhs.base() > __rhs.base(); } 693 694 template<typename _IteratorL, typename _IteratorR, typename _Container> 695 inline bool 696 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 697 const __normal_iterator<_IteratorR, _Container>& __rhs) 698 { return __lhs.base() <= __rhs.base(); } 699 700 template<typename _Iterator, typename _Container> 701 inline bool 702 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 703 const __normal_iterator<_Iterator, _Container>& __rhs) 704 { return __lhs.base() <= __rhs.base(); } 705 706 template<typename _IteratorL, typename _IteratorR, typename _Container> 707 inline bool 708 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 709 const __normal_iterator<_IteratorR, _Container>& __rhs) 710 { return __lhs.base() >= __rhs.base(); } 711 712 template<typename _Iterator, typename _Container> 713 inline bool 714 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 715 const __normal_iterator<_Iterator, _Container>& __rhs) 716 { return __lhs.base() >= __rhs.base(); } 717 718 // _GLIBCPP_RESOLVE_LIB_DEFECTS 719 // According to the resolution of DR179 not only the various comparison 720 // operators but also operator- must accept mixed iterator/const_iterator 721 // parameters. 722 template<typename _IteratorL, typename _IteratorR, typename _Container> 723 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 724 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 725 const __normal_iterator<_IteratorR, _Container>& __rhs) 726 { return __lhs.base() - __rhs.base(); } 727 728 template<typename _Iterator, typename _Container> 729 inline __normal_iterator<_Iterator, _Container> 730 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n, 731 const __normal_iterator<_Iterator, _Container>& __i) 732 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 733 } // namespace __gnu_cxx 734 735 #endif 736 737 // Local Variables: 738 // mode:C++ 739 // End: 740