libstdc++
|
00001 // Iterators -*- C++ -*- 00002 00003 // Copyright (C) 2001-2015 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 #include <bits/ptr_traits.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 value-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 if the 00137 * underlying %iterator can be converted to the type of @c current. 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 A reference to the value at @c --current 00152 * 00153 * This requires that @c --current is dereferenceable. 00154 * 00155 * @warning This implementation requires that for an iterator of the 00156 * underlying iterator type, @c x, a reference obtained by 00157 * @c *x remains valid after @c x has been modified or 00158 * destroyed. This is a bug: http://gcc.gnu.org/PR51823 00159 */ 00160 reference 00161 operator*() const 00162 { 00163 _Iterator __tmp = current; 00164 return *--__tmp; 00165 } 00166 00167 /** 00168 * @return A pointer to the value at @c --current 00169 * 00170 * This requires that @c --current is dereferenceable. 00171 */ 00172 pointer 00173 operator->() const 00174 { return &(operator*()); } 00175 00176 /** 00177 * @return @c *this 00178 * 00179 * Decrements the underlying iterator. 00180 */ 00181 reverse_iterator& 00182 operator++() 00183 { 00184 --current; 00185 return *this; 00186 } 00187 00188 /** 00189 * @return The original value of @c *this 00190 * 00191 * Decrements the underlying iterator. 00192 */ 00193 reverse_iterator 00194 operator++(int) 00195 { 00196 reverse_iterator __tmp = *this; 00197 --current; 00198 return __tmp; 00199 } 00200 00201 /** 00202 * @return @c *this 00203 * 00204 * Increments the underlying iterator. 00205 */ 00206 reverse_iterator& 00207 operator--() 00208 { 00209 ++current; 00210 return *this; 00211 } 00212 00213 /** 00214 * @return A reverse_iterator with the previous value of @c *this 00215 * 00216 * Increments the underlying iterator. 00217 */ 00218 reverse_iterator 00219 operator--(int) 00220 { 00221 reverse_iterator __tmp = *this; 00222 ++current; 00223 return __tmp; 00224 } 00225 00226 /** 00227 * @return A reverse_iterator that refers to @c current - @a __n 00228 * 00229 * The underlying iterator must be a Random Access Iterator. 00230 */ 00231 reverse_iterator 00232 operator+(difference_type __n) const 00233 { return reverse_iterator(current - __n); } 00234 00235 /** 00236 * @return *this 00237 * 00238 * Moves the underlying iterator backwards @a __n steps. 00239 * The underlying iterator must be a Random Access Iterator. 00240 */ 00241 reverse_iterator& 00242 operator+=(difference_type __n) 00243 { 00244 current -= __n; 00245 return *this; 00246 } 00247 00248 /** 00249 * @return A reverse_iterator that refers to @c current - @a __n 00250 * 00251 * The underlying iterator must be a Random Access Iterator. 00252 */ 00253 reverse_iterator 00254 operator-(difference_type __n) const 00255 { return reverse_iterator(current + __n); } 00256 00257 /** 00258 * @return *this 00259 * 00260 * Moves the underlying iterator forwards @a __n steps. 00261 * The underlying iterator must be a Random Access Iterator. 00262 */ 00263 reverse_iterator& 00264 operator-=(difference_type __n) 00265 { 00266 current += __n; 00267 return *this; 00268 } 00269 00270 /** 00271 * @return The value at @c current - @a __n - 1 00272 * 00273 * The underlying iterator must be a Random Access Iterator. 00274 */ 00275 reference 00276 operator[](difference_type __n) const 00277 { return *(*this + __n); } 00278 }; 00279 00280 //@{ 00281 /** 00282 * @param __x A %reverse_iterator. 00283 * @param __y A %reverse_iterator. 00284 * @return A simple bool. 00285 * 00286 * Reverse iterators forward many operations to their underlying base() 00287 * iterators. Others are implemented in terms of one another. 00288 * 00289 */ 00290 template<typename _Iterator> 00291 inline bool 00292 operator==(const reverse_iterator<_Iterator>& __x, 00293 const reverse_iterator<_Iterator>& __y) 00294 { return __x.base() == __y.base(); } 00295 00296 template<typename _Iterator> 00297 inline bool 00298 operator<(const reverse_iterator<_Iterator>& __x, 00299 const reverse_iterator<_Iterator>& __y) 00300 { return __y.base() < __x.base(); } 00301 00302 template<typename _Iterator> 00303 inline bool 00304 operator!=(const reverse_iterator<_Iterator>& __x, 00305 const reverse_iterator<_Iterator>& __y) 00306 { return !(__x == __y); } 00307 00308 template<typename _Iterator> 00309 inline bool 00310 operator>(const reverse_iterator<_Iterator>& __x, 00311 const reverse_iterator<_Iterator>& __y) 00312 { return __y < __x; } 00313 00314 template<typename _Iterator> 00315 inline bool 00316 operator<=(const reverse_iterator<_Iterator>& __x, 00317 const reverse_iterator<_Iterator>& __y) 00318 { return !(__y < __x); } 00319 00320 template<typename _Iterator> 00321 inline bool 00322 operator>=(const reverse_iterator<_Iterator>& __x, 00323 const reverse_iterator<_Iterator>& __y) 00324 { return !(__x < __y); } 00325 00326 template<typename _Iterator> 00327 #if __cplusplus < 201103L 00328 inline typename reverse_iterator<_Iterator>::difference_type 00329 operator-(const reverse_iterator<_Iterator>& __x, 00330 const reverse_iterator<_Iterator>& __y) 00331 #else 00332 inline auto 00333 operator-(const reverse_iterator<_Iterator>& __x, 00334 const reverse_iterator<_Iterator>& __y) 00335 -> decltype(__x.base() - __y.base()) 00336 #endif 00337 { return __y.base() - __x.base(); } 00338 00339 template<typename _Iterator> 00340 inline reverse_iterator<_Iterator> 00341 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 00342 const reverse_iterator<_Iterator>& __x) 00343 { return reverse_iterator<_Iterator>(__x.base() - __n); } 00344 00345 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00346 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 00347 template<typename _IteratorL, typename _IteratorR> 00348 inline bool 00349 operator==(const reverse_iterator<_IteratorL>& __x, 00350 const reverse_iterator<_IteratorR>& __y) 00351 { return __x.base() == __y.base(); } 00352 00353 template<typename _IteratorL, typename _IteratorR> 00354 inline bool 00355 operator<(const reverse_iterator<_IteratorL>& __x, 00356 const reverse_iterator<_IteratorR>& __y) 00357 { return __y.base() < __x.base(); } 00358 00359 template<typename _IteratorL, typename _IteratorR> 00360 inline bool 00361 operator!=(const reverse_iterator<_IteratorL>& __x, 00362 const reverse_iterator<_IteratorR>& __y) 00363 { return !(__x == __y); } 00364 00365 template<typename _IteratorL, typename _IteratorR> 00366 inline bool 00367 operator>(const reverse_iterator<_IteratorL>& __x, 00368 const reverse_iterator<_IteratorR>& __y) 00369 { return __y < __x; } 00370 00371 template<typename _IteratorL, typename _IteratorR> 00372 inline bool 00373 operator<=(const reverse_iterator<_IteratorL>& __x, 00374 const reverse_iterator<_IteratorR>& __y) 00375 { return !(__y < __x); } 00376 00377 template<typename _IteratorL, typename _IteratorR> 00378 inline bool 00379 operator>=(const reverse_iterator<_IteratorL>& __x, 00380 const reverse_iterator<_IteratorR>& __y) 00381 { return !(__x < __y); } 00382 00383 template<typename _IteratorL, typename _IteratorR> 00384 #if __cplusplus >= 201103L 00385 // DR 685. 00386 inline auto 00387 operator-(const reverse_iterator<_IteratorL>& __x, 00388 const reverse_iterator<_IteratorR>& __y) 00389 -> decltype(__y.base() - __x.base()) 00390 #else 00391 inline typename reverse_iterator<_IteratorL>::difference_type 00392 operator-(const reverse_iterator<_IteratorL>& __x, 00393 const reverse_iterator<_IteratorR>& __y) 00394 #endif 00395 { return __y.base() - __x.base(); } 00396 //@} 00397 00398 #if __cplusplus > 201103L 00399 #define __cpp_lib_make_reverse_iterator 201402 00400 00401 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00402 // DR 2285. make_reverse_iterator 00403 /// Generator function for reverse_iterator. 00404 template<typename _Iterator> 00405 inline reverse_iterator<_Iterator> 00406 make_reverse_iterator(_Iterator __i) 00407 { return reverse_iterator<_Iterator>(__i); } 00408 #endif 00409 00410 // 24.4.2.2.1 back_insert_iterator 00411 /** 00412 * @brief Turns assignment into insertion. 00413 * 00414 * These are output iterators, constructed from a container-of-T. 00415 * Assigning a T to the iterator appends it to the container using 00416 * push_back. 00417 * 00418 * Tip: Using the back_inserter function to create these iterators can 00419 * save typing. 00420 */ 00421 template<typename _Container> 00422 class back_insert_iterator 00423 : public iterator<output_iterator_tag, void, void, void, void> 00424 { 00425 protected: 00426 _Container* container; 00427 00428 public: 00429 /// A nested typedef for the type of whatever container you used. 00430 typedef _Container container_type; 00431 00432 /// The only way to create this %iterator is with a container. 00433 explicit 00434 back_insert_iterator(_Container& __x) : container(&__x) { } 00435 00436 /** 00437 * @param __value An instance of whatever type 00438 * container_type::const_reference is; presumably a 00439 * reference-to-const T for container<T>. 00440 * @return This %iterator, for chained operations. 00441 * 00442 * This kind of %iterator doesn't really have a @a position in the 00443 * container (you can think of the position as being permanently at 00444 * the end, if you like). Assigning a value to the %iterator will 00445 * always append the value to the end of the container. 00446 */ 00447 #if __cplusplus < 201103L 00448 back_insert_iterator& 00449 operator=(typename _Container::const_reference __value) 00450 { 00451 container->push_back(__value); 00452 return *this; 00453 } 00454 #else 00455 back_insert_iterator& 00456 operator=(const typename _Container::value_type& __value) 00457 { 00458 container->push_back(__value); 00459 return *this; 00460 } 00461 00462 back_insert_iterator& 00463 operator=(typename _Container::value_type&& __value) 00464 { 00465 container->push_back(std::move(__value)); 00466 return *this; 00467 } 00468 #endif 00469 00470 /// Simply returns *this. 00471 back_insert_iterator& 00472 operator*() 00473 { return *this; } 00474 00475 /// Simply returns *this. (This %iterator does not @a move.) 00476 back_insert_iterator& 00477 operator++() 00478 { return *this; } 00479 00480 /// Simply returns *this. (This %iterator does not @a move.) 00481 back_insert_iterator 00482 operator++(int) 00483 { return *this; } 00484 }; 00485 00486 /** 00487 * @param __x A container of arbitrary type. 00488 * @return An instance of back_insert_iterator working on @p __x. 00489 * 00490 * This wrapper function helps in creating back_insert_iterator instances. 00491 * Typing the name of the %iterator requires knowing the precise full 00492 * type of the container, which can be tedious and impedes generic 00493 * programming. Using this function lets you take advantage of automatic 00494 * template parameter deduction, making the compiler match the correct 00495 * types for you. 00496 */ 00497 template<typename _Container> 00498 inline back_insert_iterator<_Container> 00499 back_inserter(_Container& __x) 00500 { return back_insert_iterator<_Container>(__x); } 00501 00502 /** 00503 * @brief Turns assignment into insertion. 00504 * 00505 * These are output iterators, constructed from a container-of-T. 00506 * Assigning a T to the iterator prepends it to the container using 00507 * push_front. 00508 * 00509 * Tip: Using the front_inserter function to create these iterators can 00510 * save typing. 00511 */ 00512 template<typename _Container> 00513 class front_insert_iterator 00514 : public iterator<output_iterator_tag, void, void, void, void> 00515 { 00516 protected: 00517 _Container* container; 00518 00519 public: 00520 /// A nested typedef for the type of whatever container you used. 00521 typedef _Container container_type; 00522 00523 /// The only way to create this %iterator is with a container. 00524 explicit front_insert_iterator(_Container& __x) : container(&__x) { } 00525 00526 /** 00527 * @param __value An instance of whatever type 00528 * container_type::const_reference is; presumably a 00529 * reference-to-const T for container<T>. 00530 * @return This %iterator, for chained operations. 00531 * 00532 * This kind of %iterator doesn't really have a @a position in the 00533 * container (you can think of the position as being permanently at 00534 * the front, if you like). Assigning a value to the %iterator will 00535 * always prepend the value to the front of the container. 00536 */ 00537 #if __cplusplus < 201103L 00538 front_insert_iterator& 00539 operator=(typename _Container::const_reference __value) 00540 { 00541 container->push_front(__value); 00542 return *this; 00543 } 00544 #else 00545 front_insert_iterator& 00546 operator=(const typename _Container::value_type& __value) 00547 { 00548 container->push_front(__value); 00549 return *this; 00550 } 00551 00552 front_insert_iterator& 00553 operator=(typename _Container::value_type&& __value) 00554 { 00555 container->push_front(std::move(__value)); 00556 return *this; 00557 } 00558 #endif 00559 00560 /// Simply returns *this. 00561 front_insert_iterator& 00562 operator*() 00563 { return *this; } 00564 00565 /// Simply returns *this. (This %iterator does not @a move.) 00566 front_insert_iterator& 00567 operator++() 00568 { return *this; } 00569 00570 /// Simply returns *this. (This %iterator does not @a move.) 00571 front_insert_iterator 00572 operator++(int) 00573 { return *this; } 00574 }; 00575 00576 /** 00577 * @param __x A container of arbitrary type. 00578 * @return An instance of front_insert_iterator working on @p x. 00579 * 00580 * This wrapper function helps in creating front_insert_iterator instances. 00581 * Typing the name of the %iterator requires knowing the precise full 00582 * type of the container, which can be tedious and impedes generic 00583 * programming. Using this function lets you take advantage of automatic 00584 * template parameter deduction, making the compiler match the correct 00585 * types for you. 00586 */ 00587 template<typename _Container> 00588 inline front_insert_iterator<_Container> 00589 front_inserter(_Container& __x) 00590 { return front_insert_iterator<_Container>(__x); } 00591 00592 /** 00593 * @brief Turns assignment into insertion. 00594 * 00595 * These are output iterators, constructed from a container-of-T. 00596 * Assigning a T to the iterator inserts it in the container at the 00597 * %iterator's position, rather than overwriting the value at that 00598 * position. 00599 * 00600 * (Sequences will actually insert a @e copy of the value before the 00601 * %iterator's position.) 00602 * 00603 * Tip: Using the inserter function to create these iterators can 00604 * save typing. 00605 */ 00606 template<typename _Container> 00607 class insert_iterator 00608 : public iterator<output_iterator_tag, void, void, void, void> 00609 { 00610 protected: 00611 _Container* container; 00612 typename _Container::iterator iter; 00613 00614 public: 00615 /// A nested typedef for the type of whatever container you used. 00616 typedef _Container container_type; 00617 00618 /** 00619 * The only way to create this %iterator is with a container and an 00620 * initial position (a normal %iterator into the container). 00621 */ 00622 insert_iterator(_Container& __x, typename _Container::iterator __i) 00623 : container(&__x), iter(__i) {} 00624 00625 /** 00626 * @param __value An instance of whatever type 00627 * container_type::const_reference is; presumably a 00628 * reference-to-const T for container<T>. 00629 * @return This %iterator, for chained operations. 00630 * 00631 * This kind of %iterator maintains its own position in the 00632 * container. Assigning a value to the %iterator will insert the 00633 * value into the container at the place before the %iterator. 00634 * 00635 * The position is maintained such that subsequent assignments will 00636 * insert values immediately after one another. For example, 00637 * @code 00638 * // vector v contains A and Z 00639 * 00640 * insert_iterator i (v, ++v.begin()); 00641 * i = 1; 00642 * i = 2; 00643 * i = 3; 00644 * 00645 * // vector v contains A, 1, 2, 3, and Z 00646 * @endcode 00647 */ 00648 #if __cplusplus < 201103L 00649 insert_iterator& 00650 operator=(typename _Container::const_reference __value) 00651 { 00652 iter = container->insert(iter, __value); 00653 ++iter; 00654 return *this; 00655 } 00656 #else 00657 insert_iterator& 00658 operator=(const typename _Container::value_type& __value) 00659 { 00660 iter = container->insert(iter, __value); 00661 ++iter; 00662 return *this; 00663 } 00664 00665 insert_iterator& 00666 operator=(typename _Container::value_type&& __value) 00667 { 00668 iter = container->insert(iter, std::move(__value)); 00669 ++iter; 00670 return *this; 00671 } 00672 #endif 00673 00674 /// Simply returns *this. 00675 insert_iterator& 00676 operator*() 00677 { return *this; } 00678 00679 /// Simply returns *this. (This %iterator does not @a move.) 00680 insert_iterator& 00681 operator++() 00682 { return *this; } 00683 00684 /// Simply returns *this. (This %iterator does not @a move.) 00685 insert_iterator& 00686 operator++(int) 00687 { return *this; } 00688 }; 00689 00690 /** 00691 * @param __x A container of arbitrary type. 00692 * @return An instance of insert_iterator working on @p __x. 00693 * 00694 * This wrapper function helps in creating insert_iterator instances. 00695 * Typing the name of the %iterator requires knowing the precise full 00696 * type of the container, which can be tedious and impedes generic 00697 * programming. Using this function lets you take advantage of automatic 00698 * template parameter deduction, making the compiler match the correct 00699 * types for you. 00700 */ 00701 template<typename _Container, typename _Iterator> 00702 inline insert_iterator<_Container> 00703 inserter(_Container& __x, _Iterator __i) 00704 { 00705 return insert_iterator<_Container>(__x, 00706 typename _Container::iterator(__i)); 00707 } 00708 00709 // @} group iterators 00710 00711 _GLIBCXX_END_NAMESPACE_VERSION 00712 } // namespace 00713 00714 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00715 { 00716 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00717 00718 // This iterator adapter is @a normal in the sense that it does not 00719 // change the semantics of any of the operators of its iterator 00720 // parameter. Its primary purpose is to convert an iterator that is 00721 // not a class, e.g. a pointer, into an iterator that is a class. 00722 // The _Container parameter exists solely so that different containers 00723 // using this template can instantiate different types, even if the 00724 // _Iterator parameter is the same. 00725 using std::iterator_traits; 00726 using std::iterator; 00727 template<typename _Iterator, typename _Container> 00728 class __normal_iterator 00729 { 00730 protected: 00731 _Iterator _M_current; 00732 00733 typedef iterator_traits<_Iterator> __traits_type; 00734 00735 public: 00736 typedef _Iterator iterator_type; 00737 typedef typename __traits_type::iterator_category iterator_category; 00738 typedef typename __traits_type::value_type value_type; 00739 typedef typename __traits_type::difference_type difference_type; 00740 typedef typename __traits_type::reference reference; 00741 typedef typename __traits_type::pointer pointer; 00742 00743 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 00744 : _M_current(_Iterator()) { } 00745 00746 explicit 00747 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 00748 : _M_current(__i) { } 00749 00750 // Allow iterator to const_iterator conversion 00751 template<typename _Iter> 00752 __normal_iterator(const __normal_iterator<_Iter, 00753 typename __enable_if< 00754 (std::__are_same<_Iter, typename _Container::pointer>::__value), 00755 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT 00756 : _M_current(__i.base()) { } 00757 00758 // Forward iterator requirements 00759 reference 00760 operator*() const _GLIBCXX_NOEXCEPT 00761 { return *_M_current; } 00762 00763 pointer 00764 operator->() const _GLIBCXX_NOEXCEPT 00765 { return _M_current; } 00766 00767 __normal_iterator& 00768 operator++() _GLIBCXX_NOEXCEPT 00769 { 00770 ++_M_current; 00771 return *this; 00772 } 00773 00774 __normal_iterator 00775 operator++(int) _GLIBCXX_NOEXCEPT 00776 { return __normal_iterator(_M_current++); } 00777 00778 // Bidirectional iterator requirements 00779 __normal_iterator& 00780 operator--() _GLIBCXX_NOEXCEPT 00781 { 00782 --_M_current; 00783 return *this; 00784 } 00785 00786 __normal_iterator 00787 operator--(int) _GLIBCXX_NOEXCEPT 00788 { return __normal_iterator(_M_current--); } 00789 00790 // Random access iterator requirements 00791 reference 00792 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 00793 { return _M_current[__n]; } 00794 00795 __normal_iterator& 00796 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 00797 { _M_current += __n; return *this; } 00798 00799 __normal_iterator 00800 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 00801 { return __normal_iterator(_M_current + __n); } 00802 00803 __normal_iterator& 00804 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 00805 { _M_current -= __n; return *this; } 00806 00807 __normal_iterator 00808 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 00809 { return __normal_iterator(_M_current - __n); } 00810 00811 const _Iterator& 00812 base() const _GLIBCXX_NOEXCEPT 00813 { return _M_current; } 00814 }; 00815 00816 // Note: In what follows, the left- and right-hand-side iterators are 00817 // allowed to vary in types (conceptually in cv-qualification) so that 00818 // comparison between cv-qualified and non-cv-qualified iterators be 00819 // valid. However, the greedy and unfriendly operators in std::rel_ops 00820 // will make overload resolution ambiguous (when in scope) if we don't 00821 // provide overloads whose operands are of the same type. Can someone 00822 // remind me what generic programming is about? -- Gaby 00823 00824 // Forward iterator requirements 00825 template<typename _IteratorL, typename _IteratorR, typename _Container> 00826 inline bool 00827 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 00828 const __normal_iterator<_IteratorR, _Container>& __rhs) 00829 _GLIBCXX_NOEXCEPT 00830 { return __lhs.base() == __rhs.base(); } 00831 00832 template<typename _Iterator, typename _Container> 00833 inline bool 00834 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 00835 const __normal_iterator<_Iterator, _Container>& __rhs) 00836 _GLIBCXX_NOEXCEPT 00837 { return __lhs.base() == __rhs.base(); } 00838 00839 template<typename _IteratorL, typename _IteratorR, typename _Container> 00840 inline bool 00841 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00842 const __normal_iterator<_IteratorR, _Container>& __rhs) 00843 _GLIBCXX_NOEXCEPT 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 _GLIBCXX_NOEXCEPT 00851 { return __lhs.base() != __rhs.base(); } 00852 00853 // Random access iterator requirements 00854 template<typename _IteratorL, typename _IteratorR, typename _Container> 00855 inline bool 00856 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 00857 const __normal_iterator<_IteratorR, _Container>& __rhs) 00858 _GLIBCXX_NOEXCEPT 00859 { return __lhs.base() < __rhs.base(); } 00860 00861 template<typename _Iterator, typename _Container> 00862 inline bool 00863 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 00864 const __normal_iterator<_Iterator, _Container>& __rhs) 00865 _GLIBCXX_NOEXCEPT 00866 { return __lhs.base() < __rhs.base(); } 00867 00868 template<typename _IteratorL, typename _IteratorR, typename _Container> 00869 inline bool 00870 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 00871 const __normal_iterator<_IteratorR, _Container>& __rhs) 00872 _GLIBCXX_NOEXCEPT 00873 { return __lhs.base() > __rhs.base(); } 00874 00875 template<typename _Iterator, typename _Container> 00876 inline bool 00877 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 00878 const __normal_iterator<_Iterator, _Container>& __rhs) 00879 _GLIBCXX_NOEXCEPT 00880 { return __lhs.base() > __rhs.base(); } 00881 00882 template<typename _IteratorL, typename _IteratorR, typename _Container> 00883 inline bool 00884 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00885 const __normal_iterator<_IteratorR, _Container>& __rhs) 00886 _GLIBCXX_NOEXCEPT 00887 { return __lhs.base() <= __rhs.base(); } 00888 00889 template<typename _Iterator, typename _Container> 00890 inline bool 00891 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 00892 const __normal_iterator<_Iterator, _Container>& __rhs) 00893 _GLIBCXX_NOEXCEPT 00894 { return __lhs.base() <= __rhs.base(); } 00895 00896 template<typename _IteratorL, typename _IteratorR, typename _Container> 00897 inline bool 00898 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00899 const __normal_iterator<_IteratorR, _Container>& __rhs) 00900 _GLIBCXX_NOEXCEPT 00901 { return __lhs.base() >= __rhs.base(); } 00902 00903 template<typename _Iterator, typename _Container> 00904 inline bool 00905 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 00906 const __normal_iterator<_Iterator, _Container>& __rhs) 00907 _GLIBCXX_NOEXCEPT 00908 { return __lhs.base() >= __rhs.base(); } 00909 00910 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00911 // According to the resolution of DR179 not only the various comparison 00912 // operators but also operator- must accept mixed iterator/const_iterator 00913 // parameters. 00914 template<typename _IteratorL, typename _IteratorR, typename _Container> 00915 #if __cplusplus >= 201103L 00916 // DR 685. 00917 inline auto 00918 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00919 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 00920 -> decltype(__lhs.base() - __rhs.base()) 00921 #else 00922 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 00923 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00924 const __normal_iterator<_IteratorR, _Container>& __rhs) 00925 #endif 00926 { return __lhs.base() - __rhs.base(); } 00927 00928 template<typename _Iterator, typename _Container> 00929 inline typename __normal_iterator<_Iterator, _Container>::difference_type 00930 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 00931 const __normal_iterator<_Iterator, _Container>& __rhs) 00932 _GLIBCXX_NOEXCEPT 00933 { return __lhs.base() - __rhs.base(); } 00934 00935 template<typename _Iterator, typename _Container> 00936 inline __normal_iterator<_Iterator, _Container> 00937 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 00938 __n, const __normal_iterator<_Iterator, _Container>& __i) 00939 _GLIBCXX_NOEXCEPT 00940 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 00941 00942 _GLIBCXX_END_NAMESPACE_VERSION 00943 } // namespace 00944 00945 #if __cplusplus >= 201103L 00946 00947 namespace std _GLIBCXX_VISIBILITY(default) 00948 { 00949 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00950 00951 /** 00952 * @addtogroup iterators 00953 * @{ 00954 */ 00955 00956 // 24.4.3 Move iterators 00957 /** 00958 * Class template move_iterator is an iterator adapter with the same 00959 * behavior as the underlying iterator except that its dereference 00960 * operator implicitly converts the value returned by the underlying 00961 * iterator's dereference operator to an rvalue reference. Some 00962 * generic algorithms can be called with move iterators to replace 00963 * copying with moving. 00964 */ 00965 template<typename _Iterator> 00966 class move_iterator 00967 { 00968 protected: 00969 _Iterator _M_current; 00970 00971 typedef iterator_traits<_Iterator> __traits_type; 00972 typedef typename __traits_type::reference __base_ref; 00973 00974 public: 00975 typedef _Iterator iterator_type; 00976 typedef typename __traits_type::iterator_category iterator_category; 00977 typedef typename __traits_type::value_type value_type; 00978 typedef typename __traits_type::difference_type difference_type; 00979 // NB: DR 680. 00980 typedef _Iterator pointer; 00981 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00982 // 2106. move_iterator wrapping iterators returning prvalues 00983 typedef typename conditional<is_reference<__base_ref>::value, 00984 typename remove_reference<__base_ref>::type&&, 00985 __base_ref>::type reference; 00986 00987 move_iterator() 00988 : _M_current() { } 00989 00990 explicit 00991 move_iterator(iterator_type __i) 00992 : _M_current(__i) { } 00993 00994 template<typename _Iter> 00995 move_iterator(const move_iterator<_Iter>& __i) 00996 : _M_current(__i.base()) { } 00997 00998 iterator_type 00999 base() const 01000 { return _M_current; } 01001 01002 reference 01003 operator*() const 01004 { return static_cast<reference>(*_M_current); } 01005 01006 pointer 01007 operator->() const 01008 { return _M_current; } 01009 01010 move_iterator& 01011 operator++() 01012 { 01013 ++_M_current; 01014 return *this; 01015 } 01016 01017 move_iterator 01018 operator++(int) 01019 { 01020 move_iterator __tmp = *this; 01021 ++_M_current; 01022 return __tmp; 01023 } 01024 01025 move_iterator& 01026 operator--() 01027 { 01028 --_M_current; 01029 return *this; 01030 } 01031 01032 move_iterator 01033 operator--(int) 01034 { 01035 move_iterator __tmp = *this; 01036 --_M_current; 01037 return __tmp; 01038 } 01039 01040 move_iterator 01041 operator+(difference_type __n) const 01042 { return move_iterator(_M_current + __n); } 01043 01044 move_iterator& 01045 operator+=(difference_type __n) 01046 { 01047 _M_current += __n; 01048 return *this; 01049 } 01050 01051 move_iterator 01052 operator-(difference_type __n) const 01053 { return move_iterator(_M_current - __n); } 01054 01055 move_iterator& 01056 operator-=(difference_type __n) 01057 { 01058 _M_current -= __n; 01059 return *this; 01060 } 01061 01062 reference 01063 operator[](difference_type __n) const 01064 { return std::move(_M_current[__n]); } 01065 }; 01066 01067 // Note: See __normal_iterator operators note from Gaby to understand 01068 // why there are always 2 versions for most of the move_iterator 01069 // operators. 01070 template<typename _IteratorL, typename _IteratorR> 01071 inline bool 01072 operator==(const move_iterator<_IteratorL>& __x, 01073 const move_iterator<_IteratorR>& __y) 01074 { return __x.base() == __y.base(); } 01075 01076 template<typename _Iterator> 01077 inline bool 01078 operator==(const move_iterator<_Iterator>& __x, 01079 const move_iterator<_Iterator>& __y) 01080 { return __x.base() == __y.base(); } 01081 01082 template<typename _IteratorL, typename _IteratorR> 01083 inline bool 01084 operator!=(const move_iterator<_IteratorL>& __x, 01085 const move_iterator<_IteratorR>& __y) 01086 { return !(__x == __y); } 01087 01088 template<typename _Iterator> 01089 inline bool 01090 operator!=(const move_iterator<_Iterator>& __x, 01091 const move_iterator<_Iterator>& __y) 01092 { return !(__x == __y); } 01093 01094 template<typename _IteratorL, typename _IteratorR> 01095 inline bool 01096 operator<(const move_iterator<_IteratorL>& __x, 01097 const move_iterator<_IteratorR>& __y) 01098 { return __x.base() < __y.base(); } 01099 01100 template<typename _Iterator> 01101 inline bool 01102 operator<(const move_iterator<_Iterator>& __x, 01103 const move_iterator<_Iterator>& __y) 01104 { return __x.base() < __y.base(); } 01105 01106 template<typename _IteratorL, typename _IteratorR> 01107 inline bool 01108 operator<=(const move_iterator<_IteratorL>& __x, 01109 const move_iterator<_IteratorR>& __y) 01110 { return !(__y < __x); } 01111 01112 template<typename _Iterator> 01113 inline bool 01114 operator<=(const move_iterator<_Iterator>& __x, 01115 const move_iterator<_Iterator>& __y) 01116 { return !(__y < __x); } 01117 01118 template<typename _IteratorL, typename _IteratorR> 01119 inline bool 01120 operator>(const move_iterator<_IteratorL>& __x, 01121 const move_iterator<_IteratorR>& __y) 01122 { return __y < __x; } 01123 01124 template<typename _Iterator> 01125 inline bool 01126 operator>(const move_iterator<_Iterator>& __x, 01127 const move_iterator<_Iterator>& __y) 01128 { return __y < __x; } 01129 01130 template<typename _IteratorL, typename _IteratorR> 01131 inline bool 01132 operator>=(const move_iterator<_IteratorL>& __x, 01133 const move_iterator<_IteratorR>& __y) 01134 { return !(__x < __y); } 01135 01136 template<typename _Iterator> 01137 inline bool 01138 operator>=(const move_iterator<_Iterator>& __x, 01139 const move_iterator<_Iterator>& __y) 01140 { return !(__x < __y); } 01141 01142 // DR 685. 01143 template<typename _IteratorL, typename _IteratorR> 01144 inline auto 01145 operator-(const move_iterator<_IteratorL>& __x, 01146 const move_iterator<_IteratorR>& __y) 01147 -> decltype(__x.base() - __y.base()) 01148 { return __x.base() - __y.base(); } 01149 01150 template<typename _Iterator> 01151 inline auto 01152 operator-(const move_iterator<_Iterator>& __x, 01153 const move_iterator<_Iterator>& __y) 01154 -> decltype(__x.base() - __y.base()) 01155 { return __x.base() - __y.base(); } 01156 01157 template<typename _Iterator> 01158 inline move_iterator<_Iterator> 01159 operator+(typename move_iterator<_Iterator>::difference_type __n, 01160 const move_iterator<_Iterator>& __x) 01161 { return __x + __n; } 01162 01163 template<typename _Iterator> 01164 inline move_iterator<_Iterator> 01165 make_move_iterator(_Iterator __i) 01166 { return move_iterator<_Iterator>(__i); } 01167 01168 template<typename _Iterator, typename _ReturnType 01169 = typename conditional<__move_if_noexcept_cond 01170 <typename iterator_traits<_Iterator>::value_type>::value, 01171 _Iterator, move_iterator<_Iterator>>::type> 01172 inline _ReturnType 01173 __make_move_if_noexcept_iterator(_Iterator __i) 01174 { return _ReturnType(__i); } 01175 01176 // @} group iterators 01177 01178 _GLIBCXX_END_NAMESPACE_VERSION 01179 } // namespace 01180 01181 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 01182 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 01183 std::__make_move_if_noexcept_iterator(_Iter) 01184 #else 01185 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 01186 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 01187 #endif // C++11 01188 01189 #endif