1 // Core algorithmic facilities -*- C++ -*-
2
3 // Copyright (C) 2001-2022 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 > 201703L
76 # include <compare>
77 #endif
78
_GLIBCXX_VISIBILITY(default)79 namespace std _GLIBCXX_VISIBILITY(default)
80 {
81 _GLIBCXX_BEGIN_NAMESPACE_VERSION
82
83 /*
84 * A constexpr wrapper for __builtin_memcmp.
85 * @param __num The number of elements of type _Tp (not bytes).
86 */
87 template<typename _Tp, typename _Up>
88 _GLIBCXX14_CONSTEXPR
89 inline int
90 __memcmp(const _Tp* __first1, const _Up* __first2, size_t __num)
91 {
92 #if __cplusplus >= 201103L
93 static_assert(sizeof(_Tp) == sizeof(_Up), "can be compared with memcmp");
94 #endif
95 #ifdef __cpp_lib_is_constant_evaluated
96 if (std::is_constant_evaluated())
97 {
98 for(; __num > 0; ++__first1, ++__first2, --__num)
99 if (*__first1 != *__first2)
100 return *__first1 < *__first2 ? -1 : 1;
101 return 0;
102 }
103 else
104 #endif
105 return __builtin_memcmp(__first1, __first2, sizeof(_Tp) * __num);
106 }
107
108 #if __cplusplus < 201103L
109 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
110 // nutshell, we are partially implementing the resolution of DR 187,
111 // when it's safe, i.e., the value_types are equal.
112 template<bool _BoolType>
113 struct __iter_swap
114 {
115 template<typename _ForwardIterator1, typename _ForwardIterator2>
116 static void
117 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
118 {
119 typedef typename iterator_traits<_ForwardIterator1>::value_type
120 _ValueType1;
121 _ValueType1 __tmp = *__a;
122 *__a = *__b;
123 *__b = __tmp;
124 }
125 };
126
127 template<>
128 struct __iter_swap<true>
129 {
130 template<typename _ForwardIterator1, typename _ForwardIterator2>
131 static void
132 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
133 {
134 swap(*__a, *__b);
135 }
136 };
137 #endif // C++03
138
139 /**
140 * @brief Swaps the contents of two iterators.
141 * @ingroup mutating_algorithms
142 * @param __a An iterator.
143 * @param __b Another iterator.
144 * @return Nothing.
145 *
146 * This function swaps the values pointed to by two iterators, not the
147 * iterators themselves.
148 */
149 template<typename _ForwardIterator1, typename _ForwardIterator2>
150 _GLIBCXX20_CONSTEXPR
151 inline void
152 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
153 {
154 // concept requirements
155 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
156 _ForwardIterator1>)
157 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
158 _ForwardIterator2>)
159
160 #if __cplusplus < 201103L
161 typedef typename iterator_traits<_ForwardIterator1>::value_type
162 _ValueType1;
163 typedef typename iterator_traits<_ForwardIterator2>::value_type
164 _ValueType2;
165
166 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
167 _ValueType2>)
168 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
169 _ValueType1>)
170
171 typedef typename iterator_traits<_ForwardIterator1>::reference
172 _ReferenceType1;
173 typedef typename iterator_traits<_ForwardIterator2>::reference
174 _ReferenceType2;
175 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
176 && __are_same<_ValueType1&, _ReferenceType1>::__value
177 && __are_same<_ValueType2&, _ReferenceType2>::__value>::
178 iter_swap(__a, __b);
179 #else
180 // _GLIBCXX_RESOLVE_LIB_DEFECTS
181 // 187. iter_swap underspecified
182 swap(*__a, *__b);
183 #endif
184 }
185
186 /**
187 * @brief Swap the elements of two sequences.
188 * @ingroup mutating_algorithms
189 * @param __first1 A forward iterator.
190 * @param __last1 A forward iterator.
191 * @param __first2 A forward iterator.
192 * @return An iterator equal to @p first2+(last1-first1).
193 *
194 * Swaps each element in the range @p [first1,last1) with the
195 * corresponding element in the range @p [first2,(last1-first1)).
196 * The ranges must not overlap.
197 */
198 template<typename _ForwardIterator1, typename _ForwardIterator2>
199 _GLIBCXX20_CONSTEXPR
200 _ForwardIterator2
201 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
202 _ForwardIterator2 __first2)
203 {
204 // concept requirements
205 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
206 _ForwardIterator1>)
207 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
208 _ForwardIterator2>)
209 __glibcxx_requires_valid_range(__first1, __last1);
210
211 for (; __first1 != __last1; ++__first1, (void)++__first2)
212 std::iter_swap(__first1, __first2);
213 return __first2;
214 }
215
216 /**
217 * @brief This does what you think it does.
218 * @ingroup sorting_algorithms
219 * @param __a A thing of arbitrary type.
220 * @param __b Another thing of arbitrary type.
221 * @return The lesser of the parameters.
222 *
223 * This is the simple classic generic implementation. It will work on
224 * temporary expressions, since they are only evaluated once, unlike a
225 * preprocessor macro.
226 */
227 template<typename _Tp>
228 _GLIBCXX14_CONSTEXPR
229 inline const _Tp&
230 min(const _Tp& __a, const _Tp& __b)
231 {
232 // concept requirements
233 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
234 //return __b < __a ? __b : __a;
235 if (__b < __a)
236 return __b;
237 return __a;
238 }
239
240 /**
241 * @brief This does what you think it does.
242 * @ingroup sorting_algorithms
243 * @param __a A thing of arbitrary type.
244 * @param __b Another thing of arbitrary type.
245 * @return The greater of the parameters.
246 *
247 * This is the simple classic generic implementation. It will work on
248 * temporary expressions, since they are only evaluated once, unlike a
249 * preprocessor macro.
250 */
251 template<typename _Tp>
252 _GLIBCXX14_CONSTEXPR
253 inline const _Tp&
254 max(const _Tp& __a, const _Tp& __b)
255 {
256 // concept requirements
257 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
258 //return __a < __b ? __b : __a;
259 if (__a < __b)
260 return __b;
261 return __a;
262 }
263
264 /**
265 * @brief This does what you think it does.
266 * @ingroup sorting_algorithms
267 * @param __a A thing of arbitrary type.
268 * @param __b Another thing of arbitrary type.
269 * @param __comp A @link comparison_functors comparison functor@endlink.
270 * @return The lesser of the parameters.
271 *
272 * This will work on temporary expressions, since they are only evaluated
273 * once, unlike a preprocessor macro.
274 */
275 template<typename _Tp, typename _Compare>
276 _GLIBCXX14_CONSTEXPR
277 inline const _Tp&
278 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
279 {
280 //return __comp(__b, __a) ? __b : __a;
281 if (__comp(__b, __a))
282 return __b;
283 return __a;
284 }
285
286 /**
287 * @brief This does what you think it does.
288 * @ingroup sorting_algorithms
289 * @param __a A thing of arbitrary type.
290 * @param __b Another thing of arbitrary type.
291 * @param __comp A @link comparison_functors comparison functor@endlink.
292 * @return The greater of the parameters.
293 *
294 * This will work on temporary expressions, since they are only evaluated
295 * once, unlike a preprocessor macro.
296 */
297 template<typename _Tp, typename _Compare>
298 _GLIBCXX14_CONSTEXPR
299 inline const _Tp&
300 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
301 {
302 //return __comp(__a, __b) ? __b : __a;
303 if (__comp(__a, __b))
304 return __b;
305 return __a;
306 }
307
308 // Fallback implementation of the function in bits/stl_iterator.h used to
309 // remove the __normal_iterator wrapper. See copy, fill, ...
310 template<typename _Iterator>
311 _GLIBCXX20_CONSTEXPR
312 inline _Iterator
313 __niter_base(_Iterator __it)
314 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
315 { return __it; }
316
317 template<typename _Ite, typename _Seq>
318 _Ite
319 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
320 std::random_access_iterator_tag>&);
321
322 // Reverse the __niter_base transformation to get a
323 // __normal_iterator back again (this assumes that __normal_iterator
324 // is only used to wrap random access iterators, like pointers).
325 template<typename _From, typename _To>
326 _GLIBCXX20_CONSTEXPR
327 inline _From
328 __niter_wrap(_From __from, _To __res)
329 { return __from + (__res - std::__niter_base(__from)); }
330
331 // No need to wrap, iterator already has the right type.
332 template<typename _Iterator>
333 _GLIBCXX20_CONSTEXPR
334 inline _Iterator
335 __niter_wrap(const _Iterator&, _Iterator __res)
336 { return __res; }
337
338 // All of these auxiliary structs serve two purposes. (1) Replace
339 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
340 // because the input and output ranges are permitted to overlap.)
341 // (2) If we're using random access iterators, then write the loop as
342 // a for loop with an explicit count.
343
344 template<bool _IsMove, bool _IsSimple, typename _Category>
345 struct __copy_move
346 {
347 template<typename _II, typename _OI>
348 _GLIBCXX20_CONSTEXPR
349 static _OI
350 __copy_m(_II __first, _II __last, _OI __result)
351 {
352 for (; __first != __last; ++__result, (void)++__first)
353 *__result = *__first;
354 return __result;
355 }
356 };
357
358 #if __cplusplus >= 201103L
359 template<typename _Category>
360 struct __copy_move<true, false, _Category>
361 {
362 template<typename _II, typename _OI>
363 _GLIBCXX20_CONSTEXPR
364 static _OI
365 __copy_m(_II __first, _II __last, _OI __result)
366 {
367 for (; __first != __last; ++__result, (void)++__first)
368 *__result = std::move(*__first);
369 return __result;
370 }
371 };
372 #endif
373
374 template<>
375 struct __copy_move<false, false, random_access_iterator_tag>
376 {
377 template<typename _II, typename _OI>
378 _GLIBCXX20_CONSTEXPR
379 static _OI
380 __copy_m(_II __first, _II __last, _OI __result)
381 {
382 typedef typename iterator_traits<_II>::difference_type _Distance;
383 for(_Distance __n = __last - __first; __n > 0; --__n)
384 {
385 *__result = *__first;
386 ++__first;
387 ++__result;
388 }
389 return __result;
390 }
391
392 template<typename _Tp, typename _Up>
393 static void
394 __assign_one(_Tp* __to, _Up* __from)
395 { *__to = *__from; }
396 };
397
398 #if __cplusplus >= 201103L
399 template<>
400 struct __copy_move<true, false, random_access_iterator_tag>
401 {
402 template<typename _II, typename _OI>
403 _GLIBCXX20_CONSTEXPR
404 static _OI
405 __copy_m(_II __first, _II __last, _OI __result)
406 {
407 typedef typename iterator_traits<_II>::difference_type _Distance;
408 for(_Distance __n = __last - __first; __n > 0; --__n)
409 {
410 *__result = std::move(*__first);
411 ++__first;
412 ++__result;
413 }
414 return __result;
415 }
416
417 template<typename _Tp, typename _Up>
418 static void
419 __assign_one(_Tp* __to, _Up* __from)
420 { *__to = std::move(*__from); }
421 };
422 #endif
423
424 template<bool _IsMove>
425 struct __copy_move<_IsMove, true, random_access_iterator_tag>
426 {
427 template<typename _Tp, typename _Up>
428 _GLIBCXX20_CONSTEXPR
429 static _Up*
430 __copy_m(_Tp* __first, _Tp* __last, _Up* __result)
431 {
432 const ptrdiff_t _Num = __last - __first;
433 if (__builtin_expect(_Num > 1, true))
434 __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
435 else if (_Num == 1)
436 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
437 __assign_one(__result, __first);
438 return __result + _Num;
439 }
440 };
441
442 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
443
444 template<typename _Tp, typename _Ref, typename _Ptr>
445 struct _Deque_iterator;
446
447 struct _Bit_iterator;
448
449 _GLIBCXX_END_NAMESPACE_CONTAINER
450
451 // Helpers for streambuf iterators (either istream or ostream).
452 // NB: avoid including <iosfwd>, relatively large.
453 template<typename _CharT>
454 struct char_traits;
455
456 template<typename _CharT, typename _Traits>
457 class istreambuf_iterator;
458
459 template<typename _CharT, typename _Traits>
460 class ostreambuf_iterator;
461
462 template<bool _IsMove, typename _CharT>
463 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
464 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
465 __copy_move_a2(_CharT*, _CharT*,
466 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
467
468 template<bool _IsMove, typename _CharT>
469 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
470 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
471 __copy_move_a2(const _CharT*, const _CharT*,
472 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
473
474 template<bool _IsMove, typename _CharT>
475 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
476 _CharT*>::__type
477 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
478 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
479
480 template<bool _IsMove, typename _CharT>
481 typename __gnu_cxx::__enable_if<
482 __is_char<_CharT>::__value,
483 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
484 __copy_move_a2(
485 istreambuf_iterator<_CharT, char_traits<_CharT> >,
486 istreambuf_iterator<_CharT, char_traits<_CharT> >,
487 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
488
489 template<bool _IsMove, typename _II, typename _OI>
490 _GLIBCXX20_CONSTEXPR
491 inline _OI
492 __copy_move_a2(_II __first, _II __last, _OI __result)
493 {
494 typedef typename iterator_traits<_II>::iterator_category _Category;
495 #ifdef __cpp_lib_is_constant_evaluated
496 if (std::is_constant_evaluated())
497 return std::__copy_move<_IsMove, false, _Category>::
498 __copy_m(__first, __last, __result);
499 #endif
500 return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value,
501 _Category>::__copy_m(__first, __last, __result);
502 }
503
504 template<bool _IsMove,
505 typename _Tp, typename _Ref, typename _Ptr, typename _OI>
506 _OI
507 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
508 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
509 _OI);
510
511 template<bool _IsMove,
512 typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
513 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
514 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
515 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
516 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
517
518 template<bool _IsMove, typename _II, typename _Tp>
519 typename __gnu_cxx::__enable_if<
520 __is_random_access_iter<_II>::__value,
521 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
522 __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
523
524 template<bool _IsMove, typename _II, typename _OI>
525 _GLIBCXX20_CONSTEXPR
526 inline _OI
527 __copy_move_a1(_II __first, _II __last, _OI __result)
528 { return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
529
530 template<bool _IsMove, typename _II, typename _OI>
531 _GLIBCXX20_CONSTEXPR
532 inline _OI
533 __copy_move_a(_II __first, _II __last, _OI __result)
534 {
535 return std::__niter_wrap(__result,
536 std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
537 std::__niter_base(__last),
538 std::__niter_base(__result)));
539 }
540
541 template<bool _IsMove,
542 typename _Ite, typename _Seq, typename _Cat, typename _OI>
543 _OI
544 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
545 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
546 _OI);
547
548 template<bool _IsMove,
549 typename _II, typename _Ite, typename _Seq, typename _Cat>
550 __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
551 __copy_move_a(_II, _II,
552 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
553
554 template<bool _IsMove,
555 typename _IIte, typename _ISeq, typename _ICat,
556 typename _OIte, typename _OSeq, typename _OCat>
557 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
558 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
559 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
560 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
561
562 template<typename _InputIterator, typename _Size, typename _OutputIterator>
563 _GLIBCXX20_CONSTEXPR
564 _OutputIterator
565 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
566 bool)
567 {
568 if (__n > 0)
569 {
570 while (true)
571 {
572 *__result = *__first;
573 ++__result;
574 if (--__n > 0)
575 ++__first;
576 else
577 break;
578 }
579 }
580 return __result;
581 }
582
583 template<typename _CharT, typename _Size>
584 typename __gnu_cxx::__enable_if<
585 __is_char<_CharT>::__value, _CharT*>::__type
586 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
587 _Size, _CharT*, bool);
588
589 template<typename _CharT, typename _Size>
590 typename __gnu_cxx::__enable_if<
591 __is_char<_CharT>::__value,
592 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
593 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
594 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
595 bool);
596
597 /**
598 * @brief Copies the range [first,last) into result.
599 * @ingroup mutating_algorithms
600 * @param __first An input iterator.
601 * @param __last An input iterator.
602 * @param __result An output iterator.
603 * @return result + (last - first)
604 *
605 * This inline function will boil down to a call to @c memmove whenever
606 * possible. Failing that, if random access iterators are passed, then the
607 * loop count will be known (and therefore a candidate for compiler
608 * optimizations such as unrolling). Result may not be contained within
609 * [first,last); the copy_backward function should be used instead.
610 *
611 * Note that the end of the output range is permitted to be contained
612 * within [first,last).
613 */
614 template<typename _II, typename _OI>
615 _GLIBCXX20_CONSTEXPR
616 inline _OI
617 copy(_II __first, _II __last, _OI __result)
618 {
619 // concept requirements
620 __glibcxx_function_requires(_InputIteratorConcept<_II>)
621 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
622 typename iterator_traits<_II>::reference>)
623 __glibcxx_requires_can_increment_range(__first, __last, __result);
624
625 return std::__copy_move_a<__is_move_iterator<_II>::__value>
626 (std::__miter_base(__first), std::__miter_base(__last), __result);
627 }
628
629 #if __cplusplus >= 201103L
630 /**
631 * @brief Moves the range [first,last) into result.
632 * @ingroup mutating_algorithms
633 * @param __first An input iterator.
634 * @param __last An input iterator.
635 * @param __result An output iterator.
636 * @return result + (last - first)
637 *
638 * This inline function will boil down to a call to @c memmove whenever
639 * possible. Failing that, if random access iterators are passed, then the
640 * loop count will be known (and therefore a candidate for compiler
641 * optimizations such as unrolling). Result may not be contained within
642 * [first,last); the move_backward function should be used instead.
643 *
644 * Note that the end of the output range is permitted to be contained
645 * within [first,last).
646 */
647 template<typename _II, typename _OI>
648 _GLIBCXX20_CONSTEXPR
649 inline _OI
650 move(_II __first, _II __last, _OI __result)
651 {
652 // concept requirements
653 __glibcxx_function_requires(_InputIteratorConcept<_II>)
654 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
655 typename iterator_traits<_II>::value_type&&>)
656 __glibcxx_requires_can_increment_range(__first, __last, __result);
657
658 return std::__copy_move_a<true>(std::__miter_base(__first),
659 std::__miter_base(__last), __result);
660 }
661
662 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
663 #else
664 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
665 #endif
666
667 template<bool _IsMove, bool _IsSimple, typename _Category>
668 struct __copy_move_backward
669 {
670 template<typename _BI1, typename _BI2>
671 _GLIBCXX20_CONSTEXPR
672 static _BI2
673 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
674 {
675 while (__first != __last)
676 *--__result = *--__last;
677 return __result;
678 }
679 };
680
681 #if __cplusplus >= 201103L
682 template<typename _Category>
683 struct __copy_move_backward<true, false, _Category>
684 {
685 template<typename _BI1, typename _BI2>
686 _GLIBCXX20_CONSTEXPR
687 static _BI2
688 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
689 {
690 while (__first != __last)
691 *--__result = std::move(*--__last);
692 return __result;
693 }
694 };
695 #endif
696
697 template<>
698 struct __copy_move_backward<false, false, random_access_iterator_tag>
699 {
700 template<typename _BI1, typename _BI2>
701 _GLIBCXX20_CONSTEXPR
702 static _BI2
703 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
704 {
705 typename iterator_traits<_BI1>::difference_type
706 __n = __last - __first;
707 for (; __n > 0; --__n)
708 *--__result = *--__last;
709 return __result;
710 }
711 };
712
713 #if __cplusplus >= 201103L
714 template<>
715 struct __copy_move_backward<true, false, random_access_iterator_tag>
716 {
717 template<typename _BI1, typename _BI2>
718 _GLIBCXX20_CONSTEXPR
719 static _BI2
720 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
721 {
722 typename iterator_traits<_BI1>::difference_type
723 __n = __last - __first;
724 for (; __n > 0; --__n)
725 *--__result = std::move(*--__last);
726 return __result;
727 }
728 };
729 #endif
730
731 template<bool _IsMove>
732 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
733 {
734 template<typename _Tp, typename _Up>
735 _GLIBCXX20_CONSTEXPR
736 static _Up*
737 __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result)
738 {
739 const ptrdiff_t _Num = __last - __first;
740 if (__builtin_expect(_Num > 1, true))
741 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
742 else if (_Num == 1)
743 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
744 __assign_one(__result - 1, __first);
745 return __result - _Num;
746 }
747 };
748
749 template<bool _IsMove, typename _BI1, typename _BI2>
750 _GLIBCXX20_CONSTEXPR
751 inline _BI2
752 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
753 {
754 typedef typename iterator_traits<_BI1>::iterator_category _Category;
755 #ifdef __cpp_lib_is_constant_evaluated
756 if (std::is_constant_evaluated())
757 return std::__copy_move_backward<_IsMove, false, _Category>::
758 __copy_move_b(__first, __last, __result);
759 #endif
760 return std::__copy_move_backward<_IsMove,
761 __memcpyable<_BI2, _BI1>::__value,
762 _Category>::__copy_move_b(__first,
763 __last,
764 __result);
765 }
766
767 template<bool _IsMove, typename _BI1, typename _BI2>
768 _GLIBCXX20_CONSTEXPR
769 inline _BI2
770 __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
771 { return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); }
772
773 template<bool _IsMove,
774 typename _Tp, typename _Ref, typename _Ptr, typename _OI>
775 _OI
776 __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
777 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
778 _OI);
779
780 template<bool _IsMove,
781 typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
782 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
783 __copy_move_backward_a1(
784 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
785 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
786 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
787
788 template<bool _IsMove, typename _II, typename _Tp>
789 typename __gnu_cxx::__enable_if<
790 __is_random_access_iter<_II>::__value,
791 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
792 __copy_move_backward_a1(_II, _II,
793 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
794
795 template<bool _IsMove, typename _II, typename _OI>
796 _GLIBCXX20_CONSTEXPR
797 inline _OI
798 __copy_move_backward_a(_II __first, _II __last, _OI __result)
799 {
800 return std::__niter_wrap(__result,
801 std::__copy_move_backward_a1<_IsMove>
802 (std::__niter_base(__first), std::__niter_base(__last),
803 std::__niter_base(__result)));
804 }
805
806 template<bool _IsMove,
807 typename _Ite, typename _Seq, typename _Cat, typename _OI>
808 _OI
809 __copy_move_backward_a(
810 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
811 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
812 _OI);
813
814 template<bool _IsMove,
815 typename _II, typename _Ite, typename _Seq, typename _Cat>
816 __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
817 __copy_move_backward_a(_II, _II,
818 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
819
820 template<bool _IsMove,
821 typename _IIte, typename _ISeq, typename _ICat,
822 typename _OIte, typename _OSeq, typename _OCat>
823 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
824 __copy_move_backward_a(
825 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
826 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
827 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
828
829 /**
830 * @brief Copies the range [first,last) into result.
831 * @ingroup mutating_algorithms
832 * @param __first A bidirectional iterator.
833 * @param __last A bidirectional iterator.
834 * @param __result A bidirectional iterator.
835 * @return result - (last - first)
836 *
837 * The function has the same effect as copy, but starts at the end of the
838 * range and works its way to the start, returning the start of the result.
839 * This inline function will boil down to a call to @c memmove whenever
840 * possible. Failing that, if random access iterators are passed, then the
841 * loop count will be known (and therefore a candidate for compiler
842 * optimizations such as unrolling).
843 *
844 * Result may not be in the range (first,last]. Use copy instead. Note
845 * that the start of the output range may overlap [first,last).
846 */
847 template<typename _BI1, typename _BI2>
848 _GLIBCXX20_CONSTEXPR
849 inline _BI2
850 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
851 {
852 // concept requirements
853 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
854 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
855 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
856 typename iterator_traits<_BI1>::reference>)
857 __glibcxx_requires_can_decrement_range(__first, __last, __result);
858
859 return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
860 (std::__miter_base(__first), std::__miter_base(__last), __result);
861 }
862
863 #if __cplusplus >= 201103L
864 /**
865 * @brief Moves the range [first,last) into result.
866 * @ingroup mutating_algorithms
867 * @param __first A bidirectional iterator.
868 * @param __last A bidirectional iterator.
869 * @param __result A bidirectional iterator.
870 * @return result - (last - first)
871 *
872 * The function has the same effect as move, but starts at the end of the
873 * range and works its way to the start, returning the start of the result.
874 * This inline function will boil down to a call to @c memmove whenever
875 * possible. Failing that, if random access iterators are passed, then the
876 * loop count will be known (and therefore a candidate for compiler
877 * optimizations such as unrolling).
878 *
879 * Result may not be in the range (first,last]. Use move instead. Note
880 * that the start of the output range may overlap [first,last).
881 */
882 template<typename _BI1, typename _BI2>
883 _GLIBCXX20_CONSTEXPR
884 inline _BI2
885 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
886 {
887 // concept requirements
888 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
889 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
890 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
891 typename iterator_traits<_BI1>::value_type&&>)
892 __glibcxx_requires_can_decrement_range(__first, __last, __result);
893
894 return std::__copy_move_backward_a<true>(std::__miter_base(__first),
895 std::__miter_base(__last),
896 __result);
897 }
898
899 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
900 #else
901 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
902 #endif
903
904 template<typename _ForwardIterator, typename _Tp>
905 _GLIBCXX20_CONSTEXPR
906 inline typename
907 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
908 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
909 const _Tp& __value)
910 {
911 for (; __first != __last; ++__first)
912 *__first = __value;
913 }
914
915 template<typename _ForwardIterator, typename _Tp>
916 _GLIBCXX20_CONSTEXPR
917 inline typename
918 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
919 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
920 const _Tp& __value)
921 {
922 const _Tp __tmp = __value;
923 for (; __first != __last; ++__first)
924 *__first = __tmp;
925 }
926
927 // Specialization: for char types we can use memset.
928 template<typename _Tp>
929 _GLIBCXX20_CONSTEXPR
930 inline typename
931 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
932 __fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c)
933 {
934 const _Tp __tmp = __c;
935 #if __cpp_lib_is_constant_evaluated
936 if (std::is_constant_evaluated())
937 {
938 for (; __first != __last; ++__first)
939 *__first = __tmp;
940 return;
941 }
942 #endif
943 if (const size_t __len = __last - __first)
944 __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
945 }
946
947 template<typename _Ite, typename _Cont, typename _Tp>
948 _GLIBCXX20_CONSTEXPR
949 inline void
950 __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
951 ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
952 const _Tp& __value)
953 { std::__fill_a1(__first.base(), __last.base(), __value); }
954
955 template<typename _Tp, typename _VTp>
956 void
957 __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
958 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
959 const _VTp&);
960
961 _GLIBCXX20_CONSTEXPR
962 void
963 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
964 const bool&);
965
966 template<typename _FIte, typename _Tp>
967 _GLIBCXX20_CONSTEXPR
968 inline void
969 __fill_a(_FIte __first, _FIte __last, const _Tp& __value)
970 { std::__fill_a1(__first, __last, __value); }
971
972 template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
973 void
974 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
975 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
976 const _Tp&);
977
978 /**
979 * @brief Fills the range [first,last) with copies of value.
980 * @ingroup mutating_algorithms
981 * @param __first A forward iterator.
982 * @param __last A forward iterator.
983 * @param __value A reference-to-const of arbitrary type.
984 * @return Nothing.
985 *
986 * This function fills a range with copies of the same value. For char
987 * types filling contiguous areas of memory, this becomes an inline call
988 * to @c memset or @c wmemset.
989 */
990 template<typename _ForwardIterator, typename _Tp>
991 _GLIBCXX20_CONSTEXPR
992 inline void
993 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
994 {
995 // concept requirements
996 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
997 _ForwardIterator>)
998 __glibcxx_requires_valid_range(__first, __last);
999
1000 std::__fill_a(__first, __last, __value);
1001 }
1002
1003 // Used by fill_n, generate_n, etc. to convert _Size to an integral type:
1004 inline _GLIBCXX_CONSTEXPR int
1005 __size_to_integer(int __n) { return __n; }
1006 inline _GLIBCXX_CONSTEXPR unsigned
1007 __size_to_integer(unsigned __n) { return __n; }
1008 inline _GLIBCXX_CONSTEXPR long
1009 __size_to_integer(long __n) { return __n; }
1010 inline _GLIBCXX_CONSTEXPR unsigned long
1011 __size_to_integer(unsigned long __n) { return __n; }
1012 inline _GLIBCXX_CONSTEXPR long long
1013 __size_to_integer(long long __n) { return __n; }
1014 inline _GLIBCXX_CONSTEXPR unsigned long long
1015 __size_to_integer(unsigned long long __n) { return __n; }
1016
1017 #if defined(__GLIBCXX_TYPE_INT_N_0)
1018 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1019 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
1020 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0
1021 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
1022 #endif
1023 #if defined(__GLIBCXX_TYPE_INT_N_1)
1024 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1025 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
1026 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1
1027 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
1028 #endif
1029 #if defined(__GLIBCXX_TYPE_INT_N_2)
1030 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1031 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
1032 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2
1033 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
1034 #endif
1035 #if defined(__GLIBCXX_TYPE_INT_N_3)
1036 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3
1037 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
1038 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1039 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
1040 #endif
1041
1042 inline _GLIBCXX_CONSTEXPR long long
1043 __size_to_integer(float __n) { return (long long)__n; }
1044 inline _GLIBCXX_CONSTEXPR long long
1045 __size_to_integer(double __n) { return (long long)__n; }
1046 inline _GLIBCXX_CONSTEXPR long long
1047 __size_to_integer(long double __n) { return (long long)__n; }
1048 #if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
1049 __extension__ inline _GLIBCXX_CONSTEXPR long long
1050 __size_to_integer(__float128 __n) { return (long long)__n; }
1051 #endif
1052
1053 template<typename _OutputIterator, typename _Size, typename _Tp>
1054 _GLIBCXX20_CONSTEXPR
1055 inline typename
1056 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
1057 __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value)
1058 {
1059 for (; __n > 0; --__n, (void) ++__first)
1060 *__first = __value;
1061 return __first;
1062 }
1063
1064 template<typename _OutputIterator, typename _Size, typename _Tp>
1065 _GLIBCXX20_CONSTEXPR
1066 inline typename
1067 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1068 __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value)
1069 {
1070 const _Tp __tmp = __value;
1071 for (; __n > 0; --__n, (void) ++__first)
1072 *__first = __tmp;
1073 return __first;
1074 }
1075
1076 template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
1077 typename _Tp>
1078 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1079 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1080 _Size __n, const _Tp& __value,
1081 std::input_iterator_tag);
1082
1083 template<typename _OutputIterator, typename _Size, typename _Tp>
1084 _GLIBCXX20_CONSTEXPR
1085 inline _OutputIterator
1086 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1087 std::output_iterator_tag)
1088 {
1089 #if __cplusplus >= 201103L
1090 static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1091 #endif
1092 return __fill_n_a1(__first, __n, __value);
1093 }
1094
1095 template<typename _OutputIterator, typename _Size, typename _Tp>
1096 _GLIBCXX20_CONSTEXPR
1097 inline _OutputIterator
1098 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1099 std::input_iterator_tag)
1100 {
1101 #if __cplusplus >= 201103L
1102 static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1103 #endif
1104 return __fill_n_a1(__first, __n, __value);
1105 }
1106
1107 template<typename _OutputIterator, typename _Size, typename _Tp>
1108 _GLIBCXX20_CONSTEXPR
1109 inline _OutputIterator
1110 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1111 std::random_access_iterator_tag)
1112 {
1113 #if __cplusplus >= 201103L
1114 static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1115 #endif
1116 if (__n <= 0)
1117 return __first;
1118
1119 __glibcxx_requires_can_increment(__first, __n);
1120
1121 std::__fill_a(__first, __first + __n, __value);
1122 return __first + __n;
1123 }
1124
1125 /**
1126 * @brief Fills the range [first,first+n) with copies of value.
1127 * @ingroup mutating_algorithms
1128 * @param __first An output iterator.
1129 * @param __n The count of copies to perform.
1130 * @param __value A reference-to-const of arbitrary type.
1131 * @return The iterator at first+n.
1132 *
1133 * This function fills a range with copies of the same value. For char
1134 * types filling contiguous areas of memory, this becomes an inline call
1135 * to @c memset or @c wmemset.
1136 *
1137 * If @p __n is negative, the function does nothing.
1138 */
1139 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1140 // DR 865. More algorithms that throw away information
1141 // DR 426. search_n(), fill_n(), and generate_n() with negative n
1142 template<typename _OI, typename _Size, typename _Tp>
1143 _GLIBCXX20_CONSTEXPR
1144 inline _OI
1145 fill_n(_OI __first, _Size __n, const _Tp& __value)
1146 {
1147 // concept requirements
1148 __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1149
1150 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1151 std::__iterator_category(__first));
1152 }
1153
1154 template<bool _BoolType>
1155 struct __equal
1156 {
1157 template<typename _II1, typename _II2>
1158 _GLIBCXX20_CONSTEXPR
1159 static bool
1160 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1161 {
1162 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1163 if (!(*__first1 == *__first2))
1164 return false;
1165 return true;
1166 }
1167 };
1168
1169 template<>
1170 struct __equal<true>
1171 {
1172 template<typename _Tp>
1173 _GLIBCXX20_CONSTEXPR
1174 static bool
1175 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
1176 {
1177 if (const size_t __len = (__last1 - __first1))
1178 return !std::__memcmp(__first1, __first2, __len);
1179 return true;
1180 }
1181 };
1182
1183 template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1184 typename __gnu_cxx::__enable_if<
1185 __is_random_access_iter<_II>::__value, bool>::__type
1186 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1187 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1188 _II);
1189
1190 template<typename _Tp1, typename _Ref1, typename _Ptr1,
1191 typename _Tp2, typename _Ref2, typename _Ptr2>
1192 bool
1193 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1194 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1195 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1196
1197 template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
1198 typename __gnu_cxx::__enable_if<
1199 __is_random_access_iter<_II>::__value, bool>::__type
1200 __equal_aux1(_II, _II,
1201 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1202
1203 template<typename _II1, typename _II2>
1204 _GLIBCXX20_CONSTEXPR
1205 inline bool
1206 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1207 {
1208 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1209 const bool __simple = ((__is_integer<_ValueType1>::__value
1210 || __is_pointer<_ValueType1>::__value)
1211 && __memcmpable<_II1, _II2>::__value);
1212 return std::__equal<__simple>::equal(__first1, __last1, __first2);
1213 }
1214
1215 template<typename _II1, typename _II2>
1216 _GLIBCXX20_CONSTEXPR
1217 inline bool
1218 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1219 {
1220 return std::__equal_aux1(std::__niter_base(__first1),
1221 std::__niter_base(__last1),
1222 std::__niter_base(__first2));
1223 }
1224
1225 template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
1226 bool
1227 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1228 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1229 _II2);
1230
1231 template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
1232 bool
1233 __equal_aux(_II1, _II1,
1234 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1235
1236 template<typename _II1, typename _Seq1, typename _Cat1,
1237 typename _II2, typename _Seq2, typename _Cat2>
1238 bool
1239 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1240 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1241 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1242
1243 template<typename, typename>
1244 struct __lc_rai
1245 {
1246 template<typename _II1, typename _II2>
1247 _GLIBCXX20_CONSTEXPR
1248 static _II1
1249 __newlast1(_II1, _II1 __last1, _II2, _II2)
1250 { return __last1; }
1251
1252 template<typename _II>
1253 _GLIBCXX20_CONSTEXPR
1254 static bool
1255 __cnd2(_II __first, _II __last)
1256 { return __first != __last; }
1257 };
1258
1259 template<>
1260 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1261 {
1262 template<typename _RAI1, typename _RAI2>
1263 _GLIBCXX20_CONSTEXPR
1264 static _RAI1
1265 __newlast1(_RAI1 __first1, _RAI1 __last1,
1266 _RAI2 __first2, _RAI2 __last2)
1267 {
1268 const typename iterator_traits<_RAI1>::difference_type
1269 __diff1 = __last1 - __first1;
1270 const typename iterator_traits<_RAI2>::difference_type
1271 __diff2 = __last2 - __first2;
1272 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1273 }
1274
1275 template<typename _RAI>
1276 static _GLIBCXX20_CONSTEXPR bool
1277 __cnd2(_RAI, _RAI)
1278 { return true; }
1279 };
1280
1281 template<typename _II1, typename _II2, typename _Compare>
1282 _GLIBCXX20_CONSTEXPR
1283 bool
1284 __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1285 _II2 __first2, _II2 __last2,
1286 _Compare __comp)
1287 {
1288 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1289 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1290 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1291
1292 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1293 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1294 ++__first1, (void)++__first2)
1295 {
1296 if (__comp(__first1, __first2))
1297 return true;
1298 if (__comp(__first2, __first1))
1299 return false;
1300 }
1301 return __first1 == __last1 && __first2 != __last2;
1302 }
1303
1304 template<bool _BoolType>
1305 struct __lexicographical_compare
1306 {
1307 template<typename _II1, typename _II2>
1308 _GLIBCXX20_CONSTEXPR
1309 static bool
1310 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1311 {
1312 using __gnu_cxx::__ops::__iter_less_iter;
1313 return std::__lexicographical_compare_impl(__first1, __last1,
1314 __first2, __last2,
1315 __iter_less_iter());
1316 }
1317
1318 template<typename _II1, typename _II2>
1319 _GLIBCXX20_CONSTEXPR
1320 static int
1321 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1322 {
1323 while (__first1 != __last1)
1324 {
1325 if (__first2 == __last2)
1326 return +1;
1327 if (*__first1 < *__first2)
1328 return -1;
1329 if (*__first2 < *__first1)
1330 return +1;
1331 ++__first1;
1332 ++__first2;
1333 }
1334 return int(__first2 == __last2) - 1;
1335 }
1336 };
1337
1338 template<>
1339 struct __lexicographical_compare<true>
1340 {
1341 template<typename _Tp, typename _Up>
1342 _GLIBCXX20_CONSTEXPR
1343 static bool
1344 __lc(const _Tp* __first1, const _Tp* __last1,
1345 const _Up* __first2, const _Up* __last2)
1346 { return __3way(__first1, __last1, __first2, __last2) < 0; }
1347
1348 template<typename _Tp, typename _Up>
1349 _GLIBCXX20_CONSTEXPR
1350 static ptrdiff_t
1351 __3way(const _Tp* __first1, const _Tp* __last1,
1352 const _Up* __first2, const _Up* __last2)
1353 {
1354 const size_t __len1 = __last1 - __first1;
1355 const size_t __len2 = __last2 - __first2;
1356 if (const size_t __len = std::min(__len1, __len2))
1357 if (int __result = std::__memcmp(__first1, __first2, __len))
1358 return __result;
1359 return ptrdiff_t(__len1 - __len2);
1360 }
1361 };
1362
1363 template<typename _II1, typename _II2>
1364 _GLIBCXX20_CONSTEXPR
1365 inline bool
1366 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1367 _II2 __first2, _II2 __last2)
1368 {
1369 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1370 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1371 const bool __simple =
1372 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1373 && __is_pointer<_II1>::__value
1374 && __is_pointer<_II2>::__value
1375 #if __cplusplus > 201703L && __cpp_lib_concepts
1376 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
1377 // so __is_byte<T> could be true, but we can't use memcmp with
1378 // volatile data.
1379 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1380 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1381 #endif
1382 );
1383
1384 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1385 __first2, __last2);
1386 }
1387
1388 template<typename _Tp1, typename _Ref1, typename _Ptr1,
1389 typename _Tp2>
1390 bool
1391 __lexicographical_compare_aux1(
1392 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1393 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1394 _Tp2*, _Tp2*);
1395
1396 template<typename _Tp1,
1397 typename _Tp2, typename _Ref2, typename _Ptr2>
1398 bool
1399 __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1400 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1401 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1402
1403 template<typename _Tp1, typename _Ref1, typename _Ptr1,
1404 typename _Tp2, typename _Ref2, typename _Ptr2>
1405 bool
1406 __lexicographical_compare_aux1(
1407 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1408 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1409 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1410 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1411
1412 template<typename _II1, typename _II2>
1413 _GLIBCXX20_CONSTEXPR
1414 inline bool
1415 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1416 _II2 __first2, _II2 __last2)
1417 {
1418 return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1419 std::__niter_base(__last1),
1420 std::__niter_base(__first2),
1421 std::__niter_base(__last2));
1422 }
1423
1424 template<typename _Iter1, typename _Seq1, typename _Cat1,
1425 typename _II2>
1426 bool
1427 __lexicographical_compare_aux(
1428 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1429 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1430 _II2, _II2);
1431
1432 template<typename _II1,
1433 typename _Iter2, typename _Seq2, typename _Cat2>
1434 bool
1435 __lexicographical_compare_aux(
1436 _II1, _II1,
1437 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1438 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1439
1440 template<typename _Iter1, typename _Seq1, typename _Cat1,
1441 typename _Iter2, typename _Seq2, typename _Cat2>
1442 bool
1443 __lexicographical_compare_aux(
1444 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1445 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1446 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1447 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1448
1449 template<typename _ForwardIterator, typename _Tp, typename _Compare>
1450 _GLIBCXX20_CONSTEXPR
1451 _ForwardIterator
1452 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1453 const _Tp& __val, _Compare __comp)
1454 {
1455 typedef typename iterator_traits<_ForwardIterator>::difference_type
1456 _DistanceType;
1457
1458 _DistanceType __len = std::distance(__first, __last);
1459
1460 while (__len > 0)
1461 {
1462 _DistanceType __half = __len >> 1;
1463 _ForwardIterator __middle = __first;
1464 std::advance(__middle, __half);
1465 if (__comp(__middle, __val))
1466 {
1467 __first = __middle;
1468 ++__first;
1469 __len = __len - __half - 1;
1470 }
1471 else
1472 __len = __half;
1473 }
1474 return __first;
1475 }
1476
1477 /**
1478 * @brief Finds the first position in which @a val could be inserted
1479 * without changing the ordering.
1480 * @param __first An iterator.
1481 * @param __last Another iterator.
1482 * @param __val The search term.
1483 * @return An iterator pointing to the first element <em>not less
1484 * than</em> @a val, or end() if every element is less than
1485 * @a val.
1486 * @ingroup binary_search_algorithms
1487 */
1488 template<typename _ForwardIterator, typename _Tp>
1489 _GLIBCXX20_CONSTEXPR
1490 inline _ForwardIterator
1491 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1492 const _Tp& __val)
1493 {
1494 // concept requirements
1495 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1496 __glibcxx_function_requires(_LessThanOpConcept<
1497 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1498 __glibcxx_requires_partitioned_lower(__first, __last, __val);
1499
1500 return std::__lower_bound(__first, __last, __val,
1501 __gnu_cxx::__ops::__iter_less_val());
1502 }
1503
1504 /// This is a helper function for the sort routines and for random.tcc.
1505 // Precondition: __n > 0.
1506 inline _GLIBCXX_CONSTEXPR int
1507 __lg(int __n)
1508 { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
1509
1510 inline _GLIBCXX_CONSTEXPR unsigned
1511 __lg(unsigned __n)
1512 { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
1513
1514 inline _GLIBCXX_CONSTEXPR long
1515 __lg(long __n)
1516 { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
1517
1518 inline _GLIBCXX_CONSTEXPR unsigned long
1519 __lg(unsigned long __n)
1520 { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
1521
1522 inline _GLIBCXX_CONSTEXPR long long
1523 __lg(long long __n)
1524 { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1525
1526 inline _GLIBCXX_CONSTEXPR unsigned long long
1527 __lg(unsigned long long __n)
1528 { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1529
1530 _GLIBCXX_BEGIN_NAMESPACE_ALGO
1531
1532 /**
1533 * @brief Tests a range for element-wise equality.
1534 * @ingroup non_mutating_algorithms
1535 * @param __first1 An input iterator.
1536 * @param __last1 An input iterator.
1537 * @param __first2 An input iterator.
1538 * @return A boolean true or false.
1539 *
1540 * This compares the elements of two ranges using @c == and returns true or
1541 * false depending on whether all of the corresponding elements of the
1542 * ranges are equal.
1543 */
1544 template<typename _II1, typename _II2>
1545 _GLIBCXX20_CONSTEXPR
1546 inline bool
1547 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1548 {
1549 // concept requirements
1550 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1551 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1552 __glibcxx_function_requires(_EqualOpConcept<
1553 typename iterator_traits<_II1>::value_type,
1554 typename iterator_traits<_II2>::value_type>)
1555 __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1556
1557 return std::__equal_aux(__first1, __last1, __first2);
1558 }
1559
1560 /**
1561 * @brief Tests a range for element-wise equality.
1562 * @ingroup non_mutating_algorithms
1563 * @param __first1 An input iterator.
1564 * @param __last1 An input iterator.
1565 * @param __first2 An input iterator.
1566 * @param __binary_pred A binary predicate @link functors
1567 * functor@endlink.
1568 * @return A boolean true or false.
1569 *
1570 * This compares the elements of two ranges using the binary_pred
1571 * parameter, and returns true or
1572 * false depending on whether all of the corresponding elements of the
1573 * ranges are equal.
1574 */
1575 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1576 _GLIBCXX20_CONSTEXPR
1577 inline bool
1578 equal(_IIter1 __first1, _IIter1 __last1,
1579 _IIter2 __first2, _BinaryPredicate __binary_pred)
1580 {
1581 // concept requirements
1582 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1583 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1584 __glibcxx_requires_valid_range(__first1, __last1);
1585
1586 for (; __first1 != __last1; ++__first1, (void)++__first2)
1587 if (!bool(__binary_pred(*__first1, *__first2)))
1588 return false;
1589 return true;
1590 }
1591
1592 #if __cplusplus >= 201103L
1593 // 4-iterator version of std::equal<It1, It2> for use in C++11.
1594 template<typename _II1, typename _II2>
1595 _GLIBCXX20_CONSTEXPR
1596 inline bool
1597 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1598 {
1599 using _RATag = random_access_iterator_tag;
1600 using _Cat1 = typename iterator_traits<_II1>::iterator_category;
1601 using _Cat2 = typename iterator_traits<_II2>::iterator_category;
1602 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1603 if (_RAIters())
1604 {
1605 auto __d1 = std::distance(__first1, __last1);
1606 auto __d2 = std::distance(__first2, __last2);
1607 if (__d1 != __d2)
1608 return false;
1609 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1610 }
1611
1612 for (; __first1 != __last1 && __first2 != __last2;
1613 ++__first1, (void)++__first2)
1614 if (!(*__first1 == *__first2))
1615 return false;
1616 return __first1 == __last1 && __first2 == __last2;
1617 }
1618
1619 // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11.
1620 template<typename _II1, typename _II2, typename _BinaryPredicate>
1621 _GLIBCXX20_CONSTEXPR
1622 inline bool
1623 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1624 _BinaryPredicate __binary_pred)
1625 {
1626 using _RATag = random_access_iterator_tag;
1627 using _Cat1 = typename iterator_traits<_II1>::iterator_category;
1628 using _Cat2 = typename iterator_traits<_II2>::iterator_category;
1629 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1630 if (_RAIters())
1631 {
1632 auto __d1 = std::distance(__first1, __last1);
1633 auto __d2 = std::distance(__first2, __last2);
1634 if (__d1 != __d2)
1635 return false;
1636 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1637 __binary_pred);
1638 }
1639
1640 for (; __first1 != __last1 && __first2 != __last2;
1641 ++__first1, (void)++__first2)
1642 if (!bool(__binary_pred(*__first1, *__first2)))
1643 return false;
1644 return __first1 == __last1 && __first2 == __last2;
1645 }
1646 #endif // C++11
1647
1648 #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<
1674 typename iterator_traits<_II1>::value_type,
1675 typename iterator_traits<_II2>::value_type>)
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 // Both iterators refer to contiguous ranges of unsigned narrow characters,
1784 // or std::byte, or big-endian unsigned integers, suitable for comparison
1785 // using memcmp.
1786 template<typename _Iter1, typename _Iter2>
1787 concept __memcmp_ordered_with
1788 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1789 iter_value_t<_Iter2>>::__value)
1790 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
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 (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1841 {
1842 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1843 __min_cmp(__last1 - __first1, __last2 - __first2);
1844 if (__len)
1845 {
1846 const auto __blen = __len * sizeof(*__first1);
1847 const auto __c
1848 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 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
2234