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