libstdc++
|
00001 // Iterators -*- C++ -*- 00002 00003 // Copyright (C) 2001-2018 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 * @param __i An iterator into the container. 00725 * @return An instance of insert_iterator working on @p __x. 00726 * 00727 * This wrapper function helps in creating insert_iterator instances. 00728 * Typing the name of the %iterator requires knowing the precise full 00729 * type of the container, which can be tedious and impedes generic 00730 * programming. Using this function lets you take advantage of automatic 00731 * template parameter deduction, making the compiler match the correct 00732 * types for you. 00733 */ 00734 template<typename _Container, typename _Iterator> 00735 inline insert_iterator<_Container> 00736 inserter(_Container& __x, _Iterator __i) 00737 { 00738 return insert_iterator<_Container>(__x, 00739 typename _Container::iterator(__i)); 00740 } 00741 00742 // @} group iterators 00743 00744 _GLIBCXX_END_NAMESPACE_VERSION 00745 } // namespace 00746 00747 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00748 { 00749 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00750 00751 // This iterator adapter is @a normal in the sense that it does not 00752 // change the semantics of any of the operators of its iterator 00753 // parameter. Its primary purpose is to convert an iterator that is 00754 // not a class, e.g. a pointer, into an iterator that is a class. 00755 // The _Container parameter exists solely so that different containers 00756 // using this template can instantiate different types, even if the 00757 // _Iterator parameter is the same. 00758 using std::iterator_traits; 00759 using std::iterator; 00760 template<typename _Iterator, typename _Container> 00761 class __normal_iterator 00762 { 00763 protected: 00764 _Iterator _M_current; 00765 00766 typedef iterator_traits<_Iterator> __traits_type; 00767 00768 public: 00769 typedef _Iterator iterator_type; 00770 typedef typename __traits_type::iterator_category iterator_category; 00771 typedef typename __traits_type::value_type value_type; 00772 typedef typename __traits_type::difference_type difference_type; 00773 typedef typename __traits_type::reference reference; 00774 typedef typename __traits_type::pointer pointer; 00775 00776 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 00777 : _M_current(_Iterator()) { } 00778 00779 explicit 00780 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 00781 : _M_current(__i) { } 00782 00783 // Allow iterator to const_iterator conversion 00784 template<typename _Iter> 00785 __normal_iterator(const __normal_iterator<_Iter, 00786 typename __enable_if< 00787 (std::__are_same<_Iter, typename _Container::pointer>::__value), 00788 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT 00789 : _M_current(__i.base()) { } 00790 00791 // Forward iterator requirements 00792 reference 00793 operator*() const _GLIBCXX_NOEXCEPT 00794 { return *_M_current; } 00795 00796 pointer 00797 operator->() const _GLIBCXX_NOEXCEPT 00798 { return _M_current; } 00799 00800 __normal_iterator& 00801 operator++() _GLIBCXX_NOEXCEPT 00802 { 00803 ++_M_current; 00804 return *this; 00805 } 00806 00807 __normal_iterator 00808 operator++(int) _GLIBCXX_NOEXCEPT 00809 { return __normal_iterator(_M_current++); } 00810 00811 // Bidirectional iterator requirements 00812 __normal_iterator& 00813 operator--() _GLIBCXX_NOEXCEPT 00814 { 00815 --_M_current; 00816 return *this; 00817 } 00818 00819 __normal_iterator 00820 operator--(int) _GLIBCXX_NOEXCEPT 00821 { return __normal_iterator(_M_current--); } 00822 00823 // Random access iterator requirements 00824 reference 00825 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 00826 { return _M_current[__n]; } 00827 00828 __normal_iterator& 00829 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 00830 { _M_current += __n; return *this; } 00831 00832 __normal_iterator 00833 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 00834 { return __normal_iterator(_M_current + __n); } 00835 00836 __normal_iterator& 00837 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 00838 { _M_current -= __n; return *this; } 00839 00840 __normal_iterator 00841 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 00842 { return __normal_iterator(_M_current - __n); } 00843 00844 const _Iterator& 00845 base() const _GLIBCXX_NOEXCEPT 00846 { return _M_current; } 00847 }; 00848 00849 // Note: In what follows, the left- and right-hand-side iterators are 00850 // allowed to vary in types (conceptually in cv-qualification) so that 00851 // comparison between cv-qualified and non-cv-qualified iterators be 00852 // valid. However, the greedy and unfriendly operators in std::rel_ops 00853 // will make overload resolution ambiguous (when in scope) if we don't 00854 // provide overloads whose operands are of the same type. Can someone 00855 // remind me what generic programming is about? -- Gaby 00856 00857 // Forward iterator requirements 00858 template<typename _IteratorL, typename _IteratorR, typename _Container> 00859 inline bool 00860 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 00861 const __normal_iterator<_IteratorR, _Container>& __rhs) 00862 _GLIBCXX_NOEXCEPT 00863 { return __lhs.base() == __rhs.base(); } 00864 00865 template<typename _Iterator, typename _Container> 00866 inline bool 00867 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 00868 const __normal_iterator<_Iterator, _Container>& __rhs) 00869 _GLIBCXX_NOEXCEPT 00870 { return __lhs.base() == __rhs.base(); } 00871 00872 template<typename _IteratorL, typename _IteratorR, typename _Container> 00873 inline bool 00874 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00875 const __normal_iterator<_IteratorR, _Container>& __rhs) 00876 _GLIBCXX_NOEXCEPT 00877 { return __lhs.base() != __rhs.base(); } 00878 00879 template<typename _Iterator, typename _Container> 00880 inline bool 00881 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 00882 const __normal_iterator<_Iterator, _Container>& __rhs) 00883 _GLIBCXX_NOEXCEPT 00884 { return __lhs.base() != __rhs.base(); } 00885 00886 // Random access iterator requirements 00887 template<typename _IteratorL, typename _IteratorR, typename _Container> 00888 inline bool 00889 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 00890 const __normal_iterator<_IteratorR, _Container>& __rhs) 00891 _GLIBCXX_NOEXCEPT 00892 { return __lhs.base() < __rhs.base(); } 00893 00894 template<typename _Iterator, typename _Container> 00895 inline bool 00896 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 00897 const __normal_iterator<_Iterator, _Container>& __rhs) 00898 _GLIBCXX_NOEXCEPT 00899 { return __lhs.base() < __rhs.base(); } 00900 00901 template<typename _IteratorL, typename _IteratorR, typename _Container> 00902 inline bool 00903 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 00904 const __normal_iterator<_IteratorR, _Container>& __rhs) 00905 _GLIBCXX_NOEXCEPT 00906 { return __lhs.base() > __rhs.base(); } 00907 00908 template<typename _Iterator, typename _Container> 00909 inline bool 00910 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 00911 const __normal_iterator<_Iterator, _Container>& __rhs) 00912 _GLIBCXX_NOEXCEPT 00913 { return __lhs.base() > __rhs.base(); } 00914 00915 template<typename _IteratorL, typename _IteratorR, typename _Container> 00916 inline bool 00917 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00918 const __normal_iterator<_IteratorR, _Container>& __rhs) 00919 _GLIBCXX_NOEXCEPT 00920 { return __lhs.base() <= __rhs.base(); } 00921 00922 template<typename _Iterator, typename _Container> 00923 inline bool 00924 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 00925 const __normal_iterator<_Iterator, _Container>& __rhs) 00926 _GLIBCXX_NOEXCEPT 00927 { return __lhs.base() <= __rhs.base(); } 00928 00929 template<typename _IteratorL, typename _IteratorR, typename _Container> 00930 inline bool 00931 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00932 const __normal_iterator<_IteratorR, _Container>& __rhs) 00933 _GLIBCXX_NOEXCEPT 00934 { return __lhs.base() >= __rhs.base(); } 00935 00936 template<typename _Iterator, typename _Container> 00937 inline bool 00938 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 00939 const __normal_iterator<_Iterator, _Container>& __rhs) 00940 _GLIBCXX_NOEXCEPT 00941 { return __lhs.base() >= __rhs.base(); } 00942 00943 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00944 // According to the resolution of DR179 not only the various comparison 00945 // operators but also operator- must accept mixed iterator/const_iterator 00946 // parameters. 00947 template<typename _IteratorL, typename _IteratorR, typename _Container> 00948 #if __cplusplus >= 201103L 00949 // DR 685. 00950 inline auto 00951 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00952 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept 00953 -> decltype(__lhs.base() - __rhs.base()) 00954 #else 00955 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 00956 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00957 const __normal_iterator<_IteratorR, _Container>& __rhs) 00958 #endif 00959 { return __lhs.base() - __rhs.base(); } 00960 00961 template<typename _Iterator, typename _Container> 00962 inline typename __normal_iterator<_Iterator, _Container>::difference_type 00963 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 00964 const __normal_iterator<_Iterator, _Container>& __rhs) 00965 _GLIBCXX_NOEXCEPT 00966 { return __lhs.base() - __rhs.base(); } 00967 00968 template<typename _Iterator, typename _Container> 00969 inline __normal_iterator<_Iterator, _Container> 00970 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 00971 __n, const __normal_iterator<_Iterator, _Container>& __i) 00972 _GLIBCXX_NOEXCEPT 00973 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 00974 00975 _GLIBCXX_END_NAMESPACE_VERSION 00976 } // namespace 00977 00978 namespace std _GLIBCXX_VISIBILITY(default) 00979 { 00980 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00981 00982 template<typename _Iterator, typename _Container> 00983 _Iterator 00984 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it) 00985 { return __it.base(); } 00986 00987 #if __cplusplus >= 201103L 00988 00989 /** 00990 * @addtogroup iterators 00991 * @{ 00992 */ 00993 00994 // 24.4.3 Move iterators 00995 /** 00996 * Class template move_iterator is an iterator adapter with the same 00997 * behavior as the underlying iterator except that its dereference 00998 * operator implicitly converts the value returned by the underlying 00999 * iterator's dereference operator to an rvalue reference. Some 01000 * generic algorithms can be called with move iterators to replace 01001 * copying with moving. 01002 */ 01003 template<typename _Iterator> 01004 class move_iterator 01005 { 01006 protected: 01007 _Iterator _M_current; 01008 01009 typedef iterator_traits<_Iterator> __traits_type; 01010 typedef typename __traits_type::reference __base_ref; 01011 01012 public: 01013 typedef _Iterator iterator_type; 01014 typedef typename __traits_type::iterator_category iterator_category; 01015 typedef typename __traits_type::value_type value_type; 01016 typedef typename __traits_type::difference_type difference_type; 01017 // NB: DR 680. 01018 typedef _Iterator pointer; 01019 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01020 // 2106. move_iterator wrapping iterators returning prvalues 01021 typedef typename conditional<is_reference<__base_ref>::value, 01022 typename remove_reference<__base_ref>::type&&, 01023 __base_ref>::type reference; 01024 01025 _GLIBCXX17_CONSTEXPR 01026 move_iterator() 01027 : _M_current() { } 01028 01029 explicit _GLIBCXX17_CONSTEXPR 01030 move_iterator(iterator_type __i) 01031 : _M_current(__i) { } 01032 01033 template<typename _Iter> 01034 _GLIBCXX17_CONSTEXPR 01035 move_iterator(const move_iterator<_Iter>& __i) 01036 : _M_current(__i.base()) { } 01037 01038 _GLIBCXX17_CONSTEXPR iterator_type 01039 base() const 01040 { return _M_current; } 01041 01042 _GLIBCXX17_CONSTEXPR reference 01043 operator*() const 01044 { return static_cast<reference>(*_M_current); } 01045 01046 _GLIBCXX17_CONSTEXPR pointer 01047 operator->() const 01048 { return _M_current; } 01049 01050 _GLIBCXX17_CONSTEXPR move_iterator& 01051 operator++() 01052 { 01053 ++_M_current; 01054 return *this; 01055 } 01056 01057 _GLIBCXX17_CONSTEXPR move_iterator 01058 operator++(int) 01059 { 01060 move_iterator __tmp = *this; 01061 ++_M_current; 01062 return __tmp; 01063 } 01064 01065 _GLIBCXX17_CONSTEXPR move_iterator& 01066 operator--() 01067 { 01068 --_M_current; 01069 return *this; 01070 } 01071 01072 _GLIBCXX17_CONSTEXPR move_iterator 01073 operator--(int) 01074 { 01075 move_iterator __tmp = *this; 01076 --_M_current; 01077 return __tmp; 01078 } 01079 01080 _GLIBCXX17_CONSTEXPR move_iterator 01081 operator+(difference_type __n) const 01082 { return move_iterator(_M_current + __n); } 01083 01084 _GLIBCXX17_CONSTEXPR move_iterator& 01085 operator+=(difference_type __n) 01086 { 01087 _M_current += __n; 01088 return *this; 01089 } 01090 01091 _GLIBCXX17_CONSTEXPR move_iterator 01092 operator-(difference_type __n) const 01093 { return move_iterator(_M_current - __n); } 01094 01095 _GLIBCXX17_CONSTEXPR move_iterator& 01096 operator-=(difference_type __n) 01097 { 01098 _M_current -= __n; 01099 return *this; 01100 } 01101 01102 _GLIBCXX17_CONSTEXPR reference 01103 operator[](difference_type __n) const 01104 { return std::move(_M_current[__n]); } 01105 }; 01106 01107 // Note: See __normal_iterator operators note from Gaby to understand 01108 // why there are always 2 versions for most of the move_iterator 01109 // operators. 01110 template<typename _IteratorL, typename _IteratorR> 01111 inline _GLIBCXX17_CONSTEXPR bool 01112 operator==(const move_iterator<_IteratorL>& __x, 01113 const move_iterator<_IteratorR>& __y) 01114 { return __x.base() == __y.base(); } 01115 01116 template<typename _Iterator> 01117 inline _GLIBCXX17_CONSTEXPR bool 01118 operator==(const move_iterator<_Iterator>& __x, 01119 const move_iterator<_Iterator>& __y) 01120 { return __x.base() == __y.base(); } 01121 01122 template<typename _IteratorL, typename _IteratorR> 01123 inline _GLIBCXX17_CONSTEXPR bool 01124 operator!=(const move_iterator<_IteratorL>& __x, 01125 const move_iterator<_IteratorR>& __y) 01126 { return !(__x == __y); } 01127 01128 template<typename _Iterator> 01129 inline _GLIBCXX17_CONSTEXPR bool 01130 operator!=(const move_iterator<_Iterator>& __x, 01131 const move_iterator<_Iterator>& __y) 01132 { return !(__x == __y); } 01133 01134 template<typename _IteratorL, typename _IteratorR> 01135 inline _GLIBCXX17_CONSTEXPR bool 01136 operator<(const move_iterator<_IteratorL>& __x, 01137 const move_iterator<_IteratorR>& __y) 01138 { return __x.base() < __y.base(); } 01139 01140 template<typename _Iterator> 01141 inline _GLIBCXX17_CONSTEXPR bool 01142 operator<(const move_iterator<_Iterator>& __x, 01143 const move_iterator<_Iterator>& __y) 01144 { return __x.base() < __y.base(); } 01145 01146 template<typename _IteratorL, typename _IteratorR> 01147 inline _GLIBCXX17_CONSTEXPR bool 01148 operator<=(const move_iterator<_IteratorL>& __x, 01149 const move_iterator<_IteratorR>& __y) 01150 { return !(__y < __x); } 01151 01152 template<typename _Iterator> 01153 inline _GLIBCXX17_CONSTEXPR bool 01154 operator<=(const move_iterator<_Iterator>& __x, 01155 const move_iterator<_Iterator>& __y) 01156 { return !(__y < __x); } 01157 01158 template<typename _IteratorL, typename _IteratorR> 01159 inline _GLIBCXX17_CONSTEXPR bool 01160 operator>(const move_iterator<_IteratorL>& __x, 01161 const move_iterator<_IteratorR>& __y) 01162 { return __y < __x; } 01163 01164 template<typename _Iterator> 01165 inline _GLIBCXX17_CONSTEXPR bool 01166 operator>(const move_iterator<_Iterator>& __x, 01167 const move_iterator<_Iterator>& __y) 01168 { return __y < __x; } 01169 01170 template<typename _IteratorL, typename _IteratorR> 01171 inline _GLIBCXX17_CONSTEXPR bool 01172 operator>=(const move_iterator<_IteratorL>& __x, 01173 const move_iterator<_IteratorR>& __y) 01174 { return !(__x < __y); } 01175 01176 template<typename _Iterator> 01177 inline _GLIBCXX17_CONSTEXPR bool 01178 operator>=(const move_iterator<_Iterator>& __x, 01179 const move_iterator<_Iterator>& __y) 01180 { return !(__x < __y); } 01181 01182 // DR 685. 01183 template<typename _IteratorL, typename _IteratorR> 01184 inline _GLIBCXX17_CONSTEXPR auto 01185 operator-(const move_iterator<_IteratorL>& __x, 01186 const move_iterator<_IteratorR>& __y) 01187 -> decltype(__x.base() - __y.base()) 01188 { return __x.base() - __y.base(); } 01189 01190 template<typename _Iterator> 01191 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 01192 operator+(typename move_iterator<_Iterator>::difference_type __n, 01193 const move_iterator<_Iterator>& __x) 01194 { return __x + __n; } 01195 01196 template<typename _Iterator> 01197 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator> 01198 make_move_iterator(_Iterator __i) 01199 { return move_iterator<_Iterator>(__i); } 01200 01201 template<typename _Iterator, typename _ReturnType 01202 = typename conditional<__move_if_noexcept_cond 01203 <typename iterator_traits<_Iterator>::value_type>::value, 01204 _Iterator, move_iterator<_Iterator>>::type> 01205 inline _GLIBCXX17_CONSTEXPR _ReturnType 01206 __make_move_if_noexcept_iterator(_Iterator __i) 01207 { return _ReturnType(__i); } 01208 01209 // Overload for pointers that matches std::move_if_noexcept more closely, 01210 // returning a constant iterator when we don't want to move. 01211 template<typename _Tp, typename _ReturnType 01212 = typename conditional<__move_if_noexcept_cond<_Tp>::value, 01213 const _Tp*, move_iterator<_Tp*>>::type> 01214 inline _GLIBCXX17_CONSTEXPR _ReturnType 01215 __make_move_if_noexcept_iterator(_Tp* __i) 01216 { return _ReturnType(__i); } 01217 01218 // @} group iterators 01219 01220 template<typename _Iterator> 01221 auto 01222 __niter_base(move_iterator<_Iterator> __it) 01223 -> decltype(make_move_iterator(__niter_base(__it.base()))) 01224 { return make_move_iterator(__niter_base(__it.base())); } 01225 01226 template<typename _Iterator> 01227 struct __is_move_iterator<move_iterator<_Iterator> > 01228 { 01229 enum { __value = 1 }; 01230 typedef __true_type __type; 01231 }; 01232 01233 template<typename _Iterator> 01234 auto 01235 __miter_base(move_iterator<_Iterator> __it) 01236 -> decltype(__miter_base(__it.base())) 01237 { return __miter_base(__it.base()); } 01238 01239 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 01240 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ 01241 std::__make_move_if_noexcept_iterator(_Iter) 01242 #else 01243 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 01244 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) 01245 #endif // C++11 01246 01247 #if __cpp_deduction_guides >= 201606 01248 // These helper traits are used for deduction guides 01249 // of associative containers. 01250 template<typename _InputIterator> 01251 using __iter_key_t = remove_const_t< 01252 typename iterator_traits<_InputIterator>::value_type::first_type>; 01253 01254 template<typename _InputIterator> 01255 using __iter_val_t = 01256 typename iterator_traits<_InputIterator>::value_type::second_type; 01257 01258 template<typename _T1, typename _T2> 01259 struct pair; 01260 01261 template<typename _InputIterator> 01262 using __iter_to_alloc_t = 01263 pair<add_const_t<__iter_key_t<_InputIterator>>, 01264 __iter_val_t<_InputIterator>>; 01265 01266 #endif 01267 01268 _GLIBCXX_END_NAMESPACE_VERSION 01269 } // namespace 01270 01271 #ifdef _GLIBCXX_DEBUG 01272 # include <debug/stl_iterator.h> 01273 #endif 01274 01275 #endif