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