libstdc++
|
00001 // Iterators -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996-1998 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file bits/stl_iterator.h 00053 * This is an internal header file, included by other library headers. 00054 * Do not attempt to use it directly. @headername{iterator} 00055 * 00056 * This file implements reverse_iterator, back_insert_iterator, 00057 * front_insert_iterator, insert_iterator, __normal_iterator, and their 00058 * supporting functions and overloaded operators. 00059 */ 00060 00061 #ifndef _STL_ITERATOR_H 00062 #define _STL_ITERATOR_H 1 00063 00064 #include <bits/cpp_type_traits.h> 00065 #include <ext/type_traits.h> 00066 #include <bits/move.h> 00067 00068 namespace std _GLIBCXX_VISIBILITY(default) 00069 { 00070 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00071 00072 /** 00073 * @addtogroup iterators 00074 * @{ 00075 */ 00076 00077 // 24.4.1 Reverse iterators 00078 /** 00079 * Bidirectional and random access iterators have corresponding reverse 00080 * %iterator adaptors that iterate through the data structure in the 00081 * opposite direction. They have the same signatures as the corresponding 00082 * iterators. The fundamental relation between a reverse %iterator and its 00083 * corresponding %iterator @c i is established by the identity: 00084 * @code 00085 * &*(reverse_iterator(i)) == &*(i - 1) 00086 * @endcode 00087 * 00088 * <em>This mapping is dictated by the fact that while there is always a 00089 * pointer past the end of an array, there might not be a valid pointer 00090 * before the beginning of an array.</em> [24.4.1]/1,2 00091 * 00092 * Reverse iterators can be tricky and surprising at first. Their 00093 * semantics make sense, however, and the trickiness is a side effect of 00094 * the requirement that the iterators must be safe. 00095 */ 00096 template<typename _Iterator> 00097 class reverse_iterator 00098 : public iterator<typename iterator_traits<_Iterator>::iterator_category, 00099 typename iterator_traits<_Iterator>::value_type, 00100 typename iterator_traits<_Iterator>::difference_type, 00101 typename iterator_traits<_Iterator>::pointer, 00102 typename iterator_traits<_Iterator>::reference> 00103 { 00104 protected: 00105 _Iterator current; 00106 00107 typedef iterator_traits<_Iterator> __traits_type; 00108 00109 public: 00110 typedef _Iterator iterator_type; 00111 typedef typename __traits_type::difference_type difference_type; 00112 typedef typename __traits_type::pointer pointer; 00113 typedef typename __traits_type::reference reference; 00114 00115 /** 00116 * The default constructor default-initializes member @p current. 00117 * If it is a pointer, that means it is zero-initialized. 00118 */ 00119 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00120 // 235 No specification of default ctor for reverse_iterator 00121 reverse_iterator() : current() { } 00122 00123 /** 00124 * This %iterator will move in the opposite direction that @p x does. 00125 */ 00126 explicit 00127 reverse_iterator(iterator_type __x) : current(__x) { } 00128 00129 /** 00130 * The copy constructor is normal. 00131 */ 00132 reverse_iterator(const reverse_iterator& __x) 00133 : current(__x.current) { } 00134 00135 /** 00136 * A reverse_iterator across other types can be copied in the normal 00137 * fashion. 00138 */ 00139 template<typename _Iter> 00140 reverse_iterator(const reverse_iterator<_Iter>& __x) 00141 : current(__x.base()) { } 00142 00143 /** 00144 * @return @c current, the %iterator used for underlying work. 00145 */ 00146 iterator_type 00147 base() const 00148 { return current; } 00149 00150 /** 00151 * @return TODO 00152 * 00153 * @doctodo 00154 */ 00155 reference 00156 operator*() const 00157 { 00158 _Iterator __tmp = current; 00159 return *--__tmp; 00160 } 00161 00162 /** 00163 * @return TODO 00164 * 00165 * @doctodo 00166 */ 00167 pointer 00168 operator->() const 00169 { return &(operator*()); } 00170 00171 /** 00172 * @return TODO 00173 * 00174 * @doctodo 00175 */ 00176 reverse_iterator& 00177 operator++() 00178 { 00179 --current; 00180 return *this; 00181 } 00182 00183 /** 00184 * @return TODO 00185 * 00186 * @doctodo 00187 */ 00188 reverse_iterator 00189 operator++(int) 00190 { 00191 reverse_iterator __tmp = *this; 00192 --current; 00193 return __tmp; 00194 } 00195 00196 /** 00197 * @return TODO 00198 * 00199 * @doctodo 00200 */ 00201 reverse_iterator& 00202 operator--() 00203 { 00204 ++current; 00205 return *this; 00206 } 00207 00208 /** 00209 * @return TODO 00210 * 00211 * @doctodo 00212 */ 00213 reverse_iterator 00214 operator--(int) 00215 { 00216 reverse_iterator __tmp = *this; 00217 ++current; 00218 return __tmp; 00219 } 00220 00221 /** 00222 * @return TODO 00223 * 00224 * @doctodo 00225 */ 00226 reverse_iterator 00227 operator+(difference_type __n) const 00228 { return reverse_iterator(current - __n); } 00229 00230 /** 00231 * @return TODO 00232 * 00233 * @doctodo 00234 */ 00235 reverse_iterator& 00236 operator+=(difference_type __n) 00237 { 00238 current -= __n; 00239 return *this; 00240 } 00241 00242 /** 00243 * @return TODO 00244 * 00245 * @doctodo 00246 */ 00247 reverse_iterator 00248 operator-(difference_type __n) const 00249 { return reverse_iterator(current + __n); } 00250 00251 /** 00252 * @return TODO 00253 * 00254 * @doctodo 00255 */ 00256 reverse_iterator& 00257 operator-=(difference_type __n) 00258 { 00259 current += __n; 00260 return *this; 00261 } 00262 00263 /** 00264 * @return TODO 00265 * 00266 * @doctodo 00267 */ 00268 reference 00269 operator[](difference_type __n) const 00270 { return *(*this + __n); } 00271 }; 00272 00273 //@{ 00274 /** 00275 * @param x A %reverse_iterator. 00276 * @param y A %reverse_iterator. 00277 * @return A simple bool. 00278 * 00279 * Reverse iterators forward many operations to their underlying base() 00280 * iterators. Others are implemented in terms of one another. 00281 * 00282 */ 00283 template<typename _Iterator> 00284 inline bool 00285 operator==(const reverse_iterator<_Iterator>& __x, 00286 const reverse_iterator<_Iterator>& __y) 00287 { return __x.base() == __y.base(); } 00288 00289 template<typename _Iterator> 00290 inline bool 00291 operator<(const reverse_iterator<_Iterator>& __x, 00292 const reverse_iterator<_Iterator>& __y) 00293 { return __y.base() < __x.base(); } 00294 00295 template<typename _Iterator> 00296 inline bool 00297 operator!=(const reverse_iterator<_Iterator>& __x, 00298 const reverse_iterator<_Iterator>& __y) 00299 { return !(__x == __y); } 00300 00301 template<typename _Iterator> 00302 inline bool 00303 operator>(const reverse_iterator<_Iterator>& __x, 00304 const reverse_iterator<_Iterator>& __y) 00305 { return __y < __x; } 00306 00307 template<typename _Iterator> 00308 inline bool 00309 operator<=(const reverse_iterator<_Iterator>& __x, 00310 const reverse_iterator<_Iterator>& __y) 00311 { return !(__y < __x); } 00312 00313 template<typename _Iterator> 00314 inline bool 00315 operator>=(const reverse_iterator<_Iterator>& __x, 00316 const reverse_iterator<_Iterator>& __y) 00317 { return !(__x < __y); } 00318 00319 template<typename _Iterator> 00320 inline typename reverse_iterator<_Iterator>::difference_type 00321 operator-(const reverse_iterator<_Iterator>& __x, 00322 const reverse_iterator<_Iterator>& __y) 00323 { return __y.base() - __x.base(); } 00324 00325 template<typename _Iterator> 00326 inline reverse_iterator<_Iterator> 00327 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 00328 const reverse_iterator<_Iterator>& __x) 00329 { return reverse_iterator<_Iterator>(__x.base() - __n); } 00330 00331 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00332 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 00333 template<typename _IteratorL, typename _IteratorR> 00334 inline bool 00335 operator==(const reverse_iterator<_IteratorL>& __x, 00336 const reverse_iterator<_IteratorR>& __y) 00337 { return __x.base() == __y.base(); } 00338 00339 template<typename _IteratorL, typename _IteratorR> 00340 inline bool 00341 operator<(const reverse_iterator<_IteratorL>& __x, 00342 const reverse_iterator<_IteratorR>& __y) 00343 { return __y.base() < __x.base(); } 00344 00345 template<typename _IteratorL, typename _IteratorR> 00346 inline bool 00347 operator!=(const reverse_iterator<_IteratorL>& __x, 00348 const reverse_iterator<_IteratorR>& __y) 00349 { return !(__x == __y); } 00350 00351 template<typename _IteratorL, typename _IteratorR> 00352 inline bool 00353 operator>(const reverse_iterator<_IteratorL>& __x, 00354 const reverse_iterator<_IteratorR>& __y) 00355 { return __y < __x; } 00356 00357 template<typename _IteratorL, typename _IteratorR> 00358 inline bool 00359 operator<=(const reverse_iterator<_IteratorL>& __x, 00360 const reverse_iterator<_IteratorR>& __y) 00361 { return !(__y < __x); } 00362 00363 template<typename _IteratorL, typename _IteratorR> 00364 inline bool 00365 operator>=(const reverse_iterator<_IteratorL>& __x, 00366 const reverse_iterator<_IteratorR>& __y) 00367 { return !(__x < __y); } 00368 00369 template<typename _IteratorL, typename _IteratorR> 00370 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00371 // DR 685. 00372 inline auto 00373 operator-(const reverse_iterator<_IteratorL>& __x, 00374 const reverse_iterator<_IteratorR>& __y) 00375 -> decltype(__y.base() - __x.base()) 00376 #else 00377 inline typename reverse_iterator<_IteratorL>::difference_type 00378 operator-(const reverse_iterator<_IteratorL>& __x, 00379 const reverse_iterator<_IteratorR>& __y) 00380 #endif 00381 { return __y.base() - __x.base(); } 00382 //@} 00383 00384 // 24.4.2.2.1 back_insert_iterator 00385 /** 00386 * @brief Turns assignment into insertion. 00387 * 00388 * These are output iterators, constructed from a container-of-T. 00389 * Assigning a T to the iterator appends it to the container using 00390 * push_back. 00391 * 00392 * Tip: Using the back_inserter function to create these iterators can 00393 * save typing. 00394 */ 00395 template<typename _Container> 00396 class back_insert_iterator 00397 : public iterator<output_iterator_tag, void, void, void, void> 00398 { 00399 protected: 00400 _Container* container; 00401 00402 public: 00403 /// A nested typedef for the type of whatever container you used. 00404 typedef _Container container_type; 00405 00406 /// The only way to create this %iterator is with a container. 00407 explicit 00408 back_insert_iterator(_Container& __x) : container(&__x) { } 00409 00410 /** 00411 * @param value An instance of whatever type 00412 * container_type::const_reference is; presumably a 00413 * reference-to-const T for container<T>. 00414 * @return This %iterator, for chained operations. 00415 * 00416 * This kind of %iterator doesn't really have a @a position in the 00417 * container (you can think of the position as being permanently at 00418 * the end, if you like). Assigning a value to the %iterator will 00419 * always append the value to the end of the container. 00420 */ 00421 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00422 back_insert_iterator& 00423 operator=(typename _Container::const_reference __value) 00424 { 00425 container->push_back(__value); 00426 return *this; 00427 } 00428 #else 00429 back_insert_iterator& 00430 operator=(const typename _Container::value_type& __value) 00431 { 00432 container->push_back(__value); 00433 return *this; 00434 } 00435 00436 back_insert_iterator& 00437 operator=(typename _Container::value_type&& __value) 00438 { 00439 container->push_back(std::move(__value)); 00440 return *this; 00441 } 00442 #endif 00443 00444 /// Simply returns *this. 00445 back_insert_iterator& 00446 operator*() 00447 { return *this; } 00448 00449 /// Simply returns *this. (This %iterator does not @a move.) 00450 back_insert_iterator& 00451 operator++() 00452 { return *this; } 00453 00454 /// Simply returns *this. (This %iterator does not @a move.) 00455 back_insert_iterator 00456 operator++(int) 00457 { return *this; } 00458 }; 00459 00460 /** 00461 * @param x A container of arbitrary type. 00462 * @return An instance of back_insert_iterator working on @p x. 00463 * 00464 * This wrapper function helps in creating back_insert_iterator instances. 00465 * Typing the name of the %iterator requires knowing the precise full 00466 * type of the container, which can be tedious and impedes generic 00467 * programming. Using this function lets you take advantage of automatic 00468 * template parameter deduction, making the compiler match the correct 00469 * types for you. 00470 */ 00471 template<typename _Container> 00472 inline back_insert_iterator<_Container> 00473 back_inserter(_Container& __x) 00474 { return back_insert_iterator<_Container>(__x); } 00475 00476 /** 00477 * @brief Turns assignment into insertion. 00478 * 00479 * These are output iterators, constructed from a container-of-T. 00480 * Assigning a T to the iterator prepends it to the container using 00481 * push_front. 00482 * 00483 * Tip: Using the front_inserter function to create these iterators can 00484 * save typing. 00485 */ 00486 template<typename _Container> 00487 class front_insert_iterator 00488 : public iterator<output_iterator_tag, void, void, void, void> 00489 { 00490 protected: 00491 _Container* container; 00492 00493 public: 00494 /// A nested typedef for the type of whatever container you used. 00495 typedef _Container container_type; 00496 00497 /// The only way to create this %iterator is with a container. 00498 explicit front_insert_iterator(_Container& __x) : container(&__x) { } 00499 00500 /** 00501 * @param value An instance of whatever type 00502 * container_type::const_reference is; presumably a 00503 * reference-to-const T for container<T>. 00504 * @return This %iterator, for chained operations. 00505 * 00506 * This kind of %iterator doesn't really have a @a position in the 00507 * container (you can think of the position as being permanently at 00508 * the front, if you like). Assigning a value to the %iterator will 00509 * always prepend the value to the front of the container. 00510 */ 00511 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00512 front_insert_iterator& 00513 operator=(typename _Container::const_reference __value) 00514 { 00515 container->push_front(__value); 00516 return *this; 00517 } 00518 #else 00519 front_insert_iterator& 00520 operator=(const typename _Container::value_type& __value) 00521 { 00522 container->push_front(__value); 00523 return *this; 00524 } 00525 00526 front_insert_iterator& 00527 operator=(typename _Container::value_type&& __value) 00528 { 00529 container->push_front(std::move(__value)); 00530 return *this; 00531 } 00532 #endif 00533 00534 /// Simply returns *this. 00535 front_insert_iterator& 00536 operator*() 00537 { return *this; } 00538 00539 /// Simply returns *this. (This %iterator does not @a move.) 00540 front_insert_iterator& 00541 operator++() 00542 { return *this; } 00543 00544 /// Simply returns *this. (This %iterator does not @a move.) 00545 front_insert_iterator 00546 operator++(int) 00547 { return *this; } 00548 }; 00549 00550 /** 00551 * @param x A container of arbitrary type. 00552 * @return An instance of front_insert_iterator working on @p x. 00553 * 00554 * This wrapper function helps in creating front_insert_iterator instances. 00555 * Typing the name of the %iterator requires knowing the precise full 00556 * type of the container, which can be tedious and impedes generic 00557 * programming. Using this function lets you take advantage of automatic 00558 * template parameter deduction, making the compiler match the correct 00559 * types for you. 00560 */ 00561 template<typename _Container> 00562 inline front_insert_iterator<_Container> 00563 front_inserter(_Container& __x) 00564 { return front_insert_iterator<_Container>(__x); } 00565 00566 /** 00567 * @brief Turns assignment into insertion. 00568 * 00569 * These are output iterators, constructed from a container-of-T. 00570 * Assigning a T to the iterator inserts it in the container at the 00571 * %iterator's position, rather than overwriting the value at that 00572 * position. 00573 * 00574 * (Sequences will actually insert a @e copy of the value before the 00575 * %iterator's position.) 00576 * 00577 * Tip: Using the inserter function to create these iterators can 00578 * save typing. 00579 */ 00580 template<typename _Container> 00581 class insert_iterator 00582 : public iterator<output_iterator_tag, void, void, void, void> 00583 { 00584 protected: 00585 _Container* container; 00586 typename _Container::iterator iter; 00587 00588 public: 00589 /// A nested typedef for the type of whatever container you used. 00590 typedef _Container container_type; 00591 00592 /** 00593 * The only way to create this %iterator is with a container and an 00594 * initial position (a normal %iterator into the container). 00595 */ 00596 insert_iterator(_Container& __x, typename _Container::iterator __i) 00597 : container(&__x), iter(__i) {} 00598 00599 /** 00600 * @param value An instance of whatever type 00601 * container_type::const_reference is; presumably a 00602 * reference-to-const T for container<T>. 00603 * @return This %iterator, for chained operations. 00604 * 00605 * This kind of %iterator maintains its own position in the 00606 * container. Assigning a value to the %iterator will insert the 00607 * value into the container at the place before the %iterator. 00608 * 00609 * The position is maintained such that subsequent assignments will 00610 * insert values immediately after one another. For example, 00611 * @code 00612 * // vector v contains A and Z 00613 * 00614 * insert_iterator i (v, ++v.begin()); 00615 * i = 1; 00616 * i = 2; 00617 * i = 3; 00618 * 00619 * // vector v contains A, 1, 2, 3, and Z 00620 * @endcode 00621 */ 00622 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00623 insert_iterator& 00624 operator=(typename _Container::const_reference __value) 00625 { 00626 iter = container->insert(iter, __value); 00627 ++iter; 00628 return *this; 00629 } 00630 #else 00631 insert_iterator& 00632 operator=(const typename _Container::value_type& __value) 00633 { 00634 iter = container->insert(iter, __value); 00635 ++iter; 00636 return *this; 00637 } 00638 00639 insert_iterator& 00640 operator=(typename _Container::value_type&& __value) 00641 { 00642 iter = container->insert(iter, std::move(__value)); 00643 ++iter; 00644 return *this; 00645 } 00646 #endif 00647 00648 /// Simply returns *this. 00649 insert_iterator& 00650 operator*() 00651 { return *this; } 00652 00653 /// Simply returns *this. (This %iterator does not @a move.) 00654 insert_iterator& 00655 operator++() 00656 { return *this; } 00657 00658 /// Simply returns *this. (This %iterator does not @a move.) 00659 insert_iterator& 00660 operator++(int) 00661 { return *this; } 00662 }; 00663 00664 /** 00665 * @param x A container of arbitrary type. 00666 * @return An instance of insert_iterator working on @p x. 00667 * 00668 * This wrapper function helps in creating insert_iterator instances. 00669 * Typing the name of the %iterator requires knowing the precise full 00670 * type of the container, which can be tedious and impedes generic 00671 * programming. Using this function lets you take advantage of automatic 00672 * template parameter deduction, making the compiler match the correct 00673 * types for you. 00674 */ 00675 template<typename _Container, typename _Iterator> 00676 inline insert_iterator<_Container> 00677 inserter(_Container& __x, _Iterator __i) 00678 { 00679 return insert_iterator<_Container>(__x, 00680 typename _Container::iterator(__i)); 00681 } 00682 00683 // @} group iterators 00684 00685 _GLIBCXX_END_NAMESPACE_VERSION 00686 } // namespace 00687 00688 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00689 { 00690 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00691 00692 // This iterator adapter is @a normal in the sense that it does not 00693 // change the semantics of any of the operators of its iterator 00694 // parameter. Its primary purpose is to convert an iterator that is 00695 // not a class, e.g. a pointer, into an iterator that is a class. 00696 // The _Container parameter exists solely so that different containers 00697 // using this template can instantiate different types, even if the 00698 // _Iterator parameter is the same. 00699 using std::iterator_traits; 00700 using std::iterator; 00701 template<typename _Iterator, typename _Container> 00702 class __normal_iterator 00703 { 00704 protected: 00705 _Iterator _M_current; 00706 00707 typedef iterator_traits<_Iterator> __traits_type; 00708 00709 public: 00710 typedef _Iterator iterator_type; 00711 typedef typename __traits_type::iterator_category iterator_category; 00712 typedef typename __traits_type::value_type value_type; 00713 typedef typename __traits_type::difference_type difference_type; 00714 typedef typename __traits_type::reference reference; 00715 typedef typename __traits_type::pointer pointer; 00716 00717 _GLIBCXX_CONSTEXPR __normal_iterator() : _M_current(_Iterator()) { } 00718 00719 explicit 00720 __normal_iterator(const _Iterator& __i) : _M_current(__i) { } 00721 00722 // Allow iterator to const_iterator conversion 00723 template<typename _Iter> 00724 __normal_iterator(const __normal_iterator<_Iter, 00725 typename __enable_if< 00726 (std::__are_same<_Iter, typename _Container::pointer>::__value), 00727 _Container>::__type>& __i) 00728 : _M_current(__i.base()) { } 00729 00730 // Forward iterator requirements 00731 reference 00732 operator*() const 00733 { return *_M_current; } 00734 00735 pointer 00736 operator->() const 00737 { return _M_current; } 00738 00739 __normal_iterator& 00740 operator++() 00741 { 00742 ++_M_current; 00743 return *this; 00744 } 00745 00746 __normal_iterator 00747 operator++(int) 00748 { return __normal_iterator(_M_current++); } 00749 00750 // Bidirectional iterator requirements 00751 __normal_iterator& 00752 operator--() 00753 { 00754 --_M_current; 00755 return *this; 00756 } 00757 00758 __normal_iterator 00759 operator--(int) 00760 { return __normal_iterator(_M_current--); } 00761 00762 // Random access iterator requirements 00763 reference 00764 operator[](const difference_type& __n) const 00765 { return _M_current[__n]; } 00766 00767 __normal_iterator& 00768 operator+=(const difference_type& __n) 00769 { _M_current += __n; return *this; } 00770 00771 __normal_iterator 00772 operator+(const difference_type& __n) const 00773 { return __normal_iterator(_M_current + __n); } 00774 00775 __normal_iterator& 00776 operator-=(const difference_type& __n) 00777 { _M_current -= __n; return *this; } 00778 00779 __normal_iterator 00780 operator-(const difference_type& __n) const 00781 { return __normal_iterator(_M_current - __n); } 00782 00783 const _Iterator& 00784 base() const 00785 { return _M_current; } 00786 }; 00787 00788 // Note: In what follows, the left- and right-hand-side iterators are 00789 // allowed to vary in types (conceptually in cv-qualification) so that 00790 // comparison between cv-qualified and non-cv-qualified iterators be 00791 // valid. However, the greedy and unfriendly operators in std::rel_ops 00792 // will make overload resolution ambiguous (when in scope) if we don't 00793 // provide overloads whose operands are of the same type. Can someone 00794 // remind me what generic programming is about? -- Gaby 00795 00796 // Forward iterator requirements 00797 template<typename _IteratorL, typename _IteratorR, typename _Container> 00798 inline bool 00799 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 00800 const __normal_iterator<_IteratorR, _Container>& __rhs) 00801 { return __lhs.base() == __rhs.base(); } 00802 00803 template<typename _Iterator, typename _Container> 00804 inline bool 00805 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 00806 const __normal_iterator<_Iterator, _Container>& __rhs) 00807 { return __lhs.base() == __rhs.base(); } 00808 00809 template<typename _IteratorL, typename _IteratorR, typename _Container> 00810 inline bool 00811 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00812 const __normal_iterator<_IteratorR, _Container>& __rhs) 00813 { return __lhs.base() != __rhs.base(); } 00814 00815 template<typename _Iterator, typename _Container> 00816 inline bool 00817 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 00818 const __normal_iterator<_Iterator, _Container>& __rhs) 00819 { return __lhs.base() != __rhs.base(); } 00820 00821 // Random access iterator requirements 00822 template<typename _IteratorL, typename _IteratorR, typename _Container> 00823 inline bool 00824 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 00825 const __normal_iterator<_IteratorR, _Container>& __rhs) 00826 { return __lhs.base() < __rhs.base(); } 00827 00828 template<typename _Iterator, typename _Container> 00829 inline bool 00830 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 00831 const __normal_iterator<_Iterator, _Container>& __rhs) 00832 { return __lhs.base() < __rhs.base(); } 00833 00834 template<typename _IteratorL, typename _IteratorR, typename _Container> 00835 inline bool 00836 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 00837 const __normal_iterator<_IteratorR, _Container>& __rhs) 00838 { return __lhs.base() > __rhs.base(); } 00839 00840 template<typename _Iterator, typename _Container> 00841 inline bool 00842 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 00843 const __normal_iterator<_Iterator, _Container>& __rhs) 00844 { return __lhs.base() > __rhs.base(); } 00845 00846 template<typename _IteratorL, typename _IteratorR, typename _Container> 00847 inline bool 00848 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00849 const __normal_iterator<_IteratorR, _Container>& __rhs) 00850 { return __lhs.base() <= __rhs.base(); } 00851 00852 template<typename _Iterator, typename _Container> 00853 inline bool 00854 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 00855 const __normal_iterator<_Iterator, _Container>& __rhs) 00856 { return __lhs.base() <= __rhs.base(); } 00857 00858 template<typename _IteratorL, typename _IteratorR, typename _Container> 00859 inline bool 00860 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00861 const __normal_iterator<_IteratorR, _Container>& __rhs) 00862 { return __lhs.base() >= __rhs.base(); } 00863 00864 template<typename _Iterator, typename _Container> 00865 inline bool 00866 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 00867 const __normal_iterator<_Iterator, _Container>& __rhs) 00868 { return __lhs.base() >= __rhs.base(); } 00869 00870 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00871 // According to the resolution of DR179 not only the various comparison 00872 // operators but also operator- must accept mixed iterator/const_iterator 00873 // parameters. 00874 template<typename _IteratorL, typename _IteratorR, typename _Container> 00875 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00876 // DR 685. 00877 inline auto 00878 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00879 const __normal_iterator<_IteratorR, _Container>& __rhs) 00880 -> decltype(__lhs.base() - __rhs.base()) 00881 #else 00882 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 00883 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00884 const __normal_iterator<_IteratorR, _Container>& __rhs) 00885 #endif 00886 { return __lhs.base() - __rhs.base(); } 00887 00888 template<typename _Iterator, typename _Container> 00889 inline typename __normal_iterator<_Iterator, _Container>::difference_type 00890 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 00891 const __normal_iterator<_Iterator, _Container>& __rhs) 00892 { return __lhs.base() - __rhs.base(); } 00893 00894 template<typename _Iterator, typename _Container> 00895 inline __normal_iterator<_Iterator, _Container> 00896 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 00897 __n, const __normal_iterator<_Iterator, _Container>& __i) 00898 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 00899 00900 _GLIBCXX_END_NAMESPACE_VERSION 00901 } // namespace 00902 00903 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00904 00905 namespace std _GLIBCXX_VISIBILITY(default) 00906 { 00907 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00908 00909 /** 00910 * @addtogroup iterators 00911 * @{ 00912 */ 00913 00914 // 24.4.3 Move iterators 00915 /** 00916 * Class template move_iterator is an iterator adapter with the same 00917 * behavior as the underlying iterator except that its dereference 00918 * operator implicitly converts the value returned by the underlying 00919 * iterator's dereference operator to an rvalue reference. Some 00920 * generic algorithms can be called with move iterators to replace 00921 * copying with moving. 00922 */ 00923 template<typename _Iterator> 00924 class move_iterator 00925 { 00926 protected: 00927 _Iterator _M_current; 00928 00929 typedef iterator_traits<_Iterator> __traits_type; 00930 00931 public: 00932 typedef _Iterator iterator_type; 00933 typedef typename __traits_type::iterator_category iterator_category; 00934 typedef typename __traits_type::value_type value_type; 00935 typedef typename __traits_type::difference_type difference_type; 00936 // NB: DR 680. 00937 typedef _Iterator pointer; 00938 typedef value_type&& reference; 00939 00940 move_iterator() 00941 : _M_current() { } 00942 00943 explicit 00944 move_iterator(iterator_type __i) 00945 : _M_current(__i) { } 00946 00947 template<typename _Iter> 00948 move_iterator(const move_iterator<_Iter>& __i) 00949 : _M_current(__i.base()) { } 00950 00951 iterator_type 00952 base() const 00953 { return _M_current; } 00954 00955 reference 00956 operator*() const 00957 { return std::move(*_M_current); } 00958 00959 pointer 00960 operator->() const 00961 { return _M_current; } 00962 00963 move_iterator& 00964 operator++() 00965 { 00966 ++_M_current; 00967 return *this; 00968 } 00969 00970 move_iterator 00971 operator++(int) 00972 { 00973 move_iterator __tmp = *this; 00974 ++_M_current; 00975 return __tmp; 00976 } 00977 00978 move_iterator& 00979 operator--() 00980 { 00981 --_M_current; 00982 return *this; 00983 } 00984 00985 move_iterator 00986 operator--(int) 00987 { 00988 move_iterator __tmp = *this; 00989 --_M_current; 00990 return __tmp; 00991 } 00992 00993 move_iterator 00994 operator+(difference_type __n) const 00995 { return move_iterator(_M_current + __n); } 00996 00997 move_iterator& 00998 operator+=(difference_type __n) 00999 { 01000 _M_current += __n; 01001 return *this; 01002 } 01003 01004 move_iterator 01005 operator-(difference_type __n) const 01006 { return move_iterator(_M_current - __n); } 01007 01008 move_iterator& 01009 operator-=(difference_type __n) 01010 { 01011 _M_current -= __n; 01012 return *this; 01013 } 01014 01015 reference 01016 operator[](difference_type __n) const 01017 { return std::move(_M_current[__n]); } 01018 }; 01019 01020 // Note: See __normal_iterator operators note from Gaby to understand 01021 // why there are always 2 versions for most of the move_iterator 01022 // operators. 01023 template<typename _IteratorL, typename _IteratorR> 01024 inline bool 01025 operator==(const move_iterator<_IteratorL>& __x, 01026 const move_iterator<_IteratorR>& __y) 01027 { return __x.base() == __y.base(); } 01028 01029 template<typename _Iterator> 01030 inline bool 01031 operator==(const move_iterator<_Iterator>& __x, 01032 const move_iterator<_Iterator>& __y) 01033 { return __x.base() == __y.base(); } 01034 01035 template<typename _IteratorL, typename _IteratorR> 01036 inline bool 01037 operator!=(const move_iterator<_IteratorL>& __x, 01038 const move_iterator<_IteratorR>& __y) 01039 { return !(__x == __y); } 01040 01041 template<typename _Iterator> 01042 inline bool 01043 operator!=(const move_iterator<_Iterator>& __x, 01044 const move_iterator<_Iterator>& __y) 01045 { return !(__x == __y); } 01046 01047 template<typename _IteratorL, typename _IteratorR> 01048 inline bool 01049 operator<(const move_iterator<_IteratorL>& __x, 01050 const move_iterator<_IteratorR>& __y) 01051 { return __x.base() < __y.base(); } 01052 01053 template<typename _Iterator> 01054 inline bool 01055 operator<(const move_iterator<_Iterator>& __x, 01056 const move_iterator<_Iterator>& __y) 01057 { return __x.base() < __y.base(); } 01058 01059 template<typename _IteratorL, typename _IteratorR> 01060 inline bool 01061 operator<=(const move_iterator<_IteratorL>& __x, 01062 const move_iterator<_IteratorR>& __y) 01063 { return !(__y < __x); } 01064 01065 template<typename _Iterator> 01066 inline bool 01067 operator<=(const move_iterator<_Iterator>& __x, 01068 const move_iterator<_Iterator>& __y) 01069 { return !(__y < __x); } 01070 01071 template<typename _IteratorL, typename _IteratorR> 01072 inline bool 01073 operator>(const move_iterator<_IteratorL>& __x, 01074 const move_iterator<_IteratorR>& __y) 01075 { return __y < __x; } 01076 01077 template<typename _Iterator> 01078 inline bool 01079 operator>(const move_iterator<_Iterator>& __x, 01080 const move_iterator<_Iterator>& __y) 01081 { return __y < __x; } 01082 01083 template<typename _IteratorL, typename _IteratorR> 01084 inline bool 01085 operator>=(const move_iterator<_IteratorL>& __x, 01086 const move_iterator<_IteratorR>& __y) 01087 { return !(__x < __y); } 01088 01089 template<typename _Iterator> 01090 inline bool 01091 operator>=(const move_iterator<_Iterator>& __x, 01092 const move_iterator<_Iterator>& __y) 01093 { return !(__x < __y); } 01094 01095 // DR 685. 01096 template<typename _IteratorL, typename _IteratorR> 01097 inline auto 01098 operator-(const move_iterator<_IteratorL>& __x, 01099 const move_iterator<_IteratorR>& __y) 01100 -> decltype(__x.base() - __y.base()) 01101 { return __x.base() - __y.base(); } 01102 01103 template<typename _Iterator> 01104 inline auto 01105 operator-(const move_iterator<_Iterator>& __x, 01106 const move_iterator<_Iterator>& __y) 01107 -> decltype(__x.base() - __y.base()) 01108 { return __x.base() - __y.base(); } 01109 01110 template<typename _Iterator> 01111 inline move_iterator<_Iterator> 01112 operator+(typename move_iterator<_Iterator>::difference_type __n, 01113 const move_iterator<_Iterator>& __x) 01114 { return __x + __n; } 01115 01116 template<typename _Iterator> 01117 inline move_iterator<_Iterator> 01118 make_move_iterator(const _Iterator& __i) 01119 { return move_iterator<_Iterator>(__i); } 01120 01121 // @} group iterators 01122 01123 _GLIBCXX_END_NAMESPACE_VERSION 01124 } // namespace 01125 01126 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 01127 #else 01128 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 01129 #endif // __GXX_EXPERIMENTAL_CXX0X__ 01130 01131 #endif