stl_iterator.h revision 132720
1// Iterators -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2004 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 _ITERATOR_H 66#define _ITERATOR_H 1 67 68namespace 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 default-initializes member @p current. 110 * If it is a pointer, that means it is zero-initialized. 111 */ 112 // _GLIBCXX_RESOLVE_LIB_DEFECTS 113 // 235 No specification of default ctor for reverse_iterator 114 reverse_iterator() : current() { } 115 116 /** 117 * This %iterator will move in the opposite direction that @p x does. 118 */ 119 explicit 120 reverse_iterator(iterator_type __x) : current(__x) { } 121 122 /** 123 * The copy constructor is normal. 124 */ 125 reverse_iterator(const reverse_iterator& __x) 126 : current(__x.current) { } 127 128 /** 129 * A reverse_iterator across other types can be copied in the normal 130 * fashion. 131 */ 132 template<typename _Iter> 133 reverse_iterator(const reverse_iterator<_Iter>& __x) 134 : current(__x.base()) { } 135 136 /** 137 * @return @c current, the %iterator used for underlying work. 138 */ 139 iterator_type 140 base() const 141 { return current; } 142 143 /** 144 * @return TODO 145 * 146 * @doctodo 147 */ 148 reference 149 operator*() const 150 { 151 _Iterator __tmp = current; 152 return *--__tmp; 153 } 154 155 /** 156 * @return TODO 157 * 158 * @doctodo 159 */ 160 pointer 161 operator->() const 162 { return &(operator*()); } 163 164 /** 165 * @return TODO 166 * 167 * @doctodo 168 */ 169 reverse_iterator& 170 operator++() 171 { 172 --current; 173 return *this; 174 } 175 176 /** 177 * @return TODO 178 * 179 * @doctodo 180 */ 181 reverse_iterator 182 operator++(int) 183 { 184 reverse_iterator __tmp = *this; 185 --current; 186 return __tmp; 187 } 188 189 /** 190 * @return TODO 191 * 192 * @doctodo 193 */ 194 reverse_iterator& 195 operator--() 196 { 197 ++current; 198 return *this; 199 } 200 201 /** 202 * @return TODO 203 * 204 * @doctodo 205 */ 206 reverse_iterator operator--(int) 207 { 208 reverse_iterator __tmp = *this; 209 ++current; 210 return __tmp; 211 } 212 213 /** 214 * @return TODO 215 * 216 * @doctodo 217 */ 218 reverse_iterator 219 operator+(difference_type __n) const 220 { return reverse_iterator(current - __n); } 221 222 /** 223 * @return TODO 224 * 225 * @doctodo 226 */ 227 reverse_iterator& 228 operator+=(difference_type __n) 229 { 230 current -= __n; 231 return *this; 232 } 233 234 /** 235 * @return TODO 236 * 237 * @doctodo 238 */ 239 reverse_iterator 240 operator-(difference_type __n) const 241 { return reverse_iterator(current + __n); } 242 243 /** 244 * @return TODO 245 * 246 * @doctodo 247 */ 248 reverse_iterator& 249 operator-=(difference_type __n) 250 { 251 current += __n; 252 return *this; 253 } 254 255 /** 256 * @return TODO 257 * 258 * @doctodo 259 */ 260 reference 261 operator[](difference_type __n) const 262 { return *(*this + __n); } 263 }; 264 265 //@{ 266 /** 267 * @param x A %reverse_iterator. 268 * @param y A %reverse_iterator. 269 * @return A simple bool. 270 * 271 * Reverse iterators forward many operations to their underlying base() 272 * iterators. Others are implemented in terms of one another. 273 * 274 */ 275 template<typename _Iterator> 276 inline bool 277 operator==(const reverse_iterator<_Iterator>& __x, 278 const reverse_iterator<_Iterator>& __y) 279 { return __x.base() == __y.base(); } 280 281 template<typename _Iterator> 282 inline bool 283 operator<(const reverse_iterator<_Iterator>& __x, 284 const reverse_iterator<_Iterator>& __y) 285 { return __y.base() < __x.base(); } 286 287 template<typename _Iterator> 288 inline bool 289 operator!=(const reverse_iterator<_Iterator>& __x, 290 const reverse_iterator<_Iterator>& __y) 291 { return !(__x == __y); } 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 !(__y < __x); } 304 305 template<typename _Iterator> 306 inline bool 307 operator>=(const reverse_iterator<_Iterator>& __x, 308 const reverse_iterator<_Iterator>& __y) 309 { return !(__x < __y); } 310 311 template<typename _Iterator> 312 inline typename reverse_iterator<_Iterator>::difference_type 313 operator-(const reverse_iterator<_Iterator>& __x, 314 const reverse_iterator<_Iterator>& __y) 315 { return __y.base() - __x.base(); } 316 317 template<typename _Iterator> 318 inline reverse_iterator<_Iterator> 319 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 320 const reverse_iterator<_Iterator>& __x) 321 { return reverse_iterator<_Iterator>(__x.base() - __n); } 322 //@} 323 324 // 24.4.2.2.1 back_insert_iterator 325 /** 326 * @brief Turns assignment into insertion. 327 * 328 * These are output iterators, constructed from a container-of-T. 329 * Assigning a T to the iterator appends it to the container using 330 * push_back. 331 * 332 * Tip: Using the back_inserter function to create these iterators can 333 * save typing. 334 */ 335 template<typename _Container> 336 class back_insert_iterator 337 : public iterator<output_iterator_tag, void, void, void, void> 338 { 339 protected: 340 _Container* container; 341 342 public: 343 /// A nested typedef for the type of whatever container you used. 344 typedef _Container container_type; 345 346 /// The only way to create this %iterator is with a container. 347 explicit 348 back_insert_iterator(_Container& __x) : container(&__x) { } 349 350 /** 351 * @param value An instance of whatever type 352 * container_type::const_reference is; presumably a 353 * reference-to-const T for container<T>. 354 * @return This %iterator, for chained operations. 355 * 356 * This kind of %iterator doesn't really have a "position" in the 357 * container (you can think of the position as being permanently at 358 * the end, if you like). Assigning a value to the %iterator will 359 * always append the value to the end of the container. 360 */ 361 back_insert_iterator& 362 operator=(typename _Container::const_reference __value) 363 { 364 container->push_back(__value); 365 return *this; 366 } 367 368 /// Simply returns *this. 369 back_insert_iterator& 370 operator*() 371 { return *this; } 372 373 /// Simply returns *this. (This %iterator does not "move".) 374 back_insert_iterator& 375 operator++() 376 { return *this; } 377 378 /// Simply returns *this. (This %iterator does not "move".) 379 back_insert_iterator 380 operator++(int) 381 { return *this; } 382 }; 383 384 /** 385 * @param x A container of arbitrary type. 386 * @return An instance of back_insert_iterator working on @p x. 387 * 388 * This wrapper function helps in creating back_insert_iterator instances. 389 * Typing the name of the %iterator requires knowing the precise full 390 * type of the container, which can be tedious and impedes generic 391 * programming. Using this function lets you take advantage of automatic 392 * template parameter deduction, making the compiler match the correct 393 * types for you. 394 */ 395 template<typename _Container> 396 inline back_insert_iterator<_Container> 397 back_inserter(_Container& __x) 398 { return back_insert_iterator<_Container>(__x); } 399 400 /** 401 * @brief Turns assignment into insertion. 402 * 403 * These are output iterators, constructed from a container-of-T. 404 * Assigning a T to the iterator prepends it to the container using 405 * push_front. 406 * 407 * Tip: Using the front_inserter function to create these iterators can 408 * save typing. 409 */ 410 template<typename _Container> 411 class front_insert_iterator 412 : public iterator<output_iterator_tag, void, void, void, void> 413 { 414 protected: 415 _Container* container; 416 417 public: 418 /// A nested typedef for the type of whatever container you used. 419 typedef _Container container_type; 420 421 /// The only way to create this %iterator is with a container. 422 explicit front_insert_iterator(_Container& __x) : container(&__x) { } 423 424 /** 425 * @param value An instance of whatever type 426 * container_type::const_reference is; presumably a 427 * reference-to-const T for container<T>. 428 * @return This %iterator, for chained operations. 429 * 430 * This kind of %iterator doesn't really have a "position" in the 431 * container (you can think of the position as being permanently at 432 * the front, if you like). Assigning a value to the %iterator will 433 * always prepend the value to the front of the container. 434 */ 435 front_insert_iterator& 436 operator=(typename _Container::const_reference __value) 437 { 438 container->push_front(__value); 439 return *this; 440 } 441 442 /// Simply returns *this. 443 front_insert_iterator& 444 operator*() 445 { return *this; } 446 447 /// Simply returns *this. (This %iterator does not "move".) 448 front_insert_iterator& 449 operator++() 450 { return *this; } 451 452 /// Simply returns *this. (This %iterator does not "move".) 453 front_insert_iterator 454 operator++(int) 455 { return *this; } 456 }; 457 458 /** 459 * @param x A container of arbitrary type. 460 * @return An instance of front_insert_iterator working on @p x. 461 * 462 * This wrapper function helps in creating front_insert_iterator instances. 463 * Typing the name of the %iterator requires knowing the precise full 464 * type of the container, which can be tedious and impedes generic 465 * programming. Using this function lets you take advantage of automatic 466 * template parameter deduction, making the compiler match the correct 467 * types for you. 468 */ 469 template<typename _Container> 470 inline front_insert_iterator<_Container> 471 front_inserter(_Container& __x) 472 { return front_insert_iterator<_Container>(__x); } 473 474 /** 475 * @brief Turns assignment into insertion. 476 * 477 * These are output iterators, constructed from a container-of-T. 478 * Assigning a T to the iterator inserts it in the container at the 479 * %iterator's position, rather than overwriting the value at that 480 * position. 481 * 482 * (Sequences will actually insert a @e copy of the value before the 483 * %iterator's position.) 484 * 485 * Tip: Using the inserter function to create these iterators can 486 * save typing. 487 */ 488 template<typename _Container> 489 class insert_iterator 490 : public iterator<output_iterator_tag, void, void, void, void> 491 { 492 protected: 493 _Container* container; 494 typename _Container::iterator iter; 495 496 public: 497 /// A nested typedef for the type of whatever container you used. 498 typedef _Container container_type; 499 500 /** 501 * The only way to create this %iterator is with a container and an 502 * initial position (a normal %iterator into the container). 503 */ 504 insert_iterator(_Container& __x, typename _Container::iterator __i) 505 : container(&__x), iter(__i) {} 506 507 /** 508 * @param value An instance of whatever type 509 * container_type::const_reference is; presumably a 510 * reference-to-const T for container<T>. 511 * @return This %iterator, for chained operations. 512 * 513 * This kind of %iterator maintains its own position in the 514 * container. Assigning a value to the %iterator will insert the 515 * value into the container at the place before the %iterator. 516 * 517 * The position is maintained such that subsequent assignments will 518 * insert values immediately after one another. For example, 519 * @code 520 * // vector v contains A and Z 521 * 522 * insert_iterator i (v, ++v.begin()); 523 * i = 1; 524 * i = 2; 525 * i = 3; 526 * 527 * // vector v contains A, 1, 2, 3, and Z 528 * @endcode 529 */ 530 insert_iterator& 531 operator=(const typename _Container::const_reference __value) 532 { 533 iter = container->insert(iter, __value); 534 ++iter; 535 return *this; 536 } 537 538 /// Simply returns *this. 539 insert_iterator& 540 operator*() 541 { return *this; } 542 543 /// Simply returns *this. (This %iterator does not "move".) 544 insert_iterator& 545 operator++() 546 { return *this; } 547 548 /// Simply returns *this. (This %iterator does not "move".) 549 insert_iterator& 550 operator++(int) 551 { return *this; } 552 }; 553 554 /** 555 * @param x A container of arbitrary type. 556 * @return An instance of insert_iterator working on @p x. 557 * 558 * This wrapper function helps in creating insert_iterator instances. 559 * Typing the name of the %iterator requires knowing the precise full 560 * type of the container, which can be tedious and impedes generic 561 * programming. Using this function lets you take advantage of automatic 562 * template parameter deduction, making the compiler match the correct 563 * types for you. 564 */ 565 template<typename _Container, typename _Iterator> 566 inline insert_iterator<_Container> 567 inserter(_Container& __x, _Iterator __i) 568 { 569 return insert_iterator<_Container>(__x, 570 typename _Container::iterator(__i)); 571 } 572} // namespace std 573 574namespace __gnu_cxx 575{ 576 // This iterator adapter is 'normal' in the sense that it does not 577 // change the semantics of any of the operators of its iterator 578 // parameter. Its primary purpose is to convert an iterator that is 579 // not a class, e.g. a pointer, into an iterator that is a class. 580 // The _Container parameter exists solely so that different containers 581 // using this template can instantiate different types, even if the 582 // _Iterator parameter is the same. 583 using std::iterator_traits; 584 using std::iterator; 585 template<typename _Iterator, typename _Container> 586 class __normal_iterator 587 { 588 protected: 589 _Iterator _M_current; 590 591 public: 592 typedef typename iterator_traits<_Iterator>::iterator_category 593 iterator_category; 594 typedef typename iterator_traits<_Iterator>::value_type value_type; 595 typedef typename iterator_traits<_Iterator>::difference_type 596 difference_type; 597 typedef typename iterator_traits<_Iterator>::reference reference; 598 typedef typename iterator_traits<_Iterator>::pointer pointer; 599 600 __normal_iterator() : _M_current(_Iterator()) { } 601 602 explicit 603 __normal_iterator(const _Iterator& __i) : _M_current(__i) { } 604 605 // Allow iterator to const_iterator conversion 606 template<typename _Iter> 607 inline __normal_iterator(const __normal_iterator<_Iter, 608 _Container>& __i) 609 : _M_current(__i.base()) { } 610 611 // Forward iterator requirements 612 reference 613 operator*() const 614 { return *_M_current; } 615 616 pointer 617 operator->() const 618 { return _M_current; } 619 620 __normal_iterator& 621 operator++() 622 { 623 ++_M_current; 624 return *this; 625 } 626 627 __normal_iterator 628 operator++(int) 629 { return __normal_iterator(_M_current++); } 630 631 // Bidirectional iterator requirements 632 __normal_iterator& 633 operator--() 634 { 635 --_M_current; 636 return *this; 637 } 638 639 __normal_iterator 640 operator--(int) 641 { return __normal_iterator(_M_current--); } 642 643 // Random access iterator requirements 644 reference 645 operator[](const difference_type& __n) const 646 { return _M_current[__n]; } 647 648 __normal_iterator& 649 operator+=(const difference_type& __n) 650 { _M_current += __n; return *this; } 651 652 __normal_iterator 653 operator+(const difference_type& __n) const 654 { return __normal_iterator(_M_current + __n); } 655 656 __normal_iterator& 657 operator-=(const difference_type& __n) 658 { _M_current -= __n; return *this; } 659 660 __normal_iterator 661 operator-(const difference_type& __n) const 662 { return __normal_iterator(_M_current - __n); } 663 664 const _Iterator& 665 base() const 666 { return _M_current; } 667 }; 668 669 // Note: In what follows, the left- and right-hand-side iterators are 670 // allowed to vary in types (conceptually in cv-qualification) so that 671 // comparaison between cv-qualified and non-cv-qualified iterators be 672 // valid. However, the greedy and unfriendly operators in std::rel_ops 673 // will make overload resolution ambiguous (when in scope) if we don't 674 // provide overloads whose operands are of the same type. Can someone 675 // remind me what generic programming is about? -- Gaby 676 677 // Forward iterator requirements 678 template<typename _IteratorL, typename _IteratorR, typename _Container> 679 inline bool 680 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 681 const __normal_iterator<_IteratorR, _Container>& __rhs) 682 { return __lhs.base() == __rhs.base(); } 683 684 template<typename _Iterator, typename _Container> 685 inline bool 686 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 687 const __normal_iterator<_Iterator, _Container>& __rhs) 688 { return __lhs.base() == __rhs.base(); } 689 690 template<typename _IteratorL, typename _IteratorR, typename _Container> 691 inline bool 692 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 693 const __normal_iterator<_IteratorR, _Container>& __rhs) 694 { return __lhs.base() != __rhs.base(); } 695 696 template<typename _Iterator, typename _Container> 697 inline bool 698 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 699 const __normal_iterator<_Iterator, _Container>& __rhs) 700 { return __lhs.base() != __rhs.base(); } 701 702 // Random access iterator requirements 703 template<typename _IteratorL, typename _IteratorR, typename _Container> 704 inline bool 705 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 706 const __normal_iterator<_IteratorR, _Container>& __rhs) 707 { return __lhs.base() < __rhs.base(); } 708 709 template<typename _Iterator, typename _Container> 710 inline bool 711 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 712 const __normal_iterator<_Iterator, _Container>& __rhs) 713 { return __lhs.base() < __rhs.base(); } 714 715 template<typename _IteratorL, typename _IteratorR, typename _Container> 716 inline bool 717 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 718 const __normal_iterator<_IteratorR, _Container>& __rhs) 719 { return __lhs.base() > __rhs.base(); } 720 721 template<typename _Iterator, typename _Container> 722 inline bool 723 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 724 const __normal_iterator<_Iterator, _Container>& __rhs) 725 { return __lhs.base() > __rhs.base(); } 726 727 template<typename _IteratorL, typename _IteratorR, typename _Container> 728 inline bool 729 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 730 const __normal_iterator<_IteratorR, _Container>& __rhs) 731 { return __lhs.base() <= __rhs.base(); } 732 733 template<typename _Iterator, typename _Container> 734 inline bool 735 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 736 const __normal_iterator<_Iterator, _Container>& __rhs) 737 { return __lhs.base() <= __rhs.base(); } 738 739 template<typename _IteratorL, typename _IteratorR, typename _Container> 740 inline bool 741 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 742 const __normal_iterator<_IteratorR, _Container>& __rhs) 743 { return __lhs.base() >= __rhs.base(); } 744 745 template<typename _Iterator, typename _Container> 746 inline bool 747 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 748 const __normal_iterator<_Iterator, _Container>& __rhs) 749 { return __lhs.base() >= __rhs.base(); } 750 751 // _GLIBCXX_RESOLVE_LIB_DEFECTS 752 // According to the resolution of DR179 not only the various comparison 753 // operators but also operator- must accept mixed iterator/const_iterator 754 // parameters. 755 template<typename _IteratorL, typename _IteratorR, typename _Container> 756 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 757 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 758 const __normal_iterator<_IteratorR, _Container>& __rhs) 759 { return __lhs.base() - __rhs.base(); } 760 761 template<typename _Iterator, typename _Container> 762 inline __normal_iterator<_Iterator, _Container> 763 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 764 __n, const __normal_iterator<_Iterator, _Container>& __i) 765 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 766} // namespace __gnu_cxx 767 768#endif 769 770// Local Variables: 771// mode:C++ 772// End: 773