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