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 && __cpp_lib_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 const int __sz = sizeof(+__n);
1522 int __w = __sz * __CHAR_BIT__ - 1;
1523 if (__sz == sizeof(long long))
1524 __w -= __builtin_clzll(+__n);
1525 else if (__sz == sizeof(long))
1526 __w -= __builtin_clzl(+__n);
1527 else if (__sz == sizeof(int))
1528 __w -= __builtin_clz(+__n);
1529 return __w;
1530 #endif
1531 }
1532
1533 _GLIBCXX_BEGIN_NAMESPACE_ALGO
1534
1535 /**
1536 * @brief Tests a range for element-wise equality.
1537 * @ingroup non_mutating_algorithms
1538 * @param __first1 An input iterator.
1539 * @param __last1 An input iterator.
1540 * @param __first2 An input iterator.
1541 * @return A boolean true or false.
1542 *
1543 * This compares the elements of two ranges using @c == and returns true or
1544 * false depending on whether all of the corresponding elements of the
1545 * ranges are equal.
1546 */
1547 template<typename _II1, typename _II2>
1548 _GLIBCXX20_CONSTEXPR
1549 inline bool
1550 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1551 {
1552 // concept requirements
1553 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1554 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1555 __glibcxx_function_requires(_EqualOpConcept<
1556 typename iterator_traits<_II1>::value_type,
1557 typename iterator_traits<_II2>::value_type>)
1558 __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1559
1560 return std::__equal_aux(__first1, __last1, __first2);
1561 }
1562
1563 /**
1564 * @brief Tests a range for element-wise equality.
1565 * @ingroup non_mutating_algorithms
1566 * @param __first1 An input iterator.
1567 * @param __last1 An input iterator.
1568 * @param __first2 An input iterator.
1569 * @param __binary_pred A binary predicate @link functors
1570 * functor@endlink.
1571 * @return A boolean true or false.
1572 *
1573 * This compares the elements of two ranges using the binary_pred
1574 * parameter, and returns true or
1575 * false depending on whether all of the corresponding elements of the
1576 * ranges are equal.
1577 */
1578 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1579 _GLIBCXX20_CONSTEXPR
1580 inline bool
1581 equal(_IIter1 __first1, _IIter1 __last1,
1582 _IIter2 __first2, _BinaryPredicate __binary_pred)
1583 {
1584 // concept requirements
1585 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1586 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1587 __glibcxx_requires_valid_range(__first1, __last1);
1588
1589 for (; __first1 != __last1; ++__first1, (void)++__first2)
1590 if (!bool(__binary_pred(*__first1, *__first2)))
1591 return false;
1592 return true;
1593 }
1594
1595 #if __cplusplus >= 201103L
1596 // 4-iterator version of std::equal<It1, It2> for use in C++11.
1597 template<typename _II1, typename _II2>
1598 _GLIBCXX20_CONSTEXPR
1599 inline bool
1600 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1601 {
1602 using _RATag = random_access_iterator_tag;
1603 using _Cat1 = typename iterator_traits<_II1>::iterator_category;
1604 using _Cat2 = typename iterator_traits<_II2>::iterator_category;
1605 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1606 if (_RAIters())
1607 {
1608 auto __d1 = std::distance(__first1, __last1);
1609 auto __d2 = std::distance(__first2, __last2);
1610 if (__d1 != __d2)
1611 return false;
1612 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1613 }
1614
1615 for (; __first1 != __last1 && __first2 != __last2;
1616 ++__first1, (void)++__first2)
1617 if (!(*__first1 == *__first2))
1618 return false;
1619 return __first1 == __last1 && __first2 == __last2;
1620 }
1621
1622 // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11.
1623 template<typename _II1, typename _II2, typename _BinaryPredicate>
1624 _GLIBCXX20_CONSTEXPR
1625 inline bool
1626 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1627 _BinaryPredicate __binary_pred)
1628 {
1629 using _RATag = random_access_iterator_tag;
1630 using _Cat1 = typename iterator_traits<_II1>::iterator_category;
1631 using _Cat2 = typename iterator_traits<_II2>::iterator_category;
1632 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1633 if (_RAIters())
1634 {
1635 auto __d1 = std::distance(__first1, __last1);
1636 auto __d2 = std::distance(__first2, __last2);
1637 if (__d1 != __d2)
1638 return false;
1639 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1640 __binary_pred);
1641 }
1642
1643 for (; __first1 != __last1 && __first2 != __last2;
1644 ++__first1, (void)++__first2)
1645 if (!bool(__binary_pred(*__first1, *__first2)))
1646 return false;
1647 return __first1 == __last1 && __first2 == __last2;
1648 }
1649 #endif // C++11
1650
1651 #if __cplusplus > 201103L
1652
1653 #define __cpp_lib_robust_nonmodifying_seq_ops 201304L
1654
1655 /**
1656 * @brief Tests a range for element-wise equality.
1657 * @ingroup non_mutating_algorithms
1658 * @param __first1 An input iterator.
1659 * @param __last1 An input iterator.
1660 * @param __first2 An input iterator.
1661 * @param __last2 An input iterator.
1662 * @return A boolean true or false.
1663 *
1664 * This compares the elements of two ranges using @c == and returns true or
1665 * false depending on whether all of the corresponding elements of the
1666 * ranges are equal.
1667 */
1668 template<typename _II1, typename _II2>
1669 _GLIBCXX20_CONSTEXPR
1670 inline bool
1671 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1672 {
1673 // concept requirements
1674 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1675 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1676 __glibcxx_function_requires(_EqualOpConcept<
1677 typename iterator_traits<_II1>::value_type,
1678 typename iterator_traits<_II2>::value_type>)
1679 __glibcxx_requires_valid_range(__first1, __last1);
1680 __glibcxx_requires_valid_range(__first2, __last2);
1681
1682 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1683 }
1684
1685 /**
1686 * @brief Tests a range for element-wise equality.
1687 * @ingroup non_mutating_algorithms
1688 * @param __first1 An input iterator.
1689 * @param __last1 An input iterator.
1690 * @param __first2 An input iterator.
1691 * @param __last2 An input iterator.
1692 * @param __binary_pred A binary predicate @link functors
1693 * functor@endlink.
1694 * @return A boolean true or false.
1695 *
1696 * This compares the elements of two ranges using the binary_pred
1697 * parameter, and returns true or
1698 * false depending on whether all of the corresponding elements of the
1699 * ranges are equal.
1700 */
1701 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1702 _GLIBCXX20_CONSTEXPR
1703 inline bool
1704 equal(_IIter1 __first1, _IIter1 __last1,
1705 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1706 {
1707 // concept requirements
1708 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1709 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1710 __glibcxx_requires_valid_range(__first1, __last1);
1711 __glibcxx_requires_valid_range(__first2, __last2);
1712
1713 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1714 __binary_pred);
1715 }
1716 #endif // C++14
1717
1718 /**
1719 * @brief Performs @b dictionary comparison on ranges.
1720 * @ingroup sorting_algorithms
1721 * @param __first1 An input iterator.
1722 * @param __last1 An input iterator.
1723 * @param __first2 An input iterator.
1724 * @param __last2 An input iterator.
1725 * @return A boolean true or false.
1726 *
1727 * <em>Returns true if the sequence of elements defined by the range
1728 * [first1,last1) is lexicographically less than the sequence of elements
1729 * defined by the range [first2,last2). Returns false otherwise.</em>
1730 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1731 * then this is an inline call to @c memcmp.
1732 */
1733 template<typename _II1, typename _II2>
1734 _GLIBCXX20_CONSTEXPR
1735 inline bool
1736 lexicographical_compare(_II1 __first1, _II1 __last1,
1737 _II2 __first2, _II2 __last2)
1738 {
1739 #ifdef _GLIBCXX_CONCEPT_CHECKS
1740 // concept requirements
1741 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1742 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1743 #endif
1744 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1745 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1746 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1747 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1748 __glibcxx_requires_valid_range(__first1, __last1);
1749 __glibcxx_requires_valid_range(__first2, __last2);
1750
1751 return std::__lexicographical_compare_aux(__first1, __last1,
1752 __first2, __last2);
1753 }
1754
1755 /**
1756 * @brief Performs @b dictionary comparison on ranges.
1757 * @ingroup sorting_algorithms
1758 * @param __first1 An input iterator.
1759 * @param __last1 An input iterator.
1760 * @param __first2 An input iterator.
1761 * @param __last2 An input iterator.
1762 * @param __comp A @link comparison_functors comparison functor@endlink.
1763 * @return A boolean true or false.
1764 *
1765 * The same as the four-parameter @c lexicographical_compare, but uses the
1766 * comp parameter instead of @c <.
1767 */
1768 template<typename _II1, typename _II2, typename _Compare>
1769 _GLIBCXX20_CONSTEXPR
1770 inline bool
1771 lexicographical_compare(_II1 __first1, _II1 __last1,
1772 _II2 __first2, _II2 __last2, _Compare __comp)
1773 {
1774 // concept requirements
1775 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1776 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1777 __glibcxx_requires_valid_range(__first1, __last1);
1778 __glibcxx_requires_valid_range(__first2, __last2);
1779
1780 return std::__lexicographical_compare_impl
1781 (__first1, __last1, __first2, __last2,
1782 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1783 }
1784
1785 #if __cpp_lib_three_way_comparison
1786 // Iter points to a contiguous range of unsigned narrow character type
1787 // or std::byte, suitable for comparison by memcmp.
1788 template<typename _Iter>
1789 concept __is_byte_iter = contiguous_iterator<_Iter>
1790 && __is_memcmp_ordered<iter_value_t<_Iter>>::__value;
1791
1792 // Return a struct with two members, initialized to the smaller of x and y
1793 // (or x if they compare equal) and the result of the comparison x <=> y.
1794 template<typename _Tp>
1795 constexpr auto
1796 __min_cmp(_Tp __x, _Tp __y)
1797 {
1798 struct _Res {
1799 _Tp _M_min;
1800 decltype(__x <=> __y) _M_cmp;
1801 };
1802 auto __c = __x <=> __y;
1803 if (__c > 0)
1804 return _Res{__y, __c};
1805 return _Res{__x, __c};
1806 }
1807
1808 /**
1809 * @brief Performs dictionary comparison on ranges.
1810 * @ingroup sorting_algorithms
1811 * @param __first1 An input iterator.
1812 * @param __last1 An input iterator.
1813 * @param __first2 An input iterator.
1814 * @param __last2 An input iterator.
1815 * @param __comp A @link comparison_functors comparison functor@endlink.
1816 * @return The comparison category that `__comp(*__first1, *__first2)`
1817 * returns.
1818 */
1819 template<typename _InputIter1, typename _InputIter2, typename _Comp>
1820 constexpr auto
1821 lexicographical_compare_three_way(_InputIter1 __first1,
1822 _InputIter1 __last1,
1823 _InputIter2 __first2,
1824 _InputIter2 __last2,
1825 _Comp __comp)
1826 -> decltype(__comp(*__first1, *__first2))
1827 {
1828 // concept requirements
1829 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1830 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1831 __glibcxx_requires_valid_range(__first1, __last1);
1832 __glibcxx_requires_valid_range(__first2, __last2);
1833
1834 using _Cat = decltype(__comp(*__first1, *__first2));
1835 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1836
1837 if (!std::__is_constant_evaluated())
1838 if constexpr (same_as<_Comp, __detail::_Synth3way>
1839 || same_as<_Comp, compare_three_way>)
1840 if constexpr (__is_byte_iter<_InputIter1>)
1841 if constexpr (__is_byte_iter<_InputIter2>)
1842 {
1843 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1844 __min_cmp(__last1 - __first1, __last2 - __first2);
1845 if (__len)
1846 {
1847 const auto __c
1848 = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
1849 if (__c != 0)
1850 return __c;
1851 }
1852 return __lencmp;
1853 }
1854
1855 while (__first1 != __last1)
1856 {
1857 if (__first2 == __last2)
1858 return strong_ordering::greater;
1859 if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1860 return __cmp;
1861 ++__first1;
1862 ++__first2;
1863 }
1864 return (__first2 == __last2) <=> true; // See PR 94006
1865 }
1866
1867 template<typename _InputIter1, typename _InputIter2>
1868 constexpr auto
1869 lexicographical_compare_three_way(_InputIter1 __first1,
1870 _InputIter1 __last1,
1871 _InputIter2 __first2,
1872 _InputIter2 __last2)
1873 {
1874 return _GLIBCXX_STD_A::
1875 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1876 compare_three_way{});
1877 }
1878 #endif // three_way_comparison
1879
1880 template<typename _InputIterator1, typename _InputIterator2,
1881 typename _BinaryPredicate>
1882 _GLIBCXX20_CONSTEXPR
1883 pair<_InputIterator1, _InputIterator2>
1884 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1885 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1886 {
1887 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1888 {
1889 ++__first1;
1890 ++__first2;
1891 }
1892 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1893 }
1894
1895 /**
1896 * @brief Finds the places in ranges which don't match.
1897 * @ingroup non_mutating_algorithms
1898 * @param __first1 An input iterator.
1899 * @param __last1 An input iterator.
1900 * @param __first2 An input iterator.
1901 * @return A pair of iterators pointing to the first mismatch.
1902 *
1903 * This compares the elements of two ranges using @c == and returns a pair
1904 * of iterators. The first iterator points into the first range, the
1905 * second iterator points into the second range, and the elements pointed
1906 * to by the iterators are not equal.
1907 */
1908 template<typename _InputIterator1, typename _InputIterator2>
1909 _GLIBCXX20_CONSTEXPR
1910 inline pair<_InputIterator1, _InputIterator2>
1911 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1912 _InputIterator2 __first2)
1913 {
1914 // concept requirements
1915 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1916 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1917 __glibcxx_function_requires(_EqualOpConcept<
1918 typename iterator_traits<_InputIterator1>::value_type,
1919 typename iterator_traits<_InputIterator2>::value_type>)
1920 __glibcxx_requires_valid_range(__first1, __last1);
1921
1922 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1923 __gnu_cxx::__ops::__iter_equal_to_iter());
1924 }
1925
1926 /**
1927 * @brief Finds the places in ranges which don't match.
1928 * @ingroup non_mutating_algorithms
1929 * @param __first1 An input iterator.
1930 * @param __last1 An input iterator.
1931 * @param __first2 An input iterator.
1932 * @param __binary_pred A binary predicate @link functors
1933 * functor@endlink.
1934 * @return A pair of iterators pointing to the first mismatch.
1935 *
1936 * This compares the elements of two ranges using the binary_pred
1937 * parameter, and returns a pair
1938 * of iterators. The first iterator points into the first range, the
1939 * second iterator points into the second range, and the elements pointed
1940 * to by the iterators are not equal.
1941 */
1942 template<typename _InputIterator1, typename _InputIterator2,
1943 typename _BinaryPredicate>
1944 _GLIBCXX20_CONSTEXPR
1945 inline pair<_InputIterator1, _InputIterator2>
1946 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1947 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1948 {
1949 // concept requirements
1950 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1951 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1952 __glibcxx_requires_valid_range(__first1, __last1);
1953
1954 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1955 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1956 }
1957
1958 #if __cplusplus > 201103L
1959
1960 template<typename _InputIterator1, typename _InputIterator2,
1961 typename _BinaryPredicate>
1962 _GLIBCXX20_CONSTEXPR
1963 pair<_InputIterator1, _InputIterator2>
1964 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1965 _InputIterator2 __first2, _InputIterator2 __last2,
1966 _BinaryPredicate __binary_pred)
1967 {
1968 while (__first1 != __last1 && __first2 != __last2
1969 && __binary_pred(__first1, __first2))
1970 {
1971 ++__first1;
1972 ++__first2;
1973 }
1974 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1975 }
1976
1977 /**
1978 * @brief Finds the places in ranges which don't match.
1979 * @ingroup non_mutating_algorithms
1980 * @param __first1 An input iterator.
1981 * @param __last1 An input iterator.
1982 * @param __first2 An input iterator.
1983 * @param __last2 An input iterator.
1984 * @return A pair of iterators pointing to the first mismatch.
1985 *
1986 * This compares the elements of two ranges using @c == and returns a pair
1987 * of iterators. The first iterator points into the first range, the
1988 * second iterator points into the second range, and the elements pointed
1989 * to by the iterators are not equal.
1990 */
1991 template<typename _InputIterator1, typename _InputIterator2>
1992 _GLIBCXX20_CONSTEXPR
1993 inline pair<_InputIterator1, _InputIterator2>
1994 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1995 _InputIterator2 __first2, _InputIterator2 __last2)
1996 {
1997 // concept requirements
1998 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1999 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2000 __glibcxx_function_requires(_EqualOpConcept<
2001 typename iterator_traits<_InputIterator1>::value_type,
2002 typename iterator_traits<_InputIterator2>::value_type>)
2003 __glibcxx_requires_valid_range(__first1, __last1);
2004 __glibcxx_requires_valid_range(__first2, __last2);
2005
2006 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2007 __gnu_cxx::__ops::__iter_equal_to_iter());
2008 }
2009
2010 /**
2011 * @brief Finds the places in ranges which don't match.
2012 * @ingroup non_mutating_algorithms
2013 * @param __first1 An input iterator.
2014 * @param __last1 An input iterator.
2015 * @param __first2 An input iterator.
2016 * @param __last2 An input iterator.
2017 * @param __binary_pred A binary predicate @link functors
2018 * functor@endlink.
2019 * @return A pair of iterators pointing to the first mismatch.
2020 *
2021 * This compares the elements of two ranges using the binary_pred
2022 * parameter, and returns a pair
2023 * of iterators. The first iterator points into the first range, the
2024 * second iterator points into the second range, and the elements pointed
2025 * to by the iterators are not equal.
2026 */
2027 template<typename _InputIterator1, typename _InputIterator2,
2028 typename _BinaryPredicate>
2029 _GLIBCXX20_CONSTEXPR
2030 inline pair<_InputIterator1, _InputIterator2>
2031 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2032 _InputIterator2 __first2, _InputIterator2 __last2,
2033 _BinaryPredicate __binary_pred)
2034 {
2035 // concept requirements
2036 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2037 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2038 __glibcxx_requires_valid_range(__first1, __last1);
2039 __glibcxx_requires_valid_range(__first2, __last2);
2040
2041 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2042 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2043 }
2044 #endif
2045
2046 _GLIBCXX_END_NAMESPACE_ALGO
2047
2048 /// This is an overload used by find algos for the Input Iterator case.
2049 template<typename _InputIterator, typename _Predicate>
2050 _GLIBCXX20_CONSTEXPR
2051 inline _InputIterator
2052 __find_if(_InputIterator __first, _InputIterator __last,
2053 _Predicate __pred, input_iterator_tag)
2054 {
2055 while (__first != __last && !__pred(__first))
2056 ++__first;
2057 return __first;
2058 }
2059
2060 /// This is an overload used by find algos for the RAI case.
2061 template<typename _RandomAccessIterator, typename _Predicate>
2062 _GLIBCXX20_CONSTEXPR
2063 _RandomAccessIterator
2064 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
2065 _Predicate __pred, random_access_iterator_tag)
2066 {
2067 typename iterator_traits<_RandomAccessIterator>::difference_type
2068 __trip_count = (__last - __first) >> 2;
2069
2070 for (; __trip_count > 0; --__trip_count)
2071 {
2072 if (__pred(__first))
2073 return __first;
2074 ++__first;
2075
2076 if (__pred(__first))
2077 return __first;
2078 ++__first;
2079
2080 if (__pred(__first))
2081 return __first;
2082 ++__first;
2083
2084 if (__pred(__first))
2085 return __first;
2086 ++__first;
2087 }
2088
2089 switch (__last - __first)
2090 {
2091 case 3:
2092 if (__pred(__first))
2093 return __first;
2094 ++__first;
2095 // FALLTHRU
2096 case 2:
2097 if (__pred(__first))
2098 return __first;
2099 ++__first;
2100 // FALLTHRU
2101 case 1:
2102 if (__pred(__first))
2103 return __first;
2104 ++__first;
2105 // FALLTHRU
2106 case 0:
2107 default:
2108 return __last;
2109 }
2110 }
2111
2112 template<typename _Iterator, typename _Predicate>
2113 _GLIBCXX20_CONSTEXPR
2114 inline _Iterator
2115 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2116 {
2117 return __find_if(__first, __last, __pred,
2118 std::__iterator_category(__first));
2119 }
2120
2121 template<typename _InputIterator, typename _Predicate>
2122 _GLIBCXX20_CONSTEXPR
2123 typename iterator_traits<_InputIterator>::difference_type
2124 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2125 {
2126 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2127 for (; __first != __last; ++__first)
2128 if (__pred(__first))
2129 ++__n;
2130 return __n;
2131 }
2132
2133 template<typename _ForwardIterator, typename _Predicate>
2134 _GLIBCXX20_CONSTEXPR
2135 _ForwardIterator
2136 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2137 _Predicate __pred)
2138 {
2139 __first = std::__find_if(__first, __last, __pred);
2140 if (__first == __last)
2141 return __first;
2142 _ForwardIterator __result = __first;
2143 ++__first;
2144 for (; __first != __last; ++__first)
2145 if (!__pred(__first))
2146 {
2147 *__result = _GLIBCXX_MOVE(*__first);
2148 ++__result;
2149 }
2150 return __result;
2151 }
2152
2153 #if __cplusplus >= 201103L
2154 template<typename _ForwardIterator1, typename _ForwardIterator2,
2155 typename _BinaryPredicate>
2156 _GLIBCXX20_CONSTEXPR
2157 bool
2158 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2159 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2160 {
2161 // Efficiently compare identical prefixes: O(N) if sequences
2162 // have the same elements in the same order.
2163 for (; __first1 != __last1; ++__first1, (void)++__first2)
2164 if (!__pred(__first1, __first2))
2165 break;
2166
2167 if (__first1 == __last1)
2168 return true;
2169
2170 // Establish __last2 assuming equal ranges by iterating over the
2171 // rest of the list.
2172 _ForwardIterator2 __last2 = __first2;
2173 std::advance(__last2, std::distance(__first1, __last1));
2174 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2175 {
2176 if (__scan != std::__find_if(__first1, __scan,
2177 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2178 continue; // We've seen this one before.
2179
2180 auto __matches
2181 = std::__count_if(__first2, __last2,
2182 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2183 if (0 == __matches ||
2184 std::__count_if(__scan, __last1,
2185 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2186 != __matches)
2187 return false;
2188 }
2189 return true;
2190 }
2191
2192 /**
2193 * @brief Checks whether a permutation of the second sequence is equal
2194 * to the first sequence.
2195 * @ingroup non_mutating_algorithms
2196 * @param __first1 Start of first range.
2197 * @param __last1 End of first range.
2198 * @param __first2 Start of second range.
2199 * @return true if there exists a permutation of the elements in the range
2200 * [__first2, __first2 + (__last1 - __first1)), beginning with
2201 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
2202 * returns true; otherwise, returns false.
2203 */
2204 template<typename _ForwardIterator1, typename _ForwardIterator2>
2205 _GLIBCXX20_CONSTEXPR
2206 inline bool
2207 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2208 _ForwardIterator2 __first2)
2209 {
2210 // concept requirements
2211 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2212 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2213 __glibcxx_function_requires(_EqualOpConcept<
2214 typename iterator_traits<_ForwardIterator1>::value_type,
2215 typename iterator_traits<_ForwardIterator2>::value_type>)
2216 __glibcxx_requires_valid_range(__first1, __last1);
2217
2218 return std::__is_permutation(__first1, __last1, __first2,
2219 __gnu_cxx::__ops::__iter_equal_to_iter());
2220 }
2221 #endif // C++11
2222
2223 _GLIBCXX_END_NAMESPACE_VERSION
2224 } // namespace std
2225
2226 // NB: This file is included within many other C++ includes, as a way
2227 // of getting the base algorithms. So, make sure that parallel bits
2228 // come in too if requested.
2229 #ifdef _GLIBCXX_PARALLEL
2230 # include <parallel/algobase.h>
2231 #endif
2232
2233 #endif