]>
Commit | Line | Data |
---|---|---|
c60cd1dc | 1 | // Core algorithmic facilities -*- C++ -*- |
42526146 | 2 | |
a945c346 | 3 | // Copyright (C) 2001-2024 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 | |
725dc051 BK |
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_algobase.h |
729e3d3f | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{algorithm} |
725dc051 BK |
54 | */ |
55 | ||
046d30f4 PC |
56 | #ifndef _STL_ALGOBASE_H |
57 | #define _STL_ALGOBASE_H 1 | |
725dc051 | 58 | |
9cfeea6e | 59 | #include <bits/c++config.h> |
39b8cd70 | 60 | #include <bits/functexcept.h> |
badd64ad | 61 | #include <bits/cpp_type_traits.h> |
105c6331 | 62 | #include <ext/type_traits.h> |
6725add5 | 63 | #include <ext/numeric_traits.h> |
8ad7097c | 64 | #include <bits/stl_pair.h> |
4f39bf5c | 65 | #include <bits/stl_iterator_base_types.h> |
30a20a1e | 66 | #include <bits/stl_iterator_base_funcs.h> |
725dc051 | 67 | #include <bits/stl_iterator.h> |
30a20a1e | 68 | #include <bits/concept_check.h> |
285b36d6 | 69 | #include <debug/debug.h> |
e5795ce4 | 70 | #include <bits/move.h> // For std::swap |
ea89b248 | 71 | #include <bits/predefined_ops.h> |
ff2e7f19 MG |
72 | #if __cplusplus >= 201103L |
73 | # include <type_traits> | |
74 | #endif | |
769fae76 JW |
75 | #if __cplusplus >= 201402L |
76 | # include <bit> // std::__bit_width | |
77 | #endif | |
78 | #if __cplusplus >= 202002L | |
f1355c8d JW |
79 | # include <compare> |
80 | #endif | |
3a6b0f54 | 81 | |
12ffa228 BK |
82 | namespace std _GLIBCXX_VISIBILITY(default) |
83 | { | |
84 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
575665ff | 85 | |
3a66e68a ESR |
86 | /* |
87 | * A constexpr wrapper for __builtin_memcmp. | |
88 | * @param __num The number of elements of type _Tp (not bytes). | |
89 | */ | |
d112e173 | 90 | template<typename _Tp, typename _Up> |
3a66e68a ESR |
91 | _GLIBCXX14_CONSTEXPR |
92 | inline int | |
d112e173 | 93 | __memcmp(const _Tp* __first1, const _Up* __first2, size_t __num) |
3a66e68a | 94 | { |
d112e173 JW |
95 | #if __cplusplus >= 201103L |
96 | static_assert(sizeof(_Tp) == sizeof(_Up), "can be compared with memcmp"); | |
97 | #endif | |
3a66e68a ESR |
98 | #ifdef __cpp_lib_is_constant_evaluated |
99 | if (std::is_constant_evaluated()) | |
100 | { | |
101 | for(; __num > 0; ++__first1, ++__first2, --__num) | |
102 | if (*__first1 != *__first2) | |
103 | return *__first1 < *__first2 ? -1 : 1; | |
104 | return 0; | |
105 | } | |
106 | else | |
107 | #endif | |
108 | return __builtin_memcmp(__first1, __first2, sizeof(_Tp) * __num); | |
109 | } | |
110 | ||
734f5023 | 111 | #if __cplusplus < 201103L |
575665ff CJ |
112 | // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a |
113 | // nutshell, we are partially implementing the resolution of DR 187, | |
114 | // when it's safe, i.e., the value_types are equal. | |
115 | template<bool _BoolType> | |
116 | struct __iter_swap | |
117 | { | |
118 | template<typename _ForwardIterator1, typename _ForwardIterator2> | |
e5795ce4 FD |
119 | static void |
120 | iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) | |
121 | { | |
122 | typedef typename iterator_traits<_ForwardIterator1>::value_type | |
123 | _ValueType1; | |
124 | _ValueType1 __tmp = *__a; | |
125 | *__a = *__b; | |
126 | *__b = __tmp; | |
575665ff CJ |
127 | } |
128 | }; | |
129 | ||
130 | template<> | |
131 | struct __iter_swap<true> | |
132 | { | |
133 | template<typename _ForwardIterator1, typename _ForwardIterator2> | |
e5795ce4 FD |
134 | static void |
135 | iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) | |
136 | { | |
137 | swap(*__a, *__b); | |
138 | } | |
575665ff | 139 | }; |
d1aa7705 | 140 | #endif // C++03 |
575665ff | 141 | |
729e3d3f PE |
142 | /** |
143 | * @brief Swaps the contents of two iterators. | |
5b9daa7e | 144 | * @ingroup mutating_algorithms |
93c66bc6 BK |
145 | * @param __a An iterator. |
146 | * @param __b Another iterator. | |
729e3d3f PE |
147 | * @return Nothing. |
148 | * | |
149 | * This function swaps the values pointed to by two iterators, not the | |
150 | * iterators themselves. | |
151 | */ | |
08addde6 | 152 | template<typename _ForwardIterator1, typename _ForwardIterator2> |
7a91c710 | 153 | _GLIBCXX20_CONSTEXPR |
02d92e3b | 154 | inline void |
08addde6 | 155 | iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) |
02d92e3b | 156 | { |
02d92e3b | 157 | // concept requirements |
ffa67767 PC |
158 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
159 | _ForwardIterator1>) | |
160 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
161 | _ForwardIterator2>) | |
93d9a365 | 162 | |
734f5023 | 163 | #if __cplusplus < 201103L |
93d9a365 PC |
164 | typedef typename iterator_traits<_ForwardIterator1>::value_type |
165 | _ValueType1; | |
166 | typedef typename iterator_traits<_ForwardIterator2>::value_type | |
167 | _ValueType2; | |
168 | ||
ffa67767 PC |
169 | __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, |
170 | _ValueType2>) | |
171 | __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, | |
172 | _ValueType1>) | |
aed63147 CJ |
173 | |
174 | typedef typename iterator_traits<_ForwardIterator1>::reference | |
175 | _ReferenceType1; | |
176 | typedef typename iterator_traits<_ForwardIterator2>::reference | |
177 | _ReferenceType2; | |
d22a3166 PC |
178 | std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value |
179 | && __are_same<_ValueType1&, _ReferenceType1>::__value | |
180 | && __are_same<_ValueType2&, _ReferenceType2>::__value>:: | |
575665ff | 181 | iter_swap(__a, __b); |
93d9a365 | 182 | #else |
d1aa7705 JW |
183 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
184 | // 187. iter_swap underspecified | |
93d9a365 PC |
185 | swap(*__a, *__b); |
186 | #endif | |
02d92e3b SW |
187 | } |
188 | ||
91b0b94a PC |
189 | /** |
190 | * @brief Swap the elements of two sequences. | |
5b9daa7e | 191 | * @ingroup mutating_algorithms |
93c66bc6 BK |
192 | * @param __first1 A forward iterator. |
193 | * @param __last1 A forward iterator. | |
194 | * @param __first2 A forward iterator. | |
91b0b94a PC |
195 | * @return An iterator equal to @p first2+(last1-first1). |
196 | * | |
197 | * Swaps each element in the range @p [first1,last1) with the | |
198 | * corresponding element in the range @p [first2,(last1-first1)). | |
199 | * The ranges must not overlap. | |
200 | */ | |
201 | template<typename _ForwardIterator1, typename _ForwardIterator2> | |
7a91c710 | 202 | _GLIBCXX20_CONSTEXPR |
91b0b94a PC |
203 | _ForwardIterator2 |
204 | swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, | |
205 | _ForwardIterator2 __first2) | |
206 | { | |
207 | // concept requirements | |
208 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
209 | _ForwardIterator1>) | |
210 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
211 | _ForwardIterator2>) | |
91b0b94a PC |
212 | __glibcxx_requires_valid_range(__first1, __last1); |
213 | ||
f970a17d | 214 | for (; __first1 != __last1; ++__first1, (void)++__first2) |
91b0b94a PC |
215 | std::iter_swap(__first1, __first2); |
216 | return __first2; | |
217 | } | |
218 | ||
729e3d3f PE |
219 | /** |
220 | * @brief This does what you think it does. | |
5b9daa7e | 221 | * @ingroup sorting_algorithms |
93c66bc6 BK |
222 | * @param __a A thing of arbitrary type. |
223 | * @param __b Another thing of arbitrary type. | |
729e3d3f PE |
224 | * @return The lesser of the parameters. |
225 | * | |
226 | * This is the simple classic generic implementation. It will work on | |
227 | * temporary expressions, since they are only evaluated once, unlike a | |
228 | * preprocessor macro. | |
229 | */ | |
02d92e3b | 230 | template<typename _Tp> |
df483ebd | 231 | _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR |
02d92e3b SW |
232 | inline const _Tp& |
233 | min(const _Tp& __a, const _Tp& __b) | |
234 | { | |
235 | // concept requirements | |
3d7c150e | 236 | __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
4fd97a63 PC |
237 | //return __b < __a ? __b : __a; |
238 | if (__b < __a) | |
239 | return __b; | |
240 | return __a; | |
02d92e3b SW |
241 | } |
242 | ||
1b4a6975 PE |
243 | /** |
244 | * @brief This does what you think it does. | |
5b9daa7e | 245 | * @ingroup sorting_algorithms |
93c66bc6 BK |
246 | * @param __a A thing of arbitrary type. |
247 | * @param __b Another thing of arbitrary type. | |
1b4a6975 PE |
248 | * @return The greater of the parameters. |
249 | * | |
250 | * This is the simple classic generic implementation. It will work on | |
251 | * temporary expressions, since they are only evaluated once, unlike a | |
252 | * preprocessor macro. | |
253 | */ | |
02d92e3b | 254 | template<typename _Tp> |
df483ebd | 255 | _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR |
02d92e3b | 256 | inline const _Tp& |
ed6814f7 | 257 | max(const _Tp& __a, const _Tp& __b) |
02d92e3b SW |
258 | { |
259 | // concept requirements | |
3d7c150e | 260 | __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
4fd97a63 PC |
261 | //return __a < __b ? __b : __a; |
262 | if (__a < __b) | |
263 | return __b; | |
264 | return __a; | |
02d92e3b SW |
265 | } |
266 | ||
1b4a6975 PE |
267 | /** |
268 | * @brief This does what you think it does. | |
5b9daa7e | 269 | * @ingroup sorting_algorithms |
93c66bc6 BK |
270 | * @param __a A thing of arbitrary type. |
271 | * @param __b Another thing of arbitrary type. | |
272 | * @param __comp A @link comparison_functors comparison functor@endlink. | |
1b4a6975 PE |
273 | * @return The lesser of the parameters. |
274 | * | |
275 | * This will work on temporary expressions, since they are only evaluated | |
276 | * once, unlike a preprocessor macro. | |
277 | */ | |
02d92e3b | 278 | template<typename _Tp, typename _Compare> |
df483ebd | 279 | _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR |
02d92e3b SW |
280 | inline const _Tp& |
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp) | |
4fd97a63 PC |
282 | { |
283 | //return __comp(__b, __a) ? __b : __a; | |
284 | if (__comp(__b, __a)) | |
285 | return __b; | |
286 | return __a; | |
287 | } | |
02d92e3b | 288 | |
1b4a6975 PE |
289 | /** |
290 | * @brief This does what you think it does. | |
5b9daa7e | 291 | * @ingroup sorting_algorithms |
93c66bc6 BK |
292 | * @param __a A thing of arbitrary type. |
293 | * @param __b Another thing of arbitrary type. | |
294 | * @param __comp A @link comparison_functors comparison functor@endlink. | |
1b4a6975 PE |
295 | * @return The greater of the parameters. |
296 | * | |
297 | * This will work on temporary expressions, since they are only evaluated | |
298 | * once, unlike a preprocessor macro. | |
299 | */ | |
02d92e3b | 300 | template<typename _Tp, typename _Compare> |
df483ebd | 301 | _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR |
02d92e3b SW |
302 | inline const _Tp& |
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp) | |
4fd97a63 PC |
304 | { |
305 | //return __comp(__a, __b) ? __b : __a; | |
306 | if (__comp(__a, __b)) | |
307 | return __b; | |
308 | return __a; | |
309 | } | |
02d92e3b | 310 | |
e1c444fe FD |
311 | // Fallback implementation of the function in bits/stl_iterator.h used to |
312 | // remove the __normal_iterator wrapper. See copy, fill, ... | |
a2fe9203 | 313 | template<typename _Iterator> |
3a66e68a | 314 | _GLIBCXX20_CONSTEXPR |
e1c444fe | 315 | inline _Iterator |
6989b63f | 316 | __niter_base(_Iterator __it) |
ff2e7f19 | 317 | _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value) |
e1c444fe | 318 | { return __it; } |
6989b63f | 319 | |
9739d7eb | 320 | #if __cplusplus < 201103L |
4e05c918 FD |
321 | template<typename _Ite, typename _Seq> |
322 | _Ite | |
323 | __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, | |
324 | std::random_access_iterator_tag>&); | |
325 | ||
9739d7eb FD |
326 | template<typename _Ite, typename _Cont, typename _Seq> |
327 | _Ite | |
328 | __niter_base(const ::__gnu_debug::_Safe_iterator< | |
329 | ::__gnu_cxx::__normal_iterator<_Ite, _Cont>, _Seq, | |
330 | std::random_access_iterator_tag>&); | |
331 | #else | |
332 | template<typename _Ite, typename _Seq> | |
333 | _GLIBCXX20_CONSTEXPR | |
334 | decltype(std::__niter_base(std::declval<_Ite>())) | |
335 | __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, | |
336 | std::random_access_iterator_tag>&) | |
337 | noexcept(std::is_nothrow_copy_constructible<_Ite>::value); | |
338 | #endif | |
339 | ||
315aadc8 FD |
340 | // Reverse the __niter_base transformation to get a |
341 | // __normal_iterator back again (this assumes that __normal_iterator | |
342 | // is only used to wrap random access iterators, like pointers). | |
343 | template<typename _From, typename _To> | |
3a66e68a | 344 | _GLIBCXX20_CONSTEXPR |
315aadc8 FD |
345 | inline _From |
346 | __niter_wrap(_From __from, _To __res) | |
ca5f5099 | 347 | { return __from + (std::__niter_base(__res) - std::__niter_base(__from)); } |
315aadc8 FD |
348 | |
349 | // No need to wrap, iterator already has the right type. | |
350 | template<typename _Iterator> | |
3a66e68a | 351 | _GLIBCXX20_CONSTEXPR |
315aadc8 | 352 | inline _Iterator |
e874029d | 353 | __niter_wrap(const _Iterator&, _Iterator __res) |
315aadc8 FD |
354 | { return __res; } |
355 | ||
5e91e92e | 356 | // All of these auxiliary structs serve two purposes. (1) Replace |
02d92e3b SW |
357 | // calls to copy with memmove whenever possible. (Memmove, not memcpy, |
358 | // because the input and output ranges are permitted to overlap.) | |
359 | // (2) If we're using random access iterators, then write the loop as | |
360 | // a for loop with an explicit count. | |
361 | ||
61f5cb23 | 362 | template<bool _IsMove, bool _IsSimple, typename _Category> |
3c167a8b | 363 | struct __copy_move |
02d92e3b | 364 | { |
695e0fbf | 365 | template<typename _II, typename _OI> |
3a66e68a | 366 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
367 | static _OI |
368 | __copy_m(_II __first, _II __last, _OI __result) | |
369 | { | |
f970a17d | 370 | for (; __first != __last; ++__result, (void)++__first) |
5f6d5f0a PC |
371 | *__result = *__first; |
372 | return __result; | |
373 | } | |
374 | }; | |
375 | ||
734f5023 | 376 | #if __cplusplus >= 201103L |
5f6d5f0a PC |
377 | template<typename _Category> |
378 | struct __copy_move<true, false, _Category> | |
379 | { | |
380 | template<typename _II, typename _OI> | |
3a66e68a | 381 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
382 | static _OI |
383 | __copy_m(_II __first, _II __last, _OI __result) | |
384 | { | |
f970a17d | 385 | for (; __first != __last; ++__result, (void)++__first) |
5f6d5f0a PC |
386 | *__result = std::move(*__first); |
387 | return __result; | |
388 | } | |
389 | }; | |
390 | #endif | |
391 | ||
392 | template<> | |
393 | struct __copy_move<false, false, random_access_iterator_tag> | |
394 | { | |
395 | template<typename _II, typename _OI> | |
3a66e68a | 396 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
397 | static _OI |
398 | __copy_m(_II __first, _II __last, _OI __result) | |
399 | { | |
5f6d5f0a PC |
400 | typedef typename iterator_traits<_II>::difference_type _Distance; |
401 | for(_Distance __n = __last - __first; __n > 0; --__n) | |
402 | { | |
403 | *__result = *__first; | |
404 | ++__first; | |
405 | ++__result; | |
406 | } | |
695e0fbf PC |
407 | return __result; |
408 | } | |
822a11a1 JW |
409 | |
410 | template<typename _Tp, typename _Up> | |
411 | static void | |
412 | __assign_one(_Tp* __to, _Up* __from) | |
413 | { *__to = *__from; } | |
695e0fbf | 414 | }; |
02d92e3b | 415 | |
734f5023 | 416 | #if __cplusplus >= 201103L |
5f6d5f0a PC |
417 | template<> |
418 | struct __copy_move<true, false, random_access_iterator_tag> | |
02d92e3b | 419 | { |
695e0fbf | 420 | template<typename _II, typename _OI> |
3a66e68a | 421 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
422 | static _OI |
423 | __copy_m(_II __first, _II __last, _OI __result) | |
424 | { | |
695e0fbf PC |
425 | typedef typename iterator_traits<_II>::difference_type _Distance; |
426 | for(_Distance __n = __last - __first; __n > 0; --__n) | |
427 | { | |
5f6d5f0a | 428 | *__result = std::move(*__first); |
695e0fbf PC |
429 | ++__first; |
430 | ++__result; | |
431 | } | |
432 | return __result; | |
46c4e5d6 | 433 | } |
822a11a1 JW |
434 | |
435 | template<typename _Tp, typename _Up> | |
436 | static void | |
437 | __assign_one(_Tp* __to, _Up* __from) | |
438 | { *__to = std::move(*__from); } | |
695e0fbf | 439 | }; |
5f6d5f0a | 440 | #endif |
02d92e3b | 441 | |
f0112db9 PC |
442 | template<bool _IsMove> |
443 | struct __copy_move<_IsMove, true, random_access_iterator_tag> | |
02d92e3b | 444 | { |
822a11a1 | 445 | template<typename _Tp, typename _Up> |
3a66e68a | 446 | _GLIBCXX20_CONSTEXPR |
822a11a1 JW |
447 | static _Up* |
448 | __copy_m(_Tp* __first, _Tp* __last, _Up* __result) | |
e5795ce4 | 449 | { |
f7d601a5 | 450 | const ptrdiff_t _Num = __last - __first; |
822a11a1 | 451 | if (__builtin_expect(_Num > 1, true)) |
490350a1 | 452 | __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); |
822a11a1 JW |
453 | else if (_Num == 1) |
454 | std::__copy_move<_IsMove, false, random_access_iterator_tag>:: | |
455 | __assign_one(__result, __first); | |
f7d601a5 | 456 | return __result + _Num; |
695e0fbf PC |
457 | } |
458 | }; | |
02d92e3b | 459 | |
72a54e5e FD |
460 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
461 | ||
462 | template<typename _Tp, typename _Ref, typename _Ptr> | |
463 | struct _Deque_iterator; | |
464 | ||
465 | struct _Bit_iterator; | |
466 | ||
467 | _GLIBCXX_END_NAMESPACE_CONTAINER | |
468 | ||
cf0fded5 | 469 | #if _GLIBCXX_HOSTED |
0002d5d2 | 470 | // Helpers for streambuf iterators (either istream or ostream). |
39b8cd70 PC |
471 | // NB: avoid including <iosfwd>, relatively large. |
472 | template<typename _CharT> | |
473 | struct char_traits; | |
474 | ||
475 | template<typename _CharT, typename _Traits> | |
476 | class istreambuf_iterator; | |
477 | ||
478 | template<typename _CharT, typename _Traits> | |
479 | class ostreambuf_iterator; | |
480 | ||
f0112db9 | 481 | template<bool _IsMove, typename _CharT> |
e5795ce4 | 482 | typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
39b8cd70 | 483 | ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type |
f0112db9 PC |
484 | __copy_move_a2(_CharT*, _CharT*, |
485 | ostreambuf_iterator<_CharT, char_traits<_CharT> >); | |
0002d5d2 | 486 | |
f0112db9 | 487 | template<bool _IsMove, typename _CharT> |
e5795ce4 | 488 | typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
39b8cd70 | 489 | ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type |
f0112db9 PC |
490 | __copy_move_a2(const _CharT*, const _CharT*, |
491 | ostreambuf_iterator<_CharT, char_traits<_CharT> >); | |
0002d5d2 | 492 | |
f0112db9 | 493 | template<bool _IsMove, typename _CharT> |
f56fe8ff PC |
494 | typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
495 | _CharT*>::__type | |
f0112db9 PC |
496 | __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, |
497 | istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); | |
498 | ||
4e05c918 FD |
499 | template<bool _IsMove, typename _CharT> |
500 | typename __gnu_cxx::__enable_if< | |
501 | __is_char<_CharT>::__value, | |
502 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type | |
503 | __copy_move_a2( | |
504 | istreambuf_iterator<_CharT, char_traits<_CharT> >, | |
505 | istreambuf_iterator<_CharT, char_traits<_CharT> >, | |
506 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>); | |
cf0fded5 | 507 | #endif // HOSTED |
4e05c918 | 508 | |
f0112db9 | 509 | template<bool _IsMove, typename _II, typename _OI> |
3a66e68a | 510 | _GLIBCXX20_CONSTEXPR |
f0112db9 PC |
511 | inline _OI |
512 | __copy_move_a2(_II __first, _II __last, _OI __result) | |
6004c17b | 513 | { |
490350a1 JW |
514 | typedef typename iterator_traits<_II>::iterator_category _Category; |
515 | #ifdef __cpp_lib_is_constant_evaluated | |
516 | if (std::is_constant_evaluated()) | |
517 | return std::__copy_move<_IsMove, false, _Category>:: | |
518 | __copy_m(__first, __last, __result); | |
519 | #endif | |
462f6c20 | 520 | return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value, |
6004c17b FD |
521 | _Category>::__copy_m(__first, __last, __result); |
522 | } | |
523 | ||
6004c17b FD |
524 | template<bool _IsMove, |
525 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> | |
526 | _OI | |
527 | __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, | |
528 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, | |
529 | _OI); | |
530 | ||
531 | template<bool _IsMove, | |
532 | typename _ITp, typename _IRef, typename _IPtr, typename _OTp> | |
533 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> | |
534 | __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, | |
535 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, | |
536 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>); | |
537 | ||
538 | template<bool _IsMove, typename _II, typename _Tp> | |
539 | typename __gnu_cxx::__enable_if< | |
540 | __is_random_access_iter<_II>::__value, | |
541 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type | |
542 | __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>); | |
543 | ||
544 | template<bool _IsMove, typename _II, typename _OI> | |
545 | _GLIBCXX20_CONSTEXPR | |
546 | inline _OI | |
547 | __copy_move_a1(_II __first, _II __last, _OI __result) | |
548 | { return std::__copy_move_a2<_IsMove>(__first, __last, __result); } | |
549 | ||
550 | template<bool _IsMove, typename _II, typename _OI> | |
551 | _GLIBCXX20_CONSTEXPR | |
552 | inline _OI | |
553 | __copy_move_a(_II __first, _II __last, _OI __result) | |
f0112db9 | 554 | { |
315aadc8 | 555 | return std::__niter_wrap(__result, |
6004c17b FD |
556 | std::__copy_move_a1<_IsMove>(std::__niter_base(__first), |
557 | std::__niter_base(__last), | |
558 | std::__niter_base(__result))); | |
f0112db9 | 559 | } |
0002d5d2 | 560 | |
6004c17b FD |
561 | template<bool _IsMove, |
562 | typename _Ite, typename _Seq, typename _Cat, typename _OI> | |
7d00a592 | 563 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
564 | _OI |
565 | __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, | |
566 | const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, | |
567 | _OI); | |
568 | ||
569 | template<bool _IsMove, | |
570 | typename _II, typename _Ite, typename _Seq, typename _Cat> | |
7d00a592 | 571 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
572 | __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> |
573 | __copy_move_a(_II, _II, | |
574 | const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&); | |
575 | ||
576 | template<bool _IsMove, | |
577 | typename _IIte, typename _ISeq, typename _ICat, | |
578 | typename _OIte, typename _OSeq, typename _OCat> | |
7d00a592 | 579 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
580 | ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> |
581 | __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, | |
582 | const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, | |
583 | const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&); | |
584 | ||
4e05c918 FD |
585 | template<typename _InputIterator, typename _Size, typename _OutputIterator> |
586 | _GLIBCXX20_CONSTEXPR | |
587 | _OutputIterator | |
588 | __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result, | |
589 | bool) | |
590 | { | |
591 | if (__n > 0) | |
592 | { | |
593 | while (true) | |
594 | { | |
595 | *__result = *__first; | |
596 | ++__result; | |
597 | if (--__n > 0) | |
598 | ++__first; | |
599 | else | |
600 | break; | |
601 | } | |
602 | } | |
603 | return __result; | |
604 | } | |
605 | ||
cf0fded5 | 606 | #if _GLIBCXX_HOSTED |
4e05c918 FD |
607 | template<typename _CharT, typename _Size> |
608 | typename __gnu_cxx::__enable_if< | |
609 | __is_char<_CharT>::__value, _CharT*>::__type | |
610 | __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, | |
611 | _Size, _CharT*, bool); | |
612 | ||
613 | template<typename _CharT, typename _Size> | |
614 | typename __gnu_cxx::__enable_if< | |
615 | __is_char<_CharT>::__value, | |
616 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type | |
617 | __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size, | |
618 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>, | |
619 | bool); | |
cf0fded5 | 620 | #endif |
4e05c918 | 621 | |
1b4a6975 PE |
622 | /** |
623 | * @brief Copies the range [first,last) into result. | |
5b9daa7e | 624 | * @ingroup mutating_algorithms |
93c66bc6 BK |
625 | * @param __first An input iterator. |
626 | * @param __last An input iterator. | |
627 | * @param __result An output iterator. | |
ae3967ca | 628 | * @return result + (last - first) |
1b4a6975 PE |
629 | * |
630 | * This inline function will boil down to a call to @c memmove whenever | |
631 | * possible. Failing that, if random access iterators are passed, then the | |
632 | * loop count will be known (and therefore a candidate for compiler | |
119dbb1f JQ |
633 | * optimizations such as unrolling). Result may not be contained within |
634 | * [first,last); the copy_backward function should be used instead. | |
635 | * | |
636 | * Note that the end of the output range is permitted to be contained | |
637 | * within [first,last). | |
1b4a6975 | 638 | */ |
d22a3166 | 639 | template<typename _II, typename _OI> |
3a66e68a | 640 | _GLIBCXX20_CONSTEXPR |
d22a3166 PC |
641 | inline _OI |
642 | copy(_II __first, _II __last, _OI __result) | |
02d92e3b SW |
643 | { |
644 | // concept requirements | |
d22a3166 PC |
645 | __glibcxx_function_requires(_InputIteratorConcept<_II>) |
646 | __glibcxx_function_requires(_OutputIteratorConcept<_OI, | |
45a8cd25 | 647 | typename iterator_traits<_II>::reference>) |
84a9d3b6 | 648 | __glibcxx_requires_can_increment_range(__first, __last, __result); |
02d92e3b | 649 | |
6004c17b | 650 | return std::__copy_move_a<__is_move_iterator<_II>::__value> |
84a9d3b6 | 651 | (std::__miter_base(__first), std::__miter_base(__last), __result); |
02d92e3b | 652 | } |
0002d5d2 | 653 | |
734f5023 | 654 | #if __cplusplus >= 201103L |
3c167a8b PC |
655 | /** |
656 | * @brief Moves the range [first,last) into result. | |
5b9daa7e | 657 | * @ingroup mutating_algorithms |
93c66bc6 BK |
658 | * @param __first An input iterator. |
659 | * @param __last An input iterator. | |
660 | * @param __result An output iterator. | |
ae3967ca | 661 | * @return result + (last - first) |
3c167a8b PC |
662 | * |
663 | * This inline function will boil down to a call to @c memmove whenever | |
664 | * possible. Failing that, if random access iterators are passed, then the | |
665 | * loop count will be known (and therefore a candidate for compiler | |
666 | * optimizations such as unrolling). Result may not be contained within | |
667 | * [first,last); the move_backward function should be used instead. | |
668 | * | |
669 | * Note that the end of the output range is permitted to be contained | |
670 | * within [first,last). | |
671 | */ | |
672 | template<typename _II, typename _OI> | |
3a66e68a | 673 | _GLIBCXX20_CONSTEXPR |
3c167a8b PC |
674 | inline _OI |
675 | move(_II __first, _II __last, _OI __result) | |
676 | { | |
677 | // concept requirements | |
678 | __glibcxx_function_requires(_InputIteratorConcept<_II>) | |
679 | __glibcxx_function_requires(_OutputIteratorConcept<_OI, | |
45a8cd25 | 680 | typename iterator_traits<_II>::value_type&&>) |
84a9d3b6 | 681 | __glibcxx_requires_can_increment_range(__first, __last, __result); |
3c167a8b | 682 | |
6004c17b FD |
683 | return std::__copy_move_a<true>(std::__miter_base(__first), |
684 | std::__miter_base(__last), __result); | |
3c167a8b | 685 | } |
245a5fe5 PC |
686 | |
687 | #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) | |
688 | #else | |
689 | #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) | |
3c167a8b | 690 | #endif |
d22a3166 | 691 | |
6004c17b | 692 | template<bool _IsMove, bool _IsSimple, typename _Category> |
3c167a8b | 693 | struct __copy_move_backward |
badd64ad PC |
694 | { |
695 | template<typename _BI1, typename _BI2> | |
3a66e68a | 696 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
697 | static _BI2 |
698 | __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) | |
699 | { | |
badd64ad | 700 | while (__first != __last) |
5f6d5f0a | 701 | *--__result = *--__last; |
badd64ad PC |
702 | return __result; |
703 | } | |
02d92e3b SW |
704 | }; |
705 | ||
734f5023 | 706 | #if __cplusplus >= 201103L |
5f6d5f0a PC |
707 | template<typename _Category> |
708 | struct __copy_move_backward<true, false, _Category> | |
709 | { | |
710 | template<typename _BI1, typename _BI2> | |
3a66e68a | 711 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
712 | static _BI2 |
713 | __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) | |
714 | { | |
5f6d5f0a PC |
715 | while (__first != __last) |
716 | *--__result = std::move(*--__last); | |
717 | return __result; | |
718 | } | |
719 | }; | |
720 | #endif | |
721 | ||
722 | template<> | |
723 | struct __copy_move_backward<false, false, random_access_iterator_tag> | |
badd64ad PC |
724 | { |
725 | template<typename _BI1, typename _BI2> | |
3a66e68a | 726 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
727 | static _BI2 |
728 | __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) | |
729 | { | |
3a66e68a ESR |
730 | typename iterator_traits<_BI1>::difference_type |
731 | __n = __last - __first; | |
732 | for (; __n > 0; --__n) | |
5f6d5f0a | 733 | *--__result = *--__last; |
badd64ad PC |
734 | return __result; |
735 | } | |
02d92e3b SW |
736 | }; |
737 | ||
734f5023 | 738 | #if __cplusplus >= 201103L |
5f6d5f0a PC |
739 | template<> |
740 | struct __copy_move_backward<true, false, random_access_iterator_tag> | |
741 | { | |
742 | template<typename _BI1, typename _BI2> | |
3a66e68a | 743 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
744 | static _BI2 |
745 | __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) | |
746 | { | |
3a66e68a ESR |
747 | typename iterator_traits<_BI1>::difference_type |
748 | __n = __last - __first; | |
749 | for (; __n > 0; --__n) | |
5f6d5f0a PC |
750 | *--__result = std::move(*--__last); |
751 | return __result; | |
752 | } | |
753 | }; | |
754 | #endif | |
755 | ||
f0112db9 PC |
756 | template<bool _IsMove> |
757 | struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> | |
badd64ad | 758 | { |
822a11a1 | 759 | template<typename _Tp, typename _Up> |
3a66e68a | 760 | _GLIBCXX20_CONSTEXPR |
822a11a1 JW |
761 | static _Up* |
762 | __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result) | |
e5795ce4 | 763 | { |
badd64ad | 764 | const ptrdiff_t _Num = __last - __first; |
822a11a1 | 765 | if (__builtin_expect(_Num > 1, true)) |
490350a1 | 766 | __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); |
822a11a1 JW |
767 | else if (_Num == 1) |
768 | std::__copy_move<_IsMove, false, random_access_iterator_tag>:: | |
769 | __assign_one(__result - 1, __first); | |
badd64ad PC |
770 | return __result - _Num; |
771 | } | |
02d92e3b SW |
772 | }; |
773 | ||
f0112db9 | 774 | template<bool _IsMove, typename _BI1, typename _BI2> |
3a66e68a | 775 | _GLIBCXX20_CONSTEXPR |
02d92e3b | 776 | inline _BI2 |
6004c17b | 777 | __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) |
02d92e3b | 778 | { |
490350a1 JW |
779 | typedef typename iterator_traits<_BI1>::iterator_category _Category; |
780 | #ifdef __cpp_lib_is_constant_evaluated | |
781 | if (std::is_constant_evaluated()) | |
782 | return std::__copy_move_backward<_IsMove, false, _Category>:: | |
783 | __copy_move_b(__first, __last, __result); | |
784 | #endif | |
462f6c20 JW |
785 | return std::__copy_move_backward<_IsMove, |
786 | __memcpyable<_BI2, _BI1>::__value, | |
e5795ce4 | 787 | _Category>::__copy_move_b(__first, |
e75ea710 PC |
788 | __last, |
789 | __result); | |
02d92e3b SW |
790 | } |
791 | ||
f0112db9 | 792 | template<bool _IsMove, typename _BI1, typename _BI2> |
3a66e68a | 793 | _GLIBCXX20_CONSTEXPR |
f0112db9 | 794 | inline _BI2 |
6004c17b FD |
795 | __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result) |
796 | { return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); } | |
797 | ||
798 | template<bool _IsMove, | |
799 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> | |
800 | _OI | |
801 | __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, | |
802 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, | |
803 | _OI); | |
804 | ||
805 | template<bool _IsMove, | |
806 | typename _ITp, typename _IRef, typename _IPtr, typename _OTp> | |
807 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> | |
808 | __copy_move_backward_a1( | |
809 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, | |
810 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, | |
811 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>); | |
812 | ||
813 | template<bool _IsMove, typename _II, typename _Tp> | |
814 | typename __gnu_cxx::__enable_if< | |
815 | __is_random_access_iter<_II>::__value, | |
816 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type | |
817 | __copy_move_backward_a1(_II, _II, | |
818 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>); | |
819 | ||
820 | template<bool _IsMove, typename _II, typename _OI> | |
821 | _GLIBCXX20_CONSTEXPR | |
822 | inline _OI | |
823 | __copy_move_backward_a(_II __first, _II __last, _OI __result) | |
f0112db9 | 824 | { |
315aadc8 | 825 | return std::__niter_wrap(__result, |
6004c17b | 826 | std::__copy_move_backward_a1<_IsMove> |
6989b63f PC |
827 | (std::__niter_base(__first), std::__niter_base(__last), |
828 | std::__niter_base(__result))); | |
f0112db9 PC |
829 | } |
830 | ||
6004c17b FD |
831 | template<bool _IsMove, |
832 | typename _Ite, typename _Seq, typename _Cat, typename _OI> | |
7d00a592 | 833 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
834 | _OI |
835 | __copy_move_backward_a( | |
836 | const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, | |
837 | const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, | |
838 | _OI); | |
839 | ||
840 | template<bool _IsMove, | |
841 | typename _II, typename _Ite, typename _Seq, typename _Cat> | |
7d00a592 | 842 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
843 | __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> |
844 | __copy_move_backward_a(_II, _II, | |
845 | const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&); | |
846 | ||
847 | template<bool _IsMove, | |
848 | typename _IIte, typename _ISeq, typename _ICat, | |
849 | typename _OIte, typename _OSeq, typename _OCat> | |
7d00a592 | 850 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
851 | ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> |
852 | __copy_move_backward_a( | |
853 | const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, | |
854 | const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, | |
855 | const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&); | |
856 | ||
1b4a6975 PE |
857 | /** |
858 | * @brief Copies the range [first,last) into result. | |
5b9daa7e | 859 | * @ingroup mutating_algorithms |
93c66bc6 BK |
860 | * @param __first A bidirectional iterator. |
861 | * @param __last A bidirectional iterator. | |
862 | * @param __result A bidirectional iterator. | |
ae3967ca | 863 | * @return result - (last - first) |
1b4a6975 PE |
864 | * |
865 | * The function has the same effect as copy, but starts at the end of the | |
866 | * range and works its way to the start, returning the start of the result. | |
867 | * This inline function will boil down to a call to @c memmove whenever | |
868 | * possible. Failing that, if random access iterators are passed, then the | |
869 | * loop count will be known (and therefore a candidate for compiler | |
870 | * optimizations such as unrolling). | |
119dbb1f | 871 | * |
9a7fb488 | 872 | * Result may not be in the range (first,last]. Use copy instead. Note |
119dbb1f | 873 | * that the start of the output range may overlap [first,last). |
1b4a6975 | 874 | */ |
f0112db9 | 875 | template<typename _BI1, typename _BI2> |
3a66e68a | 876 | _GLIBCXX20_CONSTEXPR |
02d92e3b SW |
877 | inline _BI2 |
878 | copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) | |
879 | { | |
880 | // concept requirements | |
3d7c150e BK |
881 | __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) |
882 | __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) | |
45a8cd25 JW |
883 | __glibcxx_function_requires(_OutputIteratorConcept<_BI2, |
884 | typename iterator_traits<_BI1>::reference>) | |
84a9d3b6 | 885 | __glibcxx_requires_can_decrement_range(__first, __last, __result); |
02d92e3b | 886 | |
6004c17b | 887 | return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value> |
84a9d3b6 | 888 | (std::__miter_base(__first), std::__miter_base(__last), __result); |
02d92e3b SW |
889 | } |
890 | ||
734f5023 | 891 | #if __cplusplus >= 201103L |
3c167a8b PC |
892 | /** |
893 | * @brief Moves the range [first,last) into result. | |
5b9daa7e | 894 | * @ingroup mutating_algorithms |
93c66bc6 BK |
895 | * @param __first A bidirectional iterator. |
896 | * @param __last A bidirectional iterator. | |
897 | * @param __result A bidirectional iterator. | |
ae3967ca | 898 | * @return result - (last - first) |
3c167a8b PC |
899 | * |
900 | * The function has the same effect as move, but starts at the end of the | |
901 | * range and works its way to the start, returning the start of the result. | |
902 | * This inline function will boil down to a call to @c memmove whenever | |
903 | * possible. Failing that, if random access iterators are passed, then the | |
904 | * loop count will be known (and therefore a candidate for compiler | |
905 | * optimizations such as unrolling). | |
906 | * | |
848ca96f | 907 | * Result may not be in the range (first,last]. Use move instead. Note |
3c167a8b PC |
908 | * that the start of the output range may overlap [first,last). |
909 | */ | |
910 | template<typename _BI1, typename _BI2> | |
3a66e68a | 911 | _GLIBCXX20_CONSTEXPR |
3c167a8b PC |
912 | inline _BI2 |
913 | move_backward(_BI1 __first, _BI1 __last, _BI2 __result) | |
914 | { | |
915 | // concept requirements | |
916 | __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) | |
917 | __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) | |
45a8cd25 JW |
918 | __glibcxx_function_requires(_OutputIteratorConcept<_BI2, |
919 | typename iterator_traits<_BI1>::value_type&&>) | |
84a9d3b6 | 920 | __glibcxx_requires_can_decrement_range(__first, __last, __result); |
3c167a8b | 921 | |
6004c17b FD |
922 | return std::__copy_move_backward_a<true>(std::__miter_base(__first), |
923 | std::__miter_base(__last), | |
924 | __result); | |
3c167a8b | 925 | } |
245a5fe5 PC |
926 | |
927 | #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) | |
928 | #else | |
929 | #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) | |
3c167a8b | 930 | #endif |
e9e90c1f | 931 | |
b3743181 JW |
932 | #pragma GCC diagnostic push |
933 | #pragma GCC diagnostic ignored "-Wc++17-extensions" | |
394033f8 | 934 | template<typename _ForwardIterator, typename _Tp> |
3a66e68a | 935 | _GLIBCXX20_CONSTEXPR |
b3743181 | 936 | inline void |
6004c17b FD |
937 | __fill_a1(_ForwardIterator __first, _ForwardIterator __last, |
938 | const _Tp& __value) | |
02d92e3b | 939 | { |
68854071 JW |
940 | #pragma GCC diagnostic push |
941 | #pragma GCC diagnostic ignored "-Wlong-long" | |
b3743181 JW |
942 | // We can optimize this loop by moving the load from __value outside |
943 | // the loop, but only if we know that making that copy is trivial, | |
944 | // and the assignment in the loop is also trivial (so that the identity | |
945 | // of the operand doesn't matter). | |
946 | const bool __load_outside_loop = | |
947 | #if __has_builtin(__is_trivially_constructible) \ | |
948 | && __has_builtin(__is_trivially_assignable) | |
949 | __is_trivially_constructible(_Tp, const _Tp&) | |
950 | && __is_trivially_assignable(__decltype(*__first), const _Tp&) | |
951 | #else | |
952 | __is_trivially_copyable(_Tp) | |
953 | && __is_same(_Tp, __typeof__(*__first)) | |
954 | #endif | |
955 | && sizeof(_Tp) <= sizeof(long long); | |
68854071 | 956 | #pragma GCC diagnostic pop |
b3743181 JW |
957 | |
958 | // When the condition is true, we use a copy of __value, | |
959 | // otherwise we just use another reference. | |
960 | typedef typename __gnu_cxx::__conditional_type<__load_outside_loop, | |
961 | const _Tp, | |
962 | const _Tp&>::__type _Up; | |
963 | _Up __val(__value); | |
394033f8 | 964 | for (; __first != __last; ++__first) |
b3743181 | 965 | *__first = __val; |
02d92e3b | 966 | } |
b3743181 | 967 | #pragma GCC diagnostic pop |
02d92e3b | 968 | |
d22a3166 | 969 | // Specialization: for char types we can use memset. |
394033f8 | 970 | template<typename _Tp> |
22b6b5d6 | 971 | _GLIBCXX20_CONSTEXPR |
394033f8 PC |
972 | inline typename |
973 | __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type | |
6004c17b | 974 | __fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c) |
b14f95a8 PC |
975 | { |
976 | const _Tp __tmp = __c; | |
22b6b5d6 JW |
977 | #if __cpp_lib_is_constant_evaluated |
978 | if (std::is_constant_evaluated()) | |
979 | { | |
980 | for (; __first != __last; ++__first) | |
981 | *__first = __tmp; | |
982 | return; | |
983 | } | |
984 | #endif | |
5d946f42 JW |
985 | if (const size_t __len = __last - __first) |
986 | __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len); | |
b14f95a8 | 987 | } |
725dc051 | 988 | |
6004c17b FD |
989 | template<typename _Ite, typename _Cont, typename _Tp> |
990 | _GLIBCXX20_CONSTEXPR | |
991 | inline void | |
992 | __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first, | |
993 | ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last, | |
994 | const _Tp& __value) | |
995 | { std::__fill_a1(__first.base(), __last.base(), __value); } | |
996 | ||
997 | template<typename _Tp, typename _VTp> | |
998 | void | |
999 | __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&, | |
1000 | const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&, | |
1001 | const _VTp&); | |
1002 | ||
1ae8edf5 | 1003 | _GLIBCXX20_CONSTEXPR |
72a54e5e FD |
1004 | void |
1005 | __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator, | |
1006 | const bool&); | |
1007 | ||
6004c17b FD |
1008 | template<typename _FIte, typename _Tp> |
1009 | _GLIBCXX20_CONSTEXPR | |
1010 | inline void | |
1011 | __fill_a(_FIte __first, _FIte __last, const _Tp& __value) | |
1012 | { std::__fill_a1(__first, __last, __value); } | |
1013 | ||
1014 | template<typename _Ite, typename _Seq, typename _Cat, typename _Tp> | |
7d00a592 | 1015 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
1016 | void |
1017 | __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, | |
1018 | const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, | |
1019 | const _Tp&); | |
1020 | ||
e9e90c1f PC |
1021 | /** |
1022 | * @brief Fills the range [first,last) with copies of value. | |
5b9daa7e | 1023 | * @ingroup mutating_algorithms |
93c66bc6 BK |
1024 | * @param __first A forward iterator. |
1025 | * @param __last A forward iterator. | |
1026 | * @param __value A reference-to-const of arbitrary type. | |
e9e90c1f PC |
1027 | * @return Nothing. |
1028 | * | |
1029 | * This function fills a range with copies of the same value. For char | |
1030 | * types filling contiguous areas of memory, this becomes an inline call | |
1031 | * to @c memset or @c wmemset. | |
1032 | */ | |
1033 | template<typename _ForwardIterator, typename _Tp> | |
3a66e68a | 1034 | _GLIBCXX20_CONSTEXPR |
e9e90c1f PC |
1035 | inline void |
1036 | fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) | |
1037 | { | |
1038 | // concept requirements | |
1039 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< | |
1040 | _ForwardIterator>) | |
1041 | __glibcxx_requires_valid_range(__first, __last); | |
1042 | ||
6004c17b | 1043 | std::__fill_a(__first, __last, __value); |
e9e90c1f PC |
1044 | } |
1045 | ||
68854071 JW |
1046 | #pragma GCC diagnostic push |
1047 | #pragma GCC diagnostic ignored "-Wlong-long" | |
846541dd JW |
1048 | // Used by fill_n, generate_n, etc. to convert _Size to an integral type: |
1049 | inline _GLIBCXX_CONSTEXPR int | |
1050 | __size_to_integer(int __n) { return __n; } | |
1051 | inline _GLIBCXX_CONSTEXPR unsigned | |
1052 | __size_to_integer(unsigned __n) { return __n; } | |
1053 | inline _GLIBCXX_CONSTEXPR long | |
1054 | __size_to_integer(long __n) { return __n; } | |
1055 | inline _GLIBCXX_CONSTEXPR unsigned long | |
1056 | __size_to_integer(unsigned long __n) { return __n; } | |
1057 | inline _GLIBCXX_CONSTEXPR long long | |
1058 | __size_to_integer(long long __n) { return __n; } | |
1059 | inline _GLIBCXX_CONSTEXPR unsigned long long | |
1060 | __size_to_integer(unsigned long long __n) { return __n; } | |
1061 | ||
1062 | #if defined(__GLIBCXX_TYPE_INT_N_0) | |
42167831 | 1063 | __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0 |
846541dd | 1064 | __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) { return __n; } |
42167831 | 1065 | __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0 |
846541dd JW |
1066 | __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n) { return __n; } |
1067 | #endif | |
1068 | #if defined(__GLIBCXX_TYPE_INT_N_1) | |
42167831 | 1069 | __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1 |
846541dd | 1070 | __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) { return __n; } |
42167831 | 1071 | __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1 |
846541dd JW |
1072 | __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n) { return __n; } |
1073 | #endif | |
1074 | #if defined(__GLIBCXX_TYPE_INT_N_2) | |
42167831 | 1075 | __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2 |
846541dd | 1076 | __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) { return __n; } |
42167831 | 1077 | __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2 |
846541dd JW |
1078 | __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n) { return __n; } |
1079 | #endif | |
1080 | #if defined(__GLIBCXX_TYPE_INT_N_3) | |
42167831 | 1081 | __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3 |
846541dd | 1082 | __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) { return __n; } |
42167831 | 1083 | __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3 |
846541dd JW |
1084 | __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n) { return __n; } |
1085 | #endif | |
1086 | ||
1087 | inline _GLIBCXX_CONSTEXPR long long | |
5b621508 | 1088 | __size_to_integer(float __n) { return (long long)__n; } |
846541dd | 1089 | inline _GLIBCXX_CONSTEXPR long long |
5b621508 | 1090 | __size_to_integer(double __n) { return (long long)__n; } |
846541dd | 1091 | inline _GLIBCXX_CONSTEXPR long long |
5b621508 | 1092 | __size_to_integer(long double __n) { return (long long)__n; } |
846541dd | 1093 | #if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128) |
42167831 | 1094 | __extension__ inline _GLIBCXX_CONSTEXPR long long |
5b621508 | 1095 | __size_to_integer(__float128 __n) { return (long long)__n; } |
846541dd | 1096 | #endif |
68854071 | 1097 | #pragma GCC diagnostic pop |
846541dd | 1098 | |
b3743181 JW |
1099 | #pragma GCC diagnostic push |
1100 | #pragma GCC diagnostic ignored "-Wc++17-extensions" | |
68854071 | 1101 | #pragma GCC diagnostic ignored "-Wlong-long" |
6e539e23 | 1102 | template<typename _OutputIterator, typename _Size, typename _Tp> |
3a66e68a | 1103 | _GLIBCXX20_CONSTEXPR |
b3743181 | 1104 | inline _OutputIterator |
6004c17b | 1105 | __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value) |
02d92e3b | 1106 | { |
b3743181 JW |
1107 | // See std::__fill_a1 for explanation of this condition. |
1108 | const bool __load_outside_loop = | |
1109 | #if __has_builtin(__is_trivially_constructible) \ | |
1110 | && __has_builtin(__is_trivially_assignable) | |
1111 | __is_trivially_constructible(_Tp, const _Tp&) | |
1112 | && __is_trivially_assignable(__decltype(*__first), const _Tp&) | |
1113 | #else | |
1114 | __is_trivially_copyable(_Tp) | |
1115 | && __is_same(_Tp, __typeof__(*__first)) | |
1116 | #endif | |
1117 | && sizeof(_Tp) <= sizeof(long long); | |
1118 | ||
1119 | // When the condition is true, we use a copy of __value, | |
1120 | // otherwise we just use another reference. | |
1121 | typedef typename __gnu_cxx::__conditional_type<__load_outside_loop, | |
1122 | const _Tp, | |
1123 | const _Tp&>::__type _Up; | |
1124 | _Up __val(__value); | |
846541dd | 1125 | for (; __n > 0; --__n, (void) ++__first) |
b3743181 | 1126 | *__first = __val; |
394033f8 | 1127 | return __first; |
02d92e3b | 1128 | } |
b3743181 | 1129 | #pragma GCC diagnostic pop |
02d92e3b | 1130 | |
6004c17b FD |
1131 | template<typename _Ite, typename _Seq, typename _Cat, typename _Size, |
1132 | typename _Tp> | |
7d00a592 | 1133 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
1134 | ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> |
1135 | __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, | |
1136 | _Size __n, const _Tp& __value, | |
1137 | std::input_iterator_tag); | |
1138 | ||
1139 | template<typename _OutputIterator, typename _Size, typename _Tp> | |
3a66e68a | 1140 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
1141 | inline _OutputIterator |
1142 | __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, | |
1143 | std::output_iterator_tag) | |
1144 | { | |
1145 | #if __cplusplus >= 201103L | |
1146 | static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); | |
1147 | #endif | |
1148 | return __fill_n_a1(__first, __n, __value); | |
1149 | } | |
1150 | ||
1151 | template<typename _OutputIterator, typename _Size, typename _Tp> | |
1152 | _GLIBCXX20_CONSTEXPR | |
1153 | inline _OutputIterator | |
1154 | __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, | |
1155 | std::input_iterator_tag) | |
1156 | { | |
1157 | #if __cplusplus >= 201103L | |
1158 | static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); | |
1159 | #endif | |
1160 | return __fill_n_a1(__first, __n, __value); | |
1161 | } | |
1162 | ||
1163 | template<typename _OutputIterator, typename _Size, typename _Tp> | |
1164 | _GLIBCXX20_CONSTEXPR | |
1165 | inline _OutputIterator | |
1166 | __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, | |
1167 | std::random_access_iterator_tag) | |
e9e90c1f | 1168 | { |
6004c17b FD |
1169 | #if __cplusplus >= 201103L |
1170 | static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); | |
1171 | #endif | |
1172 | if (__n <= 0) | |
1173 | return __first; | |
1174 | ||
1175 | __glibcxx_requires_can_increment(__first, __n); | |
1176 | ||
1177 | std::__fill_a(__first, __first + __n, __value); | |
e9e90c1f PC |
1178 | return __first + __n; |
1179 | } | |
1180 | ||
e9e90c1f PC |
1181 | /** |
1182 | * @brief Fills the range [first,first+n) with copies of value. | |
5b9daa7e | 1183 | * @ingroup mutating_algorithms |
93c66bc6 BK |
1184 | * @param __first An output iterator. |
1185 | * @param __n The count of copies to perform. | |
1186 | * @param __value A reference-to-const of arbitrary type. | |
e9e90c1f PC |
1187 | * @return The iterator at first+n. |
1188 | * | |
1189 | * This function fills a range with copies of the same value. For char | |
1190 | * types filling contiguous areas of memory, this becomes an inline call | |
846541dd | 1191 | * to @c memset or @c wmemset. |
82ab4b64 | 1192 | * |
846541dd | 1193 | * If @p __n is negative, the function does nothing. |
e9e90c1f | 1194 | */ |
846541dd JW |
1195 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1196 | // DR 865. More algorithms that throw away information | |
1197 | // DR 426. search_n(), fill_n(), and generate_n() with negative n | |
d22a3166 | 1198 | template<typename _OI, typename _Size, typename _Tp> |
3a66e68a | 1199 | _GLIBCXX20_CONSTEXPR |
d22a3166 PC |
1200 | inline _OI |
1201 | fill_n(_OI __first, _Size __n, const _Tp& __value) | |
e9e90c1f PC |
1202 | { |
1203 | // concept requirements | |
45a8cd25 | 1204 | __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>) |
e9e90c1f | 1205 | |
6004c17b FD |
1206 | return std::__fill_n_a(__first, std::__size_to_integer(__n), __value, |
1207 | std::__iterator_category(__first)); | |
e9e90c1f | 1208 | } |
02d92e3b | 1209 | |
d22a3166 PC |
1210 | template<bool _BoolType> |
1211 | struct __equal | |
1212 | { | |
1213 | template<typename _II1, typename _II2> | |
3a66e68a | 1214 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
1215 | static bool |
1216 | equal(_II1 __first1, _II1 __last1, _II2 __first2) | |
1217 | { | |
d67be443 | 1218 | for (; __first1 != __last1; ++__first1, (void) ++__first2) |
d22a3166 PC |
1219 | if (!(*__first1 == *__first2)) |
1220 | return false; | |
1221 | return true; | |
1222 | } | |
1223 | }; | |
1224 | ||
1225 | template<> | |
1226 | struct __equal<true> | |
1227 | { | |
1228 | template<typename _Tp> | |
3a66e68a | 1229 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
1230 | static bool |
1231 | equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) | |
1232 | { | |
12fc64ac | 1233 | if (const size_t __len = (__last1 - __first1)) |
3a66e68a | 1234 | return !std::__memcmp(__first1, __first2, __len); |
12fc64ac | 1235 | return true; |
d22a3166 PC |
1236 | } |
1237 | }; | |
1238 | ||
6004c17b FD |
1239 | template<typename _Tp, typename _Ref, typename _Ptr, typename _II> |
1240 | typename __gnu_cxx::__enable_if< | |
1241 | __is_random_access_iter<_II>::__value, bool>::__type | |
1242 | __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, | |
1243 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, | |
1244 | _II); | |
1245 | ||
1246 | template<typename _Tp1, typename _Ref1, typename _Ptr1, | |
1247 | typename _Tp2, typename _Ref2, typename _Ptr2> | |
1248 | bool | |
1249 | __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, | |
1250 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, | |
1251 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); | |
1252 | ||
1253 | template<typename _II, typename _Tp, typename _Ref, typename _Ptr> | |
1254 | typename __gnu_cxx::__enable_if< | |
1255 | __is_random_access_iter<_II>::__value, bool>::__type | |
1256 | __equal_aux1(_II, _II, | |
1257 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>); | |
1258 | ||
d22a3166 | 1259 | template<typename _II1, typename _II2> |
3a66e68a | 1260 | _GLIBCXX20_CONSTEXPR |
d22a3166 | 1261 | inline bool |
6004c17b | 1262 | __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2) |
d22a3166 PC |
1263 | { |
1264 | typedef typename iterator_traits<_II1>::value_type _ValueType1; | |
92b2342a | 1265 | const bool __simple = ((__is_integer<_ValueType1>::__value |
5f10547e | 1266 | #if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer) |
fab60eaa JW |
1267 | || __is_pointer(_ValueType1) |
1268 | #endif | |
1269 | #if __glibcxx_byte && __glibcxx_type_trait_variable_templates | |
1270 | // bits/cpp_type_traits.h declares std::byte | |
1271 | || is_same_v<_ValueType1, byte> | |
5f10547e JW |
1272 | #endif |
1273 | ) && __memcmpable<_II1, _II2>::__value); | |
d22a3166 PC |
1274 | return std::__equal<__simple>::equal(__first1, __last1, __first2); |
1275 | } | |
1276 | ||
6004c17b FD |
1277 | template<typename _II1, typename _II2> |
1278 | _GLIBCXX20_CONSTEXPR | |
1279 | inline bool | |
1280 | __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) | |
1281 | { | |
1282 | return std::__equal_aux1(std::__niter_base(__first1), | |
1283 | std::__niter_base(__last1), | |
1284 | std::__niter_base(__first2)); | |
1285 | } | |
1286 | ||
1287 | template<typename _II1, typename _Seq1, typename _Cat1, typename _II2> | |
7d00a592 | 1288 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
1289 | bool |
1290 | __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, | |
1291 | const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, | |
1292 | _II2); | |
1293 | ||
1294 | template<typename _II1, typename _II2, typename _Seq2, typename _Cat2> | |
7d00a592 | 1295 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
1296 | bool |
1297 | __equal_aux(_II1, _II1, | |
1298 | const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&); | |
1299 | ||
1300 | template<typename _II1, typename _Seq1, typename _Cat1, | |
1301 | typename _II2, typename _Seq2, typename _Cat2> | |
7d00a592 | 1302 | _GLIBCXX20_CONSTEXPR |
6004c17b FD |
1303 | bool |
1304 | __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, | |
1305 | const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, | |
1306 | const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&); | |
1307 | ||
c2ba9709 JS |
1308 | template<typename, typename> |
1309 | struct __lc_rai | |
1310 | { | |
1311 | template<typename _II1, typename _II2> | |
3a66e68a | 1312 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
1313 | static _II1 |
1314 | __newlast1(_II1, _II1 __last1, _II2, _II2) | |
1315 | { return __last1; } | |
c2ba9709 JS |
1316 | |
1317 | template<typename _II> | |
3a66e68a | 1318 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
1319 | static bool |
1320 | __cnd2(_II __first, _II __last) | |
1321 | { return __first != __last; } | |
c2ba9709 JS |
1322 | }; |
1323 | ||
1324 | template<> | |
1325 | struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> | |
1326 | { | |
1327 | template<typename _RAI1, typename _RAI2> | |
3a66e68a | 1328 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
1329 | static _RAI1 |
1330 | __newlast1(_RAI1 __first1, _RAI1 __last1, | |
c2ba9709 | 1331 | _RAI2 __first2, _RAI2 __last2) |
e5795ce4 | 1332 | { |
c2ba9709 JS |
1333 | const typename iterator_traits<_RAI1>::difference_type |
1334 | __diff1 = __last1 - __first1; | |
1335 | const typename iterator_traits<_RAI2>::difference_type | |
1336 | __diff2 = __last2 - __first2; | |
1337 | return __diff2 < __diff1 ? __first1 + __diff2 : __last1; | |
1338 | } | |
1339 | ||
1340 | template<typename _RAI> | |
3a66e68a | 1341 | static _GLIBCXX20_CONSTEXPR bool |
e5795ce4 FD |
1342 | __cnd2(_RAI, _RAI) |
1343 | { return true; } | |
c2ba9709 JS |
1344 | }; |
1345 | ||
ea89b248 | 1346 | template<typename _II1, typename _II2, typename _Compare> |
3a66e68a | 1347 | _GLIBCXX20_CONSTEXPR |
ea89b248 FD |
1348 | bool |
1349 | __lexicographical_compare_impl(_II1 __first1, _II1 __last1, | |
1350 | _II2 __first2, _II2 __last2, | |
1351 | _Compare __comp) | |
1352 | { | |
1353 | typedef typename iterator_traits<_II1>::iterator_category _Category1; | |
1354 | typedef typename iterator_traits<_II2>::iterator_category _Category2; | |
1355 | typedef std::__lc_rai<_Category1, _Category2> __rai_type; | |
1356 | ||
1357 | __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); | |
1358 | for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); | |
f970a17d | 1359 | ++__first1, (void)++__first2) |
ea89b248 FD |
1360 | { |
1361 | if (__comp(__first1, __first2)) | |
1362 | return true; | |
1363 | if (__comp(__first2, __first1)) | |
1364 | return false; | |
1365 | } | |
1366 | return __first1 == __last1 && __first2 != __last2; | |
1367 | } | |
1368 | ||
478b2b9c PC |
1369 | template<bool _BoolType> |
1370 | struct __lexicographical_compare | |
1371 | { | |
1372 | template<typename _II1, typename _II2> | |
3a66e68a | 1373 | _GLIBCXX20_CONSTEXPR |
113f0a63 JW |
1374 | static bool |
1375 | __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) | |
1376 | { | |
1377 | using __gnu_cxx::__ops::__iter_less_iter; | |
1378 | return std::__lexicographical_compare_impl(__first1, __last1, | |
1379 | __first2, __last2, | |
1380 | __iter_less_iter()); | |
1381 | } | |
3a391adf FD |
1382 | |
1383 | template<typename _II1, typename _II2> | |
1384 | _GLIBCXX20_CONSTEXPR | |
1385 | static int | |
1386 | __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) | |
1387 | { | |
1388 | while (__first1 != __last1) | |
1389 | { | |
1390 | if (__first2 == __last2) | |
1391 | return +1; | |
1392 | if (*__first1 < *__first2) | |
1393 | return -1; | |
1394 | if (*__first2 < *__first1) | |
1395 | return +1; | |
1396 | ++__first1; | |
1397 | ++__first2; | |
1398 | } | |
1399 | return int(__first2 == __last2) - 1; | |
1400 | } | |
478b2b9c PC |
1401 | }; |
1402 | ||
1403 | template<> | |
1404 | struct __lexicographical_compare<true> | |
1405 | { | |
1406 | template<typename _Tp, typename _Up> | |
3a66e68a | 1407 | _GLIBCXX20_CONSTEXPR |
e5795ce4 FD |
1408 | static bool |
1409 | __lc(const _Tp* __first1, const _Tp* __last1, | |
478b2b9c | 1410 | const _Up* __first2, const _Up* __last2) |
3a391adf FD |
1411 | { return __3way(__first1, __last1, __first2, __last2) < 0; } |
1412 | ||
1413 | template<typename _Tp, typename _Up> | |
1414 | _GLIBCXX20_CONSTEXPR | |
1415 | static ptrdiff_t | |
1416 | __3way(const _Tp* __first1, const _Tp* __last1, | |
1417 | const _Up* __first2, const _Up* __last2) | |
478b2b9c PC |
1418 | { |
1419 | const size_t __len1 = __last1 - __first1; | |
1420 | const size_t __len2 = __last2 - __first2; | |
12fc64ac | 1421 | if (const size_t __len = std::min(__len1, __len2)) |
3a66e68a | 1422 | if (int __result = std::__memcmp(__first1, __first2, __len)) |
3a391adf FD |
1423 | return __result; |
1424 | return ptrdiff_t(__len1 - __len2); | |
478b2b9c PC |
1425 | } |
1426 | }; | |
1427 | ||
1428 | template<typename _II1, typename _II2> | |
3a66e68a | 1429 | _GLIBCXX20_CONSTEXPR |
478b2b9c | 1430 | inline bool |
3a391adf FD |
1431 | __lexicographical_compare_aux1(_II1 __first1, _II1 __last1, |
1432 | _II2 __first2, _II2 __last2) | |
478b2b9c PC |
1433 | { |
1434 | typedef typename iterator_traits<_II1>::value_type _ValueType1; | |
1435 | typedef typename iterator_traits<_II2>::value_type _ValueType2; | |
5f10547e | 1436 | #if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer) |
478b2b9c | 1437 | const bool __simple = |
2f983fa6 | 1438 | (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value |
5f10547e | 1439 | && __is_pointer(_II1) && __is_pointer(_II2) |
7ffa63df | 1440 | #if __cplusplus > 201703L && __glibcxx_concepts |
462f6c20 JW |
1441 | // For C++20 iterator_traits<volatile T*>::value_type is non-volatile |
1442 | // so __is_byte<T> could be true, but we can't use memcmp with | |
1443 | // volatile data. | |
1444 | && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>> | |
1445 | && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>> | |
1446 | #endif | |
1447 | ); | |
5f10547e JW |
1448 | #else |
1449 | const bool __simple = false; | |
1450 | #endif | |
478b2b9c PC |
1451 | |
1452 | return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, | |
1453 | __first2, __last2); | |
1454 | } | |
1455 | ||
3a391adf FD |
1456 | template<typename _Tp1, typename _Ref1, typename _Ptr1, |
1457 | typename _Tp2> | |
1458 | bool | |
1459 | __lexicographical_compare_aux1( | |
1460 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, | |
1461 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, | |
1462 | _Tp2*, _Tp2*); | |
1463 | ||
1464 | template<typename _Tp1, | |
1465 | typename _Tp2, typename _Ref2, typename _Ptr2> | |
1466 | bool | |
1467 | __lexicographical_compare_aux1(_Tp1*, _Tp1*, | |
1468 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>, | |
1469 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); | |
1470 | ||
1471 | template<typename _Tp1, typename _Ref1, typename _Ptr1, | |
1472 | typename _Tp2, typename _Ref2, typename _Ptr2> | |
1473 | bool | |
1474 | __lexicographical_compare_aux1( | |
1475 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, | |
1476 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, | |
1477 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>, | |
1478 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); | |
1479 | ||
1480 | template<typename _II1, typename _II2> | |
1481 | _GLIBCXX20_CONSTEXPR | |
1482 | inline bool | |
1483 | __lexicographical_compare_aux(_II1 __first1, _II1 __last1, | |
1484 | _II2 __first2, _II2 __last2) | |
1485 | { | |
1486 | return std::__lexicographical_compare_aux1(std::__niter_base(__first1), | |
1487 | std::__niter_base(__last1), | |
1488 | std::__niter_base(__first2), | |
1489 | std::__niter_base(__last2)); | |
1490 | } | |
1491 | ||
1492 | template<typename _Iter1, typename _Seq1, typename _Cat1, | |
1493 | typename _II2> | |
7d00a592 | 1494 | _GLIBCXX20_CONSTEXPR |
3a391adf FD |
1495 | bool |
1496 | __lexicographical_compare_aux( | |
1497 | const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, | |
1498 | const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, | |
1499 | _II2, _II2); | |
1500 | ||
1501 | template<typename _II1, | |
1502 | typename _Iter2, typename _Seq2, typename _Cat2> | |
7d00a592 | 1503 | _GLIBCXX20_CONSTEXPR |
3a391adf FD |
1504 | bool |
1505 | __lexicographical_compare_aux( | |
1506 | _II1, _II1, | |
1507 | const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&, | |
1508 | const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&); | |
1509 | ||
1510 | template<typename _Iter1, typename _Seq1, typename _Cat1, | |
1511 | typename _Iter2, typename _Seq2, typename _Cat2> | |
7d00a592 | 1512 | _GLIBCXX20_CONSTEXPR |
3a391adf FD |
1513 | bool |
1514 | __lexicographical_compare_aux( | |
1515 | const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, | |
1516 | const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, | |
1517 | const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&, | |
1518 | const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&); | |
1519 | ||
ea89b248 | 1520 | template<typename _ForwardIterator, typename _Tp, typename _Compare> |
3a66e68a | 1521 | _GLIBCXX20_CONSTEXPR |
247d8075 | 1522 | _ForwardIterator |
ea89b248 FD |
1523 | __lower_bound(_ForwardIterator __first, _ForwardIterator __last, |
1524 | const _Tp& __val, _Compare __comp) | |
247d8075 | 1525 | { |
247d8075 PC |
1526 | typedef typename iterator_traits<_ForwardIterator>::difference_type |
1527 | _DistanceType; | |
1528 | ||
247d8075 | 1529 | _DistanceType __len = std::distance(__first, __last); |
247d8075 PC |
1530 | |
1531 | while (__len > 0) | |
1532 | { | |
1ed78d6c CY |
1533 | _DistanceType __half = __len >> 1; |
1534 | _ForwardIterator __middle = __first; | |
247d8075 | 1535 | std::advance(__middle, __half); |
ea89b248 | 1536 | if (__comp(__middle, __val)) |
247d8075 PC |
1537 | { |
1538 | __first = __middle; | |
1539 | ++__first; | |
1540 | __len = __len - __half - 1; | |
1541 | } | |
1542 | else | |
1543 | __len = __half; | |
1544 | } | |
1545 | return __first; | |
1546 | } | |
1547 | ||
ea89b248 FD |
1548 | /** |
1549 | * @brief Finds the first position in which @a val could be inserted | |
1550 | * without changing the ordering. | |
1551 | * @param __first An iterator. | |
1552 | * @param __last Another iterator. | |
1553 | * @param __val The search term. | |
1554 | * @return An iterator pointing to the first element <em>not less | |
e5795ce4 | 1555 | * than</em> @a val, or end() if every element is less than |
ea89b248 FD |
1556 | * @a val. |
1557 | * @ingroup binary_search_algorithms | |
1558 | */ | |
1559 | template<typename _ForwardIterator, typename _Tp> | |
df483ebd | 1560 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
3bd2644c | 1561 | inline _ForwardIterator |
ea89b248 FD |
1562 | lower_bound(_ForwardIterator __first, _ForwardIterator __last, |
1563 | const _Tp& __val) | |
1564 | { | |
1565 | // concept requirements | |
1566 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) | |
1567 | __glibcxx_function_requires(_LessThanOpConcept< | |
1568 | typename iterator_traits<_ForwardIterator>::value_type, _Tp>) | |
1569 | __glibcxx_requires_partitioned_lower(__first, __last, __val); | |
1570 | ||
1571 | return std::__lower_bound(__first, __last, __val, | |
1572 | __gnu_cxx::__ops::__iter_less_val()); | |
1573 | } | |
1574 | ||
247d8075 PC |
1575 | /// This is a helper function for the sort routines and for random.tcc. |
1576 | // Precondition: __n > 0. | |
769fae76 JW |
1577 | template<typename _Tp> |
1578 | inline _GLIBCXX_CONSTEXPR _Tp | |
1579 | __lg(_Tp __n) | |
1580 | { | |
1581 | #if __cplusplus >= 201402L | |
1582 | return std::__bit_width(make_unsigned_t<_Tp>(__n)) - 1; | |
1583 | #else | |
68854071 JW |
1584 | #pragma GCC diagnostic push |
1585 | #pragma GCC diagnostic ignored "-Wlong-long" | |
769fae76 | 1586 | // Use +__n so it promotes to at least int. |
b3a2b307 JW |
1587 | return (sizeof(+__n) * __CHAR_BIT__ - 1) |
1588 | - (sizeof(+__n) == sizeof(long long) | |
1589 | ? __builtin_clzll(+__n) | |
1590 | : (sizeof(+__n) == sizeof(long) | |
1591 | ? __builtin_clzl(+__n) | |
1592 | : __builtin_clz(+__n))); | |
68854071 | 1593 | #pragma GCC diagnostic pop |
769fae76 JW |
1594 | #endif |
1595 | } | |
f84ca6e7 | 1596 | |
12ffa228 | 1597 | _GLIBCXX_BEGIN_NAMESPACE_ALGO |
c2ba9709 | 1598 | |
1b4a6975 PE |
1599 | /** |
1600 | * @brief Tests a range for element-wise equality. | |
5b9daa7e | 1601 | * @ingroup non_mutating_algorithms |
93c66bc6 BK |
1602 | * @param __first1 An input iterator. |
1603 | * @param __last1 An input iterator. | |
1604 | * @param __first2 An input iterator. | |
1b4a6975 PE |
1605 | * @return A boolean true or false. |
1606 | * | |
1607 | * This compares the elements of two ranges using @c == and returns true or | |
1608 | * false depending on whether all of the corresponding elements of the | |
1609 | * ranges are equal. | |
1610 | */ | |
d22a3166 | 1611 | template<typename _II1, typename _II2> |
df483ebd | 1612 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
02d92e3b | 1613 | inline bool |
d22a3166 | 1614 | equal(_II1 __first1, _II1 __last1, _II2 __first2) |
02d92e3b SW |
1615 | { |
1616 | // concept requirements | |
d22a3166 PC |
1617 | __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
1618 | __glibcxx_function_requires(_InputIteratorConcept<_II2>) | |
3d7c150e | 1619 | __glibcxx_function_requires(_EqualOpConcept< |
d22a3166 PC |
1620 | typename iterator_traits<_II1>::value_type, |
1621 | typename iterator_traits<_II2>::value_type>) | |
315aadc8 | 1622 | __glibcxx_requires_can_increment_range(__first1, __last1, __first2); |
d22a3166 | 1623 | |
6004c17b | 1624 | return std::__equal_aux(__first1, __last1, __first2); |
02d92e3b SW |
1625 | } |
1626 | ||
1b4a6975 PE |
1627 | /** |
1628 | * @brief Tests a range for element-wise equality. | |
5b9daa7e | 1629 | * @ingroup non_mutating_algorithms |
93c66bc6 BK |
1630 | * @param __first1 An input iterator. |
1631 | * @param __last1 An input iterator. | |
1632 | * @param __first2 An input iterator. | |
1633 | * @param __binary_pred A binary predicate @link functors | |
c2ba9709 JS |
1634 | * functor@endlink. |
1635 | * @return A boolean true or false. | |
1b4a6975 PE |
1636 | * |
1637 | * This compares the elements of two ranges using the binary_pred | |
1638 | * parameter, and returns true or | |
1639 | * false depending on whether all of the corresponding elements of the | |
1640 | * ranges are equal. | |
1641 | */ | |
c2ba9709 | 1642 | template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> |
df483ebd | 1643 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
02d92e3b | 1644 | inline bool |
c2ba9709 JS |
1645 | equal(_IIter1 __first1, _IIter1 __last1, |
1646 | _IIter2 __first2, _BinaryPredicate __binary_pred) | |
02d92e3b SW |
1647 | { |
1648 | // concept requirements | |
c2ba9709 JS |
1649 | __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) |
1650 | __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) | |
285b36d6 | 1651 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b | 1652 | |
f970a17d | 1653 | for (; __first1 != __last1; ++__first1, (void)++__first2) |
dded9d2c | 1654 | if (!bool(__binary_pred(*__first1, *__first2))) |
02d92e3b | 1655 | return false; |
725dc051 | 1656 | return true; |
02d92e3b SW |
1657 | } |
1658 | ||
23b49089 JW |
1659 | #if __cplusplus >= 201103L |
1660 | // 4-iterator version of std::equal<It1, It2> for use in C++11. | |
1661 | template<typename _II1, typename _II2> | |
3a66e68a | 1662 | _GLIBCXX20_CONSTEXPR |
23b49089 JW |
1663 | inline bool |
1664 | __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) | |
1665 | { | |
1666 | using _RATag = random_access_iterator_tag; | |
1667 | using _Cat1 = typename iterator_traits<_II1>::iterator_category; | |
1668 | using _Cat2 = typename iterator_traits<_II2>::iterator_category; | |
1669 | using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; | |
1670 | if (_RAIters()) | |
1671 | { | |
1672 | auto __d1 = std::distance(__first1, __last1); | |
1673 | auto __d2 = std::distance(__first2, __last2); | |
1674 | if (__d1 != __d2) | |
1675 | return false; | |
1676 | return _GLIBCXX_STD_A::equal(__first1, __last1, __first2); | |
1677 | } | |
1678 | ||
1679 | for (; __first1 != __last1 && __first2 != __last2; | |
1680 | ++__first1, (void)++__first2) | |
1681 | if (!(*__first1 == *__first2)) | |
1682 | return false; | |
1683 | return __first1 == __last1 && __first2 == __last2; | |
1684 | } | |
1685 | ||
1686 | // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11. | |
1687 | template<typename _II1, typename _II2, typename _BinaryPredicate> | |
3a66e68a | 1688 | _GLIBCXX20_CONSTEXPR |
23b49089 JW |
1689 | inline bool |
1690 | __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, | |
1691 | _BinaryPredicate __binary_pred) | |
1692 | { | |
1693 | using _RATag = random_access_iterator_tag; | |
1694 | using _Cat1 = typename iterator_traits<_II1>::iterator_category; | |
1695 | using _Cat2 = typename iterator_traits<_II2>::iterator_category; | |
1696 | using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; | |
1697 | if (_RAIters()) | |
1698 | { | |
1699 | auto __d1 = std::distance(__first1, __last1); | |
1700 | auto __d2 = std::distance(__first2, __last2); | |
1701 | if (__d1 != __d2) | |
1702 | return false; | |
1703 | return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, | |
1704 | __binary_pred); | |
1705 | } | |
1706 | ||
1707 | for (; __first1 != __last1 && __first2 != __last2; | |
1708 | ++__first1, (void)++__first2) | |
1709 | if (!bool(__binary_pred(*__first1, *__first2))) | |
1710 | return false; | |
1711 | return __first1 == __last1 && __first2 == __last2; | |
1712 | } | |
1713 | #endif // C++11 | |
1714 | ||
7ffa63df | 1715 | #ifdef __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14 |
f7fbb003 JW |
1716 | /** |
1717 | * @brief Tests a range for element-wise equality. | |
1718 | * @ingroup non_mutating_algorithms | |
1719 | * @param __first1 An input iterator. | |
1720 | * @param __last1 An input iterator. | |
1721 | * @param __first2 An input iterator. | |
1722 | * @param __last2 An input iterator. | |
1723 | * @return A boolean true or false. | |
1724 | * | |
1725 | * This compares the elements of two ranges using @c == and returns true or | |
1726 | * false depending on whether all of the corresponding elements of the | |
1727 | * ranges are equal. | |
1728 | */ | |
1729 | template<typename _II1, typename _II2> | |
df483ebd | 1730 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
f7fbb003 JW |
1731 | inline bool |
1732 | equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) | |
1733 | { | |
1734 | // concept requirements | |
1735 | __glibcxx_function_requires(_InputIteratorConcept<_II1>) | |
1736 | __glibcxx_function_requires(_InputIteratorConcept<_II2>) | |
1737 | __glibcxx_function_requires(_EqualOpConcept< | |
1738 | typename iterator_traits<_II1>::value_type, | |
1739 | typename iterator_traits<_II2>::value_type>) | |
1740 | __glibcxx_requires_valid_range(__first1, __last1); | |
1741 | __glibcxx_requires_valid_range(__first2, __last2); | |
1742 | ||
23b49089 | 1743 | return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2); |
f7fbb003 JW |
1744 | } |
1745 | ||
1746 | /** | |
1747 | * @brief Tests a range for element-wise equality. | |
1748 | * @ingroup non_mutating_algorithms | |
1749 | * @param __first1 An input iterator. | |
1750 | * @param __last1 An input iterator. | |
1751 | * @param __first2 An input iterator. | |
1752 | * @param __last2 An input iterator. | |
1753 | * @param __binary_pred A binary predicate @link functors | |
1754 | * functor@endlink. | |
1755 | * @return A boolean true or false. | |
1756 | * | |
1757 | * This compares the elements of two ranges using the binary_pred | |
1758 | * parameter, and returns true or | |
1759 | * false depending on whether all of the corresponding elements of the | |
1760 | * ranges are equal. | |
1761 | */ | |
1762 | template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> | |
df483ebd | 1763 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
f7fbb003 JW |
1764 | inline bool |
1765 | equal(_IIter1 __first1, _IIter1 __last1, | |
1766 | _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred) | |
1767 | { | |
1768 | // concept requirements | |
1769 | __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) | |
1770 | __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) | |
1771 | __glibcxx_requires_valid_range(__first1, __last1); | |
1772 | __glibcxx_requires_valid_range(__first2, __last2); | |
1773 | ||
23b49089 JW |
1774 | return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2, |
1775 | __binary_pred); | |
f7fbb003 | 1776 | } |
7ffa63df | 1777 | #endif // __glibcxx_robust_nonmodifying_seq_ops |
f7fbb003 | 1778 | |
1b4a6975 | 1779 | /** |
2a60a9f6 | 1780 | * @brief Performs @b dictionary comparison on ranges. |
5b9daa7e | 1781 | * @ingroup sorting_algorithms |
93c66bc6 BK |
1782 | * @param __first1 An input iterator. |
1783 | * @param __last1 An input iterator. | |
1784 | * @param __first2 An input iterator. | |
1785 | * @param __last2 An input iterator. | |
1b4a6975 PE |
1786 | * @return A boolean true or false. |
1787 | * | |
2a60a9f6 | 1788 | * <em>Returns true if the sequence of elements defined by the range |
1b4a6975 | 1789 | * [first1,last1) is lexicographically less than the sequence of elements |
2a60a9f6 | 1790 | * defined by the range [first2,last2). Returns false otherwise.</em> |
1b4a6975 PE |
1791 | * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, |
1792 | * then this is an inline call to @c memcmp. | |
1793 | */ | |
c2fe93f7 | 1794 | template<typename _II1, typename _II2> |
df483ebd | 1795 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
de03de64 PC |
1796 | inline bool |
1797 | lexicographical_compare(_II1 __first1, _II1 __last1, | |
c2fe93f7 | 1798 | _II2 __first2, _II2 __last2) |
02d92e3b | 1799 | { |
650dc14a | 1800 | #ifdef _GLIBCXX_CONCEPT_CHECKS |
02d92e3b | 1801 | // concept requirements |
c2fe93f7 PC |
1802 | typedef typename iterator_traits<_II1>::value_type _ValueType1; |
1803 | typedef typename iterator_traits<_II2>::value_type _ValueType2; | |
650dc14a | 1804 | #endif |
c2fe93f7 PC |
1805 | __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
1806 | __glibcxx_function_requires(_InputIteratorConcept<_II2>) | |
1807 | __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) | |
1808 | __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) | |
285b36d6 BK |
1809 | __glibcxx_requires_valid_range(__first1, __last1); |
1810 | __glibcxx_requires_valid_range(__first2, __last2); | |
02d92e3b | 1811 | |
3a391adf FD |
1812 | return std::__lexicographical_compare_aux(__first1, __last1, |
1813 | __first2, __last2); | |
de03de64 | 1814 | } |
4f39bf5c | 1815 | |
1b4a6975 | 1816 | /** |
2a60a9f6 | 1817 | * @brief Performs @b dictionary comparison on ranges. |
5b9daa7e | 1818 | * @ingroup sorting_algorithms |
93c66bc6 BK |
1819 | * @param __first1 An input iterator. |
1820 | * @param __last1 An input iterator. | |
1821 | * @param __first2 An input iterator. | |
1822 | * @param __last2 An input iterator. | |
1823 | * @param __comp A @link comparison_functors comparison functor@endlink. | |
1b4a6975 PE |
1824 | * @return A boolean true or false. |
1825 | * | |
c2fe93f7 | 1826 | * The same as the four-parameter @c lexicographical_compare, but uses the |
1b4a6975 PE |
1827 | * comp parameter instead of @c <. |
1828 | */ | |
c2fe93f7 | 1829 | template<typename _II1, typename _II2, typename _Compare> |
df483ebd | 1830 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
3bd2644c | 1831 | inline bool |
c2fe93f7 PC |
1832 | lexicographical_compare(_II1 __first1, _II1 __last1, |
1833 | _II2 __first2, _II2 __last2, _Compare __comp) | |
02d92e3b SW |
1834 | { |
1835 | // concept requirements | |
c2fe93f7 PC |
1836 | __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
1837 | __glibcxx_function_requires(_InputIteratorConcept<_II2>) | |
285b36d6 BK |
1838 | __glibcxx_requires_valid_range(__first1, __last1); |
1839 | __glibcxx_requires_valid_range(__first2, __last2); | |
02d92e3b | 1840 | |
ea89b248 FD |
1841 | return std::__lexicographical_compare_impl |
1842 | (__first1, __last1, __first2, __last2, | |
1843 | __gnu_cxx::__ops::__iter_comp_iter(__comp)); | |
1844 | } | |
1845 | ||
f1355c8d | 1846 | #if __cpp_lib_three_way_comparison |
f5cdda8a JW |
1847 | // Both iterators refer to contiguous ranges of unsigned narrow characters, |
1848 | // or std::byte, or big-endian unsigned integers, suitable for comparison | |
1849 | // using memcmp. | |
1850 | template<typename _Iter1, typename _Iter2> | |
1851 | concept __memcmp_ordered_with | |
1852 | = (__is_memcmp_ordered_with<iter_value_t<_Iter1>, | |
1853 | iter_value_t<_Iter2>>::__value) | |
1854 | && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>; | |
f1355c8d JW |
1855 | |
1856 | // Return a struct with two members, initialized to the smaller of x and y | |
1857 | // (or x if they compare equal) and the result of the comparison x <=> y. | |
1858 | template<typename _Tp> | |
1859 | constexpr auto | |
1860 | __min_cmp(_Tp __x, _Tp __y) | |
1861 | { | |
1862 | struct _Res { | |
1863 | _Tp _M_min; | |
1864 | decltype(__x <=> __y) _M_cmp; | |
1865 | }; | |
1866 | auto __c = __x <=> __y; | |
1867 | if (__c > 0) | |
1868 | return _Res{__y, __c}; | |
1869 | return _Res{__x, __c}; | |
1870 | } | |
f1355c8d JW |
1871 | |
1872 | /** | |
1873 | * @brief Performs dictionary comparison on ranges. | |
1874 | * @ingroup sorting_algorithms | |
1875 | * @param __first1 An input iterator. | |
1876 | * @param __last1 An input iterator. | |
1877 | * @param __first2 An input iterator. | |
1878 | * @param __last2 An input iterator. | |
1879 | * @param __comp A @link comparison_functors comparison functor@endlink. | |
1880 | * @return The comparison category that `__comp(*__first1, *__first2)` | |
1881 | * returns. | |
1882 | */ | |
1883 | template<typename _InputIter1, typename _InputIter2, typename _Comp> | |
df483ebd | 1884 | [[nodiscard]] constexpr auto |
f1355c8d JW |
1885 | lexicographical_compare_three_way(_InputIter1 __first1, |
1886 | _InputIter1 __last1, | |
1887 | _InputIter2 __first2, | |
1888 | _InputIter2 __last2, | |
1889 | _Comp __comp) | |
1890 | -> decltype(__comp(*__first1, *__first2)) | |
1891 | { | |
1892 | // concept requirements | |
1893 | __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>) | |
1894 | __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>) | |
1895 | __glibcxx_requires_valid_range(__first1, __last1); | |
1896 | __glibcxx_requires_valid_range(__first2, __last2); | |
1897 | ||
f1355c8d JW |
1898 | using _Cat = decltype(__comp(*__first1, *__first2)); |
1899 | static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>); | |
1900 | ||
74d14778 | 1901 | if (!std::__is_constant_evaluated()) |
f1355c8d JW |
1902 | if constexpr (same_as<_Comp, __detail::_Synth3way> |
1903 | || same_as<_Comp, compare_three_way>) | |
f5cdda8a JW |
1904 | if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>) |
1905 | { | |
1906 | const auto [__len, __lencmp] = _GLIBCXX_STD_A:: | |
1907 | __min_cmp(__last1 - __first1, __last2 - __first2); | |
1908 | if (__len) | |
1909 | { | |
1910 | const auto __blen = __len * sizeof(*__first1); | |
1911 | const auto __c | |
1912 | = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0; | |
1913 | if (__c != 0) | |
1914 | return __c; | |
1915 | } | |
1916 | return __lencmp; | |
1917 | } | |
74d14778 | 1918 | |
9b4f00dd | 1919 | while (__first1 != __last1) |
f1355c8d | 1920 | { |
9b4f00dd JW |
1921 | if (__first2 == __last2) |
1922 | return strong_ordering::greater; | |
f1355c8d JW |
1923 | if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0) |
1924 | return __cmp; | |
1925 | ++__first1; | |
1926 | ++__first2; | |
1927 | } | |
9b4f00dd | 1928 | return (__first2 == __last2) <=> true; // See PR 94006 |
f1355c8d JW |
1929 | } |
1930 | ||
1931 | template<typename _InputIter1, typename _InputIter2> | |
1932 | constexpr auto | |
1933 | lexicographical_compare_three_way(_InputIter1 __first1, | |
1934 | _InputIter1 __last1, | |
1935 | _InputIter2 __first2, | |
1936 | _InputIter2 __last2) | |
1937 | { | |
9c24e97a JW |
1938 | return _GLIBCXX_STD_A:: |
1939 | lexicographical_compare_three_way(__first1, __last1, __first2, __last2, | |
1940 | compare_three_way{}); | |
f1355c8d JW |
1941 | } |
1942 | #endif // three_way_comparison | |
1943 | ||
ea89b248 FD |
1944 | template<typename _InputIterator1, typename _InputIterator2, |
1945 | typename _BinaryPredicate> | |
3a66e68a | 1946 | _GLIBCXX20_CONSTEXPR |
ea89b248 FD |
1947 | pair<_InputIterator1, _InputIterator2> |
1948 | __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, | |
1949 | _InputIterator2 __first2, _BinaryPredicate __binary_pred) | |
1950 | { | |
1951 | while (__first1 != __last1 && __binary_pred(__first1, __first2)) | |
e5795ce4 | 1952 | { |
ea89b248 FD |
1953 | ++__first1; |
1954 | ++__first2; | |
e5795ce4 | 1955 | } |
ea89b248 | 1956 | return pair<_InputIterator1, _InputIterator2>(__first1, __first2); |
02d92e3b SW |
1957 | } |
1958 | ||
c2ba9709 JS |
1959 | /** |
1960 | * @brief Finds the places in ranges which don't match. | |
5b9daa7e | 1961 | * @ingroup non_mutating_algorithms |
93c66bc6 BK |
1962 | * @param __first1 An input iterator. |
1963 | * @param __last1 An input iterator. | |
1964 | * @param __first2 An input iterator. | |
c2ba9709 JS |
1965 | * @return A pair of iterators pointing to the first mismatch. |
1966 | * | |
1967 | * This compares the elements of two ranges using @c == and returns a pair | |
1968 | * of iterators. The first iterator points into the first range, the | |
1969 | * second iterator points into the second range, and the elements pointed | |
1970 | * to by the iterators are not equal. | |
1971 | */ | |
1972 | template<typename _InputIterator1, typename _InputIterator2> | |
df483ebd | 1973 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
3bd2644c | 1974 | inline pair<_InputIterator1, _InputIterator2> |
c2ba9709 JS |
1975 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, |
1976 | _InputIterator2 __first2) | |
1977 | { | |
1978 | // concept requirements | |
1979 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) | |
1980 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
1981 | __glibcxx_function_requires(_EqualOpConcept< | |
1982 | typename iterator_traits<_InputIterator1>::value_type, | |
1983 | typename iterator_traits<_InputIterator2>::value_type>) | |
1984 | __glibcxx_requires_valid_range(__first1, __last1); | |
02d92e3b | 1985 | |
ea89b248 FD |
1986 | return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, |
1987 | __gnu_cxx::__ops::__iter_equal_to_iter()); | |
c2ba9709 | 1988 | } |
285b36d6 | 1989 | |
c2ba9709 JS |
1990 | /** |
1991 | * @brief Finds the places in ranges which don't match. | |
5b9daa7e | 1992 | * @ingroup non_mutating_algorithms |
93c66bc6 BK |
1993 | * @param __first1 An input iterator. |
1994 | * @param __last1 An input iterator. | |
1995 | * @param __first2 An input iterator. | |
1996 | * @param __binary_pred A binary predicate @link functors | |
c2ba9709 JS |
1997 | * functor@endlink. |
1998 | * @return A pair of iterators pointing to the first mismatch. | |
1999 | * | |
2000 | * This compares the elements of two ranges using the binary_pred | |
2001 | * parameter, and returns a pair | |
2002 | * of iterators. The first iterator points into the first range, the | |
2003 | * second iterator points into the second range, and the elements pointed | |
2004 | * to by the iterators are not equal. | |
2005 | */ | |
2006 | template<typename _InputIterator1, typename _InputIterator2, | |
2007 | typename _BinaryPredicate> | |
df483ebd | 2008 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
3bd2644c | 2009 | inline pair<_InputIterator1, _InputIterator2> |
c2ba9709 JS |
2010 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, |
2011 | _InputIterator2 __first2, _BinaryPredicate __binary_pred) | |
2012 | { | |
2013 | // concept requirements | |
2014 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) | |
2015 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
2016 | __glibcxx_requires_valid_range(__first1, __last1); | |
02d92e3b | 2017 | |
ea89b248 FD |
2018 | return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, |
2019 | __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); | |
2020 | } | |
2021 | ||
7ffa63df | 2022 | #if __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14 |
ea89b248 FD |
2023 | template<typename _InputIterator1, typename _InputIterator2, |
2024 | typename _BinaryPredicate> | |
3a66e68a | 2025 | _GLIBCXX20_CONSTEXPR |
ea89b248 FD |
2026 | pair<_InputIterator1, _InputIterator2> |
2027 | __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, | |
2028 | _InputIterator2 __first2, _InputIterator2 __last2, | |
2029 | _BinaryPredicate __binary_pred) | |
2030 | { | |
2031 | while (__first1 != __last1 && __first2 != __last2 | |
2032 | && __binary_pred(__first1, __first2)) | |
e5795ce4 | 2033 | { |
c2ba9709 JS |
2034 | ++__first1; |
2035 | ++__first2; | |
e5795ce4 | 2036 | } |
c2ba9709 JS |
2037 | return pair<_InputIterator1, _InputIterator2>(__first1, __first2); |
2038 | } | |
2039 | ||
f7fbb003 JW |
2040 | /** |
2041 | * @brief Finds the places in ranges which don't match. | |
2042 | * @ingroup non_mutating_algorithms | |
2043 | * @param __first1 An input iterator. | |
2044 | * @param __last1 An input iterator. | |
2045 | * @param __first2 An input iterator. | |
2046 | * @param __last2 An input iterator. | |
2047 | * @return A pair of iterators pointing to the first mismatch. | |
2048 | * | |
2049 | * This compares the elements of two ranges using @c == and returns a pair | |
2050 | * of iterators. The first iterator points into the first range, the | |
2051 | * second iterator points into the second range, and the elements pointed | |
2052 | * to by the iterators are not equal. | |
2053 | */ | |
2054 | template<typename _InputIterator1, typename _InputIterator2> | |
df483ebd | 2055 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
3bd2644c | 2056 | inline pair<_InputIterator1, _InputIterator2> |
f7fbb003 JW |
2057 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, |
2058 | _InputIterator2 __first2, _InputIterator2 __last2) | |
2059 | { | |
2060 | // concept requirements | |
2061 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) | |
2062 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
2063 | __glibcxx_function_requires(_EqualOpConcept< | |
2064 | typename iterator_traits<_InputIterator1>::value_type, | |
2065 | typename iterator_traits<_InputIterator2>::value_type>) | |
2066 | __glibcxx_requires_valid_range(__first1, __last1); | |
2067 | __glibcxx_requires_valid_range(__first2, __last2); | |
2068 | ||
ea89b248 FD |
2069 | return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, |
2070 | __gnu_cxx::__ops::__iter_equal_to_iter()); | |
f7fbb003 JW |
2071 | } |
2072 | ||
2073 | /** | |
2074 | * @brief Finds the places in ranges which don't match. | |
2075 | * @ingroup non_mutating_algorithms | |
2076 | * @param __first1 An input iterator. | |
2077 | * @param __last1 An input iterator. | |
2078 | * @param __first2 An input iterator. | |
2079 | * @param __last2 An input iterator. | |
2080 | * @param __binary_pred A binary predicate @link functors | |
2081 | * functor@endlink. | |
2082 | * @return A pair of iterators pointing to the first mismatch. | |
2083 | * | |
2084 | * This compares the elements of two ranges using the binary_pred | |
2085 | * parameter, and returns a pair | |
2086 | * of iterators. The first iterator points into the first range, the | |
2087 | * second iterator points into the second range, and the elements pointed | |
2088 | * to by the iterators are not equal. | |
2089 | */ | |
2090 | template<typename _InputIterator1, typename _InputIterator2, | |
2091 | typename _BinaryPredicate> | |
df483ebd | 2092 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |
3bd2644c | 2093 | inline pair<_InputIterator1, _InputIterator2> |
f7fbb003 JW |
2094 | mismatch(_InputIterator1 __first1, _InputIterator1 __last1, |
2095 | _InputIterator2 __first2, _InputIterator2 __last2, | |
2096 | _BinaryPredicate __binary_pred) | |
2097 | { | |
2098 | // concept requirements | |
2099 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) | |
2100 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
2101 | __glibcxx_requires_valid_range(__first1, __last1); | |
2102 | __glibcxx_requires_valid_range(__first2, __last2); | |
2103 | ||
ea89b248 FD |
2104 | return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, |
2105 | __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); | |
f7fbb003 JW |
2106 | } |
2107 | #endif | |
2108 | ||
12ffa228 | 2109 | _GLIBCXX_END_NAMESPACE_ALGO |
44c85722 | 2110 | |
e69456ff | 2111 | // Implementation of std::find_if, also used in std::remove_if and others. |
44c85722 FD |
2112 | template<typename _Iterator, typename _Predicate> |
2113 | _GLIBCXX20_CONSTEXPR | |
2114 | inline _Iterator | |
2115 | __find_if(_Iterator __first, _Iterator __last, _Predicate __pred) | |
2116 | { | |
3fd07d4f | 2117 | #pragma GCC unroll 4 |
e69456ff JW |
2118 | while (__first != __last && !__pred(__first)) |
2119 | ++__first; | |
2120 | return __first; | |
44c85722 FD |
2121 | } |
2122 | ||
2123 | template<typename _InputIterator, typename _Predicate> | |
2124 | _GLIBCXX20_CONSTEXPR | |
2125 | typename iterator_traits<_InputIterator>::difference_type | |
2126 | __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) | |
2127 | { | |
2128 | typename iterator_traits<_InputIterator>::difference_type __n = 0; | |
2129 | for (; __first != __last; ++__first) | |
2130 | if (__pred(__first)) | |
2131 | ++__n; | |
2132 | return __n; | |
2133 | } | |
2134 | ||
acf3a21c JW |
2135 | template<typename _ForwardIterator, typename _Predicate> |
2136 | _GLIBCXX20_CONSTEXPR | |
2137 | _ForwardIterator | |
2138 | __remove_if(_ForwardIterator __first, _ForwardIterator __last, | |
2139 | _Predicate __pred) | |
2140 | { | |
2141 | __first = std::__find_if(__first, __last, __pred); | |
2142 | if (__first == __last) | |
2143 | return __first; | |
2144 | _ForwardIterator __result = __first; | |
2145 | ++__first; | |
2146 | for (; __first != __last; ++__first) | |
2147 | if (!__pred(__first)) | |
2148 | { | |
2149 | *__result = _GLIBCXX_MOVE(*__first); | |
2150 | ++__result; | |
2151 | } | |
2152 | return __result; | |
2153 | } | |
2154 | ||
940645ce FD |
2155 | template<typename _ForwardIterator1, typename _ForwardIterator2, |
2156 | typename _BinaryPredicate> | |
2157 | _GLIBCXX20_CONSTEXPR | |
2158 | _ForwardIterator1 | |
2159 | __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, | |
2160 | _ForwardIterator2 __first2, _ForwardIterator2 __last2, | |
2161 | _BinaryPredicate __predicate) | |
2162 | { | |
2163 | // Test for empty ranges | |
2164 | if (__first1 == __last1 || __first2 == __last2) | |
2165 | return __first1; | |
2166 | ||
2167 | // Test for a pattern of length 1. | |
2168 | _ForwardIterator2 __p1(__first2); | |
2169 | if (++__p1 == __last2) | |
2170 | return std::__find_if(__first1, __last1, | |
2171 | __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); | |
2172 | ||
2173 | // General case. | |
2174 | _ForwardIterator1 __current = __first1; | |
2175 | ||
2176 | for (;;) | |
2177 | { | |
2178 | __first1 = | |
2179 | std::__find_if(__first1, __last1, | |
2180 | __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); | |
2181 | ||
2182 | if (__first1 == __last1) | |
2183 | return __last1; | |
2184 | ||
2185 | _ForwardIterator2 __p = __p1; | |
2186 | __current = __first1; | |
2187 | if (++__current == __last1) | |
2188 | return __last1; | |
2189 | ||
2190 | while (__predicate(__current, __p)) | |
2191 | { | |
2192 | if (++__p == __last2) | |
2193 | return __first1; | |
2194 | if (++__current == __last1) | |
2195 | return __last1; | |
2196 | } | |
2197 | ++__first1; | |
2198 | } | |
2199 | return __first1; | |
2200 | } | |
2201 | ||
44c85722 FD |
2202 | #if __cplusplus >= 201103L |
2203 | template<typename _ForwardIterator1, typename _ForwardIterator2, | |
2204 | typename _BinaryPredicate> | |
2205 | _GLIBCXX20_CONSTEXPR | |
2206 | bool | |
2207 | __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, | |
2208 | _ForwardIterator2 __first2, _BinaryPredicate __pred) | |
2209 | { | |
2210 | // Efficiently compare identical prefixes: O(N) if sequences | |
2211 | // have the same elements in the same order. | |
2212 | for (; __first1 != __last1; ++__first1, (void)++__first2) | |
2213 | if (!__pred(__first1, __first2)) | |
2214 | break; | |
2215 | ||
2216 | if (__first1 == __last1) | |
2217 | return true; | |
2218 | ||
2219 | // Establish __last2 assuming equal ranges by iterating over the | |
2220 | // rest of the list. | |
2221 | _ForwardIterator2 __last2 = __first2; | |
2222 | std::advance(__last2, std::distance(__first1, __last1)); | |
2223 | for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) | |
2224 | { | |
2225 | if (__scan != std::__find_if(__first1, __scan, | |
2226 | __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) | |
2227 | continue; // We've seen this one before. | |
2228 | ||
2229 | auto __matches | |
2230 | = std::__count_if(__first2, __last2, | |
2231 | __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); | |
2232 | if (0 == __matches || | |
2233 | std::__count_if(__scan, __last1, | |
2234 | __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) | |
2235 | != __matches) | |
2236 | return false; | |
2237 | } | |
2238 | return true; | |
2239 | } | |
2240 | ||
2241 | /** | |
2242 | * @brief Checks whether a permutation of the second sequence is equal | |
2243 | * to the first sequence. | |
2244 | * @ingroup non_mutating_algorithms | |
2245 | * @param __first1 Start of first range. | |
2246 | * @param __last1 End of first range. | |
2247 | * @param __first2 Start of second range. | |
2248 | * @return true if there exists a permutation of the elements in the range | |
2249 | * [__first2, __first2 + (__last1 - __first1)), beginning with | |
2250 | * ForwardIterator2 begin, such that equal(__first1, __last1, begin) | |
2251 | * returns true; otherwise, returns false. | |
2252 | */ | |
2253 | template<typename _ForwardIterator1, typename _ForwardIterator2> | |
2254 | _GLIBCXX20_CONSTEXPR | |
2255 | inline bool | |
2256 | is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, | |
2257 | _ForwardIterator2 __first2) | |
2258 | { | |
2259 | // concept requirements | |
2260 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) | |
2261 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) | |
2262 | __glibcxx_function_requires(_EqualOpConcept< | |
2263 | typename iterator_traits<_ForwardIterator1>::value_type, | |
2264 | typename iterator_traits<_ForwardIterator2>::value_type>) | |
2265 | __glibcxx_requires_valid_range(__first1, __last1); | |
2266 | ||
2267 | return std::__is_permutation(__first1, __last1, __first2, | |
2268 | __gnu_cxx::__ops::__iter_equal_to_iter()); | |
2269 | } | |
2270 | #endif // C++11 | |
2271 | ||
940645ce FD |
2272 | _GLIBCXX_BEGIN_NAMESPACE_ALGO |
2273 | ||
2274 | /** | |
2275 | * @brief Search a sequence for a matching sub-sequence using a predicate. | |
2276 | * @ingroup non_mutating_algorithms | |
2277 | * @param __first1 A forward iterator. | |
2278 | * @param __last1 A forward iterator. | |
2279 | * @param __first2 A forward iterator. | |
2280 | * @param __last2 A forward iterator. | |
2281 | * @param __predicate A binary predicate. | |
2282 | * @return The first iterator @c i in the range | |
2283 | * @p [__first1,__last1-(__last2-__first2)) such that | |
2284 | * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range | |
2285 | * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. | |
2286 | * | |
2287 | * Searches the range @p [__first1,__last1) for a sub-sequence that | |
2288 | * compares equal value-by-value with the sequence given by @p | |
2289 | * [__first2,__last2), using @p __predicate to determine equality, | |
2290 | * and returns an iterator to the first element of the | |
2291 | * sub-sequence, or @p __last1 if no such iterator exists. | |
2292 | * | |
2293 | * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) | |
2294 | */ | |
2295 | template<typename _ForwardIterator1, typename _ForwardIterator2, | |
2296 | typename _BinaryPredicate> | |
2297 | _GLIBCXX20_CONSTEXPR | |
2298 | inline _ForwardIterator1 | |
2299 | search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, | |
2300 | _ForwardIterator2 __first2, _ForwardIterator2 __last2, | |
2301 | _BinaryPredicate __predicate) | |
2302 | { | |
2303 | // concept requirements | |
2304 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) | |
2305 | __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) | |
2306 | __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, | |
2307 | typename iterator_traits<_ForwardIterator1>::value_type, | |
2308 | typename iterator_traits<_ForwardIterator2>::value_type>) | |
2309 | __glibcxx_requires_valid_range(__first1, __last1); | |
2310 | __glibcxx_requires_valid_range(__first2, __last2); | |
2311 | ||
2312 | return std::__search(__first1, __last1, __first2, __last2, | |
2313 | __gnu_cxx::__ops::__iter_comp_iter(__predicate)); | |
2314 | } | |
2315 | ||
2316 | _GLIBCXX_END_NAMESPACE_ALGO | |
4a15d842 | 2317 | _GLIBCXX_END_NAMESPACE_VERSION |
12ffa228 | 2318 | } // namespace std |
c2ba9709 JS |
2319 | |
2320 | // NB: This file is included within many other C++ includes, as a way | |
2321 | // of getting the base algorithms. So, make sure that parallel bits | |
e5795ce4 | 2322 | // come in too if requested. |
c2ba9709 | 2323 | #ifdef _GLIBCXX_PARALLEL |
c2ba9709 JS |
2324 | # include <parallel/algobase.h> |
2325 | #endif | |
725dc051 | 2326 | |
ed6814f7 | 2327 | #endif |