libstdc++
|
00001 // Iterators -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996-1998 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file stl_iterator.h 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 00055 * 00056 * This file implements reverse_iterator, back_insert_iterator, 00057 * front_insert_iterator, insert_iterator, __normal_iterator, and their 00058 * supporting functions and overloaded operators. 00059 */ 00060 00061 #ifndef _STL_ITERATOR_H 00062 #define _STL_ITERATOR_H 1 00063 00064 #include <bits/cpp_type_traits.h> 00065 #include <ext/type_traits.h> 00066 #include <bits/move.h> 00067 00068 _GLIBCXX_BEGIN_NAMESPACE(std) 00069 00070 // 24.4.1 Reverse iterators 00071 /** 00072 * "Bidirectional and random access iterators have corresponding reverse 00073 * %iterator adaptors that iterate through the data structure in the 00074 * opposite direction. They have the same signatures as the corresponding 00075 * iterators. The fundamental relation between a reverse %iterator and its 00076 * corresponding %iterator @c i is established by the identity: 00077 * @code 00078 * &*(reverse_iterator(i)) == &*(i - 1) 00079 * @endcode 00080 * 00081 * This mapping is dictated by the fact that while there is always a 00082 * pointer past the end of an array, there might not be a valid pointer 00083 * before the beginning of an array." [24.4.1]/1,2 00084 * 00085 * Reverse iterators can be tricky and surprising at first. Their 00086 * semantics make sense, however, and the trickiness is a side effect of 00087 * the requirement that the iterators must be safe. 00088 */ 00089 template<typename _Iterator> 00090 class reverse_iterator 00091 : public iterator<typename iterator_traits<_Iterator>::iterator_category, 00092 typename iterator_traits<_Iterator>::value_type, 00093 typename iterator_traits<_Iterator>::difference_type, 00094 typename iterator_traits<_Iterator>::pointer, 00095 typename iterator_traits<_Iterator>::reference> 00096 { 00097 protected: 00098 _Iterator current; 00099 00100 public: 00101 typedef _Iterator iterator_type; 00102 typedef typename iterator_traits<_Iterator>::difference_type 00103 difference_type; 00104 typedef typename iterator_traits<_Iterator>::reference reference; 00105 typedef typename iterator_traits<_Iterator>::pointer pointer; 00106 00107 public: 00108 /** 00109 * The default constructor default-initializes member @p current. 00110 * If it is a pointer, that means it is zero-initialized. 00111 */ 00112 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00113 // 235 No specification of default ctor for reverse_iterator 00114 reverse_iterator() : current() { } 00115 00116 /** 00117 * This %iterator will move in the opposite direction that @p x does. 00118 */ 00119 explicit 00120 reverse_iterator(iterator_type __x) : current(__x) { } 00121 00122 /** 00123 * The copy constructor is normal. 00124 */ 00125 reverse_iterator(const reverse_iterator& __x) 00126 : current(__x.current) { } 00127 00128 /** 00129 * A reverse_iterator across other types can be copied in the normal 00130 * fashion. 00131 */ 00132 template<typename _Iter> 00133 reverse_iterator(const reverse_iterator<_Iter>& __x) 00134 : current(__x.base()) { } 00135 00136 /** 00137 * @return @c current, the %iterator used for underlying work. 00138 */ 00139 iterator_type 00140 base() const 00141 { return current; } 00142 00143 /** 00144 * @return TODO 00145 * 00146 * @doctodo 00147 */ 00148 reference 00149 operator*() const 00150 { 00151 _Iterator __tmp = current; 00152 return *--__tmp; 00153 } 00154 00155 /** 00156 * @return TODO 00157 * 00158 * @doctodo 00159 */ 00160 pointer 00161 operator->() const 00162 { return &(operator*()); } 00163 00164 /** 00165 * @return TODO 00166 * 00167 * @doctodo 00168 */ 00169 reverse_iterator& 00170 operator++() 00171 { 00172 --current; 00173 return *this; 00174 } 00175 00176 /** 00177 * @return TODO 00178 * 00179 * @doctodo 00180 */ 00181 reverse_iterator 00182 operator++(int) 00183 { 00184 reverse_iterator __tmp = *this; 00185 --current; 00186 return __tmp; 00187 } 00188 00189 /** 00190 * @return TODO 00191 * 00192 * @doctodo 00193 */ 00194 reverse_iterator& 00195 operator--() 00196 { 00197 ++current; 00198 return *this; 00199 } 00200 00201 /** 00202 * @return TODO 00203 * 00204 * @doctodo 00205 */ 00206 reverse_iterator 00207 operator--(int) 00208 { 00209 reverse_iterator __tmp = *this; 00210 ++current; 00211 return __tmp; 00212 } 00213 00214 /** 00215 * @return TODO 00216 * 00217 * @doctodo 00218 */ 00219 reverse_iterator 00220 operator+(difference_type __n) const 00221 { return reverse_iterator(current - __n); } 00222 00223 /** 00224 * @return TODO 00225 * 00226 * @doctodo 00227 */ 00228 reverse_iterator& 00229 operator+=(difference_type __n) 00230 { 00231 current -= __n; 00232 return *this; 00233 } 00234 00235 /** 00236 * @return TODO 00237 * 00238 * @doctodo 00239 */ 00240 reverse_iterator 00241 operator-(difference_type __n) const 00242 { return reverse_iterator(current + __n); } 00243 00244 /** 00245 * @return TODO 00246 * 00247 * @doctodo 00248 */ 00249 reverse_iterator& 00250 operator-=(difference_type __n) 00251 { 00252 current += __n; 00253 return *this; 00254 } 00255 00256 /** 00257 * @return TODO 00258 * 00259 * @doctodo 00260 */ 00261 reference 00262 operator[](difference_type __n) const 00263 { return *(*this + __n); } 00264 }; 00265 00266 //@{ 00267 /** 00268 * @param x A %reverse_iterator. 00269 * @param y A %reverse_iterator. 00270 * @return A simple bool. 00271 * 00272 * Reverse iterators forward many operations to their underlying base() 00273 * iterators. Others are implemented in terms of one another. 00274 * 00275 */ 00276 template<typename _Iterator> 00277 inline bool 00278 operator==(const reverse_iterator<_Iterator>& __x, 00279 const reverse_iterator<_Iterator>& __y) 00280 { return __x.base() == __y.base(); } 00281 00282 template<typename _Iterator> 00283 inline bool 00284 operator<(const reverse_iterator<_Iterator>& __x, 00285 const reverse_iterator<_Iterator>& __y) 00286 { return __y.base() < __x.base(); } 00287 00288 template<typename _Iterator> 00289 inline bool 00290 operator!=(const reverse_iterator<_Iterator>& __x, 00291 const reverse_iterator<_Iterator>& __y) 00292 { return !(__x == __y); } 00293 00294 template<typename _Iterator> 00295 inline bool 00296 operator>(const reverse_iterator<_Iterator>& __x, 00297 const reverse_iterator<_Iterator>& __y) 00298 { return __y < __x; } 00299 00300 template<typename _Iterator> 00301 inline bool 00302 operator<=(const reverse_iterator<_Iterator>& __x, 00303 const reverse_iterator<_Iterator>& __y) 00304 { return !(__y < __x); } 00305 00306 template<typename _Iterator> 00307 inline bool 00308 operator>=(const reverse_iterator<_Iterator>& __x, 00309 const reverse_iterator<_Iterator>& __y) 00310 { return !(__x < __y); } 00311 00312 template<typename _Iterator> 00313 inline typename reverse_iterator<_Iterator>::difference_type 00314 operator-(const reverse_iterator<_Iterator>& __x, 00315 const reverse_iterator<_Iterator>& __y) 00316 { return __y.base() - __x.base(); } 00317 00318 template<typename _Iterator> 00319 inline reverse_iterator<_Iterator> 00320 operator+(typename reverse_iterator<_Iterator>::difference_type __n, 00321 const reverse_iterator<_Iterator>& __x) 00322 { return reverse_iterator<_Iterator>(__x.base() - __n); } 00323 00324 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00325 // DR 280. Comparison of reverse_iterator to const reverse_iterator. 00326 template<typename _IteratorL, typename _IteratorR> 00327 inline bool 00328 operator==(const reverse_iterator<_IteratorL>& __x, 00329 const reverse_iterator<_IteratorR>& __y) 00330 { return __x.base() == __y.base(); } 00331 00332 template<typename _IteratorL, typename _IteratorR> 00333 inline bool 00334 operator<(const reverse_iterator<_IteratorL>& __x, 00335 const reverse_iterator<_IteratorR>& __y) 00336 { return __y.base() < __x.base(); } 00337 00338 template<typename _IteratorL, typename _IteratorR> 00339 inline bool 00340 operator!=(const reverse_iterator<_IteratorL>& __x, 00341 const reverse_iterator<_IteratorR>& __y) 00342 { return !(__x == __y); } 00343 00344 template<typename _IteratorL, typename _IteratorR> 00345 inline bool 00346 operator>(const reverse_iterator<_IteratorL>& __x, 00347 const reverse_iterator<_IteratorR>& __y) 00348 { return __y < __x; } 00349 00350 template<typename _IteratorL, typename _IteratorR> 00351 inline bool 00352 operator<=(const reverse_iterator<_IteratorL>& __x, 00353 const reverse_iterator<_IteratorR>& __y) 00354 { return !(__y < __x); } 00355 00356 template<typename _IteratorL, typename _IteratorR> 00357 inline bool 00358 operator>=(const reverse_iterator<_IteratorL>& __x, 00359 const reverse_iterator<_IteratorR>& __y) 00360 { return !(__x < __y); } 00361 00362 template<typename _IteratorL, typename _IteratorR> 00363 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00364 // DR 685. 00365 inline auto 00366 operator-(const reverse_iterator<_IteratorL>& __x, 00367 const reverse_iterator<_IteratorR>& __y) 00368 -> decltype(__y.base() - __x.base()) 00369 #else 00370 inline typename reverse_iterator<_IteratorL>::difference_type 00371 operator-(const reverse_iterator<_IteratorL>& __x, 00372 const reverse_iterator<_IteratorR>& __y) 00373 #endif 00374 { return __y.base() - __x.base(); } 00375 //@} 00376 00377 // 24.4.2.2.1 back_insert_iterator 00378 /** 00379 * @brief Turns assignment into insertion. 00380 * 00381 * These are output iterators, constructed from a container-of-T. 00382 * Assigning a T to the iterator appends it to the container using 00383 * push_back. 00384 * 00385 * Tip: Using the back_inserter function to create these iterators can 00386 * save typing. 00387 */ 00388 template<typename _Container> 00389 class back_insert_iterator 00390 : public iterator<output_iterator_tag, void, void, void, void> 00391 { 00392 protected: 00393 _Container* container; 00394 00395 public: 00396 /// A nested typedef for the type of whatever container you used. 00397 typedef _Container container_type; 00398 00399 /// The only way to create this %iterator is with a container. 00400 explicit 00401 back_insert_iterator(_Container& __x) : container(&__x) { } 00402 00403 /** 00404 * @param value An instance of whatever type 00405 * container_type::const_reference is; presumably a 00406 * reference-to-const T for container<T>. 00407 * @return This %iterator, for chained operations. 00408 * 00409 * This kind of %iterator doesn't really have a "position" in the 00410 * container (you can think of the position as being permanently at 00411 * the end, if you like). Assigning a value to the %iterator will 00412 * always append the value to the end of the container. 00413 */ 00414 back_insert_iterator& 00415 operator=(typename _Container::const_reference __value) 00416 { 00417 container->push_back(__value); 00418 return *this; 00419 } 00420 00421 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00422 back_insert_iterator& 00423 operator=(typename _Container::value_type&& __value) 00424 { 00425 container->push_back(std::move(__value)); 00426 return *this; 00427 } 00428 #endif 00429 00430 /// Simply returns *this. 00431 back_insert_iterator& 00432 operator*() 00433 { return *this; } 00434 00435 /// Simply returns *this. (This %iterator does not "move".) 00436 back_insert_iterator& 00437 operator++() 00438 { return *this; } 00439 00440 /// Simply returns *this. (This %iterator does not "move".) 00441 back_insert_iterator 00442 operator++(int) 00443 { return *this; } 00444 }; 00445 00446 /** 00447 * @param x A container of arbitrary type. 00448 * @return An instance of back_insert_iterator working on @p x. 00449 * 00450 * This wrapper function helps in creating back_insert_iterator instances. 00451 * Typing the name of the %iterator requires knowing the precise full 00452 * type of the container, which can be tedious and impedes generic 00453 * programming. Using this function lets you take advantage of automatic 00454 * template parameter deduction, making the compiler match the correct 00455 * types for you. 00456 */ 00457 template<typename _Container> 00458 inline back_insert_iterator<_Container> 00459 back_inserter(_Container& __x) 00460 { return back_insert_iterator<_Container>(__x); } 00461 00462 /** 00463 * @brief Turns assignment into insertion. 00464 * 00465 * These are output iterators, constructed from a container-of-T. 00466 * Assigning a T to the iterator prepends it to the container using 00467 * push_front. 00468 * 00469 * Tip: Using the front_inserter function to create these iterators can 00470 * save typing. 00471 */ 00472 template<typename _Container> 00473 class front_insert_iterator 00474 : public iterator<output_iterator_tag, void, void, void, void> 00475 { 00476 protected: 00477 _Container* container; 00478 00479 public: 00480 /// A nested typedef for the type of whatever container you used. 00481 typedef _Container container_type; 00482 00483 /// The only way to create this %iterator is with a container. 00484 explicit front_insert_iterator(_Container& __x) : container(&__x) { } 00485 00486 /** 00487 * @param value An instance of whatever type 00488 * container_type::const_reference is; presumably a 00489 * reference-to-const T for container<T>. 00490 * @return This %iterator, for chained operations. 00491 * 00492 * This kind of %iterator doesn't really have a "position" in the 00493 * container (you can think of the position as being permanently at 00494 * the front, if you like). Assigning a value to the %iterator will 00495 * always prepend the value to the front of the container. 00496 */ 00497 front_insert_iterator& 00498 operator=(typename _Container::const_reference __value) 00499 { 00500 container->push_front(__value); 00501 return *this; 00502 } 00503 00504 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00505 front_insert_iterator& 00506 operator=(typename _Container::value_type&& __value) 00507 { 00508 container->push_front(std::move(__value)); 00509 return *this; 00510 } 00511 #endif 00512 00513 /// Simply returns *this. 00514 front_insert_iterator& 00515 operator*() 00516 { return *this; } 00517 00518 /// Simply returns *this. (This %iterator does not "move".) 00519 front_insert_iterator& 00520 operator++() 00521 { return *this; } 00522 00523 /// Simply returns *this. (This %iterator does not "move".) 00524 front_insert_iterator 00525 operator++(int) 00526 { return *this; } 00527 }; 00528 00529 /** 00530 * @param x A container of arbitrary type. 00531 * @return An instance of front_insert_iterator working on @p x. 00532 * 00533 * This wrapper function helps in creating front_insert_iterator instances. 00534 * Typing the name of the %iterator requires knowing the precise full 00535 * type of the container, which can be tedious and impedes generic 00536 * programming. Using this function lets you take advantage of automatic 00537 * template parameter deduction, making the compiler match the correct 00538 * types for you. 00539 */ 00540 template<typename _Container> 00541 inline front_insert_iterator<_Container> 00542 front_inserter(_Container& __x) 00543 { return front_insert_iterator<_Container>(__x); } 00544 00545 /** 00546 * @brief Turns assignment into insertion. 00547 * 00548 * These are output iterators, constructed from a container-of-T. 00549 * Assigning a T to the iterator inserts it in the container at the 00550 * %iterator's position, rather than overwriting the value at that 00551 * position. 00552 * 00553 * (Sequences will actually insert a @e copy of the value before the 00554 * %iterator's position.) 00555 * 00556 * Tip: Using the inserter function to create these iterators can 00557 * save typing. 00558 */ 00559 template<typename _Container> 00560 class insert_iterator 00561 : public iterator<output_iterator_tag, void, void, void, void> 00562 { 00563 protected: 00564 _Container* container; 00565 typename _Container::iterator iter; 00566 00567 public: 00568 /// A nested typedef for the type of whatever container you used. 00569 typedef _Container container_type; 00570 00571 /** 00572 * The only way to create this %iterator is with a container and an 00573 * initial position (a normal %iterator into the container). 00574 */ 00575 insert_iterator(_Container& __x, typename _Container::iterator __i) 00576 : container(&__x), iter(__i) {} 00577 00578 /** 00579 * @param value An instance of whatever type 00580 * container_type::const_reference is; presumably a 00581 * reference-to-const T for container<T>. 00582 * @return This %iterator, for chained operations. 00583 * 00584 * This kind of %iterator maintains its own position in the 00585 * container. Assigning a value to the %iterator will insert the 00586 * value into the container at the place before the %iterator. 00587 * 00588 * The position is maintained such that subsequent assignments will 00589 * insert values immediately after one another. For example, 00590 * @code 00591 * // vector v contains A and Z 00592 * 00593 * insert_iterator i (v, ++v.begin()); 00594 * i = 1; 00595 * i = 2; 00596 * i = 3; 00597 * 00598 * // vector v contains A, 1, 2, 3, and Z 00599 * @endcode 00600 */ 00601 insert_iterator& 00602 operator=(typename _Container::const_reference __value) 00603 { 00604 iter = container->insert(iter, __value); 00605 ++iter; 00606 return *this; 00607 } 00608 00609 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00610 insert_iterator& 00611 operator=(typename _Container::value_type&& __value) 00612 { 00613 iter = container->insert(iter, std::move(__value)); 00614 ++iter; 00615 return *this; 00616 } 00617 #endif 00618 00619 /// Simply returns *this. 00620 insert_iterator& 00621 operator*() 00622 { return *this; } 00623 00624 /// Simply returns *this. (This %iterator does not "move".) 00625 insert_iterator& 00626 operator++() 00627 { return *this; } 00628 00629 /// Simply returns *this. (This %iterator does not "move".) 00630 insert_iterator& 00631 operator++(int) 00632 { return *this; } 00633 }; 00634 00635 /** 00636 * @param x A container of arbitrary type. 00637 * @return An instance of insert_iterator working on @p x. 00638 * 00639 * This wrapper function helps in creating insert_iterator instances. 00640 * Typing the name of the %iterator requires knowing the precise full 00641 * type of the container, which can be tedious and impedes generic 00642 * programming. Using this function lets you take advantage of automatic 00643 * template parameter deduction, making the compiler match the correct 00644 * types for you. 00645 */ 00646 template<typename _Container, typename _Iterator> 00647 inline insert_iterator<_Container> 00648 inserter(_Container& __x, _Iterator __i) 00649 { 00650 return insert_iterator<_Container>(__x, 00651 typename _Container::iterator(__i)); 00652 } 00653 00654 _GLIBCXX_END_NAMESPACE 00655 00656 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 00657 00658 // This iterator adapter is 'normal' in the sense that it does not 00659 // change the semantics of any of the operators of its iterator 00660 // parameter. Its primary purpose is to convert an iterator that is 00661 // not a class, e.g. a pointer, into an iterator that is a class. 00662 // The _Container parameter exists solely so that different containers 00663 // using this template can instantiate different types, even if the 00664 // _Iterator parameter is the same. 00665 using std::iterator_traits; 00666 using std::iterator; 00667 template<typename _Iterator, typename _Container> 00668 class __normal_iterator 00669 { 00670 protected: 00671 _Iterator _M_current; 00672 00673 public: 00674 typedef _Iterator iterator_type; 00675 typedef typename iterator_traits<_Iterator>::iterator_category 00676 iterator_category; 00677 typedef typename iterator_traits<_Iterator>::value_type value_type; 00678 typedef typename iterator_traits<_Iterator>::difference_type 00679 difference_type; 00680 typedef typename iterator_traits<_Iterator>::reference reference; 00681 typedef typename iterator_traits<_Iterator>::pointer pointer; 00682 00683 __normal_iterator() : _M_current(_Iterator()) { } 00684 00685 explicit 00686 __normal_iterator(const _Iterator& __i) : _M_current(__i) { } 00687 00688 // Allow iterator to const_iterator conversion 00689 template<typename _Iter> 00690 __normal_iterator(const __normal_iterator<_Iter, 00691 typename __enable_if< 00692 (std::__are_same<_Iter, typename _Container::pointer>::__value), 00693 _Container>::__type>& __i) 00694 : _M_current(__i.base()) { } 00695 00696 // Forward iterator requirements 00697 reference 00698 operator*() const 00699 { return *_M_current; } 00700 00701 pointer 00702 operator->() const 00703 { return _M_current; } 00704 00705 __normal_iterator& 00706 operator++() 00707 { 00708 ++_M_current; 00709 return *this; 00710 } 00711 00712 __normal_iterator 00713 operator++(int) 00714 { return __normal_iterator(_M_current++); } 00715 00716 // Bidirectional iterator requirements 00717 __normal_iterator& 00718 operator--() 00719 { 00720 --_M_current; 00721 return *this; 00722 } 00723 00724 __normal_iterator 00725 operator--(int) 00726 { return __normal_iterator(_M_current--); } 00727 00728 // Random access iterator requirements 00729 reference 00730 operator[](const difference_type& __n) const 00731 { return _M_current[__n]; } 00732 00733 __normal_iterator& 00734 operator+=(const difference_type& __n) 00735 { _M_current += __n; return *this; } 00736 00737 __normal_iterator 00738 operator+(const difference_type& __n) const 00739 { return __normal_iterator(_M_current + __n); } 00740 00741 __normal_iterator& 00742 operator-=(const difference_type& __n) 00743 { _M_current -= __n; return *this; } 00744 00745 __normal_iterator 00746 operator-(const difference_type& __n) const 00747 { return __normal_iterator(_M_current - __n); } 00748 00749 const _Iterator& 00750 base() const 00751 { return _M_current; } 00752 }; 00753 00754 // Note: In what follows, the left- and right-hand-side iterators are 00755 // allowed to vary in types (conceptually in cv-qualification) so that 00756 // comparison between cv-qualified and non-cv-qualified iterators be 00757 // valid. However, the greedy and unfriendly operators in std::rel_ops 00758 // will make overload resolution ambiguous (when in scope) if we don't 00759 // provide overloads whose operands are of the same type. Can someone 00760 // remind me what generic programming is about? -- Gaby 00761 00762 // Forward iterator requirements 00763 template<typename _IteratorL, typename _IteratorR, typename _Container> 00764 inline bool 00765 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 00766 const __normal_iterator<_IteratorR, _Container>& __rhs) 00767 { return __lhs.base() == __rhs.base(); } 00768 00769 template<typename _Iterator, typename _Container> 00770 inline bool 00771 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 00772 const __normal_iterator<_Iterator, _Container>& __rhs) 00773 { return __lhs.base() == __rhs.base(); } 00774 00775 template<typename _IteratorL, typename _IteratorR, typename _Container> 00776 inline bool 00777 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00778 const __normal_iterator<_IteratorR, _Container>& __rhs) 00779 { return __lhs.base() != __rhs.base(); } 00780 00781 template<typename _Iterator, typename _Container> 00782 inline bool 00783 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 00784 const __normal_iterator<_Iterator, _Container>& __rhs) 00785 { return __lhs.base() != __rhs.base(); } 00786 00787 // Random access iterator requirements 00788 template<typename _IteratorL, typename _IteratorR, typename _Container> 00789 inline bool 00790 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, 00791 const __normal_iterator<_IteratorR, _Container>& __rhs) 00792 { return __lhs.base() < __rhs.base(); } 00793 00794 template<typename _Iterator, typename _Container> 00795 inline bool 00796 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 00797 const __normal_iterator<_Iterator, _Container>& __rhs) 00798 { return __lhs.base() < __rhs.base(); } 00799 00800 template<typename _IteratorL, typename _IteratorR, typename _Container> 00801 inline bool 00802 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, 00803 const __normal_iterator<_IteratorR, _Container>& __rhs) 00804 { return __lhs.base() > __rhs.base(); } 00805 00806 template<typename _Iterator, typename _Container> 00807 inline bool 00808 operator>(const __normal_iterator<_Iterator, _Container>& __lhs, 00809 const __normal_iterator<_Iterator, _Container>& __rhs) 00810 { return __lhs.base() > __rhs.base(); } 00811 00812 template<typename _IteratorL, typename _IteratorR, typename _Container> 00813 inline bool 00814 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00815 const __normal_iterator<_IteratorR, _Container>& __rhs) 00816 { return __lhs.base() <= __rhs.base(); } 00817 00818 template<typename _Iterator, typename _Container> 00819 inline bool 00820 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, 00821 const __normal_iterator<_Iterator, _Container>& __rhs) 00822 { return __lhs.base() <= __rhs.base(); } 00823 00824 template<typename _IteratorL, typename _IteratorR, typename _Container> 00825 inline bool 00826 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, 00827 const __normal_iterator<_IteratorR, _Container>& __rhs) 00828 { return __lhs.base() >= __rhs.base(); } 00829 00830 template<typename _Iterator, typename _Container> 00831 inline bool 00832 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, 00833 const __normal_iterator<_Iterator, _Container>& __rhs) 00834 { return __lhs.base() >= __rhs.base(); } 00835 00836 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00837 // According to the resolution of DR179 not only the various comparison 00838 // operators but also operator- must accept mixed iterator/const_iterator 00839 // parameters. 00840 template<typename _IteratorL, typename _IteratorR, typename _Container> 00841 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00842 // DR 685. 00843 inline auto 00844 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00845 const __normal_iterator<_IteratorR, _Container>& __rhs) 00846 -> decltype(__lhs.base() - __rhs.base()) 00847 #else 00848 inline typename __normal_iterator<_IteratorL, _Container>::difference_type 00849 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, 00850 const __normal_iterator<_IteratorR, _Container>& __rhs) 00851 #endif 00852 { return __lhs.base() - __rhs.base(); } 00853 00854 template<typename _Iterator, typename _Container> 00855 inline typename __normal_iterator<_Iterator, _Container>::difference_type 00856 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 00857 const __normal_iterator<_Iterator, _Container>& __rhs) 00858 { return __lhs.base() - __rhs.base(); } 00859 00860 template<typename _Iterator, typename _Container> 00861 inline __normal_iterator<_Iterator, _Container> 00862 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type 00863 __n, const __normal_iterator<_Iterator, _Container>& __i) 00864 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } 00865 00866 _GLIBCXX_END_NAMESPACE 00867 00868 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00869 00870 _GLIBCXX_BEGIN_NAMESPACE(std) 00871 00872 // 24.4.3 Move iterators 00873 /** 00874 * Class template move_iterator is an iterator adapter with the same 00875 * behavior as the underlying iterator except that its dereference 00876 * operator implicitly converts the value returned by the underlying 00877 * iterator's dereference operator to an rvalue reference. Some 00878 * generic algorithms can be called with move iterators to replace 00879 * copying with moving. 00880 */ 00881 template<typename _Iterator> 00882 class move_iterator 00883 { 00884 protected: 00885 _Iterator _M_current; 00886 00887 public: 00888 typedef _Iterator iterator_type; 00889 typedef typename iterator_traits<_Iterator>::difference_type 00890 difference_type; 00891 // NB: DR 680. 00892 typedef _Iterator pointer; 00893 typedef typename iterator_traits<_Iterator>::value_type value_type; 00894 typedef typename iterator_traits<_Iterator>::iterator_category 00895 iterator_category; 00896 typedef value_type&& reference; 00897 00898 public: 00899 move_iterator() 00900 : _M_current() { } 00901 00902 explicit 00903 move_iterator(iterator_type __i) 00904 : _M_current(__i) { } 00905 00906 template<typename _Iter> 00907 move_iterator(const move_iterator<_Iter>& __i) 00908 : _M_current(__i.base()) { } 00909 00910 iterator_type 00911 base() const 00912 { return _M_current; } 00913 00914 reference 00915 operator*() const 00916 { return *_M_current; } 00917 00918 pointer 00919 operator->() const 00920 { return _M_current; } 00921 00922 move_iterator& 00923 operator++() 00924 { 00925 ++_M_current; 00926 return *this; 00927 } 00928 00929 move_iterator 00930 operator++(int) 00931 { 00932 move_iterator __tmp = *this; 00933 ++_M_current; 00934 return __tmp; 00935 } 00936 00937 move_iterator& 00938 operator--() 00939 { 00940 --_M_current; 00941 return *this; 00942 } 00943 00944 move_iterator 00945 operator--(int) 00946 { 00947 move_iterator __tmp = *this; 00948 --_M_current; 00949 return __tmp; 00950 } 00951 00952 move_iterator 00953 operator+(difference_type __n) const 00954 { return move_iterator(_M_current + __n); } 00955 00956 move_iterator& 00957 operator+=(difference_type __n) 00958 { 00959 _M_current += __n; 00960 return *this; 00961 } 00962 00963 move_iterator 00964 operator-(difference_type __n) const 00965 { return move_iterator(_M_current - __n); } 00966 00967 move_iterator& 00968 operator-=(difference_type __n) 00969 { 00970 _M_current -= __n; 00971 return *this; 00972 } 00973 00974 reference 00975 operator[](difference_type __n) const 00976 { return _M_current[__n]; } 00977 }; 00978 00979 template<typename _IteratorL, typename _IteratorR> 00980 inline bool 00981 operator==(const move_iterator<_IteratorL>& __x, 00982 const move_iterator<_IteratorR>& __y) 00983 { return __x.base() == __y.base(); } 00984 00985 template<typename _IteratorL, typename _IteratorR> 00986 inline bool 00987 operator!=(const move_iterator<_IteratorL>& __x, 00988 const move_iterator<_IteratorR>& __y) 00989 { return !(__x == __y); } 00990 00991 template<typename _IteratorL, typename _IteratorR> 00992 inline bool 00993 operator<(const move_iterator<_IteratorL>& __x, 00994 const move_iterator<_IteratorR>& __y) 00995 { return __x.base() < __y.base(); } 00996 00997 template<typename _IteratorL, typename _IteratorR> 00998 inline bool 00999 operator<=(const move_iterator<_IteratorL>& __x, 01000 const move_iterator<_IteratorR>& __y) 01001 { return !(__y < __x); } 01002 01003 template<typename _IteratorL, typename _IteratorR> 01004 inline bool 01005 operator>(const move_iterator<_IteratorL>& __x, 01006 const move_iterator<_IteratorR>& __y) 01007 { return __y < __x; } 01008 01009 template<typename _IteratorL, typename _IteratorR> 01010 inline bool 01011 operator>=(const move_iterator<_IteratorL>& __x, 01012 const move_iterator<_IteratorR>& __y) 01013 { return !(__x < __y); } 01014 01015 // DR 685. 01016 template<typename _IteratorL, typename _IteratorR> 01017 inline auto 01018 operator-(const move_iterator<_IteratorL>& __x, 01019 const move_iterator<_IteratorR>& __y) 01020 -> decltype(__x.base() - __y.base()) 01021 { return __x.base() - __y.base(); } 01022 01023 template<typename _Iterator> 01024 inline move_iterator<_Iterator> 01025 operator+(typename move_iterator<_Iterator>::difference_type __n, 01026 const move_iterator<_Iterator>& __x) 01027 { return __x + __n; } 01028 01029 template<typename _Iterator> 01030 inline move_iterator<_Iterator> 01031 make_move_iterator(const _Iterator& __i) 01032 { return move_iterator<_Iterator>(__i); } 01033 01034 _GLIBCXX_END_NAMESPACE 01035 01036 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) 01037 #else 01038 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) 01039 #endif // __GXX_EXPERIMENTAL_CXX0X__ 01040 01041 #endif