1 // Iterators -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 stl_iterator.h 53 * This is an internal header file, included by other library headers. 54 * You should not attempt to use it directly. 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 _GLIBCXX_BEGIN_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 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 207 operator--(int) 208 { 209 reverse_iterator __tmp = *this; 210 ++current; 211 return __tmp; 212 } 213 214 /** 215 * @return TODO 216 * 217 * @doctodo 218 */ 219 reverse_iterator 220 operator+(difference_type __n) const 221 { return reverse_iterator(current - __n); } 222 223 /** 224 * @return TODO 225 * 226 * @doctodo 227 */ 228 reverse_iterator& 229 operator+=(difference_type __n) 230 { 231 current -= __n; 232 return *this; 233 } 234 235 /** 236 * @return TODO 237 * 238 * @doctodo 239 */ 240 reverse_iterator 241 operator-(difference_type __n) const 242 { return reverse_iterator(current + __n); } 243 244 /** 245 * @return TODO 246 * 247 * @doctodo 248 */ 249 reverse_iterator& 250 operator-=(difference_type __n) 251 { 252 current += __n; 253 return *this; 254 } 255 256 /** 257 * @return TODO 258 * 259 * @doctodo 260 */ 261 reference 262 operator[](difference_type __n) const 263 { return *(*this + __n); } 264 }; 265 266 //@{ 267 /** 268 * @param x A %reverse_iterator. 269 * @param y A %reverse_iterator. 270 * @return A simple bool. 271 * 272 * Reverse iterators forward many operations to their underlying base() 273 * iterators. Others are implemented in terms of one another. 274 * 275 */ 276 template<typename _Iterator> 277 inline bool 278 operator==(const reverse_iterator<_Iterator>& __x, 279 const reverse_iterator<_Iterator>& __y) 280 { return __x.base() == __y.base(); } 281 282 template<typename _Iterator> 283 inline bool 284 operator<(const reverse_iterator<_Iterator>& __x, 285 const reverse_iterator<_Iterator>& __y) 286 { return __y.base() < __x.base(); } 287 288 template<typename _Iterator> 289 inline bool 290 operator!=(const reverse_iterator<_Iterator>& __x, 291 const reverse_iterator<_Iterator>& __y) 292 { return !(__x == __y); } 293 294 template<typename _Iterator> 295 inline bool 296 operator>(const reverse_iterator<_Iterator>& __x, 297 const reverse_iterator<_Iterator>& __y) 298 { return __y < __x; } 299 300 template<typename _Iterator> 301 inline bool 302 operator<=(const reverse_iterator<_Iterator>& __x, 303 const reverse_iterator<_Iterator>& __y) 304 { return !(__y < __x); } 305 306 template<typename _Iterator> 307 inline bool 308 operator>=(const reverse_iterator<_Iterator>& __x, 309 const reverse_iterator<_Iterator>& __y) 310 { return !(__x < __y); } 311 312 template<typename _Iterator> 313 inline typename reverse_iterator<_Iterator>::difference_type 314 operator-(const reverse_iterator<_Iterator>& __x, 315 const reverse_iterator<_Iterator>& __y) 316 { return __y.base() - __x.base(); } 317 318 template<typename _Iterator> 319 inline reverse_iterator<_Iterator> 320 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 321 const reverse_iterator<_Iterator>& __x) 322 { return reverse_iterator<_Iterator>(__x.base() - __n); } 323 324 // _GLIBCXX_RESOLVE_LIB_DEFECTS 325 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 326 template<typename _IteratorL, typename _IteratorR> 327 inline bool 328 operator==(const reverse_iterator<_IteratorL>& __x, 329 const reverse_iterator<_IteratorR>& __y) 330 { return __x.base() == __y.base(); } 331 332 template<typename _IteratorL, typename _IteratorR> 333 inline bool 334 operator<(const reverse_iterator<_IteratorL>& __x, 335 const reverse_iterator<_IteratorR>& __y) 336 { return __y.base() < __x.base(); } 337 338 template<typename _IteratorL, typename _IteratorR> 339 inline bool 340 operator!=(const reverse_iterator<_IteratorL>& __x, 341 const reverse_iterator<_IteratorR>& __y) 342 { return !(__x == __y); } 343 344 template<typename _IteratorL, typename _IteratorR> 345 inline bool 346 operator>(const reverse_iterator<_IteratorL>& __x, 347 const reverse_iterator<_IteratorR>& __y) 348 { return __y < __x; } 349 350 template<typename _IteratorL, typename _IteratorR> 351 inline bool 352 operator<=(const reverse_iterator<_IteratorL>& __x, 353 const reverse_iterator<_IteratorR>& __y) 354 { return !(__y < __x); } 355 356 template<typename _IteratorL, typename _IteratorR> 357 inline bool 358 operator>=(const reverse_iterator<_IteratorL>& __x, 359 const reverse_iterator<_IteratorR>& __y) 360 { return !(__x < __y); } 361 362 template<typename _IteratorL, typename _IteratorR> 363 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 364 // DR 685. 365 inline auto 366 operator-(const reverse_iterator<_IteratorL>& __x, 367 const reverse_iterator<_IteratorR>& __y) 368 -> decltype(__y.base() - __x.base()) 369 #else 370 inline typename reverse_iterator<_IteratorL>::difference_type 371 operator-(const reverse_iterator<_IteratorL>& __x, 372 const reverse_iterator<_IteratorR>& __y) 373 #endif 374 { return __y.base() - __x.base(); } 375 //@} 376 377 // 24.4.2.2.1 back_insert_iterator 378 /** 379 * @brief Turns assignment into insertion. 380 * 381 * These are output iterators, constructed from a container-of-T. 382 * Assigning a T to the iterator appends it to the container using 383 * push_back. 384 * 385 * Tip: Using the back_inserter function to create these iterators can 386 * save typing. 387 */ 388 template<typename _Container> 389 class back_insert_iterator 390 : public iterator<output_iterator_tag, void, void, void, void> 391 { 392 protected: 393 _Container* container; 394 395 public: 396 /// A nested typedef for the type of whatever container you used. 397 typedef _Container container_type; 398 399 /// The only way to create this %iterator is with a container. 400 explicit 401 back_insert_iterator(_Container& __x) : container(&__x) { } 402 403 /** 404 * @param value An instance of whatever type 405 * container_type::const_reference is; presumably a 406 * reference-to-const T for container<T>. 407 * @return This %iterator, for chained operations. 408 * 409 * This kind of %iterator doesn't really have a "position" in the 410 * container (you can think of the position as being permanently at 411 * the end, if you like). Assigning a value to the %iterator will 412 * always append the value to the end of the container. 413 */ 414 back_insert_iterator& 415 operator=(typename _Container::const_reference __value) 416 { 417 container->push_back(__value); 418 return *this; 419 } 420 421 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 422 back_insert_iterator& 423 operator=(typename _Container::value_type&& __value) 424 { 425 container->push_back(std::move(__value)); 426 return *this; 427 } 428 #endif 429 430 /// Simply returns *this. 431 back_insert_iterator& 432 operator*() 433 { return *this; } 434 435 /// Simply returns *this. (This %iterator does not "move".) 436 back_insert_iterator& 437 operator++() 438 { return *this; } 439 440 /// Simply returns *this. (This %iterator does not "move".) 441 back_insert_iterator 442 operator++(int) 443 { return *this; } 444 }; 445 446 /** 447 * @param x A container of arbitrary type. 448 * @return An instance of back_insert_iterator working on @p x. 449 * 450 * This wrapper function helps in creating back_insert_iterator instances. 451 * Typing the name of the %iterator requires knowing the precise full 452 * type of the container, which can be tedious and impedes generic 453 * programming. Using this function lets you take advantage of automatic 454 * template parameter deduction, making the compiler match the correct 455 * types for you. 456 */ 457 template<typename _Container> 458 inline back_insert_iterator<_Container> 459 back_inserter(_Container& __x) 460 { return back_insert_iterator<_Container>(__x); } 461 462 /** 463 * @brief Turns assignment into insertion. 464 * 465 * These are output iterators, constructed from a container-of-T. 466 * Assigning a T to the iterator prepends it to the container using 467 * push_front. 468 * 469 * Tip: Using the front_inserter function to create these iterators can 470 * save typing. 471 */ 472 template<typename _Container> 473 class front_insert_iterator 474 : public iterator<output_iterator_tag, void, void, void, void> 475 { 476 protected: 477 _Container* container; 478 479 public: 480 /// A nested typedef for the type of whatever container you used. 481 typedef _Container container_type; 482 483 /// The only way to create this %iterator is with a container. 484 explicit front_insert_iterator(_Container& __x) : container(&__x) { } 485 486 /** 487 * @param value An instance of whatever type 488 * container_type::const_reference is; presumably a 489 * reference-to-const T for container<T>. 490 * @return This %iterator, for chained operations. 491 * 492 * This kind of %iterator doesn't really have a "position" in the 493 * container (you can think of the position as being permanently at 494 * the front, if you like). Assigning a value to the %iterator will 495 * always prepend the value to the front of the container. 496 */ 497 front_insert_iterator& 498 operator=(typename _Container::const_reference __value) 499 { 500 container->push_front(__value); 501 return *this; 502 } 503 504 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 505 front_insert_iterator& 506 operator=(typename _Container::value_type&& __value) 507 { 508 container->push_front(std::move(__value)); 509 return *this; 510 } 511 #endif 512 513 /// Simply returns *this. 514 front_insert_iterator& 515 operator*() 516 { return *this; } 517 518 /// Simply returns *this. (This %iterator does not "move".) 519 front_insert_iterator& 520 operator++() 521 { return *this; } 522 523 /// Simply returns *this. (This %iterator does not "move".) 524 front_insert_iterator 525 operator++(int) 526 { return *this; } 527 }; 528 529 /** 530 * @param x A container of arbitrary type. 531 * @return An instance of front_insert_iterator working on @p x. 532 * 533 * This wrapper function helps in creating front_insert_iterator instances. 534 * Typing the name of the %iterator requires knowing the precise full 535 * type of the container, which can be tedious and impedes generic 536 * programming. Using this function lets you take advantage of automatic 537 * template parameter deduction, making the compiler match the correct 538 * types for you. 539 */ 540 template<typename _Container> 541 inline front_insert_iterator<_Container> 542 front_inserter(_Container& __x) 543 { return front_insert_iterator<_Container>(__x); } 544 545 /** 546 * @brief Turns assignment into insertion. 547 * 548 * These are output iterators, constructed from a container-of-T. 549 * Assigning a T to the iterator inserts it in the container at the 550 * %iterator's position, rather than overwriting the value at that 551 * position. 552 * 553 * (Sequences will actually insert a @e copy of the value before the 554 * %iterator's position.) 555 * 556 * Tip: Using the inserter function to create these iterators can 557 * save typing. 558 */ 559 template<typename _Container> 560 class insert_iterator 561 : public iterator<output_iterator_tag, void, void, void, void> 562 { 563 protected: 564 _Container* container; 565 typename _Container::iterator iter; 566 567 public: 568 /// A nested typedef for the type of whatever container you used. 569 typedef _Container container_type; 570 571 /** 572 * The only way to create this %iterator is with a container and an 573 * initial position (a normal %iterator into the container). 574 */ 575 insert_iterator(_Container& __x, typename _Container::iterator __i) 576 : container(&__x), iter(__i) {} 577 578 /** 579 * @param value An instance of whatever type 580 * container_type::const_reference is; presumably a 581 * reference-to-const T for container<T>. 582 * @return This %iterator, for chained operations. 583 * 584 * This kind of %iterator maintains its own position in the 585 * container. Assigning a value to the %iterator will insert the 586 * value into the container at the place before the %iterator. 587 * 588 * The position is maintained such that subsequent assignments will 589 * insert values immediately after one another. For example, 590 * @code 591 * // vector v contains A and Z 592 * 593 * insert_iterator i (v, ++v.begin()); 594 * i = 1; 595 * i = 2; 596 * i = 3; 597 * 598 * // vector v contains A, 1, 2, 3, and Z 599 * @endcode 600 */ 601 insert_iterator& 602 operator=(typename _Container::const_reference __value) 603 { 604 iter = container->insert(iter, __value); 605 ++iter; 606 return *this; 607 } 608 609 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 610 insert_iterator& 611 operator=(typename _Container::value_type&& __value) 612 { 613 iter = container->insert(iter, std::move(__value)); 614 ++iter; 615 return *this; 616 } 617 #endif 618 619 /// Simply returns *this. 620 insert_iterator& 621 operator*() 622 { return *this; } 623 624 /// Simply returns *this. (This %iterator does not "move".) 625 insert_iterator& 626 operator++() 627 { return *this; } 628 629 /// Simply returns *this. (This %iterator does not "move".) 630 insert_iterator& 631 operator++(int) 632 { return *this; } 633 }; 634 635 /** 636 * @param x A container of arbitrary type. 637 * @return An instance of insert_iterator working on @p x. 638 * 639 * This wrapper function helps in creating insert_iterator instances. 640 * Typing the name of the %iterator requires knowing the precise full 641 * type of the container, which can be tedious and impedes generic 642 * programming. Using this function lets you take advantage of automatic 643 * template parameter deduction, making the compiler match the correct 644 * types for you. 645 */ 646 template<typename _Container, typename _Iterator> 647 inline insert_iterator<_Container> 648 inserter(_Container& __x, _Iterator __i) 649 { 650 return insert_iterator<_Container>(__x, 651 typename _Container::iterator(__i)); 652 } 653 654 _GLIBCXX_END_NAMESPACE 655 656 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 657 658 // This iterator adapter is 'normal' in the sense that it does not 659 // change the semantics of any of the operators of its iterator 660 // parameter. Its primary purpose is to convert an iterator that is 661 // not a class, e.g. a pointer, into an iterator that is a class. 662 // The _Container parameter exists solely so that different containers 663 // using this template can instantiate different types, even if the 664 // _Iterator parameter is the same. 665 using std::iterator_traits; 666 using std::iterator; 667 template<typename _Iterator, typename _Container> 668 class __normal_iterator 669 { 670 protected: 671 _Iterator _M_current; 672 673 public: 674 typedef _Iterator iterator_type; 675 typedef typename iterator_traits<_Iterator>::iterator_category 676 iterator_category; 677 typedef typename iterator_traits<_Iterator>::value_type value_type; 678 typedef typename iterator_traits<_Iterator>::difference_type 679 difference_type; 680 typedef typename iterator_traits<_Iterator>::reference reference; 681 typedef typename iterator_traits<_Iterator>::pointer pointer; 682 683 __normal_iterator() : _M_current(_Iterator()) { } 684 685 explicit 686 __normal_iterator(const _Iterator& __i) : _M_current(__i) { } 687 688 // Allow iterator to const_iterator conversion 689 template<typename _Iter> 690 __normal_iterator(const __normal_iterator<_Iter, 691 typename __enable_if< 692 (std::__are_same<_Iter, typename _Container::pointer>::__value), 693 _Container>::__type>& __i) 694 : _M_current(__i.base()) { } 695 696 // Forward iterator requirements 697 reference 698 operator*() const 699 { return *_M_current; } 700 701 pointer 702 operator->() const 703 { return _M_current; } 704 705 __normal_iterator& 706 operator++() 707 { 708 ++_M_current; 709 return *this; 710 } 711 712 __normal_iterator 713 operator++(int) 714 { return __normal_iterator(_M_current++); } 715 716 // Bidirectional iterator requirements 717 __normal_iterator& 718 operator--() 719 { 720 --_M_current; 721 return *this; 722 } 723 724 __normal_iterator 725 operator--(int) 726 { return __normal_iterator(_M_current--); } 727 728 // Random access iterator requirements 729 reference 730 operator[](const difference_type& __n) const 731 { return _M_current[__n]; } 732 733 __normal_iterator& 734 operator+=(const difference_type& __n) 735 { _M_current += __n; return *this; } 736 737 __normal_iterator 738 operator+(const difference_type& __n) const 739 { return __normal_iterator(_M_current + __n); } 740 741 __normal_iterator& 742 operator-=(const difference_type& __n) 743 { _M_current -= __n; return *this; } 744 745 __normal_iterator 746 operator-(const difference_type& __n) const 747 { return __normal_iterator(_M_current - __n); } 748 749 const _Iterator& 750 base() const 751 { return _M_current; } 752 }; 753 754 // Note: In what follows, the left- and right-hand-side iterators are 755 // allowed to vary in types (conceptually in cv-qualification) so that 756 // comparison between cv-qualified and non-cv-qualified iterators be 757 // valid. However, the greedy and unfriendly operators in std::rel_ops 758 // will make overload resolution ambiguous (when in scope) if we don't 759 // provide overloads whose operands are of the same type. Can someone 760 // remind me what generic programming is about? -- Gaby 761 762 // Forward iterator requirements 763 template<typename _IteratorL, typename _IteratorR, typename _Container> 764 inline bool 765 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 766 const __normal_iterator<_IteratorR, _Container>& __rhs) 767 { return __lhs.base() == __rhs.base(); } 768 769 template<typename _Iterator, typename _Container> 770 inline bool 771 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 772 const __normal_iterator<_Iterator, _Container>& __rhs) 773 { return __lhs.base() == __rhs.base(); } 774 775 template<typename _IteratorL, typename _IteratorR, typename _Container> 776 inline bool 777 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 778 const __normal_iterator<_IteratorR, _Container>& __rhs) 779 { return __lhs.base() != __rhs.base(); } 780 781 template<typename _Iterator, typename _Container> 782 inline bool 783 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 784 const __normal_iterator<_Iterator, _Container>& __rhs) 785 { return __lhs.base() != __rhs.base(); } 786 787 // Random access iterator requirements 788 template<typename _IteratorL, typename _IteratorR, typename _Container> 789 inline bool 790 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 791 const __normal_iterator<_IteratorR, _Container>& __rhs) 792 { return __lhs.base() < __rhs.base(); } 793 794 template<typename _Iterator, typename _Container> 795 inline bool 796 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 797 const __normal_iterator<_Iterator, _Container>& __rhs) 798 { return __lhs.base() < __rhs.base(); } 799 800 template<typename _IteratorL, typename _IteratorR, typename _Container> 801 inline bool 802 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 803 const __normal_iterator<_IteratorR, _Container>& __rhs) 804 { return __lhs.base() > __rhs.base(); } 805 806 template<typename _Iterator, typename _Container> 807 inline bool 808 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 809 const __normal_iterator<_Iterator, _Container>& __rhs) 810 { return __lhs.base() > __rhs.base(); } 811 812 template<typename _IteratorL, typename _IteratorR, typename _Container> 813 inline bool 814 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 815 const __normal_iterator<_IteratorR, _Container>& __rhs) 816 { return __lhs.base() <= __rhs.base(); } 817 818 template<typename _Iterator, typename _Container> 819 inline bool 820 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 821 const __normal_iterator<_Iterator, _Container>& __rhs) 822 { return __lhs.base() <= __rhs.base(); } 823 824 template<typename _IteratorL, typename _IteratorR, typename _Container> 825 inline bool 826 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 827 const __normal_iterator<_IteratorR, _Container>& __rhs) 828 { return __lhs.base() >= __rhs.base(); } 829 830 template<typename _Iterator, typename _Container> 831 inline bool 832 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 833 const __normal_iterator<_Iterator, _Container>& __rhs) 834 { return __lhs.base() >= __rhs.base(); } 835 836 // _GLIBCXX_RESOLVE_LIB_DEFECTS 837 // According to the resolution of DR179 not only the various comparison 838 // operators but also operator- must accept mixed iterator/const_iterator 839 // parameters. 840 template<typename _IteratorL, typename _IteratorR, typename _Container> 841 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 842 // DR 685. 843 inline auto 844 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 845 const __normal_iterator<_IteratorR, _Container>& __rhs) 846 -> decltype(__lhs.base() - __rhs.base()) 847 #else 848 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 849 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 850 const __normal_iterator<_IteratorR, _Container>& __rhs) 851 #endif 852 { return __lhs.base() - __rhs.base(); } 853 854 template<typename _Iterator, typename _Container> 855 inline typename __normal_iterator<_Iterator, _Container>::difference_type 856 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 857 const __normal_iterator<_Iterator, _Container>& __rhs) 858 { return __lhs.base() - __rhs.base(); } 859 860 template<typename _Iterator, typename _Container> 861 inline __normal_iterator<_Iterator, _Container> 862 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 863 __n, const __normal_iterator<_Iterator, _Container>& __i) 864 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 865 866 _GLIBCXX_END_NAMESPACE 867 868 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 869 870 _GLIBCXX_BEGIN_NAMESPACE(std) 871 872 // 24.4.3 Move iterators 873 /** 874 * Class template move_iterator is an iterator adapter with the same 875 * behavior as the underlying iterator except that its dereference 876 * operator implicitly converts the value returned by the underlying 877 * iterator's dereference operator to an rvalue reference. Some 878 * generic algorithms can be called with move iterators to replace 879 * copying with moving. 880 */ 881 template<typename _Iterator> 882 class move_iterator 883 { 884 protected: 885 _Iterator _M_current; 886 887 public: 888 typedef _Iterator iterator_type; 889 typedef typename iterator_traits<_Iterator>::difference_type 890 difference_type; 891 // NB: DR 680. 892 typedef _Iterator pointer; 893 typedef typename iterator_traits<_Iterator>::value_type value_type; 894 typedef typename iterator_traits<_Iterator>::iterator_category 895 iterator_category; 896 typedef value_type&& reference; 897 898 public: 899 move_iterator() 900 : _M_current() { } 901 902 explicit 903 move_iterator(iterator_type __i) 904 : _M_current(__i) { } 905 906 template<typename _Iter> 907 move_iterator(const move_iterator<_Iter>& __i) 908 : _M_current(__i.base()) { } 909 910 iterator_type 911 base() const 912 { return _M_current; } 913 914 reference 915 operator*() const 916 { return std::move(*_M_current); } 917 918 pointer 919 operator->() const 920 { return _M_current; } 921 922 move_iterator& 923 operator++() 924 { 925 ++_M_current; 926 return *this; 927 } 928 929 move_iterator 930 operator++(int) 931 { 932 move_iterator __tmp = *this; 933 ++_M_current; 934 return __tmp; 935 } 936 937 move_iterator& 938 operator--() 939 { 940 --_M_current; 941 return *this; 942 } 943 944 move_iterator 945 operator--(int) 946 { 947 move_iterator __tmp = *this; 948 --_M_current; 949 return __tmp; 950 } 951 952 move_iterator 953 operator+(difference_type __n) const 954 { return move_iterator(_M_current + __n); } 955 956 move_iterator& 957 operator+=(difference_type __n) 958 { 959 _M_current += __n; 960 return *this; 961 } 962 963 move_iterator 964 operator-(difference_type __n) const 965 { return move_iterator(_M_current - __n); } 966 967 move_iterator& 968 operator-=(difference_type __n) 969 { 970 _M_current -= __n; 971 return *this; 972 } 973 974 reference 975 operator[](difference_type __n) const 976 { return _M_current[__n]; } 977 }; 978 979 template<typename _IteratorL, typename _IteratorR> 980 inline bool 981 operator==(const move_iterator<_IteratorL>& __x, 982 const move_iterator<_IteratorR>& __y) 983 { return __x.base() == __y.base(); } 984 985 template<typename _IteratorL, typename _IteratorR> 986 inline bool 987 operator!=(const move_iterator<_IteratorL>& __x, 988 const move_iterator<_IteratorR>& __y) 989 { return !(__x == __y); } 990 991 template<typename _IteratorL, typename _IteratorR> 992 inline bool 993 operator<(const move_iterator<_IteratorL>& __x, 994 const move_iterator<_IteratorR>& __y) 995 { return __x.base() < __y.base(); } 996 997 template<typename _IteratorL, typename _IteratorR> 998 inline bool 999 operator<=(const move_iterator<_IteratorL>& __x, 1000 const move_iterator<_IteratorR>& __y) 1001 { return !(__y < __x); } 1002 1003 template<typename _IteratorL, typename _IteratorR> 1004 inline bool 1005 operator>(const move_iterator<_IteratorL>& __x, 1006 const move_iterator<_IteratorR>& __y) 1007 { return __y < __x; } 1008 1009 template<typename _IteratorL, typename _IteratorR> 1010 inline bool 1011 operator>=(const move_iterator<_IteratorL>& __x, 1012 const move_iterator<_IteratorR>& __y) 1013 { return !(__x < __y); } 1014 1015 // DR 685. 1016 template<typename _IteratorL, typename _IteratorR> 1017 inline auto 1018 operator-(const move_iterator<_IteratorL>& __x, 1019 const move_iterator<_IteratorR>& __y) 1020 -> decltype(__x.base() - __y.base()) 1021 { return __x.base() - __y.base(); } 1022 1023 template<typename _Iterator> 1024 inline move_iterator<_Iterator> 1025 operator+(typename move_iterator<_Iterator>::difference_type __n, 1026 const move_iterator<_Iterator>& __x) 1027 { return __x + __n; } 1028 1029 template<typename _Iterator> 1030 inline move_iterator<_Iterator> 1031 make_move_iterator(const _Iterator& __i) 1032 { return move_iterator<_Iterator>(__i); } 1033 1034 _GLIBCXX_END_NAMESPACE 1035 1036 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 1037 #else 1038 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 1039 #endif // __GXX_EXPERIMENTAL_CXX0X__ 1040 1041 #endif 1042