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