]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Functions used by iterators -*- C++ -*- |
2 | ||
83ffe9cd | 3 | // Copyright (C) 2001-2023 Free Software Foundation, Inc. |
42526146 PE |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
42526146 PE |
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 | ||
748086b7 JJ |
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. | |
42526146 | 19 | |
748086b7 JJ |
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/>. | |
42526146 | 24 | |
30a20a1e PE |
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 | ||
f910786b | 51 | /** @file bits/stl_iterator_base_funcs.h |
729e3d3f | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{iterator} |
8f94053d PE |
54 | * |
55 | * This file contains all of the general iterator-related utility | |
56 | * functions, such as distance() and advance(). | |
30a20a1e PE |
57 | */ |
58 | ||
046d30f4 PC |
59 | #ifndef _STL_ITERATOR_BASE_FUNCS_H |
60 | #define _STL_ITERATOR_BASE_FUNCS_H 1 | |
30a20a1e | 61 | |
30a20a1e | 62 | #pragma GCC system_header |
7ec62b25 | 63 | |
30a20a1e | 64 | #include <bits/concept_check.h> |
adad2a7d | 65 | #include <debug/assertions.h> |
a4438054 | 66 | #include <bits/stl_iterator_base_types.h> |
30a20a1e | 67 | |
12ffa228 BK |
68 | namespace std _GLIBCXX_VISIBILITY(default) |
69 | { | |
4a15d842 FD |
70 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
71 | ||
194571f1 MG |
72 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
73 | // Forward declaration for the overloads of __distance. | |
74 | template <typename> struct _List_iterator; | |
75 | template <typename> struct _List_const_iterator; | |
76 | _GLIBCXX_END_NAMESPACE_CONTAINER | |
77 | ||
3971a4d2 | 78 | template<typename _InputIterator> |
06db9920 JW |
79 | inline _GLIBCXX14_CONSTEXPR |
80 | typename iterator_traits<_InputIterator>::difference_type | |
3971a4d2 PE |
81 | __distance(_InputIterator __first, _InputIterator __last, |
82 | input_iterator_tag) | |
83 | { | |
84 | // concept requirements | |
3d7c150e | 85 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
ed6814f7 | 86 | |
3971a4d2 | 87 | typename iterator_traits<_InputIterator>::difference_type __n = 0; |
f6592a9e PC |
88 | while (__first != __last) |
89 | { | |
90 | ++__first; | |
91 | ++__n; | |
92 | } | |
3971a4d2 | 93 | return __n; |
02d92e3b | 94 | } |
ed6814f7 | 95 | |
3971a4d2 | 96 | template<typename _RandomAccessIterator> |
6bd8d119 | 97 | __attribute__((__always_inline__)) |
06db9920 JW |
98 | inline _GLIBCXX14_CONSTEXPR |
99 | typename iterator_traits<_RandomAccessIterator>::difference_type | |
3971a4d2 PE |
100 | __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, |
101 | random_access_iterator_tag) | |
102 | { | |
103 | // concept requirements | |
f6592a9e PC |
104 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
105 | _RandomAccessIterator>) | |
3971a4d2 PE |
106 | return __last - __first; |
107 | } | |
ed6814f7 | 108 | |
194571f1 MG |
109 | #if _GLIBCXX_USE_CXX11_ABI |
110 | // Forward declaration because of the qualified call in distance. | |
111 | template<typename _Tp> | |
112 | ptrdiff_t | |
113 | __distance(_GLIBCXX_STD_C::_List_iterator<_Tp>, | |
114 | _GLIBCXX_STD_C::_List_iterator<_Tp>, | |
115 | input_iterator_tag); | |
116 | ||
117 | template<typename _Tp> | |
118 | ptrdiff_t | |
119 | __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp>, | |
120 | _GLIBCXX_STD_C::_List_const_iterator<_Tp>, | |
121 | input_iterator_tag); | |
122 | #endif | |
123 | ||
d9dfd7ad JW |
124 | #if __cplusplus >= 201103L |
125 | // Give better error if std::distance called with a non-Cpp17InputIterator. | |
126 | template<typename _OutputIterator> | |
127 | void | |
128 | __distance(_OutputIterator, _OutputIterator, output_iterator_tag) = delete; | |
129 | #endif | |
130 | ||
3971a4d2 PE |
131 | /** |
132 | * @brief A generalization of pointer arithmetic. | |
93c66bc6 BK |
133 | * @param __first An input iterator. |
134 | * @param __last An input iterator. | |
3971a4d2 PE |
135 | * @return The distance between them. |
136 | * | |
93c66bc6 BK |
137 | * Returns @c n such that __first + n == __last. This requires |
138 | * that @p __last must be reachable from @p __first. Note that @c | |
139 | * n may be negative. | |
3971a4d2 PE |
140 | * |
141 | * For random access iterators, this uses their @c + and @c - operations | |
142 | * and are constant time. For other %iterator classes they are linear time. | |
143 | */ | |
144 | template<typename _InputIterator> | |
6bd8d119 | 145 | _GLIBCXX_NODISCARD __attribute__((__always_inline__)) |
06db9920 JW |
146 | inline _GLIBCXX17_CONSTEXPR |
147 | typename iterator_traits<_InputIterator>::difference_type | |
3971a4d2 PE |
148 | distance(_InputIterator __first, _InputIterator __last) |
149 | { | |
150 | // concept requirements -- taken care of in __distance | |
f6592a9e PC |
151 | return std::__distance(__first, __last, |
152 | std::__iterator_category(__first)); | |
3971a4d2 | 153 | } |
ed6814f7 | 154 | |
08addde6 | 155 | template<typename _InputIterator, typename _Distance> |
06db9920 | 156 | inline _GLIBCXX14_CONSTEXPR void |
08addde6 | 157 | __advance(_InputIterator& __i, _Distance __n, input_iterator_tag) |
3971a4d2 PE |
158 | { |
159 | // concept requirements | |
3d7c150e | 160 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
2f1e8e7c | 161 | __glibcxx_assert(__n >= 0); |
f6592a9e PC |
162 | while (__n--) |
163 | ++__i; | |
3971a4d2 | 164 | } |
ed6814f7 | 165 | |
3971a4d2 | 166 | template<typename _BidirectionalIterator, typename _Distance> |
06db9920 | 167 | inline _GLIBCXX14_CONSTEXPR void |
3971a4d2 | 168 | __advance(_BidirectionalIterator& __i, _Distance __n, |
8f407473 | 169 | bidirectional_iterator_tag) |
3971a4d2 PE |
170 | { |
171 | // concept requirements | |
f6592a9e PC |
172 | __glibcxx_function_requires(_BidirectionalIteratorConcept< |
173 | _BidirectionalIterator>) | |
3971a4d2 | 174 | if (__n > 0) |
83042fca PC |
175 | while (__n--) |
176 | ++__i; | |
3971a4d2 | 177 | else |
83042fca PC |
178 | while (__n++) |
179 | --__i; | |
3971a4d2 | 180 | } |
ed6814f7 | 181 | |
3971a4d2 | 182 | template<typename _RandomAccessIterator, typename _Distance> |
06db9920 | 183 | inline _GLIBCXX14_CONSTEXPR void |
3971a4d2 PE |
184 | __advance(_RandomAccessIterator& __i, _Distance __n, |
185 | random_access_iterator_tag) | |
186 | { | |
187 | // concept requirements | |
f6592a9e PC |
188 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
189 | _RandomAccessIterator>) | |
6c241778 JW |
190 | if (__builtin_constant_p(__n) && __n == 1) |
191 | ++__i; | |
192 | else if (__builtin_constant_p(__n) && __n == -1) | |
193 | --__i; | |
194 | else | |
195 | __i += __n; | |
3971a4d2 | 196 | } |
ed6814f7 | 197 | |
d9dfd7ad JW |
198 | #if __cplusplus >= 201103L |
199 | // Give better error if std::advance called with a non-Cpp17InputIterator. | |
200 | template<typename _OutputIterator, typename _Distance> | |
201 | void | |
202 | __advance(_OutputIterator&, _Distance, output_iterator_tag) = delete; | |
203 | #endif | |
204 | ||
3971a4d2 PE |
205 | /** |
206 | * @brief A generalization of pointer arithmetic. | |
93c66bc6 BK |
207 | * @param __i An input iterator. |
208 | * @param __n The @a delta by which to change @p __i. | |
3971a4d2 PE |
209 | * @return Nothing. |
210 | * | |
211 | * This increments @p i by @p n. For bidirectional and random access | |
93c66bc6 | 212 | * iterators, @p __n may be negative, in which case @p __i is decremented. |
3971a4d2 PE |
213 | * |
214 | * For random access iterators, this uses their @c + and @c - operations | |
215 | * and are constant time. For other %iterator classes they are linear time. | |
216 | */ | |
217 | template<typename _InputIterator, typename _Distance> | |
6bd8d119 | 218 | __attribute__((__always_inline__)) |
06db9920 | 219 | inline _GLIBCXX17_CONSTEXPR void |
3971a4d2 PE |
220 | advance(_InputIterator& __i, _Distance __n) |
221 | { | |
222 | // concept requirements -- taken care of in __advance | |
8f407473 PC |
223 | typename iterator_traits<_InputIterator>::difference_type __d = __n; |
224 | std::__advance(__i, __d, std::__iterator_category(__i)); | |
3971a4d2 | 225 | } |
3cbc7af0 | 226 | |
734f5023 | 227 | #if __cplusplus >= 201103L |
7ec62b25 | 228 | |
7b7b60c8 | 229 | template<typename _InputIterator> |
6bd8d119 | 230 | _GLIBCXX_NODISCARD [[__gnu__::__always_inline__]] |
7b7b60c8 VV |
231 | inline _GLIBCXX17_CONSTEXPR _InputIterator |
232 | next(_InputIterator __x, typename | |
233 | iterator_traits<_InputIterator>::difference_type __n = 1) | |
65b0413a | 234 | { |
500dc9a6 | 235 | // concept requirements |
7b7b60c8 | 236 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
65b0413a CF |
237 | std::advance(__x, __n); |
238 | return __x; | |
239 | } | |
240 | ||
241 | template<typename _BidirectionalIterator> | |
6bd8d119 | 242 | _GLIBCXX_NODISCARD [[__gnu__::__always_inline__]] |
06db9920 | 243 | inline _GLIBCXX17_CONSTEXPR _BidirectionalIterator |
1a9e603e PC |
244 | prev(_BidirectionalIterator __x, typename |
245 | iterator_traits<_BidirectionalIterator>::difference_type __n = 1) | |
65b0413a | 246 | { |
500dc9a6 JW |
247 | // concept requirements |
248 | __glibcxx_function_requires(_BidirectionalIteratorConcept< | |
249 | _BidirectionalIterator>) | |
65b0413a CF |
250 | std::advance(__x, -__n); |
251 | return __x; | |
252 | } | |
65b0413a | 253 | |
734f5023 | 254 | #endif // C++11 |
7ec62b25 | 255 | |
12ffa228 BK |
256 | _GLIBCXX_END_NAMESPACE_VERSION |
257 | } // namespace | |
ccef29e8 | 258 | |
046d30f4 | 259 | #endif /* _STL_ITERATOR_BASE_FUNCS_H */ |