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