1 // Core algorithmic facilities -*- C++ -*-
3 // Copyright (C) 2001-2020 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
56 #ifndef _STL_ALGOBASE_H
57 #define _STL_ALGOBASE_H 1
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>
75 #if __cplusplus > 201703L
79 namespace std
_GLIBCXX_VISIBILITY(default)
81 _GLIBCXX_BEGIN_NAMESPACE_VERSION
84 * A constexpr wrapper for __builtin_memcmp.
85 * @param __num The number of elements of type _Tp (not bytes).
87 template<typename _Tp
, typename _Up
>
90 __memcmp(const _Tp
* __first1
, const _Up
* __first2
, size_t __num
)
92 #if __cplusplus >= 201103L
93 static_assert(sizeof(_Tp
) == sizeof(_Up
), "can be compared with memcmp");
95 #ifdef __cpp_lib_is_constant_evaluated
96 if (std::is_constant_evaluated())
98 for(; __num
> 0; ++__first1
, ++__first2
, --__num
)
99 if (*__first1
!= *__first2
)
100 return *__first1
< *__first2
? -1 : 1;
105 return __builtin_memcmp(__first1
, __first2
, sizeof(_Tp
) * __num
);
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
>
115 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
117 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
119 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
121 _ValueType1 __tmp
= *__a
;
128 struct __iter_swap
<true>
130 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
132 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
140 * @brief Swaps the contents of two iterators.
141 * @ingroup mutating_algorithms
142 * @param __a An iterator.
143 * @param __b Another iterator.
146 * This function swaps the values pointed to by two iterators, not the
147 * iterators themselves.
149 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
152 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
154 // concept requirements
155 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
157 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
160 #if __cplusplus < 201103L
161 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
163 typedef typename iterator_traits
<_ForwardIterator2
>::value_type
166 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType1
,
168 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType2
,
171 typedef typename iterator_traits
<_ForwardIterator1
>::reference
173 typedef typename iterator_traits
<_ForwardIterator2
>::reference
175 std::__iter_swap
<__are_same
<_ValueType1
, _ValueType2
>::__value
176 && __are_same
<_ValueType1
&, _ReferenceType1
>::__value
177 && __are_same
<_ValueType2
&, _ReferenceType2
>::__value
>::
180 // _GLIBCXX_RESOLVE_LIB_DEFECTS
181 // 187. iter_swap underspecified
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).
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.
198 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
201 swap_ranges(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
202 _ForwardIterator2 __first2
)
204 // concept requirements
205 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
207 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
209 __glibcxx_requires_valid_range(__first1
, __last1
);
211 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
)
212 std::iter_swap(__first1
, __first2
);
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.
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.
227 template<typename _Tp
>
230 min(const _Tp
& __a
, const _Tp
& __b
)
232 // concept requirements
233 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
234 //return __b < __a ? __b : __a;
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.
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.
251 template<typename _Tp
>
254 max(const _Tp
& __a
, const _Tp
& __b
)
256 // concept requirements
257 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
258 //return __a < __b ? __b : __a;
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.
272 * This will work on temporary expressions, since they are only evaluated
273 * once, unlike a preprocessor macro.
275 template<typename _Tp
, typename _Compare
>
278 min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
280 //return __comp(__b, __a) ? __b : __a;
281 if (__comp(__b
, __a
))
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.
294 * This will work on temporary expressions, since they are only evaluated
295 * once, unlike a preprocessor macro.
297 template<typename _Tp
, typename _Compare
>
300 max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
302 //return __comp(__a, __b) ? __b : __a;
303 if (__comp(__a
, __b
))
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
>
313 __niter_base(_Iterator __it
)
314 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible
<_Iterator
>::value
)
317 // Reverse the __niter_base transformation to get a
318 // __normal_iterator back again (this assumes that __normal_iterator
319 // is only used to wrap random access iterators, like pointers).
320 template<typename _From
, typename _To
>
323 __niter_wrap(_From __from
, _To __res
)
324 { return __from
+ (__res
- std::__niter_base(__from
)); }
326 // No need to wrap, iterator already has the right type.
327 template<typename _Iterator
>
330 __niter_wrap(const _Iterator
&, _Iterator __res
)
333 // All of these auxiliary structs serve two purposes. (1) Replace
334 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
335 // because the input and output ranges are permitted to overlap.)
336 // (2) If we're using random access iterators, then write the loop as
337 // a for loop with an explicit count.
339 template<bool _IsMove
, bool _IsSimple
, typename _Category
>
342 template<typename _II
, typename _OI
>
345 __copy_m(_II __first
, _II __last
, _OI __result
)
347 for (; __first
!= __last
; ++__result
, (void)++__first
)
348 *__result
= *__first
;
353 #if __cplusplus >= 201103L
354 template<typename _Category
>
355 struct __copy_move
<true, false, _Category
>
357 template<typename _II
, typename _OI
>
360 __copy_m(_II __first
, _II __last
, _OI __result
)
362 for (; __first
!= __last
; ++__result
, (void)++__first
)
363 *__result
= std::move(*__first
);
370 struct __copy_move
<false, false, random_access_iterator_tag
>
372 template<typename _II
, typename _OI
>
375 __copy_m(_II __first
, _II __last
, _OI __result
)
377 typedef typename iterator_traits
<_II
>::difference_type _Distance
;
378 for(_Distance __n
= __last
- __first
; __n
> 0; --__n
)
380 *__result
= *__first
;
388 #if __cplusplus >= 201103L
390 struct __copy_move
<true, false, random_access_iterator_tag
>
392 template<typename _II
, typename _OI
>
395 __copy_m(_II __first
, _II __last
, _OI __result
)
397 typedef typename iterator_traits
<_II
>::difference_type _Distance
;
398 for(_Distance __n
= __last
- __first
; __n
> 0; --__n
)
400 *__result
= std::move(*__first
);
409 template<bool _IsMove
>
410 struct __copy_move
<_IsMove
, true, random_access_iterator_tag
>
412 template<typename _Tp
>
415 __copy_m(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
417 #if __cplusplus >= 201103L
418 using __assignable
= conditional
<_IsMove
,
419 is_move_assignable
<_Tp
>,
420 is_copy_assignable
<_Tp
>>;
421 // trivial types can have deleted assignment
422 static_assert( __assignable::type::value
, "type is not assignable" );
424 const ptrdiff_t _Num
= __last
- __first
;
426 __builtin_memmove(__result
, __first
, sizeof(_Tp
) * _Num
);
427 return __result
+ _Num
;
431 // Helpers for streambuf iterators (either istream or ostream).
432 // NB: avoid including <iosfwd>, relatively large.
433 template<typename _CharT
>
436 template<typename _CharT
, typename _Traits
>
437 class istreambuf_iterator
;
439 template<typename _CharT
, typename _Traits
>
440 class ostreambuf_iterator
;
442 template<bool _IsMove
, typename _CharT
>
443 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
444 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
445 __copy_move_a2(_CharT
*, _CharT
*,
446 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
448 template<bool _IsMove
, typename _CharT
>
449 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
450 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
451 __copy_move_a2(const _CharT
*, const _CharT
*,
452 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
454 template<bool _IsMove
, typename _CharT
>
455 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
457 __copy_move_a2(istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >,
458 istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >, _CharT
*);
460 template<bool _IsMove
, typename _II
, typename _OI
>
463 __copy_move_a2(_II __first
, _II __last
, _OI __result
)
465 typedef typename iterator_traits
<_II
>::iterator_category _Category
;
466 #ifdef __cpp_lib_is_constant_evaluated
467 if (std::is_constant_evaluated())
468 return std::__copy_move
<_IsMove
, false, _Category
>::
469 __copy_m(__first
, __last
, __result
);
471 return std::__copy_move
<_IsMove
, __memcpyable
<_OI
, _II
>::__value
,
472 _Category
>::__copy_m(__first
, __last
, __result
);
475 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
477 template<typename _Tp
, typename _Ref
, typename _Ptr
>
478 struct _Deque_iterator
;
480 _GLIBCXX_END_NAMESPACE_CONTAINER
482 template<bool _IsMove
,
483 typename _Tp
, typename _Ref
, typename _Ptr
, typename _OI
>
485 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Ref
, _Ptr
>,
486 _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Ref
, _Ptr
>,
489 template<bool _IsMove
,
490 typename _ITp
, typename _IRef
, typename _IPtr
, typename _OTp
>
491 _GLIBCXX_STD_C::_Deque_iterator
<_OTp
, _OTp
&, _OTp
*>
492 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator
<_ITp
, _IRef
, _IPtr
>,
493 _GLIBCXX_STD_C::_Deque_iterator
<_ITp
, _IRef
, _IPtr
>,
494 _GLIBCXX_STD_C::_Deque_iterator
<_OTp
, _OTp
&, _OTp
*>);
496 template<bool _IsMove
, typename _II
, typename _Tp
>
497 typename
__gnu_cxx::__enable_if
<
498 __is_random_access_iter
<_II
>::__value
,
499 _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Tp
&, _Tp
*> >::__type
500 __copy_move_a1(_II
, _II
, _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Tp
&, _Tp
*>);
502 template<bool _IsMove
, typename _II
, typename _OI
>
505 __copy_move_a1(_II __first
, _II __last
, _OI __result
)
506 { return std::__copy_move_a2
<_IsMove
>(__first
, __last
, __result
); }
508 template<bool _IsMove
, typename _II
, typename _OI
>
511 __copy_move_a(_II __first
, _II __last
, _OI __result
)
513 return std::__niter_wrap(__result
,
514 std::__copy_move_a1
<_IsMove
>(std::__niter_base(__first
),
515 std::__niter_base(__last
),
516 std::__niter_base(__result
)));
519 template<bool _IsMove
,
520 typename _Ite
, typename _Seq
, typename _Cat
, typename _OI
>
522 __copy_move_a(const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&,
523 const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&,
526 template<bool _IsMove
,
527 typename _II
, typename _Ite
, typename _Seq
, typename _Cat
>
528 __gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>
529 __copy_move_a(_II
, _II
,
530 const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&);
532 template<bool _IsMove
,
533 typename _IIte
, typename _ISeq
, typename _ICat
,
534 typename _OIte
, typename _OSeq
, typename _OCat
>
535 ::__gnu_debug::_Safe_iterator
<_OIte
, _OSeq
, _OCat
>
536 __copy_move_a(const ::__gnu_debug::_Safe_iterator
<_IIte
, _ISeq
, _ICat
>&,
537 const ::__gnu_debug::_Safe_iterator
<_IIte
, _ISeq
, _ICat
>&,
538 const ::__gnu_debug::_Safe_iterator
<_OIte
, _OSeq
, _OCat
>&);
541 * @brief Copies the range [first,last) into result.
542 * @ingroup mutating_algorithms
543 * @param __first An input iterator.
544 * @param __last An input iterator.
545 * @param __result An output iterator.
546 * @return result + (first - last)
548 * This inline function will boil down to a call to @c memmove whenever
549 * possible. Failing that, if random access iterators are passed, then the
550 * loop count will be known (and therefore a candidate for compiler
551 * optimizations such as unrolling). Result may not be contained within
552 * [first,last); the copy_backward function should be used instead.
554 * Note that the end of the output range is permitted to be contained
555 * within [first,last).
557 template<typename _II
, typename _OI
>
560 copy(_II __first
, _II __last
, _OI __result
)
562 // concept requirements
563 __glibcxx_function_requires(_InputIteratorConcept
<_II
>)
564 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
,
565 typename iterator_traits
<_II
>::value_type
>)
566 __glibcxx_requires_can_increment_range(__first
, __last
, __result
);
568 return std::__copy_move_a
<__is_move_iterator
<_II
>::__value
>
569 (std::__miter_base(__first
), std::__miter_base(__last
), __result
);
572 #if __cplusplus >= 201103L
574 * @brief Moves the range [first,last) into result.
575 * @ingroup mutating_algorithms
576 * @param __first An input iterator.
577 * @param __last An input iterator.
578 * @param __result An output iterator.
579 * @return result + (first - last)
581 * This inline function will boil down to a call to @c memmove whenever
582 * possible. Failing that, if random access iterators are passed, then the
583 * loop count will be known (and therefore a candidate for compiler
584 * optimizations such as unrolling). Result may not be contained within
585 * [first,last); the move_backward function should be used instead.
587 * Note that the end of the output range is permitted to be contained
588 * within [first,last).
590 template<typename _II
, typename _OI
>
593 move(_II __first
, _II __last
, _OI __result
)
595 // concept requirements
596 __glibcxx_function_requires(_InputIteratorConcept
<_II
>)
597 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
,
598 typename iterator_traits
<_II
>::value_type
>)
599 __glibcxx_requires_can_increment_range(__first
, __last
, __result
);
601 return std::__copy_move_a
<true>(std::__miter_base(__first
),
602 std::__miter_base(__last
), __result
);
605 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
607 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
610 template<bool _IsMove
, bool _IsSimple
, typename _Category
>
611 struct __copy_move_backward
613 template<typename _BI1
, typename _BI2
>
616 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
618 while (__first
!= __last
)
619 *--__result
= *--__last
;
624 #if __cplusplus >= 201103L
625 template<typename _Category
>
626 struct __copy_move_backward
<true, false, _Category
>
628 template<typename _BI1
, typename _BI2
>
631 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
633 while (__first
!= __last
)
634 *--__result
= std::move(*--__last
);
641 struct __copy_move_backward
<false, false, random_access_iterator_tag
>
643 template<typename _BI1
, typename _BI2
>
646 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
648 typename iterator_traits
<_BI1
>::difference_type
649 __n
= __last
- __first
;
650 for (; __n
> 0; --__n
)
651 *--__result
= *--__last
;
656 #if __cplusplus >= 201103L
658 struct __copy_move_backward
<true, false, random_access_iterator_tag
>
660 template<typename _BI1
, typename _BI2
>
663 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
665 typename iterator_traits
<_BI1
>::difference_type
666 __n
= __last
- __first
;
667 for (; __n
> 0; --__n
)
668 *--__result
= std::move(*--__last
);
674 template<bool _IsMove
>
675 struct __copy_move_backward
<_IsMove
, true, random_access_iterator_tag
>
677 template<typename _Tp
>
680 __copy_move_b(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
682 #if __cplusplus >= 201103L
683 using __assignable
= conditional
<_IsMove
,
684 is_move_assignable
<_Tp
>,
685 is_copy_assignable
<_Tp
>>;
686 // trivial types can have deleted assignment
687 static_assert( __assignable::type::value
, "type is not assignable" );
689 const ptrdiff_t _Num
= __last
- __first
;
691 __builtin_memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
692 return __result
- _Num
;
696 template<bool _IsMove
, typename _BI1
, typename _BI2
>
699 __copy_move_backward_a2(_BI1 __first
, _BI1 __last
, _BI2 __result
)
701 typedef typename iterator_traits
<_BI1
>::iterator_category _Category
;
702 #ifdef __cpp_lib_is_constant_evaluated
703 if (std::is_constant_evaluated())
704 return std::__copy_move_backward
<_IsMove
, false, _Category
>::
705 __copy_move_b(__first
, __last
, __result
);
707 return std::__copy_move_backward
<_IsMove
,
708 __memcpyable
<_BI2
, _BI1
>::__value
,
709 _Category
>::__copy_move_b(__first
,
714 template<bool _IsMove
, typename _BI1
, typename _BI2
>
717 __copy_move_backward_a1(_BI1 __first
, _BI1 __last
, _BI2 __result
)
718 { return std::__copy_move_backward_a2
<_IsMove
>(__first
, __last
, __result
); }
720 template<bool _IsMove
,
721 typename _Tp
, typename _Ref
, typename _Ptr
, typename _OI
>
723 __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Ref
, _Ptr
>,
724 _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Ref
, _Ptr
>,
727 template<bool _IsMove
,
728 typename _ITp
, typename _IRef
, typename _IPtr
, typename _OTp
>
729 _GLIBCXX_STD_C::_Deque_iterator
<_OTp
, _OTp
&, _OTp
*>
730 __copy_move_backward_a1(
731 _GLIBCXX_STD_C::_Deque_iterator
<_ITp
, _IRef
, _IPtr
>,
732 _GLIBCXX_STD_C::_Deque_iterator
<_ITp
, _IRef
, _IPtr
>,
733 _GLIBCXX_STD_C::_Deque_iterator
<_OTp
, _OTp
&, _OTp
*>);
735 template<bool _IsMove
, typename _II
, typename _Tp
>
736 typename
__gnu_cxx::__enable_if
<
737 __is_random_access_iter
<_II
>::__value
,
738 _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Tp
&, _Tp
*> >::__type
739 __copy_move_backward_a1(_II
, _II
,
740 _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Tp
&, _Tp
*>);
742 template<bool _IsMove
, typename _II
, typename _OI
>
745 __copy_move_backward_a(_II __first
, _II __last
, _OI __result
)
747 return std::__niter_wrap(__result
,
748 std::__copy_move_backward_a1
<_IsMove
>
749 (std::__niter_base(__first
), std::__niter_base(__last
),
750 std::__niter_base(__result
)));
753 template<bool _IsMove
,
754 typename _Ite
, typename _Seq
, typename _Cat
, typename _OI
>
756 __copy_move_backward_a(
757 const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&,
758 const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&,
761 template<bool _IsMove
,
762 typename _II
, typename _Ite
, typename _Seq
, typename _Cat
>
763 __gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>
764 __copy_move_backward_a(_II
, _II
,
765 const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&);
767 template<bool _IsMove
,
768 typename _IIte
, typename _ISeq
, typename _ICat
,
769 typename _OIte
, typename _OSeq
, typename _OCat
>
770 ::__gnu_debug::_Safe_iterator
<_OIte
, _OSeq
, _OCat
>
771 __copy_move_backward_a(
772 const ::__gnu_debug::_Safe_iterator
<_IIte
, _ISeq
, _ICat
>&,
773 const ::__gnu_debug::_Safe_iterator
<_IIte
, _ISeq
, _ICat
>&,
774 const ::__gnu_debug::_Safe_iterator
<_OIte
, _OSeq
, _OCat
>&);
777 * @brief Copies the range [first,last) into result.
778 * @ingroup mutating_algorithms
779 * @param __first A bidirectional iterator.
780 * @param __last A bidirectional iterator.
781 * @param __result A bidirectional iterator.
782 * @return result - (first - last)
784 * The function has the same effect as copy, but starts at the end of the
785 * range and works its way to the start, returning the start of the result.
786 * This inline function will boil down to a call to @c memmove whenever
787 * possible. Failing that, if random access iterators are passed, then the
788 * loop count will be known (and therefore a candidate for compiler
789 * optimizations such as unrolling).
791 * Result may not be in the range (first,last]. Use copy instead. Note
792 * that the start of the output range may overlap [first,last).
794 template<typename _BI1
, typename _BI2
>
797 copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
799 // concept requirements
800 __glibcxx_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
801 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
802 __glibcxx_function_requires(_ConvertibleConcept
<
803 typename iterator_traits
<_BI1
>::value_type
,
804 typename iterator_traits
<_BI2
>::value_type
>)
805 __glibcxx_requires_can_decrement_range(__first
, __last
, __result
);
807 return std::__copy_move_backward_a
<__is_move_iterator
<_BI1
>::__value
>
808 (std::__miter_base(__first
), std::__miter_base(__last
), __result
);
811 #if __cplusplus >= 201103L
813 * @brief Moves the range [first,last) into result.
814 * @ingroup mutating_algorithms
815 * @param __first A bidirectional iterator.
816 * @param __last A bidirectional iterator.
817 * @param __result A bidirectional iterator.
818 * @return result - (first - last)
820 * The function has the same effect as move, but starts at the end of the
821 * range and works its way to the start, returning the start of the result.
822 * This inline function will boil down to a call to @c memmove whenever
823 * possible. Failing that, if random access iterators are passed, then the
824 * loop count will be known (and therefore a candidate for compiler
825 * optimizations such as unrolling).
827 * Result may not be in the range (first,last]. Use move instead. Note
828 * that the start of the output range may overlap [first,last).
830 template<typename _BI1
, typename _BI2
>
833 move_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
835 // concept requirements
836 __glibcxx_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
837 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
838 __glibcxx_function_requires(_ConvertibleConcept
<
839 typename iterator_traits
<_BI1
>::value_type
,
840 typename iterator_traits
<_BI2
>::value_type
>)
841 __glibcxx_requires_can_decrement_range(__first
, __last
, __result
);
843 return std::__copy_move_backward_a
<true>(std::__miter_base(__first
),
844 std::__miter_base(__last
),
848 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
850 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
853 template<typename _ForwardIterator
, typename _Tp
>
856 __gnu_cxx::__enable_if
<!__is_scalar
<_Tp
>::__value
, void>::__type
857 __fill_a1(_ForwardIterator __first
, _ForwardIterator __last
,
860 for (; __first
!= __last
; ++__first
)
864 template<typename _ForwardIterator
, typename _Tp
>
867 __gnu_cxx::__enable_if
<__is_scalar
<_Tp
>::__value
, void>::__type
868 __fill_a1(_ForwardIterator __first
, _ForwardIterator __last
,
871 const _Tp __tmp
= __value
;
872 for (; __first
!= __last
; ++__first
)
876 // Specialization: for char types we can use memset.
877 template<typename _Tp
>
879 __gnu_cxx::__enable_if
<__is_byte
<_Tp
>::__value
, void>::__type
880 __fill_a1(_Tp
* __first
, _Tp
* __last
, const _Tp
& __c
)
882 const _Tp __tmp
= __c
;
883 if (const size_t __len
= __last
- __first
)
884 __builtin_memset(__first
, static_cast<unsigned char>(__tmp
), __len
);
887 template<typename _Ite
, typename _Cont
, typename _Tp
>
890 __fill_a1(::__gnu_cxx::__normal_iterator
<_Ite
, _Cont
> __first
,
891 ::__gnu_cxx::__normal_iterator
<_Ite
, _Cont
> __last
,
893 { std::__fill_a1(__first
.base(), __last
.base(), __value
); }
895 template<typename _Tp
, typename _VTp
>
897 __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Tp
&, _Tp
*>&,
898 const _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Tp
&, _Tp
*>&,
901 template<typename _FIte
, typename _Tp
>
904 __fill_a(_FIte __first
, _FIte __last
, const _Tp
& __value
)
905 { std::__fill_a1(__first
, __last
, __value
); }
907 template<typename _Ite
, typename _Seq
, typename _Cat
, typename _Tp
>
909 __fill_a(const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&,
910 const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>&,
914 * @brief Fills the range [first,last) with copies of value.
915 * @ingroup mutating_algorithms
916 * @param __first A forward iterator.
917 * @param __last A forward iterator.
918 * @param __value A reference-to-const of arbitrary type.
921 * This function fills a range with copies of the same value. For char
922 * types filling contiguous areas of memory, this becomes an inline call
923 * to @c memset or @c wmemset.
925 template<typename _ForwardIterator
, typename _Tp
>
928 fill(_ForwardIterator __first
, _ForwardIterator __last
, const _Tp
& __value
)
930 // concept requirements
931 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
933 __glibcxx_requires_valid_range(__first
, __last
);
935 std::__fill_a(__first
, __last
, __value
);
938 // Used by fill_n, generate_n, etc. to convert _Size to an integral type:
939 inline _GLIBCXX_CONSTEXPR
int
940 __size_to_integer(int __n
) { return __n
; }
941 inline _GLIBCXX_CONSTEXPR
unsigned
942 __size_to_integer(unsigned __n
) { return __n
; }
943 inline _GLIBCXX_CONSTEXPR
long
944 __size_to_integer(long __n
) { return __n
; }
945 inline _GLIBCXX_CONSTEXPR
unsigned long
946 __size_to_integer(unsigned long __n
) { return __n
; }
947 inline _GLIBCXX_CONSTEXPR
long long
948 __size_to_integer(long long __n
) { return __n
; }
949 inline _GLIBCXX_CONSTEXPR
unsigned long long
950 __size_to_integer(unsigned long long __n
) { return __n
; }
952 #if defined(__GLIBCXX_TYPE_INT_N_0)
953 inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
954 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n
) { return __n
; }
955 inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_0
956 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n
) { return __n
; }
958 #if defined(__GLIBCXX_TYPE_INT_N_1)
959 inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
960 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n
) { return __n
; }
961 inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_1
962 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n
) { return __n
; }
964 #if defined(__GLIBCXX_TYPE_INT_N_2)
965 inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
966 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n
) { return __n
; }
967 inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_2
968 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n
) { return __n
; }
970 #if defined(__GLIBCXX_TYPE_INT_N_3)
971 inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_3
972 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n
) { return __n
; }
973 inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
974 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n
) { return __n
; }
977 inline _GLIBCXX_CONSTEXPR
long long
978 __size_to_integer(float __n
) { return __n
; }
979 inline _GLIBCXX_CONSTEXPR
long long
980 __size_to_integer(double __n
) { return __n
; }
981 inline _GLIBCXX_CONSTEXPR
long long
982 __size_to_integer(long double __n
) { return __n
; }
983 #if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
984 inline _GLIBCXX_CONSTEXPR
long long
985 __size_to_integer(__float128 __n
) { return __n
; }
988 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
991 __gnu_cxx::__enable_if
<!__is_scalar
<_Tp
>::__value
, _OutputIterator
>::__type
992 __fill_n_a1(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
994 for (; __n
> 0; --__n
, (void) ++__first
)
999 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
1000 _GLIBCXX20_CONSTEXPR
1002 __gnu_cxx::__enable_if
<__is_scalar
<_Tp
>::__value
, _OutputIterator
>::__type
1003 __fill_n_a1(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
1005 const _Tp __tmp
= __value
;
1006 for (; __n
> 0; --__n
, (void) ++__first
)
1011 template<typename _Ite
, typename _Seq
, typename _Cat
, typename _Size
,
1013 ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>
1014 __fill_n_a(const ::__gnu_debug::_Safe_iterator
<_Ite
, _Seq
, _Cat
>& __first
,
1015 _Size __n
, const _Tp
& __value
,
1016 std::input_iterator_tag
);
1018 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
1019 _GLIBCXX20_CONSTEXPR
1020 inline _OutputIterator
1021 __fill_n_a(_OutputIterator __first
, _Size __n
, const _Tp
& __value
,
1022 std::output_iterator_tag
)
1024 #if __cplusplus >= 201103L
1025 static_assert(is_integral
<_Size
>{}, "fill_n must pass integral size");
1027 return __fill_n_a1(__first
, __n
, __value
);
1030 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
1031 _GLIBCXX20_CONSTEXPR
1032 inline _OutputIterator
1033 __fill_n_a(_OutputIterator __first
, _Size __n
, const _Tp
& __value
,
1034 std::input_iterator_tag
)
1036 #if __cplusplus >= 201103L
1037 static_assert(is_integral
<_Size
>{}, "fill_n must pass integral size");
1039 return __fill_n_a1(__first
, __n
, __value
);
1042 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
1043 _GLIBCXX20_CONSTEXPR
1044 inline _OutputIterator
1045 __fill_n_a(_OutputIterator __first
, _Size __n
, const _Tp
& __value
,
1046 std::random_access_iterator_tag
)
1048 #if __cplusplus >= 201103L
1049 static_assert(is_integral
<_Size
>{}, "fill_n must pass integral size");
1054 __glibcxx_requires_can_increment(__first
, __n
);
1056 std::__fill_a(__first
, __first
+ __n
, __value
);
1057 return __first
+ __n
;
1061 * @brief Fills the range [first,first+n) with copies of value.
1062 * @ingroup mutating_algorithms
1063 * @param __first An output iterator.
1064 * @param __n The count of copies to perform.
1065 * @param __value A reference-to-const of arbitrary type.
1066 * @return The iterator at first+n.
1068 * This function fills a range with copies of the same value. For char
1069 * types filling contiguous areas of memory, this becomes an inline call
1070 * to @c memset or @c wmemset.
1072 * If @p __n is negative, the function does nothing.
1074 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1075 // DR 865. More algorithms that throw away information
1076 // DR 426. search_n(), fill_n(), and generate_n() with negative n
1077 template<typename _OI
, typename _Size
, typename _Tp
>
1078 _GLIBCXX20_CONSTEXPR
1080 fill_n(_OI __first
, _Size __n
, const _Tp
& __value
)
1082 // concept requirements
1083 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
, _Tp
>)
1085 return std::__fill_n_a(__first
, std::__size_to_integer(__n
), __value
,
1086 std::__iterator_category(__first
));
1089 template<bool _BoolType
>
1092 template<typename _II1
, typename _II2
>
1093 _GLIBCXX20_CONSTEXPR
1095 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
1097 for (; __first1
!= __last1
; ++__first1
, (void) ++__first2
)
1098 if (!(*__first1
== *__first2
))
1105 struct __equal
<true>
1107 template<typename _Tp
>
1108 _GLIBCXX20_CONSTEXPR
1110 equal(const _Tp
* __first1
, const _Tp
* __last1
, const _Tp
* __first2
)
1112 if (const size_t __len
= (__last1
- __first1
))
1113 return !std::__memcmp(__first1
, __first2
, __len
);
1118 template<typename _Tp
, typename _Ref
, typename _Ptr
, typename _II
>
1119 typename
__gnu_cxx::__enable_if
<
1120 __is_random_access_iter
<_II
>::__value
, bool>::__type
1121 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Ref
, _Ptr
>,
1122 _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Ref
, _Ptr
>,
1125 template<typename _Tp1
, typename _Ref1
, typename _Ptr1
,
1126 typename _Tp2
, typename _Ref2
, typename _Ptr2
>
1128 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator
<_Tp1
, _Ref1
, _Ptr1
>,
1129 _GLIBCXX_STD_C::_Deque_iterator
<_Tp1
, _Ref1
, _Ptr1
>,
1130 _GLIBCXX_STD_C::_Deque_iterator
<_Tp2
, _Ref2
, _Ptr2
>);
1132 template<typename _II
, typename _Tp
, typename _Ref
, typename _Ptr
>
1133 typename
__gnu_cxx::__enable_if
<
1134 __is_random_access_iter
<_II
>::__value
, bool>::__type
1135 __equal_aux1(_II
, _II
,
1136 _GLIBCXX_STD_C::_Deque_iterator
<_Tp
, _Ref
, _Ptr
>);
1138 template<typename _II1
, typename _II2
>
1139 _GLIBCXX20_CONSTEXPR
1141 __equal_aux1(_II1 __first1
, _II1 __last1
, _II2 __first2
)
1143 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
1144 const bool __simple
= ((__is_integer
<_ValueType1
>::__value
1145 || __is_pointer
<_ValueType1
>::__value
)
1146 && __memcmpable
<_II1
, _II2
>::__value
);
1147 return std::__equal
<__simple
>::equal(__first1
, __last1
, __first2
);
1150 template<typename _II1
, typename _II2
>
1151 _GLIBCXX20_CONSTEXPR
1153 __equal_aux(_II1 __first1
, _II1 __last1
, _II2 __first2
)
1155 return std::__equal_aux1(std::__niter_base(__first1
),
1156 std::__niter_base(__last1
),
1157 std::__niter_base(__first2
));
1160 template<typename _II1
, typename _Seq1
, typename _Cat1
, typename _II2
>
1162 __equal_aux(const ::__gnu_debug::_Safe_iterator
<_II1
, _Seq1
, _Cat1
>&,
1163 const ::__gnu_debug::_Safe_iterator
<_II1
, _Seq1
, _Cat1
>&,
1166 template<typename _II1
, typename _II2
, typename _Seq2
, typename _Cat2
>
1168 __equal_aux(_II1
, _II1
,
1169 const ::__gnu_debug::_Safe_iterator
<_II2
, _Seq2
, _Cat2
>&);
1171 template<typename _II1
, typename _Seq1
, typename _Cat1
,
1172 typename _II2
, typename _Seq2
, typename _Cat2
>
1174 __equal_aux(const ::__gnu_debug::_Safe_iterator
<_II1
, _Seq1
, _Cat1
>&,
1175 const ::__gnu_debug::_Safe_iterator
<_II1
, _Seq1
, _Cat1
>&,
1176 const ::__gnu_debug::_Safe_iterator
<_II2
, _Seq2
, _Cat2
>&);
1178 template<typename
, typename
>
1181 template<typename _II1
, typename _II2
>
1182 _GLIBCXX20_CONSTEXPR
1184 __newlast1(_II1
, _II1 __last1
, _II2
, _II2
)
1187 template<typename _II
>
1188 _GLIBCXX20_CONSTEXPR
1190 __cnd2(_II __first
, _II __last
)
1191 { return __first
!= __last
; }
1195 struct __lc_rai
<random_access_iterator_tag
, random_access_iterator_tag
>
1197 template<typename _RAI1
, typename _RAI2
>
1198 _GLIBCXX20_CONSTEXPR
1200 __newlast1(_RAI1 __first1
, _RAI1 __last1
,
1201 _RAI2 __first2
, _RAI2 __last2
)
1203 const typename iterator_traits
<_RAI1
>::difference_type
1204 __diff1
= __last1
- __first1
;
1205 const typename iterator_traits
<_RAI2
>::difference_type
1206 __diff2
= __last2
- __first2
;
1207 return __diff2
< __diff1
? __first1
+ __diff2
: __last1
;
1210 template<typename _RAI
>
1211 static _GLIBCXX20_CONSTEXPR
bool
1216 template<typename _II1
, typename _II2
, typename _Compare
>
1217 _GLIBCXX20_CONSTEXPR
1219 __lexicographical_compare_impl(_II1 __first1
, _II1 __last1
,
1220 _II2 __first2
, _II2 __last2
,
1223 typedef typename iterator_traits
<_II1
>::iterator_category _Category1
;
1224 typedef typename iterator_traits
<_II2
>::iterator_category _Category2
;
1225 typedef std::__lc_rai
<_Category1
, _Category2
> __rai_type
;
1227 __last1
= __rai_type::__newlast1(__first1
, __last1
, __first2
, __last2
);
1228 for (; __first1
!= __last1
&& __rai_type::__cnd2(__first2
, __last2
);
1229 ++__first1
, (void)++__first2
)
1231 if (__comp(__first1
, __first2
))
1233 if (__comp(__first2
, __first1
))
1236 return __first1
== __last1
&& __first2
!= __last2
;
1239 template<bool _BoolType
>
1240 struct __lexicographical_compare
1242 template<typename _II1
, typename _II2
>
1243 _GLIBCXX20_CONSTEXPR
1245 __lc(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
1247 using __gnu_cxx::__ops::__iter_less_iter
;
1248 return std::__lexicographical_compare_impl(__first1
, __last1
,
1250 __iter_less_iter());
1255 struct __lexicographical_compare
<true>
1257 template<typename _Tp
, typename _Up
>
1258 _GLIBCXX20_CONSTEXPR
1260 __lc(const _Tp
* __first1
, const _Tp
* __last1
,
1261 const _Up
* __first2
, const _Up
* __last2
)
1263 const size_t __len1
= __last1
- __first1
;
1264 const size_t __len2
= __last2
- __first2
;
1265 if (const size_t __len
= std::min(__len1
, __len2
))
1266 if (int __result
= std::__memcmp(__first1
, __first2
, __len
))
1267 return __result
< 0;
1268 return __len1
< __len2
;
1272 template<typename _II1
, typename _II2
>
1273 _GLIBCXX20_CONSTEXPR
1275 __lexicographical_compare_aux(_II1 __first1
, _II1 __last1
,
1276 _II2 __first2
, _II2 __last2
)
1278 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
1279 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
1280 const bool __simple
=
1281 (__is_byte
<_ValueType1
>::__value
&& __is_byte
<_ValueType2
>::__value
1282 && !__gnu_cxx::__numeric_traits
<_ValueType1
>::__is_signed
1283 && !__gnu_cxx::__numeric_traits
<_ValueType2
>::__is_signed
1284 && __is_pointer
<_II1
>::__value
1285 && __is_pointer
<_II2
>::__value
1286 #if __cplusplus > 201703L
1287 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
1288 // so __is_byte<T> could be true, but we can't use memcmp with
1290 && !is_volatile_v
<remove_reference_t
<iter_reference_t
<_II1
>>>
1291 && !is_volatile_v
<remove_reference_t
<iter_reference_t
<_II2
>>>
1295 return std::__lexicographical_compare
<__simple
>::__lc(__first1
, __last1
,
1299 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
1300 _GLIBCXX20_CONSTEXPR
1302 __lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
1303 const _Tp
& __val
, _Compare __comp
)
1305 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
1308 _DistanceType __len
= std::distance(__first
, __last
);
1312 _DistanceType __half
= __len
>> 1;
1313 _ForwardIterator __middle
= __first
;
1314 std::advance(__middle
, __half
);
1315 if (__comp(__middle
, __val
))
1319 __len
= __len
- __half
- 1;
1328 * @brief Finds the first position in which @a val could be inserted
1329 * without changing the ordering.
1330 * @param __first An iterator.
1331 * @param __last Another iterator.
1332 * @param __val The search term.
1333 * @return An iterator pointing to the first element <em>not less
1334 * than</em> @a val, or end() if every element is less than
1336 * @ingroup binary_search_algorithms
1338 template<typename _ForwardIterator
, typename _Tp
>
1339 _GLIBCXX20_CONSTEXPR
1340 inline _ForwardIterator
1341 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
1344 // concept requirements
1345 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1346 __glibcxx_function_requires(_LessThanOpConcept
<
1347 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
1348 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
1350 return std::__lower_bound(__first
, __last
, __val
,
1351 __gnu_cxx::__ops::__iter_less_val());
1354 /// This is a helper function for the sort routines and for random.tcc.
1355 // Precondition: __n > 0.
1356 inline _GLIBCXX_CONSTEXPR
int
1358 { return (int)sizeof(int) * __CHAR_BIT__
- 1 - __builtin_clz(__n
); }
1360 inline _GLIBCXX_CONSTEXPR
unsigned
1362 { return (int)sizeof(int) * __CHAR_BIT__
- 1 - __builtin_clz(__n
); }
1364 inline _GLIBCXX_CONSTEXPR
long
1366 { return (int)sizeof(long) * __CHAR_BIT__
- 1 - __builtin_clzl(__n
); }
1368 inline _GLIBCXX_CONSTEXPR
unsigned long
1369 __lg(unsigned long __n
)
1370 { return (int)sizeof(long) * __CHAR_BIT__
- 1 - __builtin_clzl(__n
); }
1372 inline _GLIBCXX_CONSTEXPR
long long
1374 { return (int)sizeof(long long) * __CHAR_BIT__
- 1 - __builtin_clzll(__n
); }
1376 inline _GLIBCXX_CONSTEXPR
unsigned long long
1377 __lg(unsigned long long __n
)
1378 { return (int)sizeof(long long) * __CHAR_BIT__
- 1 - __builtin_clzll(__n
); }
1380 _GLIBCXX_BEGIN_NAMESPACE_ALGO
1383 * @brief Tests a range for element-wise equality.
1384 * @ingroup non_mutating_algorithms
1385 * @param __first1 An input iterator.
1386 * @param __last1 An input iterator.
1387 * @param __first2 An input iterator.
1388 * @return A boolean true or false.
1390 * This compares the elements of two ranges using @c == and returns true or
1391 * false depending on whether all of the corresponding elements of the
1394 template<typename _II1
, typename _II2
>
1395 _GLIBCXX20_CONSTEXPR
1397 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
1399 // concept requirements
1400 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1401 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1402 __glibcxx_function_requires(_EqualOpConcept
<
1403 typename iterator_traits
<_II1
>::value_type
,
1404 typename iterator_traits
<_II2
>::value_type
>)
1405 __glibcxx_requires_can_increment_range(__first1
, __last1
, __first2
);
1407 return std::__equal_aux(__first1
, __last1
, __first2
);
1411 * @brief Tests a range for element-wise equality.
1412 * @ingroup non_mutating_algorithms
1413 * @param __first1 An input iterator.
1414 * @param __last1 An input iterator.
1415 * @param __first2 An input iterator.
1416 * @param __binary_pred A binary predicate @link functors
1418 * @return A boolean true or false.
1420 * This compares the elements of two ranges using the binary_pred
1421 * parameter, and returns true or
1422 * false depending on whether all of the corresponding elements of the
1425 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
1426 _GLIBCXX20_CONSTEXPR
1428 equal(_IIter1 __first1
, _IIter1 __last1
,
1429 _IIter2 __first2
, _BinaryPredicate __binary_pred
)
1431 // concept requirements
1432 __glibcxx_function_requires(_InputIteratorConcept
<_IIter1
>)
1433 __glibcxx_function_requires(_InputIteratorConcept
<_IIter2
>)
1434 __glibcxx_requires_valid_range(__first1
, __last1
);
1436 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
)
1437 if (!bool(__binary_pred(*__first1
, *__first2
)))
1442 #if __cplusplus >= 201103L
1443 // 4-iterator version of std::equal<It1, It2> for use in C++11.
1444 template<typename _II1
, typename _II2
>
1445 _GLIBCXX20_CONSTEXPR
1447 __equal4(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
1449 using _RATag
= random_access_iterator_tag
;
1450 using _Cat1
= typename iterator_traits
<_II1
>::iterator_category
;
1451 using _Cat2
= typename iterator_traits
<_II2
>::iterator_category
;
1452 using _RAIters
= __and_
<is_same
<_Cat1
, _RATag
>, is_same
<_Cat2
, _RATag
>>;
1455 auto __d1
= std::distance(__first1
, __last1
);
1456 auto __d2
= std::distance(__first2
, __last2
);
1459 return _GLIBCXX_STD_A::equal(__first1
, __last1
, __first2
);
1462 for (; __first1
!= __last1
&& __first2
!= __last2
;
1463 ++__first1
, (void)++__first2
)
1464 if (!(*__first1
== *__first2
))
1466 return __first1
== __last1
&& __first2
== __last2
;
1469 // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11.
1470 template<typename _II1
, typename _II2
, typename _BinaryPredicate
>
1471 _GLIBCXX20_CONSTEXPR
1473 __equal4(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
,
1474 _BinaryPredicate __binary_pred
)
1476 using _RATag
= random_access_iterator_tag
;
1477 using _Cat1
= typename iterator_traits
<_II1
>::iterator_category
;
1478 using _Cat2
= typename iterator_traits
<_II2
>::iterator_category
;
1479 using _RAIters
= __and_
<is_same
<_Cat1
, _RATag
>, is_same
<_Cat2
, _RATag
>>;
1482 auto __d1
= std::distance(__first1
, __last1
);
1483 auto __d2
= std::distance(__first2
, __last2
);
1486 return _GLIBCXX_STD_A::equal(__first1
, __last1
, __first2
,
1490 for (; __first1
!= __last1
&& __first2
!= __last2
;
1491 ++__first1
, (void)++__first2
)
1492 if (!bool(__binary_pred(*__first1
, *__first2
)))
1494 return __first1
== __last1
&& __first2
== __last2
;
1498 #if __cplusplus > 201103L
1500 #define __cpp_lib_robust_nonmodifying_seq_ops 201304
1503 * @brief Tests a range for element-wise equality.
1504 * @ingroup non_mutating_algorithms
1505 * @param __first1 An input iterator.
1506 * @param __last1 An input iterator.
1507 * @param __first2 An input iterator.
1508 * @param __last2 An input iterator.
1509 * @return A boolean true or false.
1511 * This compares the elements of two ranges using @c == and returns true or
1512 * false depending on whether all of the corresponding elements of the
1515 template<typename _II1
, typename _II2
>
1516 _GLIBCXX20_CONSTEXPR
1518 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
1520 // concept requirements
1521 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1522 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1523 __glibcxx_function_requires(_EqualOpConcept
<
1524 typename iterator_traits
<_II1
>::value_type
,
1525 typename iterator_traits
<_II2
>::value_type
>)
1526 __glibcxx_requires_valid_range(__first1
, __last1
);
1527 __glibcxx_requires_valid_range(__first2
, __last2
);
1529 return _GLIBCXX_STD_A::__equal4(__first1
, __last1
, __first2
, __last2
);
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 * @param __last2 An input iterator.
1539 * @param __binary_pred A binary predicate @link functors
1541 * @return A boolean true or false.
1543 * This compares the elements of two ranges using the binary_pred
1544 * parameter, and returns true or
1545 * false depending on whether all of the corresponding elements of the
1548 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
1549 _GLIBCXX20_CONSTEXPR
1551 equal(_IIter1 __first1
, _IIter1 __last1
,
1552 _IIter2 __first2
, _IIter2 __last2
, _BinaryPredicate __binary_pred
)
1554 // concept requirements
1555 __glibcxx_function_requires(_InputIteratorConcept
<_IIter1
>)
1556 __glibcxx_function_requires(_InputIteratorConcept
<_IIter2
>)
1557 __glibcxx_requires_valid_range(__first1
, __last1
);
1558 __glibcxx_requires_valid_range(__first2
, __last2
);
1560 return _GLIBCXX_STD_A::__equal4(__first1
, __last1
, __first2
, __last2
,
1566 * @brief Performs @b dictionary comparison on ranges.
1567 * @ingroup sorting_algorithms
1568 * @param __first1 An input iterator.
1569 * @param __last1 An input iterator.
1570 * @param __first2 An input iterator.
1571 * @param __last2 An input iterator.
1572 * @return A boolean true or false.
1574 * <em>Returns true if the sequence of elements defined by the range
1575 * [first1,last1) is lexicographically less than the sequence of elements
1576 * defined by the range [first2,last2). Returns false otherwise.</em>
1577 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1578 * then this is an inline call to @c memcmp.
1580 template<typename _II1
, typename _II2
>
1581 _GLIBCXX20_CONSTEXPR
1583 lexicographical_compare(_II1 __first1
, _II1 __last1
,
1584 _II2 __first2
, _II2 __last2
)
1586 #ifdef _GLIBCXX_CONCEPT_CHECKS
1587 // concept requirements
1588 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
1589 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
1591 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1592 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1593 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
1594 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
1595 __glibcxx_requires_valid_range(__first1
, __last1
);
1596 __glibcxx_requires_valid_range(__first2
, __last2
);
1598 return std::__lexicographical_compare_aux(std::__niter_base(__first1
),
1599 std::__niter_base(__last1
),
1600 std::__niter_base(__first2
),
1601 std::__niter_base(__last2
));
1605 * @brief Performs @b dictionary comparison on ranges.
1606 * @ingroup sorting_algorithms
1607 * @param __first1 An input iterator.
1608 * @param __last1 An input iterator.
1609 * @param __first2 An input iterator.
1610 * @param __last2 An input iterator.
1611 * @param __comp A @link comparison_functors comparison functor@endlink.
1612 * @return A boolean true or false.
1614 * The same as the four-parameter @c lexicographical_compare, but uses the
1615 * comp parameter instead of @c <.
1617 template<typename _II1
, typename _II2
, typename _Compare
>
1618 _GLIBCXX20_CONSTEXPR
1620 lexicographical_compare(_II1 __first1
, _II1 __last1
,
1621 _II2 __first2
, _II2 __last2
, _Compare __comp
)
1623 // concept requirements
1624 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1625 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1626 __glibcxx_requires_valid_range(__first1
, __last1
);
1627 __glibcxx_requires_valid_range(__first2
, __last2
);
1629 return std::__lexicographical_compare_impl
1630 (__first1
, __last1
, __first2
, __last2
,
1631 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
1634 #if __cpp_lib_three_way_comparison
1635 // Iter points to a contiguous range of unsigned narrow character type
1636 // or std::byte, suitable for comparison by memcmp.
1637 template<typename _Iter
>
1638 concept __is_byte_iter
= contiguous_iterator
<_Iter
>
1639 && __is_byte
<iter_value_t
<_Iter
>>::__value
!= 0
1640 && !__gnu_cxx::__numeric_traits
<iter_value_t
<_Iter
>>::__is_signed
;
1642 // Return a struct with two members, initialized to the smaller of x and y
1643 // (or x if they compare equal) and the result of the comparison x <=> y.
1644 template<typename _Tp
>
1646 __min_cmp(_Tp __x
, _Tp __y
)
1650 decltype(__x
<=> __y
) _M_cmp
;
1652 auto __c
= __x
<=> __y
;
1654 return _Res
{__y
, __c
};
1655 return _Res
{__x
, __c
};
1659 * @brief Performs dictionary comparison on ranges.
1660 * @ingroup sorting_algorithms
1661 * @param __first1 An input iterator.
1662 * @param __last1 An input iterator.
1663 * @param __first2 An input iterator.
1664 * @param __last2 An input iterator.
1665 * @param __comp A @link comparison_functors comparison functor@endlink.
1666 * @return The comparison category that `__comp(*__first1, *__first2)`
1669 template<typename _InputIter1
, typename _InputIter2
, typename _Comp
>
1671 lexicographical_compare_three_way(_InputIter1 __first1
,
1672 _InputIter1 __last1
,
1673 _InputIter2 __first2
,
1674 _InputIter2 __last2
,
1676 -> decltype(__comp(*__first1
, *__first2
))
1678 // concept requirements
1679 __glibcxx_function_requires(_InputIteratorConcept
<_InputIter1
>)
1680 __glibcxx_function_requires(_InputIteratorConcept
<_InputIter2
>)
1681 __glibcxx_requires_valid_range(__first1
, __last1
);
1682 __glibcxx_requires_valid_range(__first2
, __last2
);
1684 #if __cpp_lib_is_constant_evaluated
1685 using _Cat
= decltype(__comp(*__first1
, *__first2
));
1686 static_assert(same_as
<common_comparison_category_t
<_Cat
>, _Cat
>);
1688 if (!std::is_constant_evaluated())
1689 if constexpr (same_as
<_Comp
, __detail::_Synth3way
>
1690 || same_as
<_Comp
, compare_three_way
>)
1691 if constexpr (__is_byte_iter
<_InputIter1
>)
1692 if constexpr (__is_byte_iter
<_InputIter2
>)
1694 const auto [__len
, __lencmp
]
1695 = std::__min_cmp(__last1
- __first1
, __last2
- __first2
);
1699 = __builtin_memcmp(&*__first1
, &*__first2
, __len
) <=> 0;
1705 #endif // is_constant_evaluated
1706 while (__first1
!= __last1
)
1708 if (__first2
== __last2
)
1709 return strong_ordering::greater
;
1710 if (auto __cmp
= __comp(*__first1
, *__first2
); __cmp
!= 0)
1715 return (__first2
== __last2
) <=> true; // See PR 94006
1718 template<typename _InputIter1
, typename _InputIter2
>
1720 lexicographical_compare_three_way(_InputIter1 __first1
,
1721 _InputIter1 __last1
,
1722 _InputIter2 __first2
,
1723 _InputIter2 __last2
)
1725 return std::lexicographical_compare_three_way(__first1
, __last1
,
1727 compare_three_way
{});
1729 #endif // three_way_comparison
1731 template<typename _InputIterator1
, typename _InputIterator2
,
1732 typename _BinaryPredicate
>
1733 _GLIBCXX20_CONSTEXPR
1734 pair
<_InputIterator1
, _InputIterator2
>
1735 __mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1736 _InputIterator2 __first2
, _BinaryPredicate __binary_pred
)
1738 while (__first1
!= __last1
&& __binary_pred(__first1
, __first2
))
1743 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
1747 * @brief Finds the places in ranges which don't match.
1748 * @ingroup non_mutating_algorithms
1749 * @param __first1 An input iterator.
1750 * @param __last1 An input iterator.
1751 * @param __first2 An input iterator.
1752 * @return A pair of iterators pointing to the first mismatch.
1754 * This compares the elements of two ranges using @c == and returns a pair
1755 * of iterators. The first iterator points into the first range, the
1756 * second iterator points into the second range, and the elements pointed
1757 * to by the iterators are not equal.
1759 template<typename _InputIterator1
, typename _InputIterator2
>
1760 _GLIBCXX20_CONSTEXPR
1761 inline pair
<_InputIterator1
, _InputIterator2
>
1762 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1763 _InputIterator2 __first2
)
1765 // concept requirements
1766 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1767 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1768 __glibcxx_function_requires(_EqualOpConcept
<
1769 typename iterator_traits
<_InputIterator1
>::value_type
,
1770 typename iterator_traits
<_InputIterator2
>::value_type
>)
1771 __glibcxx_requires_valid_range(__first1
, __last1
);
1773 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
,
1774 __gnu_cxx::__ops::__iter_equal_to_iter());
1778 * @brief Finds the places in ranges which don't match.
1779 * @ingroup non_mutating_algorithms
1780 * @param __first1 An input iterator.
1781 * @param __last1 An input iterator.
1782 * @param __first2 An input iterator.
1783 * @param __binary_pred A binary predicate @link functors
1785 * @return A pair of iterators pointing to the first mismatch.
1787 * This compares the elements of two ranges using the binary_pred
1788 * parameter, and returns a pair
1789 * of iterators. The first iterator points into the first range, the
1790 * second iterator points into the second range, and the elements pointed
1791 * to by the iterators are not equal.
1793 template<typename _InputIterator1
, typename _InputIterator2
,
1794 typename _BinaryPredicate
>
1795 _GLIBCXX20_CONSTEXPR
1796 inline pair
<_InputIterator1
, _InputIterator2
>
1797 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1798 _InputIterator2 __first2
, _BinaryPredicate __binary_pred
)
1800 // concept requirements
1801 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1802 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1803 __glibcxx_requires_valid_range(__first1
, __last1
);
1805 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
,
1806 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
1809 #if __cplusplus > 201103L
1811 template<typename _InputIterator1
, typename _InputIterator2
,
1812 typename _BinaryPredicate
>
1813 _GLIBCXX20_CONSTEXPR
1814 pair
<_InputIterator1
, _InputIterator2
>
1815 __mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1816 _InputIterator2 __first2
, _InputIterator2 __last2
,
1817 _BinaryPredicate __binary_pred
)
1819 while (__first1
!= __last1
&& __first2
!= __last2
1820 && __binary_pred(__first1
, __first2
))
1825 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
1829 * @brief Finds the places in ranges which don't match.
1830 * @ingroup non_mutating_algorithms
1831 * @param __first1 An input iterator.
1832 * @param __last1 An input iterator.
1833 * @param __first2 An input iterator.
1834 * @param __last2 An input iterator.
1835 * @return A pair of iterators pointing to the first mismatch.
1837 * This compares the elements of two ranges using @c == and returns a pair
1838 * of iterators. The first iterator points into the first range, the
1839 * second iterator points into the second range, and the elements pointed
1840 * to by the iterators are not equal.
1842 template<typename _InputIterator1
, typename _InputIterator2
>
1843 _GLIBCXX20_CONSTEXPR
1844 inline pair
<_InputIterator1
, _InputIterator2
>
1845 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1846 _InputIterator2 __first2
, _InputIterator2 __last2
)
1848 // concept requirements
1849 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1850 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1851 __glibcxx_function_requires(_EqualOpConcept
<
1852 typename iterator_traits
<_InputIterator1
>::value_type
,
1853 typename iterator_traits
<_InputIterator2
>::value_type
>)
1854 __glibcxx_requires_valid_range(__first1
, __last1
);
1855 __glibcxx_requires_valid_range(__first2
, __last2
);
1857 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
, __last2
,
1858 __gnu_cxx::__ops::__iter_equal_to_iter());
1862 * @brief Finds the places in ranges which don't match.
1863 * @ingroup non_mutating_algorithms
1864 * @param __first1 An input iterator.
1865 * @param __last1 An input iterator.
1866 * @param __first2 An input iterator.
1867 * @param __last2 An input iterator.
1868 * @param __binary_pred A binary predicate @link functors
1870 * @return A pair of iterators pointing to the first mismatch.
1872 * This compares the elements of two ranges using the binary_pred
1873 * parameter, and returns a pair
1874 * of iterators. The first iterator points into the first range, the
1875 * second iterator points into the second range, and the elements pointed
1876 * to by the iterators are not equal.
1878 template<typename _InputIterator1
, typename _InputIterator2
,
1879 typename _BinaryPredicate
>
1880 _GLIBCXX20_CONSTEXPR
1881 inline pair
<_InputIterator1
, _InputIterator2
>
1882 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1883 _InputIterator2 __first2
, _InputIterator2 __last2
,
1884 _BinaryPredicate __binary_pred
)
1886 // concept requirements
1887 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1888 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1889 __glibcxx_requires_valid_range(__first1
, __last1
);
1890 __glibcxx_requires_valid_range(__first2
, __last2
);
1892 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
, __last2
,
1893 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
1897 _GLIBCXX_END_NAMESPACE_ALGO
1899 /// This is an overload used by find algos for the Input Iterator case.
1900 template<typename _InputIterator
, typename _Predicate
>
1901 _GLIBCXX20_CONSTEXPR
1902 inline _InputIterator
1903 __find_if(_InputIterator __first
, _InputIterator __last
,
1904 _Predicate __pred
, input_iterator_tag
)
1906 while (__first
!= __last
&& !__pred(__first
))
1911 /// This is an overload used by find algos for the RAI case.
1912 template<typename _RandomAccessIterator
, typename _Predicate
>
1913 _GLIBCXX20_CONSTEXPR
1914 _RandomAccessIterator
1915 __find_if(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1916 _Predicate __pred
, random_access_iterator_tag
)
1918 typename iterator_traits
<_RandomAccessIterator
>::difference_type
1919 __trip_count
= (__last
- __first
) >> 2;
1921 for (; __trip_count
> 0; --__trip_count
)
1923 if (__pred(__first
))
1927 if (__pred(__first
))
1931 if (__pred(__first
))
1935 if (__pred(__first
))
1940 switch (__last
- __first
)
1943 if (__pred(__first
))
1947 if (__pred(__first
))
1951 if (__pred(__first
))
1960 template<typename _Iterator
, typename _Predicate
>
1961 _GLIBCXX20_CONSTEXPR
1963 __find_if(_Iterator __first
, _Iterator __last
, _Predicate __pred
)
1965 return __find_if(__first
, __last
, __pred
,
1966 std::__iterator_category(__first
));
1969 template<typename _InputIterator
, typename _Predicate
>
1970 _GLIBCXX20_CONSTEXPR
1971 typename iterator_traits
<_InputIterator
>::difference_type
1972 __count_if(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
1974 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
1975 for (; __first
!= __last
; ++__first
)
1976 if (__pred(__first
))
1981 #if __cplusplus >= 201103L
1982 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
1983 typename _BinaryPredicate
>
1984 _GLIBCXX20_CONSTEXPR
1986 __is_permutation(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
1987 _ForwardIterator2 __first2
, _BinaryPredicate __pred
)
1989 // Efficiently compare identical prefixes: O(N) if sequences
1990 // have the same elements in the same order.
1991 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
)
1992 if (!__pred(__first1
, __first2
))
1995 if (__first1
== __last1
)
1998 // Establish __last2 assuming equal ranges by iterating over the
1999 // rest of the list.
2000 _ForwardIterator2 __last2
= __first2
;
2001 std::advance(__last2
, std::distance(__first1
, __last1
));
2002 for (_ForwardIterator1 __scan
= __first1
; __scan
!= __last1
; ++__scan
)
2004 if (__scan
!= std::__find_if(__first1
, __scan
,
2005 __gnu_cxx::__ops::__iter_comp_iter(__pred
, __scan
)))
2006 continue; // We've seen this one before.
2009 = std::__count_if(__first2
, __last2
,
2010 __gnu_cxx::__ops::__iter_comp_iter(__pred
, __scan
));
2011 if (0 == __matches
||
2012 std::__count_if(__scan
, __last1
,
2013 __gnu_cxx::__ops::__iter_comp_iter(__pred
, __scan
))
2021 * @brief Checks whether a permutation of the second sequence is equal
2022 * to the first sequence.
2023 * @ingroup non_mutating_algorithms
2024 * @param __first1 Start of first range.
2025 * @param __last1 End of first range.
2026 * @param __first2 Start of second range.
2027 * @return true if there exists a permutation of the elements in the range
2028 * [__first2, __first2 + (__last1 - __first1)), beginning with
2029 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
2030 * returns true; otherwise, returns false.
2032 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
2033 _GLIBCXX20_CONSTEXPR
2035 is_permutation(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
2036 _ForwardIterator2 __first2
)
2038 // concept requirements
2039 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
2040 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
2041 __glibcxx_function_requires(_EqualOpConcept
<
2042 typename iterator_traits
<_ForwardIterator1
>::value_type
,
2043 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
2044 __glibcxx_requires_valid_range(__first1
, __last1
);
2046 return std::__is_permutation(__first1
, __last1
, __first2
,
2047 __gnu_cxx::__ops::__iter_equal_to_iter());
2051 _GLIBCXX_END_NAMESPACE_VERSION
2054 // NB: This file is included within many other C++ includes, as a way
2055 // of getting the base algorithms. So, make sure that parallel bits
2056 // come in too if requested.
2057 #ifdef _GLIBCXX_PARALLEL
2058 # include <parallel/algobase.h>