1 // Functions used by iterators -*- C++ -*- 2 3 // Copyright (C) 2001-2018 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/assertions.h> 66 67 namespace std _GLIBCXX_VISIBILITY(default) 68 { 69 _GLIBCXX_BEGIN_NAMESPACE_VERSION 70 71 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 72 // Forward declaration for the overloads of __distance. 73 template <typename> struct _List_iterator; 74 template <typename> struct _List_const_iterator; 75 _GLIBCXX_END_NAMESPACE_CONTAINER 76 77 template<typename _InputIterator> 78 inline _GLIBCXX14_CONSTEXPR 79 typename iterator_traits<_InputIterator>::difference_type 80 __distance(_InputIterator __first, _InputIterator __last, 81 input_iterator_tag) 82 { 83 // concept requirements 84 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 85 86 typename iterator_traits<_InputIterator>::difference_type __n = 0; 87 while (__first != __last) 88 { 89 ++__first; 90 ++__n; 91 } 92 return __n; 93 } 94 95 template<typename _RandomAccessIterator> 96 inline _GLIBCXX14_CONSTEXPR 97 typename iterator_traits<_RandomAccessIterator>::difference_type 98 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 99 random_access_iterator_tag) 100 { 101 // concept requirements 102 __glibcxx_function_requires(_RandomAccessIteratorConcept< 103 _RandomAccessIterator>) 104 return __last - __first; 105 } 106 107 #if _GLIBCXX_USE_CXX11_ABI 108 // Forward declaration because of the qualified call in distance. 109 template<typename _Tp> 110 ptrdiff_t 111 __distance(_GLIBCXX_STD_C::_List_iterator<_Tp>, 112 _GLIBCXX_STD_C::_List_iterator<_Tp>, 113 input_iterator_tag); 114 115 template<typename _Tp> 116 ptrdiff_t 117 __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp>, 118 _GLIBCXX_STD_C::_List_const_iterator<_Tp>, 119 input_iterator_tag); 120 #endif 121 122 /** 123 * @brief A generalization of pointer arithmetic. 124 * @param __first An input iterator. 125 * @param __last An input iterator. 126 * @return The distance between them. 127 * 128 * Returns @c n such that __first + n == __last. This requires 129 * that @p __last must be reachable from @p __first. Note that @c 130 * n may be negative. 131 * 132 * For random access iterators, this uses their @c + and @c - operations 133 * and are constant time. For other %iterator classes they are linear time. 134 */ 135 template<typename _InputIterator> 136 inline _GLIBCXX17_CONSTEXPR 137 typename iterator_traits<_InputIterator>::difference_type 138 distance(_InputIterator __first, _InputIterator __last) 139 { 140 // concept requirements -- taken care of in __distance 141 return std::__distance(__first, __last, 142 std::__iterator_category(__first)); 143 } 144 145 template<typename _InputIterator, typename _Distance> 146 inline _GLIBCXX14_CONSTEXPR void 147 __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) 148 { 149 // concept requirements 150 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 151 __glibcxx_assert(__n >= 0); 152 while (__n--) 153 ++__i; 154 } 155 156 template<typename _BidirectionalIterator, typename _Distance> 157 inline _GLIBCXX14_CONSTEXPR void 158 __advance(_BidirectionalIterator& __i, _Distance __n, 159 bidirectional_iterator_tag) 160 { 161 // concept requirements 162 __glibcxx_function_requires(_BidirectionalIteratorConcept< 163 _BidirectionalIterator>) 164 if (__n > 0) 165 while (__n--) 166 ++__i; 167 else 168 while (__n++) 169 --__i; 170 } 171 172 template<typename _RandomAccessIterator, typename _Distance> 173 inline _GLIBCXX14_CONSTEXPR void 174 __advance(_RandomAccessIterator& __i, _Distance __n, 175 random_access_iterator_tag) 176 { 177 // concept requirements 178 __glibcxx_function_requires(_RandomAccessIteratorConcept< 179 _RandomAccessIterator>) 180 if (__builtin_constant_p(__n) && __n == 1) 181 ++__i; 182 else if (__builtin_constant_p(__n) && __n == -1) 183 --__i; 184 else 185 __i += __n; 186 } 187 188 /** 189 * @brief A generalization of pointer arithmetic. 190 * @param __i An input iterator. 191 * @param __n The @a delta by which to change @p __i. 192 * @return Nothing. 193 * 194 * This increments @p i by @p n. For bidirectional and random access 195 * iterators, @p __n may be negative, in which case @p __i is decremented. 196 * 197 * For random access iterators, this uses their @c + and @c - operations 198 * and are constant time. For other %iterator classes they are linear time. 199 */ 200 template<typename _InputIterator, typename _Distance> 201 inline _GLIBCXX17_CONSTEXPR void 202 advance(_InputIterator& __i, _Distance __n) 203 { 204 // concept requirements -- taken care of in __advance 205 typename iterator_traits<_InputIterator>::difference_type __d = __n; 206 std::__advance(__i, __d, std::__iterator_category(__i)); 207 } 208 209 #if __cplusplus >= 201103L 210 211 template<typename _InputIterator> 212 inline _GLIBCXX17_CONSTEXPR _InputIterator 213 next(_InputIterator __x, typename 214 iterator_traits<_InputIterator>::difference_type __n = 1) 215 { 216 // concept requirements 217 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 218 std::advance(__x, __n); 219 return __x; 220 } 221 222 template<typename _BidirectionalIterator> 223 inline _GLIBCXX17_CONSTEXPR _BidirectionalIterator 224 prev(_BidirectionalIterator __x, typename 225 iterator_traits<_BidirectionalIterator>::difference_type __n = 1) 226 { 227 // concept requirements 228 __glibcxx_function_requires(_BidirectionalIteratorConcept< 229 _BidirectionalIterator>) 230 std::advance(__x, -__n); 231 return __x; 232 } 233 234 #endif // C++11 235 236 _GLIBCXX_END_NAMESPACE_VERSION 237 } // namespace 238 239 #endif /* _STL_ITERATOR_BASE_FUNCS_H */ 240