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 // 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 * @param __i An iterator into the container. 728 * @return An instance of insert_iterator working on @p __x. 729 * 730 * This wrapper function helps in creating insert_iterator instances. 731 * Typing the name of the %iterator requires knowing the precise full 732 * type of the container, which can be tedious and impedes generic 733 * programming. Using this function lets you take advantage of automatic 734 * template parameter deduction, making the compiler match the correct 735 * types for you. 736 */ 737 template<typename _Container, typename _Iterator> 738 inline insert_iterator<_Container> 739 inserter(_Container& __x, _Iterator __i) 740 { 741 return insert_iterator<_Container>(__x, 742 typename _Container::iterator(__i)); 743 } 744 745 // @} group iterators 746 747 _GLIBCXX_END_NAMESPACE_VERSION 748 } // namespace 749 750 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 751 { 752 _GLIBCXX_BEGIN_NAMESPACE_VERSION 753 754 // This iterator adapter is @a normal in the sense that it does not 755 // change the semantics of any of the operators of its iterator 756 // parameter. Its primary purpose is to convert an iterator that is 757 // not a class, e.g. a pointer, into an iterator that is a class. 758 // The _Container parameter exists solely so that different containers 759 // using this template can instantiate different types, even if the 760 // _Iterator parameter is the same. 761 using std::iterator_traits; 762 using std::iterator; 763 template<typename _Iterator, typename _Container> 764 class __normal_iterator 765 { 766 protected: 767 _Iterator _M_current; 768 769 typedef iterator_traits<_Iterator> __traits_type; 770 771 public: 772 typedef _Iterator iterator_type; 773 typedef typename __traits_type::iterator_category iterator_category; 774 typedef typename __traits_type::value_type value_type; 775 typedef typename __traits_type::difference_type difference_type; 776 typedef typename __traits_type::reference reference; 777 typedef typename __traits_type::pointer pointer; 778 779 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 780 : _M_current(_Iterator()) { } 781 782 explicit 783 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 784 : _M_current(__i) { } 785 786 // Allow iterator to const_iterator conversion 787 template<typename _Iter> 788 __normal_iterator(const __normal_iterator<_Iter, 789 typename __enable_if< 790 (std::__are_same<_Iter, typename _Container::pointer>::__value), 791 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT 792 : _M_current(__i.base()) { } 793 794 // Forward iterator requirements 795 reference 796 operator*() const _GLIBCXX_NOEXCEPT 797 { return *_M_current; } 798 799 pointer 800 operator->() const _GLIBCXX_NOEXCEPT 801 { return _M_current; } 802 803 __normal_iterator& 804 operator++() _GLIBCXX_NOEXCEPT 805 { 806 ++_M_current; 807 return *this; 808 } 809 810 __normal_iterator 811 operator++(int) _GLIBCXX_NOEXCEPT 812 { return __normal_iterator(_M_current++); } 813 814 // Bidirectional iterator requirements 815 __normal_iterator& 816 operator--() _GLIBCXX_NOEXCEPT 817 { 818 --_M_current; 819 return *this; 820 } 821 822 __normal_iterator 823 operator--(int) _GLIBCXX_NOEXCEPT 824 { return __normal_iterator(_M_current--); } 825 826 // Random access iterator requirements 827 reference 828 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 829 { return _M_current[__n]; } 830 831 __normal_iterator& 832 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 833 { _M_current += __n; return *this; } 834 835 __normal_iterator 836 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 837 { return __normal_iterator(_M_current + __n); } 838 839 __normal_iterator& 840 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 841 { _M_current -= __n; return *this; } 842 843 __normal_iterator 844 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 845 { return __normal_iterator(_M_current - __n); } 846 847 const _Iterator& 848 base() const _GLIBCXX_NOEXCEPT 849 { return _M_current; } 850 }; 851 852 // Note: In what follows, the left- and right-hand-side iterators are 853 // allowed to vary in types (conceptually in cv-qualification) so that 854 // comparison between cv-qualified and non-cv-qualified iterators be 855 // valid. However, the greedy and unfriendly operators in std::rel_ops 856 // will make overload resolution ambiguous (when in scope) if we don't 857 // provide overloads whose operands are of the same type. Can someone 858 // remind me what generic programming is about? -- Gaby 859 860 // Forward iterator requirements 861 template<typename _IteratorL, typename _IteratorR, typename _Container> 862 inline bool 863 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 864 const __normal_iterator<_IteratorR, _Container>& __rhs) 865 _GLIBCXX_NOEXCEPT 866 { return __lhs.base() == __rhs.base(); } 867 868 template<typename _Iterator, typename _Container> 869 inline bool 870 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 871 const __normal_iterator<_Iterator, _Container>& __rhs) 872 _GLIBCXX_NOEXCEPT 873 { return __lhs.base() == __rhs.base(); } 874 875 template<typename _IteratorL, typename _IteratorR, typename _Container> 876 inline bool 877 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 878 const __normal_iterator<_IteratorR, _Container>& __rhs) 879 _GLIBCXX_NOEXCEPT 880 { return __lhs.base() != __rhs.base(); } 881 882 template<typename _Iterator, typename _Container> 883 inline bool 884 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 885 const __normal_iterator<_Iterator, _Container>& __rhs) 886 _GLIBCXX_NOEXCEPT 887 { return __lhs.base() != __rhs.base(); } 888 889 // Random access iterator requirements 890 template<typename _IteratorL, typename _IteratorR, typename _Container> 891 inline bool 892 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 893 const __normal_iterator<_IteratorR, _Container>& __rhs) 894 _GLIBCXX_NOEXCEPT 895 { return __lhs.base() < __rhs.base(); } 896 897 template<typename _Iterator, typename _Container> 898 inline bool 899 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 900 const __normal_iterator<_Iterator, _Container>& __rhs) 901 _GLIBCXX_NOEXCEPT 902 { return __lhs.base() < __rhs.base(); } 903 904 template<typename _IteratorL, typename _IteratorR, typename _Container> 905 inline bool 906 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 907 const __normal_iterator<_IteratorR, _Container>& __rhs) 908 _GLIBCXX_NOEXCEPT 909 { return __lhs.base() > __rhs.base(); } 910 911 template<typename _Iterator, typename _Container> 912 inline bool 913 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 914 const __normal_iterator<_Iterator, _Container>& __rhs) 915 _GLIBCXX_NOEXCEPT 916 { return __lhs.base() > __rhs.base(); } 917 918 template<typename _IteratorL, typename _IteratorR, typename _Container> 919 inline bool 920 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 921 const __normal_iterator<_IteratorR, _Container>& __rhs) 922 _GLIBCXX_NOEXCEPT 923 { return __lhs.base() <= __rhs.base(); } 924 925 template<typename _Iterator, typename _Container> 926 inline bool 927 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 928 const __normal_iterator<_Iterator, _Container>& __rhs) 929 _GLIBCXX_NOEXCEPT 930 { return __lhs.base() <= __rhs.base(); } 931 932 template<typename _IteratorL, typename _IteratorR, typename _Container> 933 inline bool 934 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 935 const __normal_iterator<_IteratorR, _Container>& __rhs) 936 _GLIBCXX_NOEXCEPT 937 { return __lhs.base() >= __rhs.base(); } 938 939 template<typename _Iterator, typename _Container> 940 inline bool 941 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 942 const __normal_iterator<_Iterator, _Container>& __rhs) 943 _GLIBCXX_NOEXCEPT 944 { return __lhs.base() >= __rhs.base(); } 945 946 // _GLIBCXX_RESOLVE_LIB_DEFECTS 947 // According to the resolution of DR179 not only the various comparison 948 // operators but also operator- must accept mixed iterator/const_iterator 949 // parameters. 950 template<typename _IteratorL, typename _IteratorR, typename _Container> 951 #if __cplusplus >= 201103L 952 // DR 685. 953 inline auto 954 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 955 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 956 -> decltype(__lhs.base() - __rhs.base()) 957 #else 958 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 959 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 960 const __normal_iterator<_IteratorR, _Container>& __rhs) 961 #endif 962 { return __lhs.base() - __rhs.base(); } 963 964 template<typename _Iterator, typename _Container> 965 inline typename __normal_iterator<_Iterator, _Container>::difference_type 966 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 967 const __normal_iterator<_Iterator, _Container>& __rhs) 968 _GLIBCXX_NOEXCEPT 969 { return __lhs.base() - __rhs.base(); } 970 971 template<typename _Iterator, typename _Container> 972 inline __normal_iterator<_Iterator, _Container> 973 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 974 __n, const __normal_iterator<_Iterator, _Container>& __i) 975 _GLIBCXX_NOEXCEPT 976 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 977 978 _GLIBCXX_END_NAMESPACE_VERSION 979 } // namespace 980 981 namespace std _GLIBCXX_VISIBILITY(default) 982 { 983 _GLIBCXX_BEGIN_NAMESPACE_VERSION 984 985 template<typename _Iterator, typename _Container> 986 _Iterator 987 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it) 988 { return __it.base(); } 989 990 #if __cplusplus >= 201103L 991 992 /** 993 * @addtogroup iterators 994 * @{ 995 */ 996 997 // 24.4.3 Move iterators 998 /** 999 * Class template move_iterator is an iterator adapter with the same 1000 * behavior as the underlying iterator except that its dereference 1001 * operator implicitly converts the value returned by the underlying 1002 * iterator's dereference operator to an rvalue reference. Some 1003 * generic algorithms can be called with move iterators to replace 1004 * copying with moving. 1005 */ 1006 template<typename _Iterator> 1007 class move_iterator 1008 { 1009 protected: 1010 _Iterator _M_current; 1011 1012 typedef iterator_traits<_Iterator> __traits_type; 1013 typedef typename __traits_type::reference __base_ref; 1014 1015 public: 1016 typedef _Iterator iterator_type; 1017 typedef typename __traits_type::iterator_category iterator_category; 1018 typedef typename __traits_type::value_type value_type; 1019 typedef typename __traits_type::difference_type difference_type; 1020 // NB: DR 680. 1021 typedef _Iterator pointer; 1022 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1023 // 2106. move_iterator wrapping iterators returning prvalues 1024 typedef typename conditional<is_reference<__base_ref>::value, 1025 typename remove_reference<__base_ref>::type&&, 1026 __base_ref>::type reference; 1027 1028 _GLIBCXX17_CONSTEXPR 1029 move_iterator() 1030 : _M_current() { } 1031 1032 explicit _GLIBCXX17_CONSTEXPR 1033 move_iterator(iterator_type __i) 1034 : _M_current(__i) { } 1035 1036 template<typename _Iter> 1037 _GLIBCXX17_CONSTEXPR 1038 move_iterator(const move_iterator<_Iter>& __i) 1039 : _M_current(__i.base()) { } 1040 1041 _GLIBCXX17_CONSTEXPR iterator_type 1042 base() const 1043 { return _M_current; } 1044 1045 _GLIBCXX17_CONSTEXPR reference 1046 operator*() const 1047 { return static_cast<reference>(*_M_current); } 1048 1049 _GLIBCXX17_CONSTEXPR pointer 1050 operator->() const 1051 { return _M_current; } 1052 1053 _GLIBCXX17_CONSTEXPR move_iterator& 1054 operator++() 1055 { 1056 ++_M_current; 1057 return *this; 1058 } 1059 1060 _GLIBCXX17_CONSTEXPR move_iterator 1061 operator++(int) 1062 { 1063 move_iterator __tmp = *this; 1064 ++_M_current; 1065 return __tmp; 1066 } 1067 1068 _GLIBCXX17_CONSTEXPR move_iterator& 1069 operator--() 1070 { 1071 --_M_current; 1072 return *this; 1073 } 1074 1075 _GLIBCXX17_CONSTEXPR move_iterator 1076 operator--(int) 1077 { 1078 move_iterator __tmp = *this; 1079 --_M_current; 1080 return __tmp; 1081 } 1082 1083 _GLIBCXX17_CONSTEXPR move_iterator 1084 operator+(difference_type __n) const 1085 { return move_iterator(_M_current + __n); } 1086 1087 _GLIBCXX17_CONSTEXPR move_iterator& 1088 operator+=(difference_type __n) 1089 { 1090 _M_current += __n; 1091 return *this; 1092 } 1093 1094 _GLIBCXX17_CONSTEXPR move_iterator 1095 operator-(difference_type __n) const 1096 { return move_iterator(_M_current - __n); } 1097 1098 _GLIBCXX17_CONSTEXPR move_iterator& 1099 operator-=(difference_type __n) 1100 { 1101 _M_current -= __n; 1102 return *this; 1103 } 1104 1105 _GLIBCXX17_CONSTEXPR reference 1106 operator[](difference_type __n) const 1107 { return std::move(_M_current[__n]); } 1108 }; 1109 1110 // Note: See __normal_iterator operators note from Gaby to understand 1111 // why there are always 2 versions for most of the move_iterator 1112 // operators. 1113 template<typename _IteratorL, typename _IteratorR> 1114 inline _GLIBCXX17_CONSTEXPR bool 1115 operator==(const move_iterator<_IteratorL>& __x, 1116 const move_iterator<_IteratorR>& __y) 1117 { return __x.base() == __y.base(); } 1118 1119 template<typename _Iterator> 1120 inline _GLIBCXX17_CONSTEXPR bool 1121 operator==(const move_iterator<_Iterator>& __x, 1122 const move_iterator<_Iterator>& __y) 1123 { return __x.base() == __y.base(); } 1124 1125 template<typename _IteratorL, typename _IteratorR> 1126 inline _GLIBCXX17_CONSTEXPR bool 1127 operator!=(const move_iterator<_IteratorL>& __x, 1128 const move_iterator<_IteratorR>& __y) 1129 { return !(__x == __y); } 1130 1131 template<typename _Iterator> 1132 inline _GLIBCXX17_CONSTEXPR bool 1133 operator!=(const move_iterator<_Iterator>& __x, 1134 const move_iterator<_Iterator>& __y) 1135 { return !(__x == __y); } 1136 1137 template<typename _IteratorL, typename _IteratorR> 1138 inline _GLIBCXX17_CONSTEXPR bool 1139 operator<(const move_iterator<_IteratorL>& __x, 1140 const move_iterator<_IteratorR>& __y) 1141 { return __x.base() < __y.base(); } 1142 1143 template<typename _Iterator> 1144 inline _GLIBCXX17_CONSTEXPR bool 1145 operator<(const move_iterator<_Iterator>& __x, 1146 const move_iterator<_Iterator>& __y) 1147 { return __x.base() < __y.base(); } 1148 1149 template<typename _IteratorL, typename _IteratorR> 1150 inline _GLIBCXX17_CONSTEXPR bool 1151 operator<=(const move_iterator<_IteratorL>& __x, 1152 const move_iterator<_IteratorR>& __y) 1153 { return !(__y < __x); } 1154 1155 template<typename _Iterator> 1156 inline _GLIBCXX17_CONSTEXPR bool 1157 operator<=(const move_iterator<_Iterator>& __x, 1158 const move_iterator<_Iterator>& __y) 1159 { return !(__y < __x); } 1160 1161 template<typename _IteratorL, typename _IteratorR> 1162 inline _GLIBCXX17_CONSTEXPR bool 1163 operator>(const move_iterator<_IteratorL>& __x, 1164 const move_iterator<_IteratorR>& __y) 1165 { return __y < __x; } 1166 1167 template<typename _Iterator> 1168 inline _GLIBCXX17_CONSTEXPR bool 1169 operator>(const move_iterator<_Iterator>& __x, 1170 const move_iterator<_Iterator>& __y) 1171 { return __y < __x; } 1172 1173 template<typename _IteratorL, typename _IteratorR> 1174 inline _GLIBCXX17_CONSTEXPR bool 1175 operator>=(const move_iterator<_IteratorL>& __x, 1176 const move_iterator<_IteratorR>& __y) 1177 { return !(__x < __y); } 1178 1179 template<typename _Iterator> 1180 inline _GLIBCXX17_CONSTEXPR bool 1181 operator>=(const move_iterator<_Iterator>& __x, 1182 const move_iterator<_Iterator>& __y) 1183 { return !(__x < __y); } 1184 1185 // DR 685. 1186 template<typename _IteratorL, typename _IteratorR> 1187 inline _GLIBCXX17_CONSTEXPR auto 1188 operator-(const move_iterator<_IteratorL>& __x, 1189 const move_iterator<_IteratorR>& __y) 1190 -> decltype(__x.base() - __y.base()) 1191 { return __x.base() - __y.base(); } 1192 1193 template<typename _Iterator> 1194 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 1195 operator+(typename move_iterator<_Iterator>::difference_type __n, 1196 const move_iterator<_Iterator>& __x) 1197 { return __x + __n; } 1198 1199 template<typename _Iterator> 1200 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 1201 make_move_iterator(_Iterator __i) 1202 { return move_iterator<_Iterator>(__i); } 1203 1204 template<typename _Iterator, typename _ReturnType 1205 = typename conditional<__move_if_noexcept_cond 1206 <typename iterator_traits<_Iterator>::value_type>::value, 1207 _Iterator, move_iterator<_Iterator>>::type> 1208 inline _GLIBCXX17_CONSTEXPR _ReturnType 1209 __make_move_if_noexcept_iterator(_Iterator __i) 1210 { return _ReturnType(__i); } 1211 1212 // Overload for pointers that matches std::move_if_noexcept more closely, 1213 // returning a constant iterator when we don't want to move. 1214 template<typename _Tp, typename _ReturnType 1215 = typename conditional<__move_if_noexcept_cond<_Tp>::value, 1216 const _Tp*, move_iterator<_Tp*>>::type> 1217 inline _GLIBCXX17_CONSTEXPR _ReturnType 1218 __make_move_if_noexcept_iterator(_Tp* __i) 1219 { return _ReturnType(__i); } 1220 1221 // @} group iterators 1222 1223 template<typename _Iterator> 1224 auto 1225 __niter_base(move_iterator<_Iterator> __it) 1226 -> decltype(make_move_iterator(__niter_base(__it.base()))) 1227 { return make_move_iterator(__niter_base(__it.base())); } 1228 1229 template<typename _Iterator> 1230 struct __is_move_iterator<move_iterator<_Iterator> > 1231 { 1232 enum { __value = 1 }; 1233 typedef __true_type __type; 1234 }; 1235 1236 template<typename _Iterator> 1237 auto 1238 __miter_base(move_iterator<_Iterator> __it) 1239 -> decltype(__miter_base(__it.base())) 1240 { return __miter_base(__it.base()); } 1241 1242 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 1243 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 1244 std::__make_move_if_noexcept_iterator(_Iter) 1245 #else 1246 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 1247 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 1248 #endif // C++11 1249 1250 #if __cpp_deduction_guides >= 201606 1251 // These helper traits are used for deduction guides 1252 // of associative containers. 1253 template<typename _InputIterator> 1254 using __iter_key_t = remove_const_t< 1255 typename iterator_traits<_InputIterator>::value_type::first_type>; 1256 1257 template<typename _InputIterator> 1258 using __iter_val_t = 1259 typename iterator_traits<_InputIterator>::value_type::second_type; 1260 1261 template<typename _T1, typename _T2> 1262 struct pair; 1263 1264 template<typename _InputIterator> 1265 using __iter_to_alloc_t = 1266 pair<add_const_t<__iter_key_t<_InputIterator>>, 1267 __iter_val_t<_InputIterator>>; 1268 1269 #endif 1270 1271 _GLIBCXX_END_NAMESPACE_VERSION 1272 } // namespace 1273 1274 #ifdef _GLIBCXX_DEBUG 1275 # include <debug/stl_iterator.h> 1276 #endif 1277 1278 #endif 1279