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 // Forward iterator requirements 740 reference 741 operator*() const _GLIBCXX_NOEXCEPT 742 { return *_M_current; } 743 744 pointer 745 operator->() const _GLIBCXX_NOEXCEPT 746 { return _M_current; } 747 748 __normal_iterator& 749 operator++() _GLIBCXX_NOEXCEPT 750 { 751 ++_M_current; 752 return *this; 753 } 754 755 __normal_iterator 756 operator++(int) _GLIBCXX_NOEXCEPT 757 { return __normal_iterator(_M_current++); } 758 759 // Bidirectional iterator requirements 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 // Random access iterator requirements 772 reference 773 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 774 { return _M_current[__n]; } 775 776 __normal_iterator& 777 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 778 { _M_current += __n; return *this; } 779 780 __normal_iterator 781 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 782 { return __normal_iterator(_M_current + __n); } 783 784 __normal_iterator& 785 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 786 { _M_current -= __n; return *this; } 787 788 __normal_iterator 789 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 790 { return __normal_iterator(_M_current - __n); } 791 792 const _Iterator& 793 base() const _GLIBCXX_NOEXCEPT 794 { return _M_current; } 795 }; 796 797 // Note: In what follows, the left- and right-hand-side iterators are 798 // allowed to vary in types (conceptually in cv-qualification) so that 799 // comparison between cv-qualified and non-cv-qualified iterators be 800 // valid. However, the greedy and unfriendly operators in std::rel_ops 801 // will make overload resolution ambiguous (when in scope) if we don't 802 // provide overloads whose operands are of the same type. Can someone 803 // remind me what generic programming is about? -- Gaby 804 805 // Forward iterator requirements 806 template<typename _IteratorL, typename _IteratorR, typename _Container> 807 inline bool 808 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 809 const __normal_iterator<_IteratorR, _Container>& __rhs) 810 _GLIBCXX_NOEXCEPT 811 { return __lhs.base() == __rhs.base(); } 812 813 template<typename _Iterator, typename _Container> 814 inline bool 815 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 816 const __normal_iterator<_Iterator, _Container>& __rhs) 817 _GLIBCXX_NOEXCEPT 818 { return __lhs.base() == __rhs.base(); } 819 820 template<typename _IteratorL, typename _IteratorR, typename _Container> 821 inline bool 822 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 823 const __normal_iterator<_IteratorR, _Container>& __rhs) 824 _GLIBCXX_NOEXCEPT 825 { return __lhs.base() != __rhs.base(); } 826 827 template<typename _Iterator, typename _Container> 828 inline bool 829 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 830 const __normal_iterator<_Iterator, _Container>& __rhs) 831 _GLIBCXX_NOEXCEPT 832 { return __lhs.base() != __rhs.base(); } 833 834 // Random access iterator requirements 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 template<typename _IteratorL, typename _IteratorR, typename _Container> 850 inline bool 851 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 852 const __normal_iterator<_IteratorR, _Container>& __rhs) 853 _GLIBCXX_NOEXCEPT 854 { return __lhs.base() > __rhs.base(); } 855 856 template<typename _Iterator, typename _Container> 857 inline bool 858 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 859 const __normal_iterator<_Iterator, _Container>& __rhs) 860 _GLIBCXX_NOEXCEPT 861 { return __lhs.base() > __rhs.base(); } 862 863 template<typename _IteratorL, typename _IteratorR, typename _Container> 864 inline bool 865 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 866 const __normal_iterator<_IteratorR, _Container>& __rhs) 867 _GLIBCXX_NOEXCEPT 868 { return __lhs.base() <= __rhs.base(); } 869 870 template<typename _Iterator, typename _Container> 871 inline bool 872 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 873 const __normal_iterator<_Iterator, _Container>& __rhs) 874 _GLIBCXX_NOEXCEPT 875 { return __lhs.base() <= __rhs.base(); } 876 877 template<typename _IteratorL, typename _IteratorR, typename _Container> 878 inline bool 879 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 880 const __normal_iterator<_IteratorR, _Container>& __rhs) 881 _GLIBCXX_NOEXCEPT 882 { return __lhs.base() >= __rhs.base(); } 883 884 template<typename _Iterator, typename _Container> 885 inline bool 886 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 887 const __normal_iterator<_Iterator, _Container>& __rhs) 888 _GLIBCXX_NOEXCEPT 889 { return __lhs.base() >= __rhs.base(); } 890 891 // _GLIBCXX_RESOLVE_LIB_DEFECTS 892 // According to the resolution of DR179 not only the various comparison 893 // operators but also operator- must accept mixed iterator/const_iterator 894 // parameters. 895 template<typename _IteratorL, typename _IteratorR, typename _Container> 896 #if __cplusplus >= 201103L 897 // DR 685. 898 inline auto 899 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 900 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 901 -> decltype(__lhs.base() - __rhs.base()) 902 #else 903 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 904 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 905 const __normal_iterator<_IteratorR, _Container>& __rhs) 906 #endif 907 { return __lhs.base() - __rhs.base(); } 908 909 template<typename _Iterator, typename _Container> 910 inline typename __normal_iterator<_Iterator, _Container>::difference_type 911 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 912 const __normal_iterator<_Iterator, _Container>& __rhs) 913 _GLIBCXX_NOEXCEPT 914 { return __lhs.base() - __rhs.base(); } 915 916 template<typename _Iterator, typename _Container> 917 inline __normal_iterator<_Iterator, _Container> 918 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 919 __n, const __normal_iterator<_Iterator, _Container>& __i) 920 _GLIBCXX_NOEXCEPT 921 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 922 923 _GLIBCXX_END_NAMESPACE_VERSION 924 } // namespace 925 926 #if __cplusplus >= 201103L 927 928 namespace std _GLIBCXX_VISIBILITY(default) 929 { 930 _GLIBCXX_BEGIN_NAMESPACE_VERSION 931 932 /** 933 * @addtogroup iterators 934 * @{ 935 */ 936 937 // 24.4.3 Move iterators 938 /** 939 * Class template move_iterator is an iterator adapter with the same 940 * behavior as the underlying iterator except that its dereference 941 * operator implicitly converts the value returned by the underlying 942 * iterator's dereference operator to an rvalue reference. Some 943 * generic algorithms can be called with move iterators to replace 944 * copying with moving. 945 */ 946 template<typename _Iterator> 947 class move_iterator 948 { 949 protected: 950 _Iterator _M_current; 951 952 typedef iterator_traits<_Iterator> __traits_type; 953 954 public: 955 typedef _Iterator iterator_type; 956 typedef typename __traits_type::iterator_category iterator_category; 957 typedef typename __traits_type::value_type value_type; 958 typedef typename __traits_type::difference_type difference_type; 959 // NB: DR 680. 960 typedef _Iterator pointer; 961 typedef value_type&& reference; 962 963 move_iterator() 964 : _M_current() { } 965 966 explicit 967 move_iterator(iterator_type __i) 968 : _M_current(__i) { } 969 970 template<typename _Iter> 971 move_iterator(const move_iterator<_Iter>& __i) 972 : _M_current(__i.base()) { } 973 974 iterator_type 975 base() const 976 { return _M_current; } 977 978 reference 979 operator*() const 980 { return std::move(*_M_current); } 981 982 pointer 983 operator->() const 984 { return _M_current; } 985 986 move_iterator& 987 operator++() 988 { 989 ++_M_current; 990 return *this; 991 } 992 993 move_iterator 994 operator++(int) 995 { 996 move_iterator __tmp = *this; 997 ++_M_current; 998 return __tmp; 999 } 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+(difference_type __n) const 1018 { return move_iterator(_M_current + __n); } 1019 1020 move_iterator& 1021 operator+=(difference_type __n) 1022 { 1023 _M_current += __n; 1024 return *this; 1025 } 1026 1027 move_iterator 1028 operator-(difference_type __n) const 1029 { return move_iterator(_M_current - __n); } 1030 1031 move_iterator& 1032 operator-=(difference_type __n) 1033 { 1034 _M_current -= __n; 1035 return *this; 1036 } 1037 1038 reference 1039 operator[](difference_type __n) const 1040 { return std::move(_M_current[__n]); } 1041 }; 1042 1043 // Note: See __normal_iterator operators note from Gaby to understand 1044 // why there are always 2 versions for most of the move_iterator 1045 // operators. 1046 template<typename _IteratorL, typename _IteratorR> 1047 inline bool 1048 operator==(const move_iterator<_IteratorL>& __x, 1049 const move_iterator<_IteratorR>& __y) 1050 { return __x.base() == __y.base(); } 1051 1052 template<typename _Iterator> 1053 inline bool 1054 operator==(const move_iterator<_Iterator>& __x, 1055 const move_iterator<_Iterator>& __y) 1056 { return __x.base() == __y.base(); } 1057 1058 template<typename _IteratorL, typename _IteratorR> 1059 inline bool 1060 operator!=(const move_iterator<_IteratorL>& __x, 1061 const move_iterator<_IteratorR>& __y) 1062 { return !(__x == __y); } 1063 1064 template<typename _Iterator> 1065 inline bool 1066 operator!=(const move_iterator<_Iterator>& __x, 1067 const move_iterator<_Iterator>& __y) 1068 { return !(__x == __y); } 1069 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 !(__y < __x); } 1087 1088 template<typename _Iterator> 1089 inline bool 1090 operator<=(const move_iterator<_Iterator>& __x, 1091 const move_iterator<_Iterator>& __y) 1092 { return !(__y < __x); } 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 __y < __x; } 1099 1100 template<typename _Iterator> 1101 inline bool 1102 operator>(const move_iterator<_Iterator>& __x, 1103 const move_iterator<_Iterator>& __y) 1104 { return __y < __x; } 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 !(__x < __y); } 1111 1112 template<typename _Iterator> 1113 inline bool 1114 operator>=(const move_iterator<_Iterator>& __x, 1115 const move_iterator<_Iterator>& __y) 1116 { return !(__x < __y); } 1117 1118 // DR 685. 1119 template<typename _IteratorL, typename _IteratorR> 1120 inline auto 1121 operator-(const move_iterator<_IteratorL>& __x, 1122 const move_iterator<_IteratorR>& __y) 1123 -> decltype(__x.base() - __y.base()) 1124 { return __x.base() - __y.base(); } 1125 1126 template<typename _Iterator> 1127 inline auto 1128 operator-(const move_iterator<_Iterator>& __x, 1129 const move_iterator<_Iterator>& __y) 1130 -> decltype(__x.base() - __y.base()) 1131 { return __x.base() - __y.base(); } 1132 1133 template<typename _Iterator> 1134 inline move_iterator<_Iterator> 1135 operator+(typename move_iterator<_Iterator>::difference_type __n, 1136 const move_iterator<_Iterator>& __x) 1137 { return __x + __n; } 1138 1139 template<typename _Iterator> 1140 inline move_iterator<_Iterator> 1141 make_move_iterator(_Iterator __i) 1142 { return move_iterator<_Iterator>(__i); } 1143 1144 template<typename _Iterator, typename _ReturnType 1145 = typename conditional<__move_if_noexcept_cond 1146 <typename iterator_traits<_Iterator>::value_type>::value, 1147 _Iterator, move_iterator<_Iterator>>::type> 1148 inline _ReturnType 1149 __make_move_if_noexcept_iterator(_Iterator __i) 1150 { return _ReturnType(__i); } 1151 1152 // @} group iterators 1153 1154 _GLIBCXX_END_NAMESPACE_VERSION 1155 } // namespace 1156 1157 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 1158 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 1159 std::__make_move_if_noexcept_iterator(_Iter) 1160 #else 1161 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 1162 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 1163 #endif // C++11 1164 1165 #endif 1166