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