libstdc++
stl_algobase.h
Go to the documentation of this file.
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>
62#include <ext/type_traits.h>
63#include <ext/numeric_traits.h>
64#include <bits/stl_pair.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
82namespace 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
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
165 _ValueType1;
167 _ValueType2;
168
169 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
170 _ValueType2>)
171 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
172 _ValueType1>)
173
175 _ReferenceType1;
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)
318 { return __it; }
319
320 template<typename _Ite, typename _Seq>
321 _Ite
322 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
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
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>
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>
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,
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,
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
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>
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>
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,
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,
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
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>
1086 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1087 _Size __n, const _Tp& __value,
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,
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,
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,
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<
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<
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#if __cplusplus > 201103L
1649
1650#define __cpp_lib_robust_nonmodifying_seq_ops 201304L
1651
1652 /**
1653 * @brief Tests a range for element-wise equality.
1654 * @ingroup non_mutating_algorithms
1655 * @param __first1 An input iterator.
1656 * @param __last1 An input iterator.
1657 * @param __first2 An input iterator.
1658 * @param __last2 An input iterator.
1659 * @return A boolean true or false.
1660 *
1661 * This compares the elements of two ranges using @c == and returns true or
1662 * false depending on whether all of the corresponding elements of the
1663 * ranges are equal.
1664 */
1665 template<typename _II1, typename _II2>
1666 _GLIBCXX20_CONSTEXPR
1667 inline bool
1668 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1669 {
1670 // concept requirements
1671 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1672 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1673 __glibcxx_function_requires(_EqualOpConcept<
1676 __glibcxx_requires_valid_range(__first1, __last1);
1677 __glibcxx_requires_valid_range(__first2, __last2);
1678
1679 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1680 }
1681
1682 /**
1683 * @brief Tests a range for element-wise equality.
1684 * @ingroup non_mutating_algorithms
1685 * @param __first1 An input iterator.
1686 * @param __last1 An input iterator.
1687 * @param __first2 An input iterator.
1688 * @param __last2 An input iterator.
1689 * @param __binary_pred A binary predicate @link functors
1690 * functor@endlink.
1691 * @return A boolean true or false.
1692 *
1693 * This compares the elements of two ranges using the binary_pred
1694 * parameter, and returns true or
1695 * false depending on whether all of the corresponding elements of the
1696 * ranges are equal.
1697 */
1698 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1699 _GLIBCXX20_CONSTEXPR
1700 inline bool
1701 equal(_IIter1 __first1, _IIter1 __last1,
1702 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1703 {
1704 // concept requirements
1705 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1706 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1707 __glibcxx_requires_valid_range(__first1, __last1);
1708 __glibcxx_requires_valid_range(__first2, __last2);
1709
1710 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1711 __binary_pred);
1712 }
1713#endif // C++14
1714
1715 /**
1716 * @brief Performs @b dictionary comparison on ranges.
1717 * @ingroup sorting_algorithms
1718 * @param __first1 An input iterator.
1719 * @param __last1 An input iterator.
1720 * @param __first2 An input iterator.
1721 * @param __last2 An input iterator.
1722 * @return A boolean true or false.
1723 *
1724 * <em>Returns true if the sequence of elements defined by the range
1725 * [first1,last1) is lexicographically less than the sequence of elements
1726 * defined by the range [first2,last2). Returns false otherwise.</em>
1727 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1728 * then this is an inline call to @c memcmp.
1729 */
1730 template<typename _II1, typename _II2>
1731 _GLIBCXX20_CONSTEXPR
1732 inline bool
1733 lexicographical_compare(_II1 __first1, _II1 __last1,
1734 _II2 __first2, _II2 __last2)
1735 {
1736#ifdef _GLIBCXX_CONCEPT_CHECKS
1737 // concept requirements
1738 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1739 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1740#endif
1741 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1742 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1743 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1744 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1745 __glibcxx_requires_valid_range(__first1, __last1);
1746 __glibcxx_requires_valid_range(__first2, __last2);
1747
1748 return std::__lexicographical_compare_aux(__first1, __last1,
1749 __first2, __last2);
1750 }
1751
1752 /**
1753 * @brief Performs @b dictionary comparison on ranges.
1754 * @ingroup sorting_algorithms
1755 * @param __first1 An input iterator.
1756 * @param __last1 An input iterator.
1757 * @param __first2 An input iterator.
1758 * @param __last2 An input iterator.
1759 * @param __comp A @link comparison_functors comparison functor@endlink.
1760 * @return A boolean true or false.
1761 *
1762 * The same as the four-parameter @c lexicographical_compare, but uses the
1763 * comp parameter instead of @c <.
1764 */
1765 template<typename _II1, typename _II2, typename _Compare>
1766 _GLIBCXX20_CONSTEXPR
1767 inline bool
1768 lexicographical_compare(_II1 __first1, _II1 __last1,
1769 _II2 __first2, _II2 __last2, _Compare __comp)
1770 {
1771 // concept requirements
1772 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1773 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1774 __glibcxx_requires_valid_range(__first1, __last1);
1775 __glibcxx_requires_valid_range(__first2, __last2);
1776
1777 return std::__lexicographical_compare_impl
1778 (__first1, __last1, __first2, __last2,
1779 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1780 }
1781
1782#if __cpp_lib_three_way_comparison
1783 // Iter points to a contiguous range of unsigned narrow character type
1784 // or std::byte, suitable for comparison by memcmp.
1785 template<typename _Iter>
1786 concept __is_byte_iter = contiguous_iterator<_Iter>
1787 && __is_memcmp_ordered<iter_value_t<_Iter>>::__value;
1788
1789 // Return a struct with two members, initialized to the smaller of x and y
1790 // (or x if they compare equal) and the result of the comparison x <=> y.
1791 template<typename _Tp>
1792 constexpr auto
1793 __min_cmp(_Tp __x, _Tp __y)
1794 {
1795 struct _Res {
1796 _Tp _M_min;
1797 decltype(__x <=> __y) _M_cmp;
1798 };
1799 auto __c = __x <=> __y;
1800 if (__c > 0)
1801 return _Res{__y, __c};
1802 return _Res{__x, __c};
1803 }
1804
1805 /**
1806 * @brief Performs dictionary comparison on ranges.
1807 * @ingroup sorting_algorithms
1808 * @param __first1 An input iterator.
1809 * @param __last1 An input iterator.
1810 * @param __first2 An input iterator.
1811 * @param __last2 An input iterator.
1812 * @param __comp A @link comparison_functors comparison functor@endlink.
1813 * @return The comparison category that `__comp(*__first1, *__first2)`
1814 * returns.
1815 */
1816 template<typename _InputIter1, typename _InputIter2, typename _Comp>
1817 constexpr auto
1818 lexicographical_compare_three_way(_InputIter1 __first1,
1819 _InputIter1 __last1,
1820 _InputIter2 __first2,
1821 _InputIter2 __last2,
1822 _Comp __comp)
1823 -> decltype(__comp(*__first1, *__first2))
1824 {
1825 // concept requirements
1826 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1827 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1828 __glibcxx_requires_valid_range(__first1, __last1);
1829 __glibcxx_requires_valid_range(__first2, __last2);
1830
1831 using _Cat = decltype(__comp(*__first1, *__first2));
1832 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1833
1834 if (!std::__is_constant_evaluated())
1835 if constexpr (same_as<_Comp, __detail::_Synth3way>
1836 || same_as<_Comp, compare_three_way>)
1837 if constexpr (__is_byte_iter<_InputIter1>)
1838 if constexpr (__is_byte_iter<_InputIter2>)
1839 {
1840 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1841 __min_cmp(__last1 - __first1, __last2 - __first2);
1842 if (__len)
1843 {
1844 const auto __c
1845 = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
1846 if (__c != 0)
1847 return __c;
1848 }
1849 return __lencmp;
1850 }
1851
1852 while (__first1 != __last1)
1853 {
1854 if (__first2 == __last2)
1855 return strong_ordering::greater;
1856 if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1857 return __cmp;
1858 ++__first1;
1859 ++__first2;
1860 }
1861 return (__first2 == __last2) <=> true; // See PR 94006
1862 }
1863
1864 template<typename _InputIter1, typename _InputIter2>
1865 constexpr auto
1866 lexicographical_compare_three_way(_InputIter1 __first1,
1867 _InputIter1 __last1,
1868 _InputIter2 __first2,
1869 _InputIter2 __last2)
1870 {
1871 return _GLIBCXX_STD_A::
1872 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1873 compare_three_way{});
1874 }
1875#endif // three_way_comparison
1876
1877 template<typename _InputIterator1, typename _InputIterator2,
1878 typename _BinaryPredicate>
1879 _GLIBCXX20_CONSTEXPR
1880 pair<_InputIterator1, _InputIterator2>
1881 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1882 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1883 {
1884 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1885 {
1886 ++__first1;
1887 ++__first2;
1888 }
1889 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1890 }
1891
1892 /**
1893 * @brief Finds the places in ranges which don't match.
1894 * @ingroup non_mutating_algorithms
1895 * @param __first1 An input iterator.
1896 * @param __last1 An input iterator.
1897 * @param __first2 An input iterator.
1898 * @return A pair of iterators pointing to the first mismatch.
1899 *
1900 * This compares the elements of two ranges using @c == and returns a pair
1901 * of iterators. The first iterator points into the first range, the
1902 * second iterator points into the second range, and the elements pointed
1903 * to by the iterators are not equal.
1904 */
1905 template<typename _InputIterator1, typename _InputIterator2>
1906 _GLIBCXX20_CONSTEXPR
1907 inline pair<_InputIterator1, _InputIterator2>
1908 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1909 _InputIterator2 __first2)
1910 {
1911 // concept requirements
1912 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1913 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1914 __glibcxx_function_requires(_EqualOpConcept<
1917 __glibcxx_requires_valid_range(__first1, __last1);
1918
1919 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1920 __gnu_cxx::__ops::__iter_equal_to_iter());
1921 }
1922
1923 /**
1924 * @brief Finds the places in ranges which don't match.
1925 * @ingroup non_mutating_algorithms
1926 * @param __first1 An input iterator.
1927 * @param __last1 An input iterator.
1928 * @param __first2 An input iterator.
1929 * @param __binary_pred A binary predicate @link functors
1930 * functor@endlink.
1931 * @return A pair of iterators pointing to the first mismatch.
1932 *
1933 * This compares the elements of two ranges using the binary_pred
1934 * parameter, and returns a pair
1935 * of iterators. The first iterator points into the first range, the
1936 * second iterator points into the second range, and the elements pointed
1937 * to by the iterators are not equal.
1938 */
1939 template<typename _InputIterator1, typename _InputIterator2,
1940 typename _BinaryPredicate>
1941 _GLIBCXX20_CONSTEXPR
1942 inline pair<_InputIterator1, _InputIterator2>
1943 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1944 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1945 {
1946 // concept requirements
1947 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1948 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1949 __glibcxx_requires_valid_range(__first1, __last1);
1950
1951 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1952 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1953 }
1954
1955#if __cplusplus > 201103L
1956
1957 template<typename _InputIterator1, typename _InputIterator2,
1958 typename _BinaryPredicate>
1959 _GLIBCXX20_CONSTEXPR
1960 pair<_InputIterator1, _InputIterator2>
1961 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1962 _InputIterator2 __first2, _InputIterator2 __last2,
1963 _BinaryPredicate __binary_pred)
1964 {
1965 while (__first1 != __last1 && __first2 != __last2
1966 && __binary_pred(__first1, __first2))
1967 {
1968 ++__first1;
1969 ++__first2;
1970 }
1971 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1972 }
1973
1974 /**
1975 * @brief Finds the places in ranges which don't match.
1976 * @ingroup non_mutating_algorithms
1977 * @param __first1 An input iterator.
1978 * @param __last1 An input iterator.
1979 * @param __first2 An input iterator.
1980 * @param __last2 An input iterator.
1981 * @return A pair of iterators pointing to the first mismatch.
1982 *
1983 * This compares the elements of two ranges using @c == and returns a pair
1984 * of iterators. The first iterator points into the first range, the
1985 * second iterator points into the second range, and the elements pointed
1986 * to by the iterators are not equal.
1987 */
1988 template<typename _InputIterator1, typename _InputIterator2>
1989 _GLIBCXX20_CONSTEXPR
1990 inline pair<_InputIterator1, _InputIterator2>
1991 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1992 _InputIterator2 __first2, _InputIterator2 __last2)
1993 {
1994 // concept requirements
1995 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1996 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1997 __glibcxx_function_requires(_EqualOpConcept<
2000 __glibcxx_requires_valid_range(__first1, __last1);
2001 __glibcxx_requires_valid_range(__first2, __last2);
2002
2003 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2004 __gnu_cxx::__ops::__iter_equal_to_iter());
2005 }
2006
2007 /**
2008 * @brief Finds the places in ranges which don't match.
2009 * @ingroup non_mutating_algorithms
2010 * @param __first1 An input iterator.
2011 * @param __last1 An input iterator.
2012 * @param __first2 An input iterator.
2013 * @param __last2 An input iterator.
2014 * @param __binary_pred A binary predicate @link functors
2015 * functor@endlink.
2016 * @return A pair of iterators pointing to the first mismatch.
2017 *
2018 * This compares the elements of two ranges using the binary_pred
2019 * parameter, and returns a pair
2020 * of iterators. The first iterator points into the first range, the
2021 * second iterator points into the second range, and the elements pointed
2022 * to by the iterators are not equal.
2023 */
2024 template<typename _InputIterator1, typename _InputIterator2,
2025 typename _BinaryPredicate>
2026 _GLIBCXX20_CONSTEXPR
2027 inline pair<_InputIterator1, _InputIterator2>
2028 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2029 _InputIterator2 __first2, _InputIterator2 __last2,
2030 _BinaryPredicate __binary_pred)
2031 {
2032 // concept requirements
2033 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2034 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2035 __glibcxx_requires_valid_range(__first1, __last1);
2036 __glibcxx_requires_valid_range(__first2, __last2);
2037
2038 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2039 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2040 }
2041#endif
2042
2043_GLIBCXX_END_NAMESPACE_ALGO
2044
2045 /// This is an overload used by find algos for the Input Iterator case.
2046 template<typename _InputIterator, typename _Predicate>
2047 _GLIBCXX20_CONSTEXPR
2048 inline _InputIterator
2049 __find_if(_InputIterator __first, _InputIterator __last,
2050 _Predicate __pred, input_iterator_tag)
2051 {
2052 while (__first != __last && !__pred(__first))
2053 ++__first;
2054 return __first;
2055 }
2056
2057 /// This is an overload used by find algos for the RAI case.
2058 template<typename _RandomAccessIterator, typename _Predicate>
2059 _GLIBCXX20_CONSTEXPR
2060 _RandomAccessIterator
2061 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
2062 _Predicate __pred, random_access_iterator_tag)
2063 {
2065 __trip_count = (__last - __first) >> 2;
2066
2067 for (; __trip_count > 0; --__trip_count)
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 if (__pred(__first))
2082 return __first;
2083 ++__first;
2084 }
2085
2086 switch (__last - __first)
2087 {
2088 case 3:
2089 if (__pred(__first))
2090 return __first;
2091 ++__first;
2092 // FALLTHRU
2093 case 2:
2094 if (__pred(__first))
2095 return __first;
2096 ++__first;
2097 // FALLTHRU
2098 case 1:
2099 if (__pred(__first))
2100 return __first;
2101 ++__first;
2102 // FALLTHRU
2103 case 0:
2104 default:
2105 return __last;
2106 }
2107 }
2108
2109 template<typename _Iterator, typename _Predicate>
2110 _GLIBCXX20_CONSTEXPR
2111 inline _Iterator
2112 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2113 {
2114 return __find_if(__first, __last, __pred,
2115 std::__iterator_category(__first));
2116 }
2117
2118 template<typename _InputIterator, typename _Predicate>
2119 _GLIBCXX20_CONSTEXPR
2120 typename iterator_traits<_InputIterator>::difference_type
2121 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2122 {
2123 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2124 for (; __first != __last; ++__first)
2125 if (__pred(__first))
2126 ++__n;
2127 return __n;
2128 }
2129
2130 template<typename _ForwardIterator, typename _Predicate>
2131 _GLIBCXX20_CONSTEXPR
2132 _ForwardIterator
2133 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2134 _Predicate __pred)
2135 {
2136 __first = std::__find_if(__first, __last, __pred);
2137 if (__first == __last)
2138 return __first;
2139 _ForwardIterator __result = __first;
2140 ++__first;
2141 for (; __first != __last; ++__first)
2142 if (!__pred(__first))
2143 {
2144 *__result = _GLIBCXX_MOVE(*__first);
2145 ++__result;
2146 }
2147 return __result;
2148 }
2149
2150#if __cplusplus >= 201103L
2151 template<typename _ForwardIterator1, typename _ForwardIterator2,
2152 typename _BinaryPredicate>
2153 _GLIBCXX20_CONSTEXPR
2154 bool
2155 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2156 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2157 {
2158 // Efficiently compare identical prefixes: O(N) if sequences
2159 // have the same elements in the same order.
2160 for (; __first1 != __last1; ++__first1, (void)++__first2)
2161 if (!__pred(__first1, __first2))
2162 break;
2163
2164 if (__first1 == __last1)
2165 return true;
2166
2167 // Establish __last2 assuming equal ranges by iterating over the
2168 // rest of the list.
2169 _ForwardIterator2 __last2 = __first2;
2170 std::advance(__last2, std::distance(__first1, __last1));
2171 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2172 {
2173 if (__scan != std::__find_if(__first1, __scan,
2174 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2175 continue; // We've seen this one before.
2176
2177 auto __matches
2178 = std::__count_if(__first2, __last2,
2179 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2180 if (0 == __matches ||
2181 std::__count_if(__scan, __last1,
2182 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2183 != __matches)
2184 return false;
2185 }
2186 return true;
2187 }
2188
2189 /**
2190 * @brief Checks whether a permutation of the second sequence is equal
2191 * to the first sequence.
2192 * @ingroup non_mutating_algorithms
2193 * @param __first1 Start of first range.
2194 * @param __last1 End of first range.
2195 * @param __first2 Start of second range.
2196 * @return true if there exists a permutation of the elements in the range
2197 * [__first2, __first2 + (__last1 - __first1)), beginning with
2198 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
2199 * returns true; otherwise, returns false.
2200 */
2201 template<typename _ForwardIterator1, typename _ForwardIterator2>
2202 _GLIBCXX20_CONSTEXPR
2203 inline bool
2204 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2205 _ForwardIterator2 __first2)
2206 {
2207 // concept requirements
2208 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2209 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2210 __glibcxx_function_requires(_EqualOpConcept<
2213 __glibcxx_requires_valid_range(__first1, __last1);
2214
2215 return std::__is_permutation(__first1, __last1, __first2,
2216 __gnu_cxx::__ops::__iter_equal_to_iter());
2217 }
2218#endif // C++11
2219
2220_GLIBCXX_END_NAMESPACE_VERSION
2221} // namespace std
2222
2223// NB: This file is included within many other C++ includes, as a way
2224// of getting the base algorithms. So, make sure that parallel bits
2225// come in too if requested.
2226#ifdef _GLIBCXX_PARALLEL
2227# include <parallel/algobase.h>
2228#endif
2229
2230#endif
Parallel STL function calls corresponding to the stl_algobase.h header. The functions defined here ma...
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
Definition type_traits:1983
constexpr bool is_constant_evaluated() noexcept
Returns true only when called during constant evaluation.
Definition type_traits:3644
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:97
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr _Tp __lg(_Tp __n)
This is a helper function for the sort routines and for random.tcc.
constexpr _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
is_nothrow_copy_constructible
Definition type_traits:1133
Safe iterator wrapper.
Traits class for iterators.
Marking input iterators.
Marking output iterators.
Random-access iterators support a superset of bidirectional iterator operations.