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