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