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