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