libstdc++
|
00001 // Functions used by 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_base_funcs.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 contains all of the general iterator-related utility 00057 * functions, such as distance() and advance(). 00058 */ 00059 00060 #ifndef _STL_ITERATOR_BASE_FUNCS_H 00061 #define _STL_ITERATOR_BASE_FUNCS_H 1 00062 00063 #pragma GCC system_header 00064 #include <bits/concept_check.h> 00065 00066 _GLIBCXX_BEGIN_NAMESPACE(std) 00067 00068 template<typename _InputIterator> 00069 inline typename iterator_traits<_InputIterator>::difference_type 00070 __distance(_InputIterator __first, _InputIterator __last, 00071 input_iterator_tag) 00072 { 00073 // concept requirements 00074 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00075 00076 typename iterator_traits<_InputIterator>::difference_type __n = 0; 00077 while (__first != __last) 00078 { 00079 ++__first; 00080 ++__n; 00081 } 00082 return __n; 00083 } 00084 00085 template<typename _RandomAccessIterator> 00086 inline typename iterator_traits<_RandomAccessIterator>::difference_type 00087 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 00088 random_access_iterator_tag) 00089 { 00090 // concept requirements 00091 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00092 _RandomAccessIterator>) 00093 return __last - __first; 00094 } 00095 00096 /** 00097 * @brief A generalization of pointer arithmetic. 00098 * @param first An input iterator. 00099 * @param last An input iterator. 00100 * @return The distance between them. 00101 * 00102 * Returns @c n such that first + n == last. This requires that @p last 00103 * must be reachable from @p first. Note that @c n may be negative. 00104 * 00105 * For random access iterators, this uses their @c + and @c - operations 00106 * and are constant time. For other %iterator classes they are linear time. 00107 */ 00108 template<typename _InputIterator> 00109 inline typename iterator_traits<_InputIterator>::difference_type 00110 distance(_InputIterator __first, _InputIterator __last) 00111 { 00112 // concept requirements -- taken care of in __distance 00113 return std::__distance(__first, __last, 00114 std::__iterator_category(__first)); 00115 } 00116 00117 template<typename _InputIterator, typename _Distance> 00118 inline void 00119 __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) 00120 { 00121 // concept requirements 00122 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00123 while (__n--) 00124 ++__i; 00125 } 00126 00127 template<typename _BidirectionalIterator, typename _Distance> 00128 inline void 00129 __advance(_BidirectionalIterator& __i, _Distance __n, 00130 bidirectional_iterator_tag) 00131 { 00132 // concept requirements 00133 __glibcxx_function_requires(_BidirectionalIteratorConcept< 00134 _BidirectionalIterator>) 00135 if (__n > 0) 00136 while (__n--) 00137 ++__i; 00138 else 00139 while (__n++) 00140 --__i; 00141 } 00142 00143 template<typename _RandomAccessIterator, typename _Distance> 00144 inline void 00145 __advance(_RandomAccessIterator& __i, _Distance __n, 00146 random_access_iterator_tag) 00147 { 00148 // concept requirements 00149 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00150 _RandomAccessIterator>) 00151 __i += __n; 00152 } 00153 00154 /** 00155 * @brief A generalization of pointer arithmetic. 00156 * @param i An input iterator. 00157 * @param n The "delta" by which to change @p i. 00158 * @return Nothing. 00159 * 00160 * This increments @p i by @p n. For bidirectional and random access 00161 * iterators, @p n may be negative, in which case @p i is decremented. 00162 * 00163 * For random access iterators, this uses their @c + and @c - operations 00164 * and are constant time. For other %iterator classes they are linear time. 00165 */ 00166 template<typename _InputIterator, typename _Distance> 00167 inline void 00168 advance(_InputIterator& __i, _Distance __n) 00169 { 00170 // concept requirements -- taken care of in __advance 00171 typename iterator_traits<_InputIterator>::difference_type __d = __n; 00172 std::__advance(__i, __d, std::__iterator_category(__i)); 00173 } 00174 00175 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00176 template<typename _InputIterator> 00177 inline _InputIterator 00178 next(_InputIterator __x, typename 00179 iterator_traits<_InputIterator>::difference_type __n = 1) 00180 { 00181 std::advance(__x, __n); 00182 return __x; 00183 } 00184 00185 template<typename _BidirectionalIterator> 00186 inline _BidirectionalIterator 00187 prev(_BidirectionalIterator __x, typename 00188 iterator_traits<_BidirectionalIterator>::difference_type __n = 1) 00189 { 00190 std::advance(__x, -__n); 00191 return __x; 00192 } 00193 #endif 00194 00195 _GLIBCXX_END_NAMESPACE 00196 00197 #endif /* _STL_ITERATOR_BASE_FUNCS_H */