libstdc++
|
00001 // Iterators -*- C++ -*- 00002 00003 // Copyright (C) 2001-2016 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 inline typename reverse_iterator<_Iterator>::difference_type 00328 operator-(const reverse_iterator<_Iterator>& __x, 00329 const reverse_iterator<_Iterator>& __y) 00330 { return __y.base() - __x.base(); } 00331 00332 template<typename _Iterator> 00333 inline reverse_iterator<_Iterator> 00334 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 00335 const reverse_iterator<_Iterator>& __x) 00336 { return reverse_iterator<_Iterator>(__x.base() - __n); } 00337 00338 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00339 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 00340 template<typename _IteratorL, typename _IteratorR> 00341 inline bool 00342 operator==(const reverse_iterator<_IteratorL>& __x, 00343 const reverse_iterator<_IteratorR>& __y) 00344 { return __x.base() == __y.base(); } 00345 00346 template<typename _IteratorL, typename _IteratorR> 00347 inline bool 00348 operator<(const reverse_iterator<_IteratorL>& __x, 00349 const reverse_iterator<_IteratorR>& __y) 00350 { return __y.base() < __x.base(); } 00351 00352 template<typename _IteratorL, typename _IteratorR> 00353 inline bool 00354 operator!=(const reverse_iterator<_IteratorL>& __x, 00355 const reverse_iterator<_IteratorR>& __y) 00356 { return !(__x == __y); } 00357 00358 template<typename _IteratorL, typename _IteratorR> 00359 inline bool 00360 operator>(const reverse_iterator<_IteratorL>& __x, 00361 const reverse_iterator<_IteratorR>& __y) 00362 { return __y < __x; } 00363 00364 template<typename _IteratorL, typename _IteratorR> 00365 inline bool 00366 operator<=(const reverse_iterator<_IteratorL>& __x, 00367 const reverse_iterator<_IteratorR>& __y) 00368 { return !(__y < __x); } 00369 00370 template<typename _IteratorL, typename _IteratorR> 00371 inline bool 00372 operator>=(const reverse_iterator<_IteratorL>& __x, 00373 const reverse_iterator<_IteratorR>& __y) 00374 { return !(__x < __y); } 00375 00376 template<typename _IteratorL, typename _IteratorR> 00377 #if __cplusplus >= 201103L 00378 // DR 685. 00379 inline auto 00380 operator-(const reverse_iterator<_IteratorL>& __x, 00381 const reverse_iterator<_IteratorR>& __y) 00382 -> decltype(__y.base() - __x.base()) 00383 #else 00384 inline typename reverse_iterator<_IteratorL>::difference_type 00385 operator-(const reverse_iterator<_IteratorL>& __x, 00386 const reverse_iterator<_IteratorR>& __y) 00387 #endif 00388 { return __y.base() - __x.base(); } 00389 //@} 00390 00391 #if __cplusplus >= 201103L 00392 // Same as C++14 make_reverse_iterator but used in C++03 mode too. 00393 template<typename _Iterator> 00394 inline reverse_iterator<_Iterator> 00395 __make_reverse_iterator(_Iterator __i) 00396 { return reverse_iterator<_Iterator>(__i); } 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 #endif 00410 00411 #if __cplusplus >= 201103L 00412 template<typename _Iterator> 00413 auto 00414 __niter_base(reverse_iterator<_Iterator> __it) 00415 -> decltype(__make_reverse_iterator(__niter_base(__it.base()))) 00416 { return __make_reverse_iterator(__niter_base(__it.base())); } 00417 00418 template<typename _Iterator> 00419 struct __is_move_iterator<reverse_iterator<_Iterator> > 00420 : __is_move_iterator<_Iterator> 00421 { }; 00422 00423 template<typename _Iterator> 00424 auto 00425 __miter_base(reverse_iterator<_Iterator> __it) 00426 -> decltype(__make_reverse_iterator(__miter_base(__it.base()))) 00427 { return __make_reverse_iterator(__miter_base(__it.base())); } 00428 #endif 00429 00430 // 24.4.2.2.1 back_insert_iterator 00431 /** 00432 * @brief Turns assignment into insertion. 00433 * 00434 * These are output iterators, constructed from a container-of-T. 00435 * Assigning a T to the iterator appends it to the container using 00436 * push_back. 00437 * 00438 * Tip: Using the back_inserter function to create these iterators can 00439 * save typing. 00440 */ 00441 template<typename _Container> 00442 class back_insert_iterator 00443 : public iterator<output_iterator_tag, void, void, void, void> 00444 { 00445 protected: 00446 _Container* container; 00447 00448 public: 00449 /// A nested typedef for the type of whatever container you used. 00450 typedef _Container container_type; 00451 00452 /// The only way to create this %iterator is with a container. 00453 explicit 00454 back_insert_iterator(_Container& __x) 00455 : container(std::__addressof(__x)) { } 00456 00457 /** 00458 * @param __value An instance of whatever type 00459 * container_type::const_reference is; presumably a 00460 * reference-to-const T for container<T>. 00461 * @return This %iterator, for chained operations. 00462 * 00463 * This kind of %iterator doesn't really have a @a position in the 00464 * container (you can think of the position as being permanently at 00465 * the end, if you like). Assigning a value to the %iterator will 00466 * always append the value to the end of the container. 00467 */ 00468 #if __cplusplus < 201103L 00469 back_insert_iterator& 00470 operator=(typename _Container::const_reference __value) 00471 { 00472 container->push_back(__value); 00473 return *this; 00474 } 00475 #else 00476 back_insert_iterator& 00477 operator=(const typename _Container::value_type& __value) 00478 { 00479 container->push_back(__value); 00480 return *this; 00481 } 00482 00483 back_insert_iterator& 00484 operator=(typename _Container::value_type&& __value) 00485 { 00486 container->push_back(std::move(__value)); 00487 return *this; 00488 } 00489 #endif 00490 00491 /// Simply returns *this. 00492 back_insert_iterator& 00493 operator*() 00494 { return *this; } 00495 00496 /// Simply returns *this. (This %iterator does not @a move.) 00497 back_insert_iterator& 00498 operator++() 00499 { return *this; } 00500 00501 /// Simply returns *this. (This %iterator does not @a move.) 00502 back_insert_iterator 00503 operator++(int) 00504 { return *this; } 00505 }; 00506 00507 /** 00508 * @param __x A container of arbitrary type. 00509 * @return An instance of back_insert_iterator working on @p __x. 00510 * 00511 * This wrapper function helps in creating back_insert_iterator instances. 00512 * Typing the name of the %iterator requires knowing the precise full 00513 * type of the container, which can be tedious and impedes generic 00514 * programming. Using this function lets you take advantage of automatic 00515 * template parameter deduction, making the compiler match the correct 00516 * types for you. 00517 */ 00518 template<typename _Container> 00519 inline back_insert_iterator<_Container> 00520 back_inserter(_Container& __x) 00521 { return back_insert_iterator<_Container>(__x); } 00522 00523 /** 00524 * @brief Turns assignment into insertion. 00525 * 00526 * These are output iterators, constructed from a container-of-T. 00527 * Assigning a T to the iterator prepends it to the container using 00528 * push_front. 00529 * 00530 * Tip: Using the front_inserter function to create these iterators can 00531 * save typing. 00532 */ 00533 template<typename _Container> 00534 class front_insert_iterator 00535 : public iterator<output_iterator_tag, void, void, void, void> 00536 { 00537 protected: 00538 _Container* container; 00539 00540 public: 00541 /// A nested typedef for the type of whatever container you used. 00542 typedef _Container container_type; 00543 00544 /// The only way to create this %iterator is with a container. 00545 explicit front_insert_iterator(_Container& __x) 00546 : container(std::__addressof(__x)) { } 00547 00548 /** 00549 * @param __value An instance of whatever type 00550 * container_type::const_reference is; presumably a 00551 * reference-to-const T for container<T>. 00552 * @return This %iterator, for chained operations. 00553 * 00554 * This kind of %iterator doesn't really have a @a position in the 00555 * container (you can think of the position as being permanently at 00556 * the front, if you like). Assigning a value to the %iterator will 00557 * always prepend the value to the front of the container. 00558 */ 00559 #if __cplusplus < 201103L 00560 front_insert_iterator& 00561 operator=(typename _Container::const_reference __value) 00562 { 00563 container->push_front(__value); 00564 return *this; 00565 } 00566 #else 00567 front_insert_iterator& 00568 operator=(const typename _Container::value_type& __value) 00569 { 00570 container->push_front(__value); 00571 return *this; 00572 } 00573 00574 front_insert_iterator& 00575 operator=(typename _Container::value_type&& __value) 00576 { 00577 container->push_front(std::move(__value)); 00578 return *this; 00579 } 00580 #endif 00581 00582 /// Simply returns *this. 00583 front_insert_iterator& 00584 operator*() 00585 { return *this; } 00586 00587 /// Simply returns *this. (This %iterator does not @a move.) 00588 front_insert_iterator& 00589 operator++() 00590 { return *this; } 00591 00592 /// Simply returns *this. (This %iterator does not @a move.) 00593 front_insert_iterator 00594 operator++(int) 00595 { return *this; } 00596 }; 00597 00598 /** 00599 * @param __x A container of arbitrary type. 00600 * @return An instance of front_insert_iterator working on @p x. 00601 * 00602 * This wrapper function helps in creating front_insert_iterator instances. 00603 * Typing the name of the %iterator requires knowing the precise full 00604 * type of the container, which can be tedious and impedes generic 00605 * programming. Using this function lets you take advantage of automatic 00606 * template parameter deduction, making the compiler match the correct 00607 * types for you. 00608 */ 00609 template<typename _Container> 00610 inline front_insert_iterator<_Container> 00611 front_inserter(_Container& __x) 00612 { return front_insert_iterator<_Container>(__x); } 00613 00614 /** 00615 * @brief Turns assignment into insertion. 00616 * 00617 * These are output iterators, constructed from a container-of-T. 00618 * Assigning a T to the iterator inserts it in the container at the 00619 * %iterator's position, rather than overwriting the value at that 00620 * position. 00621 * 00622 * (Sequences will actually insert a @e copy of the value before the 00623 * %iterator's position.) 00624 * 00625 * Tip: Using the inserter function to create these iterators can 00626 * save typing. 00627 */ 00628 template<typename _Container> 00629 class insert_iterator 00630 : public iterator<output_iterator_tag, void, void, void, void> 00631 { 00632 protected: 00633 _Container* container; 00634 typename _Container::iterator iter; 00635 00636 public: 00637 /// A nested typedef for the type of whatever container you used. 00638 typedef _Container container_type; 00639 00640 /** 00641 * The only way to create this %iterator is with a container and an 00642 * initial position (a normal %iterator into the container). 00643 */ 00644 insert_iterator(_Container& __x, typename _Container::iterator __i) 00645 : container(std::__addressof(__x)), iter(__i) {} 00646 00647 /** 00648 * @param __value An instance of whatever type 00649 * container_type::const_reference is; presumably a 00650 * reference-to-const T for container<T>. 00651 * @return This %iterator, for chained operations. 00652 * 00653 * This kind of %iterator maintains its own position in the 00654 * container. Assigning a value to the %iterator will insert the 00655 * value into the container at the place before the %iterator. 00656 * 00657 * The position is maintained such that subsequent assignments will 00658 * insert values immediately after one another. For example, 00659 * @code 00660 * // vector v contains A and Z 00661 * 00662 * insert_iterator i (v, ++v.begin()); 00663 * i = 1; 00664 * i = 2; 00665 * i = 3; 00666 * 00667 * // vector v contains A, 1, 2, 3, and Z 00668 * @endcode 00669 */ 00670 #if __cplusplus < 201103L 00671 insert_iterator& 00672 operator=(typename _Container::const_reference __value) 00673 { 00674 iter = container->insert(iter, __value); 00675 ++iter; 00676 return *this; 00677 } 00678 #else 00679 insert_iterator& 00680 operator=(const typename _Container::value_type& __value) 00681 { 00682 iter = container->insert(iter, __value); 00683 ++iter; 00684 return *this; 00685 } 00686 00687 insert_iterator& 00688 operator=(typename _Container::value_type&& __value) 00689 { 00690 iter = container->insert(iter, std::move(__value)); 00691 ++iter; 00692 return *this; 00693 } 00694 #endif 00695 00696 /// Simply returns *this. 00697 insert_iterator& 00698 operator*() 00699 { return *this; } 00700 00701 /// Simply returns *this. (This %iterator does not @a move.) 00702 insert_iterator& 00703 operator++() 00704 { return *this; } 00705 00706 /// Simply returns *this. (This %iterator does not @a move.) 00707 insert_iterator& 00708 operator++(int) 00709 { return *this; } 00710 }; 00711 00712 /** 00713 * @param __x A container of arbitrary type. 00714 * @return An instance of insert_iterator working on @p __x. 00715 * 00716 * This wrapper function helps in creating insert_iterator instances. 00717 * Typing the name of the %iterator requires knowing the precise full 00718 * type of the container, which can be tedious and impedes generic 00719 * programming. Using this function lets you take advantage of automatic 00720 * template parameter deduction, making the compiler match the correct 00721 * types for you. 00722 */ 00723 template<typename _Container, typename _Iterator> 00724 inline insert_iterator<_Container> 00725 inserter(_Container& __x, _Iterator __i) 00726 { 00727 return insert_iterator<_Container>(__x, 00728 typename _Container::iterator(__i)); 00729 } 00730 00731 // @} group iterators 00732 00733 _GLIBCXX_END_NAMESPACE_VERSION 00734 } // namespace 00735 00736 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00737 { 00738 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00739 00740 // This iterator adapter is @a normal in the sense that it does not 00741 // change the semantics of any of the operators of its iterator 00742 // parameter. Its primary purpose is to convert an iterator that is 00743 // not a class, e.g. a pointer, into an iterator that is a class. 00744 // The _Container parameter exists solely so that different containers 00745 // using this template can instantiate different types, even if the 00746 // _Iterator parameter is the same. 00747 using std::iterator_traits; 00748 using std::iterator; 00749 template<typename _Iterator, typename _Container> 00750 class __normal_iterator 00751 { 00752 protected: 00753 _Iterator _M_current; 00754 00755 typedef iterator_traits<_Iterator> __traits_type; 00756 00757 public: 00758 typedef _Iterator iterator_type; 00759 typedef typename __traits_type::iterator_category iterator_category; 00760 typedef typename __traits_type::value_type value_type; 00761 typedef typename __traits_type::difference_type difference_type; 00762 typedef typename __traits_type::reference reference; 00763 typedef typename __traits_type::pointer pointer; 00764 00765 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 00766 : _M_current(_Iterator()) { } 00767 00768 explicit 00769 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 00770 : _M_current(__i) { } 00771 00772 // Allow iterator to const_iterator conversion 00773 template<typename _Iter> 00774 __normal_iterator(const __normal_iterator<_Iter, 00775 typename __enable_if< 00776 (std::__are_same<_Iter, typename _Container::pointer>::__value), 00777 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT 00778 : _M_current(__i.base()) { } 00779 00780 // Forward iterator requirements 00781 reference 00782 operator*() const _GLIBCXX_NOEXCEPT 00783 { return *_M_current; } 00784 00785 pointer 00786 operator->() const _GLIBCXX_NOEXCEPT 00787 { return _M_current; } 00788 00789 __normal_iterator& 00790 operator++() _GLIBCXX_NOEXCEPT 00791 { 00792 ++_M_current; 00793 return *this; 00794 } 00795 00796 __normal_iterator 00797 operator++(int) _GLIBCXX_NOEXCEPT 00798 { return __normal_iterator(_M_current++); } 00799 00800 // Bidirectional iterator requirements 00801 __normal_iterator& 00802 operator--() _GLIBCXX_NOEXCEPT 00803 { 00804 --_M_current; 00805 return *this; 00806 } 00807 00808 __normal_iterator 00809 operator--(int) _GLIBCXX_NOEXCEPT 00810 { return __normal_iterator(_M_current--); } 00811 00812 // Random access iterator requirements 00813 reference 00814 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 00815 { return _M_current[__n]; } 00816 00817 __normal_iterator& 00818 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 00819 { _M_current += __n; return *this; } 00820 00821 __normal_iterator 00822 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 00823 { return __normal_iterator(_M_current + __n); } 00824 00825 __normal_iterator& 00826 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 00827 { _M_current -= __n; return *this; } 00828 00829 __normal_iterator 00830 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 00831 { return __normal_iterator(_M_current - __n); } 00832 00833 const _Iterator& 00834 base() const _GLIBCXX_NOEXCEPT 00835 { return _M_current; } 00836 }; 00837 00838 // Note: In what follows, the left- and right-hand-side iterators are 00839 // allowed to vary in types (conceptually in cv-qualification) so that 00840 // comparison between cv-qualified and non-cv-qualified iterators be 00841 // valid. However, the greedy and unfriendly operators in std::rel_ops 00842 // will make overload resolution ambiguous (when in scope) if we don't 00843 // provide overloads whose operands are of the same type. Can someone 00844 // remind me what generic programming is about? -- Gaby 00845 00846 // Forward iterator requirements 00847 template<typename _IteratorL, typename _IteratorR, typename _Container> 00848 inline bool 00849 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 00850 const __normal_iterator<_IteratorR, _Container>& __rhs) 00851 _GLIBCXX_NOEXCEPT 00852 { return __lhs.base() == __rhs.base(); } 00853 00854 template<typename _Iterator, typename _Container> 00855 inline bool 00856 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 00857 const __normal_iterator<_Iterator, _Container>& __rhs) 00858 _GLIBCXX_NOEXCEPT 00859 { return __lhs.base() == __rhs.base(); } 00860 00861 template<typename _IteratorL, typename _IteratorR, typename _Container> 00862 inline bool 00863 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00864 const __normal_iterator<_IteratorR, _Container>& __rhs) 00865 _GLIBCXX_NOEXCEPT 00866 { return __lhs.base() != __rhs.base(); } 00867 00868 template<typename _Iterator, typename _Container> 00869 inline bool 00870 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 00871 const __normal_iterator<_Iterator, _Container>& __rhs) 00872 _GLIBCXX_NOEXCEPT 00873 { return __lhs.base() != __rhs.base(); } 00874 00875 // Random access iterator requirements 00876 template<typename _IteratorL, typename _IteratorR, typename _Container> 00877 inline bool 00878 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 00879 const __normal_iterator<_IteratorR, _Container>& __rhs) 00880 _GLIBCXX_NOEXCEPT 00881 { return __lhs.base() < __rhs.base(); } 00882 00883 template<typename _Iterator, typename _Container> 00884 inline bool 00885 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 00886 const __normal_iterator<_Iterator, _Container>& __rhs) 00887 _GLIBCXX_NOEXCEPT 00888 { return __lhs.base() < __rhs.base(); } 00889 00890 template<typename _IteratorL, typename _IteratorR, typename _Container> 00891 inline bool 00892 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 00893 const __normal_iterator<_IteratorR, _Container>& __rhs) 00894 _GLIBCXX_NOEXCEPT 00895 { return __lhs.base() > __rhs.base(); } 00896 00897 template<typename _Iterator, typename _Container> 00898 inline bool 00899 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 00900 const __normal_iterator<_Iterator, _Container>& __rhs) 00901 _GLIBCXX_NOEXCEPT 00902 { return __lhs.base() > __rhs.base(); } 00903 00904 template<typename _IteratorL, typename _IteratorR, typename _Container> 00905 inline bool 00906 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00907 const __normal_iterator<_IteratorR, _Container>& __rhs) 00908 _GLIBCXX_NOEXCEPT 00909 { return __lhs.base() <= __rhs.base(); } 00910 00911 template<typename _Iterator, typename _Container> 00912 inline bool 00913 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 00914 const __normal_iterator<_Iterator, _Container>& __rhs) 00915 _GLIBCXX_NOEXCEPT 00916 { return __lhs.base() <= __rhs.base(); } 00917 00918 template<typename _IteratorL, typename _IteratorR, typename _Container> 00919 inline bool 00920 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00921 const __normal_iterator<_IteratorR, _Container>& __rhs) 00922 _GLIBCXX_NOEXCEPT 00923 { return __lhs.base() >= __rhs.base(); } 00924 00925 template<typename _Iterator, typename _Container> 00926 inline bool 00927 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 00928 const __normal_iterator<_Iterator, _Container>& __rhs) 00929 _GLIBCXX_NOEXCEPT 00930 { return __lhs.base() >= __rhs.base(); } 00931 00932 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00933 // According to the resolution of DR179 not only the various comparison 00934 // operators but also operator- must accept mixed iterator/const_iterator 00935 // parameters. 00936 template<typename _IteratorL, typename _IteratorR, typename _Container> 00937 #if __cplusplus >= 201103L 00938 // DR 685. 00939 inline auto 00940 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00941 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 00942 -> decltype(__lhs.base() - __rhs.base()) 00943 #else 00944 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 00945 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00946 const __normal_iterator<_IteratorR, _Container>& __rhs) 00947 #endif 00948 { return __lhs.base() - __rhs.base(); } 00949 00950 template<typename _Iterator, typename _Container> 00951 inline typename __normal_iterator<_Iterator, _Container>::difference_type 00952 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 00953 const __normal_iterator<_Iterator, _Container>& __rhs) 00954 _GLIBCXX_NOEXCEPT 00955 { return __lhs.base() - __rhs.base(); } 00956 00957 template<typename _Iterator, typename _Container> 00958 inline __normal_iterator<_Iterator, _Container> 00959 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 00960 __n, const __normal_iterator<_Iterator, _Container>& __i) 00961 _GLIBCXX_NOEXCEPT 00962 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 00963 00964 _GLIBCXX_END_NAMESPACE_VERSION 00965 } // namespace 00966 00967 namespace std _GLIBCXX_VISIBILITY(default) 00968 { 00969 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00970 00971 template<typename _Iterator, typename _Container> 00972 _Iterator 00973 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it) 00974 { return __it.base(); } 00975 00976 _GLIBCXX_END_NAMESPACE_VERSION 00977 } // namespace 00978 00979 #if __cplusplus >= 201103L 00980 00981 namespace std _GLIBCXX_VISIBILITY(default) 00982 { 00983 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00984 00985 /** 00986 * @addtogroup iterators 00987 * @{ 00988 */ 00989 00990 // 24.4.3 Move iterators 00991 /** 00992 * Class template move_iterator is an iterator adapter with the same 00993 * behavior as the underlying iterator except that its dereference 00994 * operator implicitly converts the value returned by the underlying 00995 * iterator's dereference operator to an rvalue reference. Some 00996 * generic algorithms can be called with move iterators to replace 00997 * copying with moving. 00998 */ 00999 template<typename _Iterator> 01000 class move_iterator 01001 { 01002 protected: 01003 _Iterator _M_current; 01004 01005 typedef iterator_traits<_Iterator> __traits_type; 01006 typedef typename __traits_type::reference __base_ref; 01007 01008 public: 01009 typedef _Iterator iterator_type; 01010 typedef typename __traits_type::iterator_category iterator_category; 01011 typedef typename __traits_type::value_type value_type; 01012 typedef typename __traits_type::difference_type difference_type; 01013 // NB: DR 680. 01014 typedef _Iterator pointer; 01015 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01016 // 2106. move_iterator wrapping iterators returning prvalues 01017 typedef typename conditional<is_reference<__base_ref>::value, 01018 typename remove_reference<__base_ref>::type&&, 01019 __base_ref>::type reference; 01020 01021 move_iterator() 01022 : _M_current() { } 01023 01024 explicit 01025 move_iterator(iterator_type __i) 01026 : _M_current(__i) { } 01027 01028 template<typename _Iter> 01029 move_iterator(const move_iterator<_Iter>& __i) 01030 : _M_current(__i.base()) { } 01031 01032 iterator_type 01033 base() const 01034 { return _M_current; } 01035 01036 reference 01037 operator*() const 01038 { return static_cast<reference>(*_M_current); } 01039 01040 pointer 01041 operator->() const 01042 { return _M_current; } 01043 01044 move_iterator& 01045 operator++() 01046 { 01047 ++_M_current; 01048 return *this; 01049 } 01050 01051 move_iterator 01052 operator++(int) 01053 { 01054 move_iterator __tmp = *this; 01055 ++_M_current; 01056 return __tmp; 01057 } 01058 01059 move_iterator& 01060 operator--() 01061 { 01062 --_M_current; 01063 return *this; 01064 } 01065 01066 move_iterator 01067 operator--(int) 01068 { 01069 move_iterator __tmp = *this; 01070 --_M_current; 01071 return __tmp; 01072 } 01073 01074 move_iterator 01075 operator+(difference_type __n) const 01076 { return move_iterator(_M_current + __n); } 01077 01078 move_iterator& 01079 operator+=(difference_type __n) 01080 { 01081 _M_current += __n; 01082 return *this; 01083 } 01084 01085 move_iterator 01086 operator-(difference_type __n) const 01087 { return move_iterator(_M_current - __n); } 01088 01089 move_iterator& 01090 operator-=(difference_type __n) 01091 { 01092 _M_current -= __n; 01093 return *this; 01094 } 01095 01096 reference 01097 operator[](difference_type __n) const 01098 { return std::move(_M_current[__n]); } 01099 }; 01100 01101 // Note: See __normal_iterator operators note from Gaby to understand 01102 // why there are always 2 versions for most of the move_iterator 01103 // operators. 01104 template<typename _IteratorL, typename _IteratorR> 01105 inline bool 01106 operator==(const move_iterator<_IteratorL>& __x, 01107 const move_iterator<_IteratorR>& __y) 01108 { return __x.base() == __y.base(); } 01109 01110 template<typename _Iterator> 01111 inline bool 01112 operator==(const move_iterator<_Iterator>& __x, 01113 const move_iterator<_Iterator>& __y) 01114 { return __x.base() == __y.base(); } 01115 01116 template<typename _IteratorL, typename _IteratorR> 01117 inline bool 01118 operator!=(const move_iterator<_IteratorL>& __x, 01119 const move_iterator<_IteratorR>& __y) 01120 { return !(__x == __y); } 01121 01122 template<typename _Iterator> 01123 inline bool 01124 operator!=(const move_iterator<_Iterator>& __x, 01125 const move_iterator<_Iterator>& __y) 01126 { return !(__x == __y); } 01127 01128 template<typename _IteratorL, typename _IteratorR> 01129 inline bool 01130 operator<(const move_iterator<_IteratorL>& __x, 01131 const move_iterator<_IteratorR>& __y) 01132 { return __x.base() < __y.base(); } 01133 01134 template<typename _Iterator> 01135 inline bool 01136 operator<(const move_iterator<_Iterator>& __x, 01137 const move_iterator<_Iterator>& __y) 01138 { return __x.base() < __y.base(); } 01139 01140 template<typename _IteratorL, typename _IteratorR> 01141 inline bool 01142 operator<=(const move_iterator<_IteratorL>& __x, 01143 const move_iterator<_IteratorR>& __y) 01144 { return !(__y < __x); } 01145 01146 template<typename _Iterator> 01147 inline bool 01148 operator<=(const move_iterator<_Iterator>& __x, 01149 const move_iterator<_Iterator>& __y) 01150 { return !(__y < __x); } 01151 01152 template<typename _IteratorL, typename _IteratorR> 01153 inline bool 01154 operator>(const move_iterator<_IteratorL>& __x, 01155 const move_iterator<_IteratorR>& __y) 01156 { return __y < __x; } 01157 01158 template<typename _Iterator> 01159 inline bool 01160 operator>(const move_iterator<_Iterator>& __x, 01161 const move_iterator<_Iterator>& __y) 01162 { return __y < __x; } 01163 01164 template<typename _IteratorL, typename _IteratorR> 01165 inline bool 01166 operator>=(const move_iterator<_IteratorL>& __x, 01167 const move_iterator<_IteratorR>& __y) 01168 { return !(__x < __y); } 01169 01170 template<typename _Iterator> 01171 inline bool 01172 operator>=(const move_iterator<_Iterator>& __x, 01173 const move_iterator<_Iterator>& __y) 01174 { return !(__x < __y); } 01175 01176 // DR 685. 01177 template<typename _IteratorL, typename _IteratorR> 01178 inline auto 01179 operator-(const move_iterator<_IteratorL>& __x, 01180 const move_iterator<_IteratorR>& __y) 01181 -> decltype(__x.base() - __y.base()) 01182 { return __x.base() - __y.base(); } 01183 01184 template<typename _Iterator> 01185 inline auto 01186 operator-(const move_iterator<_Iterator>& __x, 01187 const move_iterator<_Iterator>& __y) 01188 -> decltype(__x.base() - __y.base()) 01189 { return __x.base() - __y.base(); } 01190 01191 template<typename _Iterator> 01192 inline move_iterator<_Iterator> 01193 operator+(typename move_iterator<_Iterator>::difference_type __n, 01194 const move_iterator<_Iterator>& __x) 01195 { return __x + __n; } 01196 01197 template<typename _Iterator> 01198 inline move_iterator<_Iterator> 01199 make_move_iterator(_Iterator __i) 01200 { return move_iterator<_Iterator>(__i); } 01201 01202 template<typename _Iterator, typename _ReturnType 01203 = typename conditional<__move_if_noexcept_cond 01204 <typename iterator_traits<_Iterator>::value_type>::value, 01205 _Iterator, move_iterator<_Iterator>>::type> 01206 inline _ReturnType 01207 __make_move_if_noexcept_iterator(_Iterator __i) 01208 { return _ReturnType(__i); } 01209 01210 // Overload for pointers that matches std::move_if_noexcept more closely, 01211 // returning a constant iterator when we don't want to move. 01212 template<typename _Tp, typename _ReturnType 01213 = typename conditional<__move_if_noexcept_cond<_Tp>::value, 01214 const _Tp*, move_iterator<_Tp*>>::type> 01215 inline _ReturnType 01216 __make_move_if_noexcept_iterator(_Tp* __i) 01217 { return _ReturnType(__i); } 01218 01219 // @} group iterators 01220 01221 template<typename _Iterator> 01222 auto 01223 __niter_base(move_iterator<_Iterator> __it) 01224 -> decltype(make_move_iterator(__niter_base(__it.base()))) 01225 { return make_move_iterator(__niter_base(__it.base())); } 01226 01227 template<typename _Iterator> 01228 struct __is_move_iterator<move_iterator<_Iterator> > 01229 { 01230 enum { __value = 1 }; 01231 typedef __true_type __type; 01232 }; 01233 01234 template<typename _Iterator> 01235 auto 01236 __miter_base(move_iterator<_Iterator> __it) 01237 -> decltype(__miter_base(__it.base())) 01238 { return __miter_base(__it.base()); } 01239 01240 _GLIBCXX_END_NAMESPACE_VERSION 01241 } // namespace 01242 01243 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 01244 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 01245 std::__make_move_if_noexcept_iterator(_Iter) 01246 #else 01247 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 01248 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 01249 #endif // C++11 01250 01251 #ifdef _GLIBCXX_DEBUG 01252 # include <debug/stl_iterator.h> 01253 #endif 01254 01255 #endif