1 // Functions used by iterators -*- C++ -*- 2 3 // Copyright (C) 2001-2013 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996-1998 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_iterator_base_funcs.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{iterator} 54 * 55 * This file contains all of the general iterator-related utility 56 * functions, such as distance() and advance(). 57 */ 58 59 #ifndef _STL_ITERATOR_BASE_FUNCS_H 60 #define _STL_ITERATOR_BASE_FUNCS_H 1 61 62 #pragma GCC system_header 63 64 #include <bits/concept_check.h> 65 #include <debug/debug.h> 66 67 namespace std _GLIBCXX_VISIBILITY(default) 68 { 69 _GLIBCXX_BEGIN_NAMESPACE_VERSION 70 71 template<typename _InputIterator> 72 inline typename iterator_traits<_InputIterator>::difference_type 73 __distance(_InputIterator __first, _InputIterator __last, 74 input_iterator_tag) 75 { 76 // concept requirements 77 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 78 79 typename iterator_traits<_InputIterator>::difference_type __n = 0; 80 while (__first != __last) 81 { 82 ++__first; 83 ++__n; 84 } 85 return __n; 86 } 87 88 template<typename _RandomAccessIterator> 89 inline typename iterator_traits<_RandomAccessIterator>::difference_type 90 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 91 random_access_iterator_tag) 92 { 93 // concept requirements 94 __glibcxx_function_requires(_RandomAccessIteratorConcept< 95 _RandomAccessIterator>) 96 return __last - __first; 97 } 98 99 /** 100 * @brief A generalization of pointer arithmetic. 101 * @param __first An input iterator. 102 * @param __last An input iterator. 103 * @return The distance between them. 104 * 105 * Returns @c n such that __first + n == __last. This requires 106 * that @p __last must be reachable from @p __first. Note that @c 107 * n may be negative. 108 * 109 * For random access iterators, this uses their @c + and @c - operations 110 * and are constant time. For other %iterator classes they are linear time. 111 */ 112 template<typename _InputIterator> 113 inline typename iterator_traits<_InputIterator>::difference_type 114 distance(_InputIterator __first, _InputIterator __last) 115 { 116 // concept requirements -- taken care of in __distance 117 return std::__distance(__first, __last, 118 std::__iterator_category(__first)); 119 } 120 121 template<typename _InputIterator, typename _Distance> 122 inline void 123 __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) 124 { 125 // concept requirements 126 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 127 _GLIBCXX_DEBUG_ASSERT(__n >= 0); 128 while (__n--) 129 ++__i; 130 } 131 132 template<typename _BidirectionalIterator, typename _Distance> 133 inline void 134 __advance(_BidirectionalIterator& __i, _Distance __n, 135 bidirectional_iterator_tag) 136 { 137 // concept requirements 138 __glibcxx_function_requires(_BidirectionalIteratorConcept< 139 _BidirectionalIterator>) 140 if (__n > 0) 141 while (__n--) 142 ++__i; 143 else 144 while (__n++) 145 --__i; 146 } 147 148 template<typename _RandomAccessIterator, typename _Distance> 149 inline void 150 __advance(_RandomAccessIterator& __i, _Distance __n, 151 random_access_iterator_tag) 152 { 153 // concept requirements 154 __glibcxx_function_requires(_RandomAccessIteratorConcept< 155 _RandomAccessIterator>) 156 __i += __n; 157 } 158 159 /** 160 * @brief A generalization of pointer arithmetic. 161 * @param __i An input iterator. 162 * @param __n The @a delta by which to change @p __i. 163 * @return Nothing. 164 * 165 * This increments @p i by @p n. For bidirectional and random access 166 * iterators, @p __n may be negative, in which case @p __i is decremented. 167 * 168 * For random access iterators, this uses their @c + and @c - operations 169 * and are constant time. For other %iterator classes they are linear time. 170 */ 171 template<typename _InputIterator, typename _Distance> 172 inline void 173 advance(_InputIterator& __i, _Distance __n) 174 { 175 // concept requirements -- taken care of in __advance 176 typename iterator_traits<_InputIterator>::difference_type __d = __n; 177 std::__advance(__i, __d, std::__iterator_category(__i)); 178 } 179 180 #if __cplusplus >= 201103L 181 182 template<typename _ForwardIterator> 183 inline _ForwardIterator 184 next(_ForwardIterator __x, typename 185 iterator_traits<_ForwardIterator>::difference_type __n = 1) 186 { 187 std::advance(__x, __n); 188 return __x; 189 } 190 191 template<typename _BidirectionalIterator> 192 inline _BidirectionalIterator 193 prev(_BidirectionalIterator __x, typename 194 iterator_traits<_BidirectionalIterator>::difference_type __n = 1) 195 { 196 std::advance(__x, -__n); 197 return __x; 198 } 199 200 #endif // C++11 201 202 _GLIBCXX_END_NAMESPACE_VERSION 203 } // namespace 204 205 #endif /* _STL_ITERATOR_BASE_FUNCS_H */ 206