1 // Iterators -*- C++ -*- 2 3 // Copyright (C) 2001-2018 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 _GLIBCXX17_CONSTEXPR 126 reverse_iterator() : current() { } 127 128 /** 129 * This %iterator will move in the opposite direction that @p x does. 130 */ 131 explicit _GLIBCXX17_CONSTEXPR 132 reverse_iterator(iterator_type __x) : current(__x) { } 133 134 /** 135 * The copy constructor is normal. 136 */ 137 _GLIBCXX17_CONSTEXPR 138 reverse_iterator(const reverse_iterator& __x) 139 : current(__x.current) { } 140 141 /** 142 * A %reverse_iterator across other types can be copied if the 143 * underlying %iterator can be converted to the type of @c current. 144 */ 145 template<typename _Iter> 146 _GLIBCXX17_CONSTEXPR 147 reverse_iterator(const reverse_iterator<_Iter>& __x) 148 : current(__x.base()) { } 149 150 /** 151 * @return @c current, the %iterator used for underlying work. 152 */ 153 _GLIBCXX17_CONSTEXPR iterator_type 154 base() const 155 { return current; } 156 157 /** 158 * @return A reference to the value at @c --current 159 * 160 * This requires that @c --current is dereferenceable. 161 * 162 * @warning This implementation requires that for an iterator of the 163 * underlying iterator type, @c x, a reference obtained by 164 * @c *x remains valid after @c x has been modified or 165 * destroyed. This is a bug: http://gcc.gnu.org/PR51823 166 */ 167 _GLIBCXX17_CONSTEXPR reference 168 operator*() const 169 { 170 _Iterator __tmp = current; 171 return *--__tmp; 172 } 173 174 /** 175 * @return A pointer to the value at @c --current 176 * 177 * This requires that @c --current is dereferenceable. 178 */ 179 _GLIBCXX17_CONSTEXPR pointer 180 operator->() const 181 { return &(operator*()); } 182 183 /** 184 * @return @c *this 185 * 186 * Decrements the underlying iterator. 187 */ 188 _GLIBCXX17_CONSTEXPR reverse_iterator& 189 operator++() 190 { 191 --current; 192 return *this; 193 } 194 195 /** 196 * @return The original value of @c *this 197 * 198 * Decrements the underlying iterator. 199 */ 200 _GLIBCXX17_CONSTEXPR reverse_iterator 201 operator++(int) 202 { 203 reverse_iterator __tmp = *this; 204 --current; 205 return __tmp; 206 } 207 208 /** 209 * @return @c *this 210 * 211 * Increments the underlying iterator. 212 */ 213 _GLIBCXX17_CONSTEXPR reverse_iterator& 214 operator--() 215 { 216 ++current; 217 return *this; 218 } 219 220 /** 221 * @return A reverse_iterator with the previous value of @c *this 222 * 223 * Increments the underlying iterator. 224 */ 225 _GLIBCXX17_CONSTEXPR reverse_iterator 226 operator--(int) 227 { 228 reverse_iterator __tmp = *this; 229 ++current; 230 return __tmp; 231 } 232 233 /** 234 * @return A reverse_iterator that refers to @c current - @a __n 235 * 236 * The underlying iterator must be a Random Access Iterator. 237 */ 238 _GLIBCXX17_CONSTEXPR reverse_iterator 239 operator+(difference_type __n) const 240 { return reverse_iterator(current - __n); } 241 242 /** 243 * @return *this 244 * 245 * Moves the underlying iterator backwards @a __n steps. 246 * The underlying iterator must be a Random Access Iterator. 247 */ 248 _GLIBCXX17_CONSTEXPR reverse_iterator& 249 operator+=(difference_type __n) 250 { 251 current -= __n; 252 return *this; 253 } 254 255 /** 256 * @return A reverse_iterator that refers to @c current - @a __n 257 * 258 * The underlying iterator must be a Random Access Iterator. 259 */ 260 _GLIBCXX17_CONSTEXPR reverse_iterator 261 operator-(difference_type __n) const 262 { return reverse_iterator(current + __n); } 263 264 /** 265 * @return *this 266 * 267 * Moves the underlying iterator forwards @a __n steps. 268 * The underlying iterator must be a Random Access Iterator. 269 */ 270 _GLIBCXX17_CONSTEXPR reverse_iterator& 271 operator-=(difference_type __n) 272 { 273 current += __n; 274 return *this; 275 } 276 277 /** 278 * @return The value at @c current - @a __n - 1 279 * 280 * The underlying iterator must be a Random Access Iterator. 281 */ 282 _GLIBCXX17_CONSTEXPR reference 283 operator[](difference_type __n) const 284 { return *(*this + __n); } 285 }; 286 287 //@{ 288 /** 289 * @param __x A %reverse_iterator. 290 * @param __y A %reverse_iterator. 291 * @return A simple bool. 292 * 293 * Reverse iterators forward many operations to their underlying base() 294 * iterators. Others are implemented in terms of one another. 295 * 296 */ 297 template<typename _Iterator> 298 inline _GLIBCXX17_CONSTEXPR bool 299 operator==(const reverse_iterator<_Iterator>& __x, 300 const reverse_iterator<_Iterator>& __y) 301 { return __x.base() == __y.base(); } 302 303 template<typename _Iterator> 304 inline _GLIBCXX17_CONSTEXPR bool 305 operator<(const reverse_iterator<_Iterator>& __x, 306 const reverse_iterator<_Iterator>& __y) 307 { return __y.base() < __x.base(); } 308 309 template<typename _Iterator> 310 inline _GLIBCXX17_CONSTEXPR bool 311 operator!=(const reverse_iterator<_Iterator>& __x, 312 const reverse_iterator<_Iterator>& __y) 313 { return !(__x == __y); } 314 315 template<typename _Iterator> 316 inline _GLIBCXX17_CONSTEXPR bool 317 operator>(const reverse_iterator<_Iterator>& __x, 318 const reverse_iterator<_Iterator>& __y) 319 { return __y < __x; } 320 321 template<typename _Iterator> 322 inline _GLIBCXX17_CONSTEXPR bool 323 operator<=(const reverse_iterator<_Iterator>& __x, 324 const reverse_iterator<_Iterator>& __y) 325 { return !(__y < __x); } 326 327 template<typename _Iterator> 328 inline _GLIBCXX17_CONSTEXPR bool 329 operator>=(const reverse_iterator<_Iterator>& __x, 330 const reverse_iterator<_Iterator>& __y) 331 { return !(__x < __y); } 332 333 // _GLIBCXX_RESOLVE_LIB_DEFECTS 334 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 335 template<typename _IteratorL, typename _IteratorR> 336 inline _GLIBCXX17_CONSTEXPR bool 337 operator==(const reverse_iterator<_IteratorL>& __x, 338 const reverse_iterator<_IteratorR>& __y) 339 { return __x.base() == __y.base(); } 340 341 template<typename _IteratorL, typename _IteratorR> 342 inline _GLIBCXX17_CONSTEXPR bool 343 operator<(const reverse_iterator<_IteratorL>& __x, 344 const reverse_iterator<_IteratorR>& __y) 345 { return __y.base() < __x.base(); } 346 347 template<typename _IteratorL, typename _IteratorR> 348 inline _GLIBCXX17_CONSTEXPR bool 349 operator!=(const reverse_iterator<_IteratorL>& __x, 350 const reverse_iterator<_IteratorR>& __y) 351 { return !(__x == __y); } 352 353 template<typename _IteratorL, typename _IteratorR> 354 inline _GLIBCXX17_CONSTEXPR bool 355 operator>(const reverse_iterator<_IteratorL>& __x, 356 const reverse_iterator<_IteratorR>& __y) 357 { return __y < __x; } 358 359 template<typename _IteratorL, typename _IteratorR> 360 inline _GLIBCXX17_CONSTEXPR bool 361 operator<=(const reverse_iterator<_IteratorL>& __x, 362 const reverse_iterator<_IteratorR>& __y) 363 { return !(__y < __x); } 364 365 template<typename _IteratorL, typename _IteratorR> 366 inline _GLIBCXX17_CONSTEXPR bool 367 operator>=(const reverse_iterator<_IteratorL>& __x, 368 const reverse_iterator<_IteratorR>& __y) 369 { return !(__x < __y); } 370 //@} 371 372 #if __cplusplus < 201103L 373 template<typename _Iterator> 374 inline typename reverse_iterator<_Iterator>::difference_type 375 operator-(const reverse_iterator<_Iterator>& __x, 376 const reverse_iterator<_Iterator>& __y) 377 { return __y.base() - __x.base(); } 378 379 template<typename _IteratorL, typename _IteratorR> 380 inline typename reverse_iterator<_IteratorL>::difference_type 381 operator-(const reverse_iterator<_IteratorL>& __x, 382 const reverse_iterator<_IteratorR>& __y) 383 { return __y.base() - __x.base(); } 384 #else 385 // _GLIBCXX_RESOLVE_LIB_DEFECTS 386 // DR 685. reverse_iterator/move_iterator difference has invalid signatures 387 template<typename _IteratorL, typename _IteratorR> 388 inline _GLIBCXX17_CONSTEXPR auto 389 operator-(const reverse_iterator<_IteratorL>& __x, 390 const reverse_iterator<_IteratorR>& __y) 391 -> decltype(__y.base() - __x.base()) 392 { return __y.base() - __x.base(); } 393 #endif 394 395 template<typename _Iterator> 396 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator> 397 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 398 const reverse_iterator<_Iterator>& __x) 399 { return reverse_iterator<_Iterator>(__x.base() - __n); } 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 _GLIBCXX17_CONSTEXPR 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 _GLIBCXX17_CONSTEXPR 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 * @param __i An iterator into the container. 725 * @return An instance of insert_iterator working on @p __x. 726 * 727 * This wrapper function helps in creating insert_iterator instances. 728 * Typing the name of the %iterator requires knowing the precise full 729 * type of the container, which can be tedious and impedes generic 730 * programming. Using this function lets you take advantage of automatic 731 * template parameter deduction, making the compiler match the correct 732 * types for you. 733 */ 734 template<typename _Container, typename _Iterator> 735 inline insert_iterator<_Container> 736 inserter(_Container& __x, _Iterator __i) 737 { 738 return insert_iterator<_Container>(__x, 739 typename _Container::iterator(__i)); 740 } 741 742 // @} group iterators 743 744 _GLIBCXX_END_NAMESPACE_VERSION 745 } // namespace 746 747 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 748 { 749 _GLIBCXX_BEGIN_NAMESPACE_VERSION 750 751 // This iterator adapter is @a normal in the sense that it does not 752 // change the semantics of any of the operators of its iterator 753 // parameter. Its primary purpose is to convert an iterator that is 754 // not a class, e.g. a pointer, into an iterator that is a class. 755 // The _Container parameter exists solely so that different containers 756 // using this template can instantiate different types, even if the 757 // _Iterator parameter is the same. 758 using std::iterator_traits; 759 using std::iterator; 760 template<typename _Iterator, typename _Container> 761 class __normal_iterator 762 { 763 protected: 764 _Iterator _M_current; 765 766 typedef iterator_traits<_Iterator> __traits_type; 767 768 public: 769 typedef _Iterator iterator_type; 770 typedef typename __traits_type::iterator_category iterator_category; 771 typedef typename __traits_type::value_type value_type; 772 typedef typename __traits_type::difference_type difference_type; 773 typedef typename __traits_type::reference reference; 774 typedef typename __traits_type::pointer pointer; 775 776 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 777 : _M_current(_Iterator()) { } 778 779 explicit 780 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 781 : _M_current(__i) { } 782 783 // Allow iterator to const_iterator conversion 784 template<typename _Iter> 785 __normal_iterator(const __normal_iterator<_Iter, 786 typename __enable_if< 787 (std::__are_same<_Iter, typename _Container::pointer>::__value), 788 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT 789 : _M_current(__i.base()) { } 790 791 // Forward iterator requirements 792 reference 793 operator*() const _GLIBCXX_NOEXCEPT 794 { return *_M_current; } 795 796 pointer 797 operator->() const _GLIBCXX_NOEXCEPT 798 { return _M_current; } 799 800 __normal_iterator& 801 operator++() _GLIBCXX_NOEXCEPT 802 { 803 ++_M_current; 804 return *this; 805 } 806 807 __normal_iterator 808 operator++(int) _GLIBCXX_NOEXCEPT 809 { return __normal_iterator(_M_current++); } 810 811 // Bidirectional iterator requirements 812 __normal_iterator& 813 operator--() _GLIBCXX_NOEXCEPT 814 { 815 --_M_current; 816 return *this; 817 } 818 819 __normal_iterator 820 operator--(int) _GLIBCXX_NOEXCEPT 821 { return __normal_iterator(_M_current--); } 822 823 // Random access iterator requirements 824 reference 825 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 826 { return _M_current[__n]; } 827 828 __normal_iterator& 829 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 830 { _M_current += __n; return *this; } 831 832 __normal_iterator 833 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 834 { return __normal_iterator(_M_current + __n); } 835 836 __normal_iterator& 837 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 838 { _M_current -= __n; return *this; } 839 840 __normal_iterator 841 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 842 { return __normal_iterator(_M_current - __n); } 843 844 const _Iterator& 845 base() const _GLIBCXX_NOEXCEPT 846 { return _M_current; } 847 }; 848 849 // Note: In what follows, the left- and right-hand-side iterators are 850 // allowed to vary in types (conceptually in cv-qualification) so that 851 // comparison between cv-qualified and non-cv-qualified iterators be 852 // valid. However, the greedy and unfriendly operators in std::rel_ops 853 // will make overload resolution ambiguous (when in scope) if we don't 854 // provide overloads whose operands are of the same type. Can someone 855 // remind me what generic programming is about? -- Gaby 856 857 // Forward iterator requirements 858 template<typename _IteratorL, typename _IteratorR, typename _Container> 859 inline bool 860 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 861 const __normal_iterator<_IteratorR, _Container>& __rhs) 862 _GLIBCXX_NOEXCEPT 863 { return __lhs.base() == __rhs.base(); } 864 865 template<typename _Iterator, typename _Container> 866 inline bool 867 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 868 const __normal_iterator<_Iterator, _Container>& __rhs) 869 _GLIBCXX_NOEXCEPT 870 { return __lhs.base() == __rhs.base(); } 871 872 template<typename _IteratorL, typename _IteratorR, typename _Container> 873 inline bool 874 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 875 const __normal_iterator<_IteratorR, _Container>& __rhs) 876 _GLIBCXX_NOEXCEPT 877 { return __lhs.base() != __rhs.base(); } 878 879 template<typename _Iterator, typename _Container> 880 inline bool 881 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 882 const __normal_iterator<_Iterator, _Container>& __rhs) 883 _GLIBCXX_NOEXCEPT 884 { return __lhs.base() != __rhs.base(); } 885 886 // Random access iterator requirements 887 template<typename _IteratorL, typename _IteratorR, typename _Container> 888 inline bool 889 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 890 const __normal_iterator<_IteratorR, _Container>& __rhs) 891 _GLIBCXX_NOEXCEPT 892 { return __lhs.base() < __rhs.base(); } 893 894 template<typename _Iterator, typename _Container> 895 inline bool 896 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 897 const __normal_iterator<_Iterator, _Container>& __rhs) 898 _GLIBCXX_NOEXCEPT 899 { return __lhs.base() < __rhs.base(); } 900 901 template<typename _IteratorL, typename _IteratorR, typename _Container> 902 inline bool 903 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 904 const __normal_iterator<_IteratorR, _Container>& __rhs) 905 _GLIBCXX_NOEXCEPT 906 { return __lhs.base() > __rhs.base(); } 907 908 template<typename _Iterator, typename _Container> 909 inline bool 910 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 911 const __normal_iterator<_Iterator, _Container>& __rhs) 912 _GLIBCXX_NOEXCEPT 913 { return __lhs.base() > __rhs.base(); } 914 915 template<typename _IteratorL, typename _IteratorR, typename _Container> 916 inline bool 917 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 918 const __normal_iterator<_IteratorR, _Container>& __rhs) 919 _GLIBCXX_NOEXCEPT 920 { return __lhs.base() <= __rhs.base(); } 921 922 template<typename _Iterator, typename _Container> 923 inline bool 924 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 925 const __normal_iterator<_Iterator, _Container>& __rhs) 926 _GLIBCXX_NOEXCEPT 927 { return __lhs.base() <= __rhs.base(); } 928 929 template<typename _IteratorL, typename _IteratorR, typename _Container> 930 inline bool 931 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 932 const __normal_iterator<_IteratorR, _Container>& __rhs) 933 _GLIBCXX_NOEXCEPT 934 { return __lhs.base() >= __rhs.base(); } 935 936 template<typename _Iterator, typename _Container> 937 inline bool 938 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 939 const __normal_iterator<_Iterator, _Container>& __rhs) 940 _GLIBCXX_NOEXCEPT 941 { return __lhs.base() >= __rhs.base(); } 942 943 // _GLIBCXX_RESOLVE_LIB_DEFECTS 944 // According to the resolution of DR179 not only the various comparison 945 // operators but also operator- must accept mixed iterator/const_iterator 946 // parameters. 947 template<typename _IteratorL, typename _IteratorR, typename _Container> 948 #if __cplusplus >= 201103L 949 // DR 685. 950 inline auto 951 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 952 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 953 -> decltype(__lhs.base() - __rhs.base()) 954 #else 955 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 956 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 957 const __normal_iterator<_IteratorR, _Container>& __rhs) 958 #endif 959 { return __lhs.base() - __rhs.base(); } 960 961 template<typename _Iterator, typename _Container> 962 inline typename __normal_iterator<_Iterator, _Container>::difference_type 963 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 964 const __normal_iterator<_Iterator, _Container>& __rhs) 965 _GLIBCXX_NOEXCEPT 966 { return __lhs.base() - __rhs.base(); } 967 968 template<typename _Iterator, typename _Container> 969 inline __normal_iterator<_Iterator, _Container> 970 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 971 __n, const __normal_iterator<_Iterator, _Container>& __i) 972 _GLIBCXX_NOEXCEPT 973 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 974 975 _GLIBCXX_END_NAMESPACE_VERSION 976 } // namespace 977 978 namespace std _GLIBCXX_VISIBILITY(default) 979 { 980 _GLIBCXX_BEGIN_NAMESPACE_VERSION 981 982 template<typename _Iterator, typename _Container> 983 _Iterator 984 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it) 985 { return __it.base(); } 986 987 #if __cplusplus >= 201103L 988 989 /** 990 * @addtogroup iterators 991 * @{ 992 */ 993 994 // 24.4.3 Move iterators 995 /** 996 * Class template move_iterator is an iterator adapter with the same 997 * behavior as the underlying iterator except that its dereference 998 * operator implicitly converts the value returned by the underlying 999 * iterator's dereference operator to an rvalue reference. Some 1000 * generic algorithms can be called with move iterators to replace 1001 * copying with moving. 1002 */ 1003 template<typename _Iterator> 1004 class move_iterator 1005 { 1006 protected: 1007 _Iterator _M_current; 1008 1009 typedef iterator_traits<_Iterator> __traits_type; 1010 typedef typename __traits_type::reference __base_ref; 1011 1012 public: 1013 typedef _Iterator iterator_type; 1014 typedef typename __traits_type::iterator_category iterator_category; 1015 typedef typename __traits_type::value_type value_type; 1016 typedef typename __traits_type::difference_type difference_type; 1017 // NB: DR 680. 1018 typedef _Iterator pointer; 1019 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1020 // 2106. move_iterator wrapping iterators returning prvalues 1021 typedef typename conditional<is_reference<__base_ref>::value, 1022 typename remove_reference<__base_ref>::type&&, 1023 __base_ref>::type reference; 1024 1025 _GLIBCXX17_CONSTEXPR 1026 move_iterator() 1027 : _M_current() { } 1028 1029 explicit _GLIBCXX17_CONSTEXPR 1030 move_iterator(iterator_type __i) 1031 : _M_current(__i) { } 1032 1033 template<typename _Iter> 1034 _GLIBCXX17_CONSTEXPR 1035 move_iterator(const move_iterator<_Iter>& __i) 1036 : _M_current(__i.base()) { } 1037 1038 _GLIBCXX17_CONSTEXPR iterator_type 1039 base() const 1040 { return _M_current; } 1041 1042 _GLIBCXX17_CONSTEXPR reference 1043 operator*() const 1044 { return static_cast<reference>(*_M_current); } 1045 1046 _GLIBCXX17_CONSTEXPR pointer 1047 operator->() const 1048 { return _M_current; } 1049 1050 _GLIBCXX17_CONSTEXPR move_iterator& 1051 operator++() 1052 { 1053 ++_M_current; 1054 return *this; 1055 } 1056 1057 _GLIBCXX17_CONSTEXPR move_iterator 1058 operator++(int) 1059 { 1060 move_iterator __tmp = *this; 1061 ++_M_current; 1062 return __tmp; 1063 } 1064 1065 _GLIBCXX17_CONSTEXPR move_iterator& 1066 operator--() 1067 { 1068 --_M_current; 1069 return *this; 1070 } 1071 1072 _GLIBCXX17_CONSTEXPR move_iterator 1073 operator--(int) 1074 { 1075 move_iterator __tmp = *this; 1076 --_M_current; 1077 return __tmp; 1078 } 1079 1080 _GLIBCXX17_CONSTEXPR move_iterator 1081 operator+(difference_type __n) const 1082 { return move_iterator(_M_current + __n); } 1083 1084 _GLIBCXX17_CONSTEXPR move_iterator& 1085 operator+=(difference_type __n) 1086 { 1087 _M_current += __n; 1088 return *this; 1089 } 1090 1091 _GLIBCXX17_CONSTEXPR move_iterator 1092 operator-(difference_type __n) const 1093 { return move_iterator(_M_current - __n); } 1094 1095 _GLIBCXX17_CONSTEXPR move_iterator& 1096 operator-=(difference_type __n) 1097 { 1098 _M_current -= __n; 1099 return *this; 1100 } 1101 1102 _GLIBCXX17_CONSTEXPR reference 1103 operator[](difference_type __n) const 1104 { return std::move(_M_current[__n]); } 1105 }; 1106 1107 // Note: See __normal_iterator operators note from Gaby to understand 1108 // why there are always 2 versions for most of the move_iterator 1109 // operators. 1110 template<typename _IteratorL, typename _IteratorR> 1111 inline _GLIBCXX17_CONSTEXPR bool 1112 operator==(const move_iterator<_IteratorL>& __x, 1113 const move_iterator<_IteratorR>& __y) 1114 { return __x.base() == __y.base(); } 1115 1116 template<typename _Iterator> 1117 inline _GLIBCXX17_CONSTEXPR bool 1118 operator==(const move_iterator<_Iterator>& __x, 1119 const move_iterator<_Iterator>& __y) 1120 { return __x.base() == __y.base(); } 1121 1122 template<typename _IteratorL, typename _IteratorR> 1123 inline _GLIBCXX17_CONSTEXPR bool 1124 operator!=(const move_iterator<_IteratorL>& __x, 1125 const move_iterator<_IteratorR>& __y) 1126 { return !(__x == __y); } 1127 1128 template<typename _Iterator> 1129 inline _GLIBCXX17_CONSTEXPR bool 1130 operator!=(const move_iterator<_Iterator>& __x, 1131 const move_iterator<_Iterator>& __y) 1132 { return !(__x == __y); } 1133 1134 template<typename _IteratorL, typename _IteratorR> 1135 inline _GLIBCXX17_CONSTEXPR bool 1136 operator<(const move_iterator<_IteratorL>& __x, 1137 const move_iterator<_IteratorR>& __y) 1138 { return __x.base() < __y.base(); } 1139 1140 template<typename _Iterator> 1141 inline _GLIBCXX17_CONSTEXPR bool 1142 operator<(const move_iterator<_Iterator>& __x, 1143 const move_iterator<_Iterator>& __y) 1144 { return __x.base() < __y.base(); } 1145 1146 template<typename _IteratorL, typename _IteratorR> 1147 inline _GLIBCXX17_CONSTEXPR bool 1148 operator<=(const move_iterator<_IteratorL>& __x, 1149 const move_iterator<_IteratorR>& __y) 1150 { return !(__y < __x); } 1151 1152 template<typename _Iterator> 1153 inline _GLIBCXX17_CONSTEXPR bool 1154 operator<=(const move_iterator<_Iterator>& __x, 1155 const move_iterator<_Iterator>& __y) 1156 { return !(__y < __x); } 1157 1158 template<typename _IteratorL, typename _IteratorR> 1159 inline _GLIBCXX17_CONSTEXPR bool 1160 operator>(const move_iterator<_IteratorL>& __x, 1161 const move_iterator<_IteratorR>& __y) 1162 { return __y < __x; } 1163 1164 template<typename _Iterator> 1165 inline _GLIBCXX17_CONSTEXPR bool 1166 operator>(const move_iterator<_Iterator>& __x, 1167 const move_iterator<_Iterator>& __y) 1168 { return __y < __x; } 1169 1170 template<typename _IteratorL, typename _IteratorR> 1171 inline _GLIBCXX17_CONSTEXPR bool 1172 operator>=(const move_iterator<_IteratorL>& __x, 1173 const move_iterator<_IteratorR>& __y) 1174 { return !(__x < __y); } 1175 1176 template<typename _Iterator> 1177 inline _GLIBCXX17_CONSTEXPR bool 1178 operator>=(const move_iterator<_Iterator>& __x, 1179 const move_iterator<_Iterator>& __y) 1180 { return !(__x < __y); } 1181 1182 // DR 685. 1183 template<typename _IteratorL, typename _IteratorR> 1184 inline _GLIBCXX17_CONSTEXPR auto 1185 operator-(const move_iterator<_IteratorL>& __x, 1186 const move_iterator<_IteratorR>& __y) 1187 -> decltype(__x.base() - __y.base()) 1188 { return __x.base() - __y.base(); } 1189 1190 template<typename _Iterator> 1191 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 1192 operator+(typename move_iterator<_Iterator>::difference_type __n, 1193 const move_iterator<_Iterator>& __x) 1194 { return __x + __n; } 1195 1196 template<typename _Iterator> 1197 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 1198 make_move_iterator(_Iterator __i) 1199 { return move_iterator<_Iterator>(__i); } 1200 1201 template<typename _Iterator, typename _ReturnType 1202 = typename conditional<__move_if_noexcept_cond 1203 <typename iterator_traits<_Iterator>::value_type>::value, 1204 _Iterator, move_iterator<_Iterator>>::type> 1205 inline _GLIBCXX17_CONSTEXPR _ReturnType 1206 __make_move_if_noexcept_iterator(_Iterator __i) 1207 { return _ReturnType(__i); } 1208 1209 // Overload for pointers that matches std::move_if_noexcept more closely, 1210 // returning a constant iterator when we don't want to move. 1211 template<typename _Tp, typename _ReturnType 1212 = typename conditional<__move_if_noexcept_cond<_Tp>::value, 1213 const _Tp*, move_iterator<_Tp*>>::type> 1214 inline _GLIBCXX17_CONSTEXPR _ReturnType 1215 __make_move_if_noexcept_iterator(_Tp* __i) 1216 { return _ReturnType(__i); } 1217 1218 // @} group iterators 1219 1220 template<typename _Iterator> 1221 auto 1222 __niter_base(move_iterator<_Iterator> __it) 1223 -> decltype(make_move_iterator(__niter_base(__it.base()))) 1224 { return make_move_iterator(__niter_base(__it.base())); } 1225 1226 template<typename _Iterator> 1227 struct __is_move_iterator<move_iterator<_Iterator> > 1228 { 1229 enum { __value = 1 }; 1230 typedef __true_type __type; 1231 }; 1232 1233 template<typename _Iterator> 1234 auto 1235 __miter_base(move_iterator<_Iterator> __it) 1236 -> decltype(__miter_base(__it.base())) 1237 { return __miter_base(__it.base()); } 1238 1239 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 1240 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 1241 std::__make_move_if_noexcept_iterator(_Iter) 1242 #else 1243 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 1244 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 1245 #endif // C++11 1246 1247 #if __cpp_deduction_guides >= 201606 1248 // These helper traits are used for deduction guides 1249 // of associative containers. 1250 template<typename _InputIterator> 1251 using __iter_key_t = remove_const_t< 1252 typename iterator_traits<_InputIterator>::value_type::first_type>; 1253 1254 template<typename _InputIterator> 1255 using __iter_val_t = 1256 typename iterator_traits<_InputIterator>::value_type::second_type; 1257 1258 template<typename _T1, typename _T2> 1259 struct pair; 1260 1261 template<typename _InputIterator> 1262 using __iter_to_alloc_t = 1263 pair<add_const_t<__iter_key_t<_InputIterator>>, 1264 __iter_val_t<_InputIterator>>; 1265 1266 #endif 1267 1268 _GLIBCXX_END_NAMESPACE_VERSION 1269 } // namespace 1270 1271 #ifdef _GLIBCXX_DEBUG 1272 # include <debug/stl_iterator.h> 1273 #endif 1274 1275 #endif 1276