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