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