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