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