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 |