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