1 // Iterators -*- C++ -*- 2 3 // Copyright (C) 2001-2015 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 #if __cplusplus > 201103L 392 #define __cpp_lib_make_reverse_iterator 201402 393 394 // _GLIBCXX_RESOLVE_LIB_DEFECTS 395 // DR 2285. make_reverse_iterator 396 /// Generator function for reverse_iterator. 397 template<typename _Iterator> 398 inline reverse_iterator<_Iterator> 399 make_reverse_iterator(_Iterator __i) 400 { return reverse_iterator<_Iterator>(__i); } 401 #endif 402 403 // 24.4.2.2.1 back_insert_iterator 404 /** 405 * @brief Turns assignment into insertion. 406 * 407 * These are output iterators, constructed from a container-of-T. 408 * Assigning a T to the iterator appends it to the container using 409 * push_back. 410 * 411 * Tip: Using the back_inserter function to create these iterators can 412 * save typing. 413 */ 414 template<typename _Container> 415 class back_insert_iterator 416 : public iterator<output_iterator_tag, void, void, void, void> 417 { 418 protected: 419 _Container* container; 420 421 public: 422 /// A nested typedef for the type of whatever container you used. 423 typedef _Container container_type; 424 425 /// The only way to create this %iterator is with a container. 426 explicit 427 back_insert_iterator(_Container& __x) : container(&__x) { } 428 429 /** 430 * @param __value An instance of whatever type 431 * container_type::const_reference is; presumably a 432 * reference-to-const T for container<T>. 433 * @return This %iterator, for chained operations. 434 * 435 * This kind of %iterator doesn't really have a @a position in the 436 * container (you can think of the position as being permanently at 437 * the end, if you like). Assigning a value to the %iterator will 438 * always append the value to the end of the container. 439 */ 440 #if __cplusplus < 201103L 441 back_insert_iterator& 442 operator=(typename _Container::const_reference __value) 443 { 444 container->push_back(__value); 445 return *this; 446 } 447 #else 448 back_insert_iterator& 449 operator=(const typename _Container::value_type& __value) 450 { 451 container->push_back(__value); 452 return *this; 453 } 454 455 back_insert_iterator& 456 operator=(typename _Container::value_type&& __value) 457 { 458 container->push_back(std::move(__value)); 459 return *this; 460 } 461 #endif 462 463 /// Simply returns *this. 464 back_insert_iterator& 465 operator*() 466 { return *this; } 467 468 /// Simply returns *this. (This %iterator does not @a move.) 469 back_insert_iterator& 470 operator++() 471 { return *this; } 472 473 /// Simply returns *this. (This %iterator does not @a move.) 474 back_insert_iterator 475 operator++(int) 476 { return *this; } 477 }; 478 479 /** 480 * @param __x A container of arbitrary type. 481 * @return An instance of back_insert_iterator working on @p __x. 482 * 483 * This wrapper function helps in creating back_insert_iterator instances. 484 * Typing the name of the %iterator requires knowing the precise full 485 * type of the container, which can be tedious and impedes generic 486 * programming. Using this function lets you take advantage of automatic 487 * template parameter deduction, making the compiler match the correct 488 * types for you. 489 */ 490 template<typename _Container> 491 inline back_insert_iterator<_Container> 492 back_inserter(_Container& __x) 493 { return back_insert_iterator<_Container>(__x); } 494 495 /** 496 * @brief Turns assignment into insertion. 497 * 498 * These are output iterators, constructed from a container-of-T. 499 * Assigning a T to the iterator prepends it to the container using 500 * push_front. 501 * 502 * Tip: Using the front_inserter function to create these iterators can 503 * save typing. 504 */ 505 template<typename _Container> 506 class front_insert_iterator 507 : public iterator<output_iterator_tag, void, void, void, void> 508 { 509 protected: 510 _Container* container; 511 512 public: 513 /// A nested typedef for the type of whatever container you used. 514 typedef _Container container_type; 515 516 /// The only way to create this %iterator is with a container. 517 explicit front_insert_iterator(_Container& __x) : container(&__x) { } 518 519 /** 520 * @param __value An instance of whatever type 521 * container_type::const_reference is; presumably a 522 * reference-to-const T for container<T>. 523 * @return This %iterator, for chained operations. 524 * 525 * This kind of %iterator doesn't really have a @a position in the 526 * container (you can think of the position as being permanently at 527 * the front, if you like). Assigning a value to the %iterator will 528 * always prepend the value to the front of the container. 529 */ 530 #if __cplusplus < 201103L 531 front_insert_iterator& 532 operator=(typename _Container::const_reference __value) 533 { 534 container->push_front(__value); 535 return *this; 536 } 537 #else 538 front_insert_iterator& 539 operator=(const typename _Container::value_type& __value) 540 { 541 container->push_front(__value); 542 return *this; 543 } 544 545 front_insert_iterator& 546 operator=(typename _Container::value_type&& __value) 547 { 548 container->push_front(std::move(__value)); 549 return *this; 550 } 551 #endif 552 553 /// Simply returns *this. 554 front_insert_iterator& 555 operator*() 556 { return *this; } 557 558 /// Simply returns *this. (This %iterator does not @a move.) 559 front_insert_iterator& 560 operator++() 561 { return *this; } 562 563 /// Simply returns *this. (This %iterator does not @a move.) 564 front_insert_iterator 565 operator++(int) 566 { return *this; } 567 }; 568 569 /** 570 * @param __x A container of arbitrary type. 571 * @return An instance of front_insert_iterator working on @p x. 572 * 573 * This wrapper function helps in creating front_insert_iterator instances. 574 * Typing the name of the %iterator requires knowing the precise full 575 * type of the container, which can be tedious and impedes generic 576 * programming. Using this function lets you take advantage of automatic 577 * template parameter deduction, making the compiler match the correct 578 * types for you. 579 */ 580 template<typename _Container> 581 inline front_insert_iterator<_Container> 582 front_inserter(_Container& __x) 583 { return front_insert_iterator<_Container>(__x); } 584 585 /** 586 * @brief Turns assignment into insertion. 587 * 588 * These are output iterators, constructed from a container-of-T. 589 * Assigning a T to the iterator inserts it in the container at the 590 * %iterator's position, rather than overwriting the value at that 591 * position. 592 * 593 * (Sequences will actually insert a @e copy of the value before the 594 * %iterator's position.) 595 * 596 * Tip: Using the inserter function to create these iterators can 597 * save typing. 598 */ 599 template<typename _Container> 600 class insert_iterator 601 : public iterator<output_iterator_tag, void, void, void, void> 602 { 603 protected: 604 _Container* container; 605 typename _Container::iterator iter; 606 607 public: 608 /// A nested typedef for the type of whatever container you used. 609 typedef _Container container_type; 610 611 /** 612 * The only way to create this %iterator is with a container and an 613 * initial position (a normal %iterator into the container). 614 */ 615 insert_iterator(_Container& __x, typename _Container::iterator __i) 616 : container(&__x), iter(__i) {} 617 618 /** 619 * @param __value An instance of whatever type 620 * container_type::const_reference is; presumably a 621 * reference-to-const T for container<T>. 622 * @return This %iterator, for chained operations. 623 * 624 * This kind of %iterator maintains its own position in the 625 * container. Assigning a value to the %iterator will insert the 626 * value into the container at the place before the %iterator. 627 * 628 * The position is maintained such that subsequent assignments will 629 * insert values immediately after one another. For example, 630 * @code 631 * // vector v contains A and Z 632 * 633 * insert_iterator i (v, ++v.begin()); 634 * i = 1; 635 * i = 2; 636 * i = 3; 637 * 638 * // vector v contains A, 1, 2, 3, and Z 639 * @endcode 640 */ 641 #if __cplusplus < 201103L 642 insert_iterator& 643 operator=(typename _Container::const_reference __value) 644 { 645 iter = container->insert(iter, __value); 646 ++iter; 647 return *this; 648 } 649 #else 650 insert_iterator& 651 operator=(const typename _Container::value_type& __value) 652 { 653 iter = container->insert(iter, __value); 654 ++iter; 655 return *this; 656 } 657 658 insert_iterator& 659 operator=(typename _Container::value_type&& __value) 660 { 661 iter = container->insert(iter, std::move(__value)); 662 ++iter; 663 return *this; 664 } 665 #endif 666 667 /// Simply returns *this. 668 insert_iterator& 669 operator*() 670 { return *this; } 671 672 /// Simply returns *this. (This %iterator does not @a move.) 673 insert_iterator& 674 operator++() 675 { return *this; } 676 677 /// Simply returns *this. (This %iterator does not @a move.) 678 insert_iterator& 679 operator++(int) 680 { return *this; } 681 }; 682 683 /** 684 * @param __x A container of arbitrary type. 685 * @return An instance of insert_iterator working on @p __x. 686 * 687 * This wrapper function helps in creating insert_iterator instances. 688 * Typing the name of the %iterator requires knowing the precise full 689 * type of the container, which can be tedious and impedes generic 690 * programming. Using this function lets you take advantage of automatic 691 * template parameter deduction, making the compiler match the correct 692 * types for you. 693 */ 694 template<typename _Container, typename _Iterator> 695 inline insert_iterator<_Container> 696 inserter(_Container& __x, _Iterator __i) 697 { 698 return insert_iterator<_Container>(__x, 699 typename _Container::iterator(__i)); 700 } 701 702 // @} group iterators 703 704 _GLIBCXX_END_NAMESPACE_VERSION 705 } // namespace 706 707 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 708 { 709 _GLIBCXX_BEGIN_NAMESPACE_VERSION 710 711 // This iterator adapter is @a normal in the sense that it does not 712 // change the semantics of any of the operators of its iterator 713 // parameter. Its primary purpose is to convert an iterator that is 714 // not a class, e.g. a pointer, into an iterator that is a class. 715 // The _Container parameter exists solely so that different containers 716 // using this template can instantiate different types, even if the 717 // _Iterator parameter is the same. 718 using std::iterator_traits; 719 using std::iterator; 720 template<typename _Iterator, typename _Container> 721 class __normal_iterator 722 { 723 protected: 724 _Iterator _M_current; 725 726 typedef iterator_traits<_Iterator> __traits_type; 727 728 public: 729 typedef _Iterator iterator_type; 730 typedef typename __traits_type::iterator_category iterator_category; 731 typedef typename __traits_type::value_type value_type; 732 typedef typename __traits_type::difference_type difference_type; 733 typedef typename __traits_type::reference reference; 734 typedef typename __traits_type::pointer pointer; 735 736 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 737 : _M_current(_Iterator()) { } 738 739 explicit 740 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 741 : _M_current(__i) { } 742 743 // Allow iterator to const_iterator conversion 744 template<typename _Iter> 745 __normal_iterator(const __normal_iterator<_Iter, 746 typename __enable_if< 747 (std::__are_same<_Iter, typename _Container::pointer>::__value), 748 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT 749 : _M_current(__i.base()) { } 750 751 // Forward iterator requirements 752 reference 753 operator*() const _GLIBCXX_NOEXCEPT 754 { return *_M_current; } 755 756 pointer 757 operator->() const _GLIBCXX_NOEXCEPT 758 { return _M_current; } 759 760 __normal_iterator& 761 operator++() _GLIBCXX_NOEXCEPT 762 { 763 ++_M_current; 764 return *this; 765 } 766 767 __normal_iterator 768 operator++(int) _GLIBCXX_NOEXCEPT 769 { return __normal_iterator(_M_current++); } 770 771 // Bidirectional iterator requirements 772 __normal_iterator& 773 operator--() _GLIBCXX_NOEXCEPT 774 { 775 --_M_current; 776 return *this; 777 } 778 779 __normal_iterator 780 operator--(int) _GLIBCXX_NOEXCEPT 781 { return __normal_iterator(_M_current--); } 782 783 // Random access iterator requirements 784 reference 785 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 786 { return _M_current[__n]; } 787 788 __normal_iterator& 789 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 790 { _M_current += __n; return *this; } 791 792 __normal_iterator 793 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 794 { return __normal_iterator(_M_current + __n); } 795 796 __normal_iterator& 797 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 798 { _M_current -= __n; return *this; } 799 800 __normal_iterator 801 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 802 { return __normal_iterator(_M_current - __n); } 803 804 const _Iterator& 805 base() const _GLIBCXX_NOEXCEPT 806 { return _M_current; } 807 }; 808 809 // Note: In what follows, the left- and right-hand-side iterators are 810 // allowed to vary in types (conceptually in cv-qualification) so that 811 // comparison between cv-qualified and non-cv-qualified iterators be 812 // valid. However, the greedy and unfriendly operators in std::rel_ops 813 // will make overload resolution ambiguous (when in scope) if we don't 814 // provide overloads whose operands are of the same type. Can someone 815 // remind me what generic programming is about? -- Gaby 816 817 // Forward iterator requirements 818 template<typename _IteratorL, typename _IteratorR, typename _Container> 819 inline bool 820 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 821 const __normal_iterator<_IteratorR, _Container>& __rhs) 822 _GLIBCXX_NOEXCEPT 823 { return __lhs.base() == __rhs.base(); } 824 825 template<typename _Iterator, typename _Container> 826 inline bool 827 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 828 const __normal_iterator<_Iterator, _Container>& __rhs) 829 _GLIBCXX_NOEXCEPT 830 { return __lhs.base() == __rhs.base(); } 831 832 template<typename _IteratorL, typename _IteratorR, typename _Container> 833 inline bool 834 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 835 const __normal_iterator<_IteratorR, _Container>& __rhs) 836 _GLIBCXX_NOEXCEPT 837 { return __lhs.base() != __rhs.base(); } 838 839 template<typename _Iterator, typename _Container> 840 inline bool 841 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 842 const __normal_iterator<_Iterator, _Container>& __rhs) 843 _GLIBCXX_NOEXCEPT 844 { return __lhs.base() != __rhs.base(); } 845 846 // Random access iterator requirements 847 template<typename _IteratorL, typename _IteratorR, typename _Container> 848 inline bool 849 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 850 const __normal_iterator<_IteratorR, _Container>& __rhs) 851 _GLIBCXX_NOEXCEPT 852 { return __lhs.base() < __rhs.base(); } 853 854 template<typename _Iterator, typename _Container> 855 inline bool 856 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 857 const __normal_iterator<_Iterator, _Container>& __rhs) 858 _GLIBCXX_NOEXCEPT 859 { return __lhs.base() < __rhs.base(); } 860 861 template<typename _IteratorL, typename _IteratorR, typename _Container> 862 inline bool 863 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 864 const __normal_iterator<_IteratorR, _Container>& __rhs) 865 _GLIBCXX_NOEXCEPT 866 { return __lhs.base() > __rhs.base(); } 867 868 template<typename _Iterator, typename _Container> 869 inline bool 870 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 871 const __normal_iterator<_Iterator, _Container>& __rhs) 872 _GLIBCXX_NOEXCEPT 873 { return __lhs.base() > __rhs.base(); } 874 875 template<typename _IteratorL, typename _IteratorR, typename _Container> 876 inline bool 877 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 878 const __normal_iterator<_IteratorR, _Container>& __rhs) 879 _GLIBCXX_NOEXCEPT 880 { return __lhs.base() <= __rhs.base(); } 881 882 template<typename _Iterator, typename _Container> 883 inline bool 884 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 885 const __normal_iterator<_Iterator, _Container>& __rhs) 886 _GLIBCXX_NOEXCEPT 887 { return __lhs.base() <= __rhs.base(); } 888 889 template<typename _IteratorL, typename _IteratorR, typename _Container> 890 inline bool 891 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 892 const __normal_iterator<_IteratorR, _Container>& __rhs) 893 _GLIBCXX_NOEXCEPT 894 { return __lhs.base() >= __rhs.base(); } 895 896 template<typename _Iterator, typename _Container> 897 inline bool 898 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 899 const __normal_iterator<_Iterator, _Container>& __rhs) 900 _GLIBCXX_NOEXCEPT 901 { return __lhs.base() >= __rhs.base(); } 902 903 // _GLIBCXX_RESOLVE_LIB_DEFECTS 904 // According to the resolution of DR179 not only the various comparison 905 // operators but also operator- must accept mixed iterator/const_iterator 906 // parameters. 907 template<typename _IteratorL, typename _IteratorR, typename _Container> 908 #if __cplusplus >= 201103L 909 // DR 685. 910 inline auto 911 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 912 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 913 -> decltype(__lhs.base() - __rhs.base()) 914 #else 915 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 916 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 917 const __normal_iterator<_IteratorR, _Container>& __rhs) 918 #endif 919 { return __lhs.base() - __rhs.base(); } 920 921 template<typename _Iterator, typename _Container> 922 inline typename __normal_iterator<_Iterator, _Container>::difference_type 923 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 924 const __normal_iterator<_Iterator, _Container>& __rhs) 925 _GLIBCXX_NOEXCEPT 926 { return __lhs.base() - __rhs.base(); } 927 928 template<typename _Iterator, typename _Container> 929 inline __normal_iterator<_Iterator, _Container> 930 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 931 __n, const __normal_iterator<_Iterator, _Container>& __i) 932 _GLIBCXX_NOEXCEPT 933 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 934 935 _GLIBCXX_END_NAMESPACE_VERSION 936 } // namespace 937 938 #if __cplusplus >= 201103L 939 940 namespace std _GLIBCXX_VISIBILITY(default) 941 { 942 _GLIBCXX_BEGIN_NAMESPACE_VERSION 943 944 /** 945 * @addtogroup iterators 946 * @{ 947 */ 948 949 // 24.4.3 Move iterators 950 /** 951 * Class template move_iterator is an iterator adapter with the same 952 * behavior as the underlying iterator except that its dereference 953 * operator implicitly converts the value returned by the underlying 954 * iterator's dereference operator to an rvalue reference. Some 955 * generic algorithms can be called with move iterators to replace 956 * copying with moving. 957 */ 958 template<typename _Iterator> 959 class move_iterator 960 { 961 protected: 962 _Iterator _M_current; 963 964 typedef iterator_traits<_Iterator> __traits_type; 965 typedef typename __traits_type::reference __base_ref; 966 967 public: 968 typedef _Iterator iterator_type; 969 typedef typename __traits_type::iterator_category iterator_category; 970 typedef typename __traits_type::value_type value_type; 971 typedef typename __traits_type::difference_type difference_type; 972 // NB: DR 680. 973 typedef _Iterator pointer; 974 // _GLIBCXX_RESOLVE_LIB_DEFECTS 975 // 2106. move_iterator wrapping iterators returning prvalues 976 typedef typename conditional<is_reference<__base_ref>::value, 977 typename remove_reference<__base_ref>::type&&, 978 __base_ref>::type reference; 979 980 move_iterator() 981 : _M_current() { } 982 983 explicit 984 move_iterator(iterator_type __i) 985 : _M_current(__i) { } 986 987 template<typename _Iter> 988 move_iterator(const move_iterator<_Iter>& __i) 989 : _M_current(__i.base()) { } 990 991 iterator_type 992 base() const 993 { return _M_current; } 994 995 reference 996 operator*() const 997 { return static_cast<reference>(*_M_current); } 998 999 pointer 1000 operator->() const 1001 { return _M_current; } 1002 1003 move_iterator& 1004 operator++() 1005 { 1006 ++_M_current; 1007 return *this; 1008 } 1009 1010 move_iterator 1011 operator++(int) 1012 { 1013 move_iterator __tmp = *this; 1014 ++_M_current; 1015 return __tmp; 1016 } 1017 1018 move_iterator& 1019 operator--() 1020 { 1021 --_M_current; 1022 return *this; 1023 } 1024 1025 move_iterator 1026 operator--(int) 1027 { 1028 move_iterator __tmp = *this; 1029 --_M_current; 1030 return __tmp; 1031 } 1032 1033 move_iterator 1034 operator+(difference_type __n) const 1035 { return move_iterator(_M_current + __n); } 1036 1037 move_iterator& 1038 operator+=(difference_type __n) 1039 { 1040 _M_current += __n; 1041 return *this; 1042 } 1043 1044 move_iterator 1045 operator-(difference_type __n) const 1046 { return move_iterator(_M_current - __n); } 1047 1048 move_iterator& 1049 operator-=(difference_type __n) 1050 { 1051 _M_current -= __n; 1052 return *this; 1053 } 1054 1055 reference 1056 operator[](difference_type __n) const 1057 { return std::move(_M_current[__n]); } 1058 }; 1059 1060 // Note: See __normal_iterator operators note from Gaby to understand 1061 // why there are always 2 versions for most of the move_iterator 1062 // operators. 1063 template<typename _IteratorL, typename _IteratorR> 1064 inline bool 1065 operator==(const move_iterator<_IteratorL>& __x, 1066 const move_iterator<_IteratorR>& __y) 1067 { return __x.base() == __y.base(); } 1068 1069 template<typename _Iterator> 1070 inline bool 1071 operator==(const move_iterator<_Iterator>& __x, 1072 const move_iterator<_Iterator>& __y) 1073 { return __x.base() == __y.base(); } 1074 1075 template<typename _IteratorL, typename _IteratorR> 1076 inline bool 1077 operator!=(const move_iterator<_IteratorL>& __x, 1078 const move_iterator<_IteratorR>& __y) 1079 { return !(__x == __y); } 1080 1081 template<typename _Iterator> 1082 inline bool 1083 operator!=(const move_iterator<_Iterator>& __x, 1084 const move_iterator<_Iterator>& __y) 1085 { return !(__x == __y); } 1086 1087 template<typename _IteratorL, typename _IteratorR> 1088 inline bool 1089 operator<(const move_iterator<_IteratorL>& __x, 1090 const move_iterator<_IteratorR>& __y) 1091 { return __x.base() < __y.base(); } 1092 1093 template<typename _Iterator> 1094 inline bool 1095 operator<(const move_iterator<_Iterator>& __x, 1096 const move_iterator<_Iterator>& __y) 1097 { return __x.base() < __y.base(); } 1098 1099 template<typename _IteratorL, typename _IteratorR> 1100 inline bool 1101 operator<=(const move_iterator<_IteratorL>& __x, 1102 const move_iterator<_IteratorR>& __y) 1103 { return !(__y < __x); } 1104 1105 template<typename _Iterator> 1106 inline bool 1107 operator<=(const move_iterator<_Iterator>& __x, 1108 const move_iterator<_Iterator>& __y) 1109 { return !(__y < __x); } 1110 1111 template<typename _IteratorL, typename _IteratorR> 1112 inline bool 1113 operator>(const move_iterator<_IteratorL>& __x, 1114 const move_iterator<_IteratorR>& __y) 1115 { return __y < __x; } 1116 1117 template<typename _Iterator> 1118 inline bool 1119 operator>(const move_iterator<_Iterator>& __x, 1120 const move_iterator<_Iterator>& __y) 1121 { return __y < __x; } 1122 1123 template<typename _IteratorL, typename _IteratorR> 1124 inline bool 1125 operator>=(const move_iterator<_IteratorL>& __x, 1126 const move_iterator<_IteratorR>& __y) 1127 { return !(__x < __y); } 1128 1129 template<typename _Iterator> 1130 inline bool 1131 operator>=(const move_iterator<_Iterator>& __x, 1132 const move_iterator<_Iterator>& __y) 1133 { return !(__x < __y); } 1134 1135 // DR 685. 1136 template<typename _IteratorL, typename _IteratorR> 1137 inline auto 1138 operator-(const move_iterator<_IteratorL>& __x, 1139 const move_iterator<_IteratorR>& __y) 1140 -> decltype(__x.base() - __y.base()) 1141 { return __x.base() - __y.base(); } 1142 1143 template<typename _Iterator> 1144 inline auto 1145 operator-(const move_iterator<_Iterator>& __x, 1146 const move_iterator<_Iterator>& __y) 1147 -> decltype(__x.base() - __y.base()) 1148 { return __x.base() - __y.base(); } 1149 1150 template<typename _Iterator> 1151 inline move_iterator<_Iterator> 1152 operator+(typename move_iterator<_Iterator>::difference_type __n, 1153 const move_iterator<_Iterator>& __x) 1154 { return __x + __n; } 1155 1156 template<typename _Iterator> 1157 inline move_iterator<_Iterator> 1158 make_move_iterator(_Iterator __i) 1159 { return move_iterator<_Iterator>(__i); } 1160 1161 template<typename _Iterator, typename _ReturnType 1162 = typename conditional<__move_if_noexcept_cond 1163 <typename iterator_traits<_Iterator>::value_type>::value, 1164 _Iterator, move_iterator<_Iterator>>::type> 1165 inline _ReturnType 1166 __make_move_if_noexcept_iterator(_Iterator __i) 1167 { return _ReturnType(__i); } 1168 1169 // @} group iterators 1170 1171 _GLIBCXX_END_NAMESPACE_VERSION 1172 } // namespace 1173 1174 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 1175 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 1176 std::__make_move_if_noexcept_iterator(_Iter) 1177 #else 1178 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 1179 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 1180 #endif // C++11 1181 1182 #endif 1183