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