1 // Iterators -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996-1998 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52 /** @file bits/stl_iterator.h 53 * This is an internal header file, included by other library headers. 54 * Do not attempt to use it directly. @headername{iterator} 55 * 56 * This file implements reverse_iterator, back_insert_iterator, 57 * front_insert_iterator, insert_iterator, __normal_iterator, and their 58 * supporting functions and overloaded operators. 59 */ 60 61 #ifndef _STL_ITERATOR_H 62 #define _STL_ITERATOR_H 1 63 64 #include <bits/cpp_type_traits.h> 65 #include <ext/type_traits.h> 66 #include <bits/move.h> 67 68 namespace std _GLIBCXX_VISIBILITY(default) 69 { 70 _GLIBCXX_BEGIN_NAMESPACE_VERSION 71 72 /** 73 * @addtogroup iterators 74 * @{ 75 */ 76 77 // 24.4.1 Reverse iterators 78 /** 79 * Bidirectional and random access iterators have corresponding reverse 80 * %iterator adaptors that iterate through the data structure in the 81 * opposite direction. They have the same signatures as the corresponding 82 * iterators. The fundamental relation between a reverse %iterator and its 83 * corresponding %iterator @c i is established by the identity: 84 * @code 85 * &*(reverse_iterator(i)) == &*(i - 1) 86 * @endcode 87 * 88 * <em>This mapping is dictated by the fact that while there is always a 89 * pointer past the end of an array, there might not be a valid pointer 90 * before the beginning of an array.</em> [24.4.1]/1,2 91 * 92 * Reverse iterators can be tricky and surprising at first. Their 93 * semantics make sense, however, and the trickiness is a side effect of 94 * the requirement that the iterators must be safe. 95 */ 96 template<typename _Iterator> 97 class reverse_iterator 98 : public iterator<typename iterator_traits<_Iterator>::iterator_category, 99 typename iterator_traits<_Iterator>::value_type, 100 typename iterator_traits<_Iterator>::difference_type, 101 typename iterator_traits<_Iterator>::pointer, 102 typename iterator_traits<_Iterator>::reference> 103 { 104 protected: 105 _Iterator current; 106 107 typedef iterator_traits<_Iterator> __traits_type; 108 109 public: 110 typedef _Iterator iterator_type; 111 typedef typename __traits_type::difference_type difference_type; 112 typedef typename __traits_type::pointer pointer; 113 typedef typename __traits_type::reference reference; 114 115 /** 116 * The default constructor default-initializes member @p current. 117 * If it is a pointer, that means it is zero-initialized. 118 */ 119 // _GLIBCXX_RESOLVE_LIB_DEFECTS 120 // 235 No specification of default ctor for reverse_iterator 121 reverse_iterator() : current() { } 122 123 /** 124 * This %iterator will move in the opposite direction that @p x does. 125 */ 126 explicit 127 reverse_iterator(iterator_type __x) : current(__x) { } 128 129 /** 130 * The copy constructor is normal. 131 */ 132 reverse_iterator(const reverse_iterator& __x) 133 : current(__x.current) { } 134 135 /** 136 * A reverse_iterator across other types can be copied in the normal 137 * fashion. 138 */ 139 template<typename _Iter> 140 reverse_iterator(const reverse_iterator<_Iter>& __x) 141 : current(__x.base()) { } 142 143 /** 144 * @return @c current, the %iterator used for underlying work. 145 */ 146 iterator_type 147 base() const 148 { return current; } 149 150 /** 151 * @return TODO 152 * 153 * @doctodo 154 */ 155 reference 156 operator*() const 157 { 158 _Iterator __tmp = current; 159 return *--__tmp; 160 } 161 162 /** 163 * @return TODO 164 * 165 * @doctodo 166 */ 167 pointer 168 operator->() const 169 { return &(operator*()); } 170 171 /** 172 * @return TODO 173 * 174 * @doctodo 175 */ 176 reverse_iterator& 177 operator++() 178 { 179 --current; 180 return *this; 181 } 182 183 /** 184 * @return TODO 185 * 186 * @doctodo 187 */ 188 reverse_iterator 189 operator++(int) 190 { 191 reverse_iterator __tmp = *this; 192 --current; 193 return __tmp; 194 } 195 196 /** 197 * @return TODO 198 * 199 * @doctodo 200 */ 201 reverse_iterator& 202 operator--() 203 { 204 ++current; 205 return *this; 206 } 207 208 /** 209 * @return TODO 210 * 211 * @doctodo 212 */ 213 reverse_iterator 214 operator--(int) 215 { 216 reverse_iterator __tmp = *this; 217 ++current; 218 return __tmp; 219 } 220 221 /** 222 * @return TODO 223 * 224 * @doctodo 225 */ 226 reverse_iterator 227 operator+(difference_type __n) const 228 { return reverse_iterator(current - __n); } 229 230 /** 231 * @return TODO 232 * 233 * @doctodo 234 */ 235 reverse_iterator& 236 operator+=(difference_type __n) 237 { 238 current -= __n; 239 return *this; 240 } 241 242 /** 243 * @return TODO 244 * 245 * @doctodo 246 */ 247 reverse_iterator 248 operator-(difference_type __n) const 249 { return reverse_iterator(current + __n); } 250 251 /** 252 * @return TODO 253 * 254 * @doctodo 255 */ 256 reverse_iterator& 257 operator-=(difference_type __n) 258 { 259 current += __n; 260 return *this; 261 } 262 263 /** 264 * @return TODO 265 * 266 * @doctodo 267 */ 268 reference 269 operator[](difference_type __n) const 270 { return *(*this + __n); } 271 }; 272 273 //@{ 274 /** 275 * @param x A %reverse_iterator. 276 * @param y A %reverse_iterator. 277 * @return A simple bool. 278 * 279 * Reverse iterators forward many operations to their underlying base() 280 * iterators. Others are implemented in terms of one another. 281 * 282 */ 283 template<typename _Iterator> 284 inline bool 285 operator==(const reverse_iterator<_Iterator>& __x, 286 const reverse_iterator<_Iterator>& __y) 287 { return __x.base() == __y.base(); } 288 289 template<typename _Iterator> 290 inline bool 291 operator<(const reverse_iterator<_Iterator>& __x, 292 const reverse_iterator<_Iterator>& __y) 293 { return __y.base() < __x.base(); } 294 295 template<typename _Iterator> 296 inline bool 297 operator!=(const reverse_iterator<_Iterator>& __x, 298 const reverse_iterator<_Iterator>& __y) 299 { return !(__x == __y); } 300 301 template<typename _Iterator> 302 inline bool 303 operator>(const reverse_iterator<_Iterator>& __x, 304 const reverse_iterator<_Iterator>& __y) 305 { return __y < __x; } 306 307 template<typename _Iterator> 308 inline bool 309 operator<=(const reverse_iterator<_Iterator>& __x, 310 const reverse_iterator<_Iterator>& __y) 311 { return !(__y < __x); } 312 313 template<typename _Iterator> 314 inline bool 315 operator>=(const reverse_iterator<_Iterator>& __x, 316 const reverse_iterator<_Iterator>& __y) 317 { return !(__x < __y); } 318 319 template<typename _Iterator> 320 inline typename reverse_iterator<_Iterator>::difference_type 321 operator-(const reverse_iterator<_Iterator>& __x, 322 const reverse_iterator<_Iterator>& __y) 323 { return __y.base() - __x.base(); } 324 325 template<typename _Iterator> 326 inline reverse_iterator<_Iterator> 327 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 328 const reverse_iterator<_Iterator>& __x) 329 { return reverse_iterator<_Iterator>(__x.base() - __n); } 330 331 // _GLIBCXX_RESOLVE_LIB_DEFECTS 332 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 333 template<typename _IteratorL, typename _IteratorR> 334 inline bool 335 operator==(const reverse_iterator<_IteratorL>& __x, 336 const reverse_iterator<_IteratorR>& __y) 337 { return __x.base() == __y.base(); } 338 339 template<typename _IteratorL, typename _IteratorR> 340 inline bool 341 operator<(const reverse_iterator<_IteratorL>& __x, 342 const reverse_iterator<_IteratorR>& __y) 343 { return __y.base() < __x.base(); } 344 345 template<typename _IteratorL, typename _IteratorR> 346 inline bool 347 operator!=(const reverse_iterator<_IteratorL>& __x, 348 const reverse_iterator<_IteratorR>& __y) 349 { return !(__x == __y); } 350 351 template<typename _IteratorL, typename _IteratorR> 352 inline bool 353 operator>(const reverse_iterator<_IteratorL>& __x, 354 const reverse_iterator<_IteratorR>& __y) 355 { return __y < __x; } 356 357 template<typename _IteratorL, typename _IteratorR> 358 inline bool 359 operator<=(const reverse_iterator<_IteratorL>& __x, 360 const reverse_iterator<_IteratorR>& __y) 361 { return !(__y < __x); } 362 363 template<typename _IteratorL, typename _IteratorR> 364 inline bool 365 operator>=(const reverse_iterator<_IteratorL>& __x, 366 const reverse_iterator<_IteratorR>& __y) 367 { return !(__x < __y); } 368 369 template<typename _IteratorL, typename _IteratorR> 370 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 371 // DR 685. 372 inline auto 373 operator-(const reverse_iterator<_IteratorL>& __x, 374 const reverse_iterator<_IteratorR>& __y) 375 -> decltype(__y.base() - __x.base()) 376 #else 377 inline typename reverse_iterator<_IteratorL>::difference_type 378 operator-(const reverse_iterator<_IteratorL>& __x, 379 const reverse_iterator<_IteratorR>& __y) 380 #endif 381 { return __y.base() - __x.base(); } 382 //@} 383 384 // 24.4.2.2.1 back_insert_iterator 385 /** 386 * @brief Turns assignment into insertion. 387 * 388 * These are output iterators, constructed from a container-of-T. 389 * Assigning a T to the iterator appends it to the container using 390 * push_back. 391 * 392 * Tip: Using the back_inserter function to create these iterators can 393 * save typing. 394 */ 395 template<typename _Container> 396 class back_insert_iterator 397 : public iterator<output_iterator_tag, void, void, void, void> 398 { 399 protected: 400 _Container* container; 401 402 public: 403 /// A nested typedef for the type of whatever container you used. 404 typedef _Container container_type; 405 406 /// The only way to create this %iterator is with a container. 407 explicit 408 back_insert_iterator(_Container& __x) : container(&__x) { } 409 410 /** 411 * @param value An instance of whatever type 412 * container_type::const_reference is; presumably a 413 * reference-to-const T for container<T>. 414 * @return This %iterator, for chained operations. 415 * 416 * This kind of %iterator doesn't really have a @a position in the 417 * container (you can think of the position as being permanently at 418 * the end, if you like). Assigning a value to the %iterator will 419 * always append the value to the end of the container. 420 */ 421 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 422 back_insert_iterator& 423 operator=(typename _Container::const_reference __value) 424 { 425 container->push_back(__value); 426 return *this; 427 } 428 #else 429 back_insert_iterator& 430 operator=(const typename _Container::value_type& __value) 431 { 432 container->push_back(__value); 433 return *this; 434 } 435 436 back_insert_iterator& 437 operator=(typename _Container::value_type&& __value) 438 { 439 container->push_back(std::move(__value)); 440 return *this; 441 } 442 #endif 443 444 /// Simply returns *this. 445 back_insert_iterator& 446 operator*() 447 { return *this; } 448 449 /// Simply returns *this. (This %iterator does not @a move.) 450 back_insert_iterator& 451 operator++() 452 { return *this; } 453 454 /// Simply returns *this. (This %iterator does not @a move.) 455 back_insert_iterator 456 operator++(int) 457 { return *this; } 458 }; 459 460 /** 461 * @param x A container of arbitrary type. 462 * @return An instance of back_insert_iterator working on @p x. 463 * 464 * This wrapper function helps in creating back_insert_iterator instances. 465 * Typing the name of the %iterator requires knowing the precise full 466 * type of the container, which can be tedious and impedes generic 467 * programming. Using this function lets you take advantage of automatic 468 * template parameter deduction, making the compiler match the correct 469 * types for you. 470 */ 471 template<typename _Container> 472 inline back_insert_iterator<_Container> 473 back_inserter(_Container& __x) 474 { return back_insert_iterator<_Container>(__x); } 475 476 /** 477 * @brief Turns assignment into insertion. 478 * 479 * These are output iterators, constructed from a container-of-T. 480 * Assigning a T to the iterator prepends it to the container using 481 * push_front. 482 * 483 * Tip: Using the front_inserter function to create these iterators can 484 * save typing. 485 */ 486 template<typename _Container> 487 class front_insert_iterator 488 : public iterator<output_iterator_tag, void, void, void, void> 489 { 490 protected: 491 _Container* container; 492 493 public: 494 /// A nested typedef for the type of whatever container you used. 495 typedef _Container container_type; 496 497 /// The only way to create this %iterator is with a container. 498 explicit front_insert_iterator(_Container& __x) : container(&__x) { } 499 500 /** 501 * @param value An instance of whatever type 502 * container_type::const_reference is; presumably a 503 * reference-to-const T for container<T>. 504 * @return This %iterator, for chained operations. 505 * 506 * This kind of %iterator doesn't really have a @a position in the 507 * container (you can think of the position as being permanently at 508 * the front, if you like). Assigning a value to the %iterator will 509 * always prepend the value to the front of the container. 510 */ 511 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 512 front_insert_iterator& 513 operator=(typename _Container::const_reference __value) 514 { 515 container->push_front(__value); 516 return *this; 517 } 518 #else 519 front_insert_iterator& 520 operator=(const typename _Container::value_type& __value) 521 { 522 container->push_front(__value); 523 return *this; 524 } 525 526 front_insert_iterator& 527 operator=(typename _Container::value_type&& __value) 528 { 529 container->push_front(std::move(__value)); 530 return *this; 531 } 532 #endif 533 534 /// Simply returns *this. 535 front_insert_iterator& 536 operator*() 537 { return *this; } 538 539 /// Simply returns *this. (This %iterator does not @a move.) 540 front_insert_iterator& 541 operator++() 542 { return *this; } 543 544 /// Simply returns *this. (This %iterator does not @a move.) 545 front_insert_iterator 546 operator++(int) 547 { return *this; } 548 }; 549 550 /** 551 * @param x A container of arbitrary type. 552 * @return An instance of front_insert_iterator working on @p x. 553 * 554 * This wrapper function helps in creating front_insert_iterator instances. 555 * Typing the name of the %iterator requires knowing the precise full 556 * type of the container, which can be tedious and impedes generic 557 * programming. Using this function lets you take advantage of automatic 558 * template parameter deduction, making the compiler match the correct 559 * types for you. 560 */ 561 template<typename _Container> 562 inline front_insert_iterator<_Container> 563 front_inserter(_Container& __x) 564 { return front_insert_iterator<_Container>(__x); } 565 566 /** 567 * @brief Turns assignment into insertion. 568 * 569 * These are output iterators, constructed from a container-of-T. 570 * Assigning a T to the iterator inserts it in the container at the 571 * %iterator's position, rather than overwriting the value at that 572 * position. 573 * 574 * (Sequences will actually insert a @e copy of the value before the 575 * %iterator's position.) 576 * 577 * Tip: Using the inserter function to create these iterators can 578 * save typing. 579 */ 580 template<typename _Container> 581 class insert_iterator 582 : public iterator<output_iterator_tag, void, void, void, void> 583 { 584 protected: 585 _Container* container; 586 typename _Container::iterator iter; 587 588 public: 589 /// A nested typedef for the type of whatever container you used. 590 typedef _Container container_type; 591 592 /** 593 * The only way to create this %iterator is with a container and an 594 * initial position (a normal %iterator into the container). 595 */ 596 insert_iterator(_Container& __x, typename _Container::iterator __i) 597 : container(&__x), iter(__i) {} 598 599 /** 600 * @param value An instance of whatever type 601 * container_type::const_reference is; presumably a 602 * reference-to-const T for container<T>. 603 * @return This %iterator, for chained operations. 604 * 605 * This kind of %iterator maintains its own position in the 606 * container. Assigning a value to the %iterator will insert the 607 * value into the container at the place before the %iterator. 608 * 609 * The position is maintained such that subsequent assignments will 610 * insert values immediately after one another. For example, 611 * @code 612 * // vector v contains A and Z 613 * 614 * insert_iterator i (v, ++v.begin()); 615 * i = 1; 616 * i = 2; 617 * i = 3; 618 * 619 * // vector v contains A, 1, 2, 3, and Z 620 * @endcode 621 */ 622 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 623 insert_iterator& 624 operator=(typename _Container::const_reference __value) 625 { 626 iter = container->insert(iter, __value); 627 ++iter; 628 return *this; 629 } 630 #else 631 insert_iterator& 632 operator=(const typename _Container::value_type& __value) 633 { 634 iter = container->insert(iter, __value); 635 ++iter; 636 return *this; 637 } 638 639 insert_iterator& 640 operator=(typename _Container::value_type&& __value) 641 { 642 iter = container->insert(iter, std::move(__value)); 643 ++iter; 644 return *this; 645 } 646 #endif 647 648 /// Simply returns *this. 649 insert_iterator& 650 operator*() 651 { return *this; } 652 653 /// Simply returns *this. (This %iterator does not @a move.) 654 insert_iterator& 655 operator++() 656 { return *this; } 657 658 /// Simply returns *this. (This %iterator does not @a move.) 659 insert_iterator& 660 operator++(int) 661 { return *this; } 662 }; 663 664 /** 665 * @param x A container of arbitrary type. 666 * @return An instance of insert_iterator working on @p x. 667 * 668 * This wrapper function helps in creating insert_iterator instances. 669 * Typing the name of the %iterator requires knowing the precise full 670 * type of the container, which can be tedious and impedes generic 671 * programming. Using this function lets you take advantage of automatic 672 * template parameter deduction, making the compiler match the correct 673 * types for you. 674 */ 675 template<typename _Container, typename _Iterator> 676 inline insert_iterator<_Container> 677 inserter(_Container& __x, _Iterator __i) 678 { 679 return insert_iterator<_Container>(__x, 680 typename _Container::iterator(__i)); 681 } 682 683 // @} group iterators 684 685 _GLIBCXX_END_NAMESPACE_VERSION 686 } // namespace 687 688 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 689 { 690 _GLIBCXX_BEGIN_NAMESPACE_VERSION 691 692 // This iterator adapter is @a normal in the sense that it does not 693 // change the semantics of any of the operators of its iterator 694 // parameter. Its primary purpose is to convert an iterator that is 695 // not a class, e.g. a pointer, into an iterator that is a class. 696 // The _Container parameter exists solely so that different containers 697 // using this template can instantiate different types, even if the 698 // _Iterator parameter is the same. 699 using std::iterator_traits; 700 using std::iterator; 701 template<typename _Iterator, typename _Container> 702 class __normal_iterator 703 { 704 protected: 705 _Iterator _M_current; 706 707 typedef iterator_traits<_Iterator> __traits_type; 708 709 public: 710 typedef _Iterator iterator_type; 711 typedef typename __traits_type::iterator_category iterator_category; 712 typedef typename __traits_type::value_type value_type; 713 typedef typename __traits_type::difference_type difference_type; 714 typedef typename __traits_type::reference reference; 715 typedef typename __traits_type::pointer pointer; 716 717 _GLIBCXX_CONSTEXPR __normal_iterator() : _M_current(_Iterator()) { } 718 719 explicit 720 __normal_iterator(const _Iterator& __i) : _M_current(__i) { } 721 722 // Allow iterator to const_iterator conversion 723 template<typename _Iter> 724 __normal_iterator(const __normal_iterator<_Iter, 725 typename __enable_if< 726 (std::__are_same<_Iter, typename _Container::pointer>::__value), 727 _Container>::__type>& __i) 728 : _M_current(__i.base()) { } 729 730 // Forward iterator requirements 731 reference 732 operator*() const 733 { return *_M_current; } 734 735 pointer 736 operator->() const 737 { return _M_current; } 738 739 __normal_iterator& 740 operator++() 741 { 742 ++_M_current; 743 return *this; 744 } 745 746 __normal_iterator 747 operator++(int) 748 { return __normal_iterator(_M_current++); } 749 750 // Bidirectional iterator requirements 751 __normal_iterator& 752 operator--() 753 { 754 --_M_current; 755 return *this; 756 } 757 758 __normal_iterator 759 operator--(int) 760 { return __normal_iterator(_M_current--); } 761 762 // Random access iterator requirements 763 reference 764 operator[](const difference_type& __n) const 765 { return _M_current[__n]; } 766 767 __normal_iterator& 768 operator+=(const difference_type& __n) 769 { _M_current += __n; return *this; } 770 771 __normal_iterator 772 operator+(const difference_type& __n) const 773 { return __normal_iterator(_M_current + __n); } 774 775 __normal_iterator& 776 operator-=(const difference_type& __n) 777 { _M_current -= __n; return *this; } 778 779 __normal_iterator 780 operator-(const difference_type& __n) const 781 { return __normal_iterator(_M_current - __n); } 782 783 const _Iterator& 784 base() const 785 { return _M_current; } 786 }; 787 788 // Note: In what follows, the left- and right-hand-side iterators are 789 // allowed to vary in types (conceptually in cv-qualification) so that 790 // comparison between cv-qualified and non-cv-qualified iterators be 791 // valid. However, the greedy and unfriendly operators in std::rel_ops 792 // will make overload resolution ambiguous (when in scope) if we don't 793 // provide overloads whose operands are of the same type. Can someone 794 // remind me what generic programming is about? -- Gaby 795 796 // Forward iterator requirements 797 template<typename _IteratorL, typename _IteratorR, typename _Container> 798 inline bool 799 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 800 const __normal_iterator<_IteratorR, _Container>& __rhs) 801 { return __lhs.base() == __rhs.base(); } 802 803 template<typename _Iterator, typename _Container> 804 inline bool 805 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 806 const __normal_iterator<_Iterator, _Container>& __rhs) 807 { return __lhs.base() == __rhs.base(); } 808 809 template<typename _IteratorL, typename _IteratorR, typename _Container> 810 inline bool 811 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 812 const __normal_iterator<_IteratorR, _Container>& __rhs) 813 { return __lhs.base() != __rhs.base(); } 814 815 template<typename _Iterator, typename _Container> 816 inline bool 817 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 818 const __normal_iterator<_Iterator, _Container>& __rhs) 819 { return __lhs.base() != __rhs.base(); } 820 821 // Random access iterator requirements 822 template<typename _IteratorL, typename _IteratorR, typename _Container> 823 inline bool 824 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 825 const __normal_iterator<_IteratorR, _Container>& __rhs) 826 { return __lhs.base() < __rhs.base(); } 827 828 template<typename _Iterator, typename _Container> 829 inline bool 830 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 831 const __normal_iterator<_Iterator, _Container>& __rhs) 832 { return __lhs.base() < __rhs.base(); } 833 834 template<typename _IteratorL, typename _IteratorR, typename _Container> 835 inline bool 836 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 837 const __normal_iterator<_IteratorR, _Container>& __rhs) 838 { return __lhs.base() > __rhs.base(); } 839 840 template<typename _Iterator, typename _Container> 841 inline bool 842 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 843 const __normal_iterator<_Iterator, _Container>& __rhs) 844 { return __lhs.base() > __rhs.base(); } 845 846 template<typename _IteratorL, typename _IteratorR, typename _Container> 847 inline bool 848 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 849 const __normal_iterator<_IteratorR, _Container>& __rhs) 850 { return __lhs.base() <= __rhs.base(); } 851 852 template<typename _Iterator, typename _Container> 853 inline bool 854 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 855 const __normal_iterator<_Iterator, _Container>& __rhs) 856 { return __lhs.base() <= __rhs.base(); } 857 858 template<typename _IteratorL, typename _IteratorR, typename _Container> 859 inline bool 860 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 861 const __normal_iterator<_IteratorR, _Container>& __rhs) 862 { return __lhs.base() >= __rhs.base(); } 863 864 template<typename _Iterator, typename _Container> 865 inline bool 866 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 867 const __normal_iterator<_Iterator, _Container>& __rhs) 868 { return __lhs.base() >= __rhs.base(); } 869 870 // _GLIBCXX_RESOLVE_LIB_DEFECTS 871 // According to the resolution of DR179 not only the various comparison 872 // operators but also operator- must accept mixed iterator/const_iterator 873 // parameters. 874 template<typename _IteratorL, typename _IteratorR, typename _Container> 875 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 876 // DR 685. 877 inline auto 878 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 879 const __normal_iterator<_IteratorR, _Container>& __rhs) 880 -> decltype(__lhs.base() - __rhs.base()) 881 #else 882 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 883 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 884 const __normal_iterator<_IteratorR, _Container>& __rhs) 885 #endif 886 { return __lhs.base() - __rhs.base(); } 887 888 template<typename _Iterator, typename _Container> 889 inline typename __normal_iterator<_Iterator, _Container>::difference_type 890 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 891 const __normal_iterator<_Iterator, _Container>& __rhs) 892 { return __lhs.base() - __rhs.base(); } 893 894 template<typename _Iterator, typename _Container> 895 inline __normal_iterator<_Iterator, _Container> 896 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 897 __n, const __normal_iterator<_Iterator, _Container>& __i) 898 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 899 900 _GLIBCXX_END_NAMESPACE_VERSION 901 } // namespace 902 903 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 904 905 namespace std _GLIBCXX_VISIBILITY(default) 906 { 907 _GLIBCXX_BEGIN_NAMESPACE_VERSION 908 909 /** 910 * @addtogroup iterators 911 * @{ 912 */ 913 914 // 24.4.3 Move iterators 915 /** 916 * Class template move_iterator is an iterator adapter with the same 917 * behavior as the underlying iterator except that its dereference 918 * operator implicitly converts the value returned by the underlying 919 * iterator's dereference operator to an rvalue reference. Some 920 * generic algorithms can be called with move iterators to replace 921 * copying with moving. 922 */ 923 template<typename _Iterator> 924 class move_iterator 925 { 926 protected: 927 _Iterator _M_current; 928 929 typedef iterator_traits<_Iterator> __traits_type; 930 931 public: 932 typedef _Iterator iterator_type; 933 typedef typename __traits_type::iterator_category iterator_category; 934 typedef typename __traits_type::value_type value_type; 935 typedef typename __traits_type::difference_type difference_type; 936 // NB: DR 680. 937 typedef _Iterator pointer; 938 typedef value_type&& reference; 939 940 move_iterator() 941 : _M_current() { } 942 943 explicit 944 move_iterator(iterator_type __i) 945 : _M_current(__i) { } 946 947 template<typename _Iter> 948 move_iterator(const move_iterator<_Iter>& __i) 949 : _M_current(__i.base()) { } 950 951 iterator_type 952 base() const 953 { return _M_current; } 954 955 reference 956 operator*() const 957 { return std::move(*_M_current); } 958 959 pointer 960 operator->() const 961 { return _M_current; } 962 963 move_iterator& 964 operator++() 965 { 966 ++_M_current; 967 return *this; 968 } 969 970 move_iterator 971 operator++(int) 972 { 973 move_iterator __tmp = *this; 974 ++_M_current; 975 return __tmp; 976 } 977 978 move_iterator& 979 operator--() 980 { 981 --_M_current; 982 return *this; 983 } 984 985 move_iterator 986 operator--(int) 987 { 988 move_iterator __tmp = *this; 989 --_M_current; 990 return __tmp; 991 } 992 993 move_iterator 994 operator+(difference_type __n) const 995 { return move_iterator(_M_current + __n); } 996 997 move_iterator& 998 operator+=(difference_type __n) 999 { 1000 _M_current += __n; 1001 return *this; 1002 } 1003 1004 move_iterator 1005 operator-(difference_type __n) const 1006 { return move_iterator(_M_current - __n); } 1007 1008 move_iterator& 1009 operator-=(difference_type __n) 1010 { 1011 _M_current -= __n; 1012 return *this; 1013 } 1014 1015 reference 1016 operator[](difference_type __n) const 1017 { return std::move(_M_current[__n]); } 1018 }; 1019 1020 // Note: See __normal_iterator operators note from Gaby to understand 1021 // why there are always 2 versions for most of the move_iterator 1022 // operators. 1023 template<typename _IteratorL, typename _IteratorR> 1024 inline bool 1025 operator==(const move_iterator<_IteratorL>& __x, 1026 const move_iterator<_IteratorR>& __y) 1027 { return __x.base() == __y.base(); } 1028 1029 template<typename _Iterator> 1030 inline bool 1031 operator==(const move_iterator<_Iterator>& __x, 1032 const move_iterator<_Iterator>& __y) 1033 { return __x.base() == __y.base(); } 1034 1035 template<typename _IteratorL, typename _IteratorR> 1036 inline bool 1037 operator!=(const move_iterator<_IteratorL>& __x, 1038 const move_iterator<_IteratorR>& __y) 1039 { return !(__x == __y); } 1040 1041 template<typename _Iterator> 1042 inline bool 1043 operator!=(const move_iterator<_Iterator>& __x, 1044 const move_iterator<_Iterator>& __y) 1045 { return !(__x == __y); } 1046 1047 template<typename _IteratorL, typename _IteratorR> 1048 inline bool 1049 operator<(const move_iterator<_IteratorL>& __x, 1050 const move_iterator<_IteratorR>& __y) 1051 { return __x.base() < __y.base(); } 1052 1053 template<typename _Iterator> 1054 inline bool 1055 operator<(const move_iterator<_Iterator>& __x, 1056 const move_iterator<_Iterator>& __y) 1057 { return __x.base() < __y.base(); } 1058 1059 template<typename _IteratorL, typename _IteratorR> 1060 inline bool 1061 operator<=(const move_iterator<_IteratorL>& __x, 1062 const move_iterator<_IteratorR>& __y) 1063 { return !(__y < __x); } 1064 1065 template<typename _Iterator> 1066 inline bool 1067 operator<=(const move_iterator<_Iterator>& __x, 1068 const move_iterator<_Iterator>& __y) 1069 { return !(__y < __x); } 1070 1071 template<typename _IteratorL, typename _IteratorR> 1072 inline bool 1073 operator>(const move_iterator<_IteratorL>& __x, 1074 const move_iterator<_IteratorR>& __y) 1075 { return __y < __x; } 1076 1077 template<typename _Iterator> 1078 inline bool 1079 operator>(const move_iterator<_Iterator>& __x, 1080 const move_iterator<_Iterator>& __y) 1081 { return __y < __x; } 1082 1083 template<typename _IteratorL, typename _IteratorR> 1084 inline bool 1085 operator>=(const move_iterator<_IteratorL>& __x, 1086 const move_iterator<_IteratorR>& __y) 1087 { return !(__x < __y); } 1088 1089 template<typename _Iterator> 1090 inline bool 1091 operator>=(const move_iterator<_Iterator>& __x, 1092 const move_iterator<_Iterator>& __y) 1093 { return !(__x < __y); } 1094 1095 // DR 685. 1096 template<typename _IteratorL, typename _IteratorR> 1097 inline auto 1098 operator-(const move_iterator<_IteratorL>& __x, 1099 const move_iterator<_IteratorR>& __y) 1100 -> decltype(__x.base() - __y.base()) 1101 { return __x.base() - __y.base(); } 1102 1103 template<typename _Iterator> 1104 inline auto 1105 operator-(const move_iterator<_Iterator>& __x, 1106 const move_iterator<_Iterator>& __y) 1107 -> decltype(__x.base() - __y.base()) 1108 { return __x.base() - __y.base(); } 1109 1110 template<typename _Iterator> 1111 inline move_iterator<_Iterator> 1112 operator+(typename move_iterator<_Iterator>::difference_type __n, 1113 const move_iterator<_Iterator>& __x) 1114 { return __x + __n; } 1115 1116 template<typename _Iterator> 1117 inline move_iterator<_Iterator> 1118 make_move_iterator(const _Iterator& __i) 1119 { return move_iterator<_Iterator>(__i); } 1120 1121 // @} group iterators 1122 1123 _GLIBCXX_END_NAMESPACE_VERSION 1124 } // namespace 1125 1126 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 1127 #else 1128 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 1129 #endif // __GXX_EXPERIMENTAL_CXX0X__ 1130 1131 #endif 1132