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