// Algorithm implementation -*- C++ -*-
-// Copyright (C) 2001-2019 Free Software Foundation, Inc.
+// Copyright (C) 2001-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
/// Swaps the median value of *__a, *__b and *__c under __comp to *__result
template<typename _Iterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
_Iterator __c, _Compare __comp)
/// This is an overload used by find algos for the Input Iterator case.
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _InputIterator
__find_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred, input_iterator_tag)
/// This is an overload used by find algos for the RAI case.
template<typename _RandomAccessIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
_RandomAccessIterator
__find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Predicate __pred, random_access_iterator_tag)
}
template<typename _Iterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _Iterator
__find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
{
/// Provided for stable_partition to use.
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _InputIterator
__find_if_not(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
/// remaining range length instead of comparing against an end
/// iterator.
template<typename _InputIterator, typename _Predicate, typename _Distance>
+ _GLIBCXX20_CONSTEXPR
_InputIterator
__find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
{
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator1
__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
// General case.
- _ForwardIterator2 __p;
_ForwardIterator1 __current = __first1;
for (;;)
if (__first1 == __last1)
return __last1;
- __p = __p1;
+ _ForwardIterator2 __p = __p1;
__current = __first1;
if (++__current == __last1)
return __last1;
*/
template<typename _ForwardIterator, typename _Integer,
typename _UnaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count, _UnaryPredicate __unary_pred,
*/
template<typename _RandomAccessIter, typename _Integer,
typename _UnaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_RandomAccessIter
__search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
_Integer __count, _UnaryPredicate __unary_pred,
template<typename _ForwardIterator, typename _Integer,
typename _UnaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__search_n(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count,
// find_end for forward iterators.
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator1
__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
// find_end for bidirectional iterators (much faster).
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_BidirectionalIterator1
__find_end(_BidirectionalIterator1 __first1,
_BidirectionalIterator1 __last1,
* [__first1,__last1-(__last2-__first2))
*/
template<typename _ForwardIterator1, typename _ForwardIterator2>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator1
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator1
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
* @p [__first,__last), and false otherwise.
*/
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline bool
all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{ return __last == std::find_if_not(__first, __last, __pred); }
* @p [__first,__last), and false otherwise.
*/
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline bool
none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{ return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
* otherwise.
*/
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline bool
any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{ return !std::none_of(__first, __last, __pred); }
* such that @p __pred(*i) is false, or @p __last if no such iterator exists.
*/
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _InputIterator
find_if_not(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
* do not.
*/
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline bool
is_partitioned(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
* and @p none_of(mid, __last, __pred) are both true.
*/
template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
partition_point(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
_DistanceType;
_DistanceType __len = std::distance(__first, __last);
- _DistanceType __half;
- _ForwardIterator __middle;
while (__len > 0)
{
- __half = __len >> 1;
- __middle = __first;
+ _DistanceType __half = __len >> 1;
+ _ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (__pred(*__middle))
{
template<typename _InputIterator, typename _OutputIterator,
typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__remove_copy_if(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _Predicate __pred)
* are copied is unchanged.
*/
template<typename _InputIterator, typename _OutputIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
remove_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, const _Tp& __value)
*/
template<typename _InputIterator, typename _OutputIterator,
typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
remove_copy_if(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _Predicate __pred)
*/
template<typename _InputIterator, typename _OutputIterator,
typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
copy_if(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _Predicate __pred)
}
template<typename _InputIterator, typename _Size, typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
- __copy_n(_InputIterator __first, _Size __n,
- _OutputIterator __result, input_iterator_tag)
+ __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result)
{
if (__n > 0)
{
}
return __result;
}
+
+ template<typename _CharT, typename _Size>
+ __enable_if_t<__is_char<_CharT>::__value, _CharT*>
+ __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT>>,
+ _Size, _CharT*);
+
+ template<typename _InputIterator, typename _Size, typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
+ _OutputIterator
+ __copy_n(_InputIterator __first, _Size __n,
+ _OutputIterator __result, input_iterator_tag)
+ {
+ return std::__niter_wrap(__result,
+ __copy_n_a(__first, __n,
+ std::__niter_base(__result)));
+ }
template<typename _RandomAccessIterator, typename _Size,
typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
__copy_n(_RandomAccessIterator __first, _Size __n,
_OutputIterator __result, random_access_iterator_tag)
* optimizations such as unrolling).
*/
template<typename _InputIterator, typename _Size, typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
{
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
typename iterator_traits<_InputIterator>::value_type>)
+ __glibcxx_requires_can_increment(__first, __n);
+ __glibcxx_requires_can_increment(__result, __n);
return std::__copy_n(__first, __n, __result,
std::__iterator_category(__first));
*/
template<typename _InputIterator, typename _OutputIterator1,
typename _OutputIterator2, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
pair<_OutputIterator1, _OutputIterator2>
partition_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator1 __out_true, _OutputIterator2 __out_false,
return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
}
-#endif
+#endif // C++11
template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__remove_if(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
* are still present, but their value is unspecified.
*/
template<typename _ForwardIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
remove(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __value)
* are still present, but their value is unspecified.
*/
template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
remove_if(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
}
template<typename _ForwardIterator, typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
_BinaryPredicate __binary_pred)
}
template<typename _ForwardIterator, typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__unique(_ForwardIterator __first, _ForwardIterator __last,
_BinaryPredicate __binary_pred)
* are still present, but their value is unspecified.
*/
template<typename _ForwardIterator>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
unique(_ForwardIterator __first, _ForwardIterator __last)
{
* are still present, but their value is unspecified.
*/
template<typename _ForwardIterator, typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
unique(_ForwardIterator __first, _ForwardIterator __last,
_BinaryPredicate __binary_pred)
*/
template<typename _ForwardIterator, typename _OutputIterator,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__unique_copy(_ForwardIterator __first, _ForwardIterator __last,
_OutputIterator __result, _BinaryPredicate __binary_pred,
*/
template<typename _InputIterator, typename _OutputIterator,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _BinaryPredicate __binary_pred,
*/
template<typename _InputIterator, typename _ForwardIterator,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__unique_copy(_InputIterator __first, _InputIterator __last,
_ForwardIterator __result, _BinaryPredicate __binary_pred,
* overloaded for bidirectional iterators.
*/
template<typename _BidirectionalIterator>
+ _GLIBCXX20_CONSTEXPR
void
__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
bidirectional_iterator_tag)
* overloaded for random access iterators.
*/
template<typename _RandomAccessIterator>
+ _GLIBCXX20_CONSTEXPR
void
__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag)
* swaps @p *(__first+i) and @p *(__last-(i+1))
*/
template<typename _BidirectionalIterator>
+ _GLIBCXX20_CONSTEXPR
inline void
reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
{
* [__result,__result+(__last-__first)) must not overlap.
*/
template<typename _BidirectionalIterator, typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
_OutputIterator __result)
* It returns the greatest common divisor of two integer values.
*/
template<typename _EuclideanRingElement>
+ _GLIBCXX20_CONSTEXPR
_EuclideanRingElement
__gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
{
/// This is a helper function for the rotate algorithm.
template<typename _ForwardIterator>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__rotate(_ForwardIterator __first,
_ForwardIterator __middle,
_ForwardIterator __last,
forward_iterator_tag)
{
+ if (__first == __middle)
+ return __last;
+ else if (__last == __middle)
+ return __first;
+
_ForwardIterator __first2 = __middle;
do
{
/// This is a helper function for the rotate algorithm.
template<typename _BidirectionalIterator>
+ _GLIBCXX20_CONSTEXPR
_BidirectionalIterator
__rotate(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
_BidirectionalIterator>)
+ if (__first == __middle)
+ return __last;
+ else if (__last == __middle)
+ return __first;
+
std::__reverse(__first, __middle, bidirectional_iterator_tag());
std::__reverse(__middle, __last, bidirectional_iterator_tag());
/// This is a helper function for the rotate algorithm.
template<typename _RandomAccessIterator>
+ _GLIBCXX20_CONSTEXPR
_RandomAccessIterator
__rotate(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
+ if (__first == __middle)
+ return __last;
+ else if (__last == __middle)
+ return __first;
+
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_Distance;
typedef typename iterator_traits<_RandomAccessIterator>::value_type
* for each @p n in the range @p [0,__last-__first).
*/
template<typename _ForwardIterator>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
rotate(_ForwardIterator __first, _ForwardIterator __middle,
_ForwardIterator __last)
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
- if (__first == __middle)
- return __last;
- else if (__last == __middle)
- return __first;
-
return std::__rotate(__first, __middle, __last,
std::__iterator_category(__first));
}
* for each @p n in the range @p [0,__last-__first).
*/
template<typename _ForwardIterator, typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
_ForwardIterator __last, _OutputIterator __result)
/// This is a helper function...
template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred, forward_iterator_tag)
/// This is a helper function...
template<typename _BidirectionalIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
_BidirectionalIterator
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
_Predicate __pred, bidirectional_iterator_tag)
/// This is a helper function for the sort routines.
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__heap_select(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
template<typename _InputIterator, typename _RandomAccessIterator,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_RandomAccessIterator
__partial_sort_copy(_InputIterator __first, _InputIterator __last,
_RandomAccessIterator __result_first,
* The value returned is @p __result_first+N.
*/
template<typename _InputIterator, typename _RandomAccessIterator>
+ _GLIBCXX20_CONSTEXPR
inline _RandomAccessIterator
partial_sort_copy(_InputIterator __first, _InputIterator __last,
_RandomAccessIterator __result_first,
*/
template<typename _InputIterator, typename _RandomAccessIterator,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _RandomAccessIterator
partial_sort_copy(_InputIterator __first, _InputIterator __last,
_RandomAccessIterator __result_first,
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__unguarded_linear_insert(_RandomAccessIterator __last,
_Compare __comp)
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline void
__unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
}
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline void
__partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
// sort
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
}
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Size __depth_limit,
* the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
}
template<typename _ForwardIterator, typename _Tp, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
* @ingroup binary_search_algorithms
*/
template<typename _ForwardIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
* the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
template<typename _ForwardIterator, typename _Tp,
typename _CompareItTp, typename _CompareTpIt>
+ _GLIBCXX20_CONSTEXPR
pair<_ForwardIterator, _ForwardIterator>
__equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val,
* but does not actually call those functions.
*/
template<typename _ForwardIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline pair<_ForwardIterator, _ForwardIterator>
equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
* but does not actually call those functions.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline pair<_ForwardIterator, _ForwardIterator>
equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
* that, use std::find or a container's specialized find member functions.
*/
template<typename _ForwardIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
bool
binary_search(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
* the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
bool
binary_search(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
template<typename _RandomAccessIterator, typename _Distance,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
void
__chunk_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last,
template<typename _InputIterator1, typename _InputIterator2,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
bool
__includes(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
* returned.
*/
template<typename _InputIterator1, typename _InputIterator2>
+ _GLIBCXX20_CONSTEXPR
inline bool
includes(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline bool
includes(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
// max_element
template<typename _BidirectionalIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
bool
__next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
* is the largest of the set, the smallest is generated and false returned.
*/
template<typename _BidirectionalIterator>
+ _GLIBCXX20_CONSTEXPR
inline bool
next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last)
* smallest is generated and false returned.
*/
template<typename _BidirectionalIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline bool
next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
}
template<typename _BidirectionalIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
bool
__prev_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
* returned.
*/
template<typename _BidirectionalIterator>
+ _GLIBCXX20_CONSTEXPR
inline bool
prev_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last)
* the largest is generated and false returned.
*/
template<typename _BidirectionalIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline bool
prev_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last, _Compare __comp)
template<typename _InputIterator, typename _OutputIterator,
typename _Predicate, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__replace_copy_if(_InputIterator __first, _InputIterator __last,
_OutputIterator __result,
* equal to @p __old_value with @p __new_value.
*/
template<typename _InputIterator, typename _OutputIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
replace_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result,
*/
template<typename _InputIterator, typename _OutputIterator,
typename _Predicate, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
replace_copy_if(_InputIterator __first, _InputIterator __last,
_OutputIterator __result,
}
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
__count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
* @return True if the elements are sorted, false otherwise.
*/
template<typename _ForwardIterator>
+ _GLIBCXX20_CONSTEXPR
inline bool
is_sorted(_ForwardIterator __first, _ForwardIterator __last)
{ return std::is_sorted_until(__first, __last) == __last; }
* @return True if the elements are sorted, false otherwise.
*/
template<typename _ForwardIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline bool
is_sorted(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
{ return std::is_sorted_until(__first, __last, __comp) == __last; }
template<typename _ForwardIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_ForwardIterator
__is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
* for which the range [__first, i) is sorted.
*/
template<typename _ForwardIterator>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
{
* for which the range [__first, i) is sorted.
*/
template<typename _ForwardIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
bool
__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _BinaryPredicate __pred)
* returns true; otherwise, returns false.
*/
template<typename _ForwardIterator1, typename _ForwardIterator2>
+ _GLIBCXX20_CONSTEXPR
inline bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2)
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _BinaryPredicate __pred)
#if __cplusplus > 201103L
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
bool
__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
* otherwise, returns false.
*/
template<typename _ForwardIterator1, typename _ForwardIterator2>
+ _GLIBCXX20_CONSTEXPR
inline bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline bool
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
* If @p __f has a return value it is ignored.
*/
template<typename _InputIterator, typename _Function>
+ _GLIBCXX20_CONSTEXPR
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
}
+#if __cplusplus >= 201703L
+ /**
+ * @brief Apply a function to every element of a sequence.
+ * @ingroup non_mutating_algorithms
+ * @param __first An input iterator.
+ * @param __n A value convertible to an integer.
+ * @param __f A unary function object.
+ * @return `__first+__n`
+ *
+ * Applies the function object `__f` to each element in the range
+ * `[first, first+n)`. `__f` must not modify the order of the sequence.
+ * If `__f` has a return value it is ignored.
+ */
+ template<typename _InputIterator, typename _Size, typename _Function>
+ _InputIterator
+ for_each_n(_InputIterator __first, _Size __n, _Function __f)
+ {
+ auto __n2 = std::__size_to_integer(__n);
+ using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
+ if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
+ {
+ if (__n2 <= 0)
+ return __first;
+ auto __last = __first + __n2;
+ std::for_each(__first, __last, std::move(__f));
+ return __last;
+ }
+ else
+ {
+ while (__n2-->0)
+ {
+ __f(*__first);
+ ++__first;
+ }
+ return __first;
+ }
+ }
+#endif // C++17
+
/**
* @brief Find the first occurrence of a value in a sequence.
* @ingroup non_mutating_algorithms
* such that @c *i == @p __val, or @p __last if no such iterator exists.
*/
template<typename _InputIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline _InputIterator
find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
* such that @p __pred(*i) is true, or @p __last if no such iterator exists.
*/
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _InputIterator
find_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
* otherwise returns @p __last1.
*/
template<typename _InputIterator, typename _ForwardIterator>
+ _GLIBCXX20_CONSTEXPR
_InputIterator
find_first_of(_InputIterator __first1, _InputIterator __last1,
_ForwardIterator __first2, _ForwardIterator __last2)
*/
template<typename _InputIterator, typename _ForwardIterator,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
_InputIterator
find_first_of(_InputIterator __first1, _InputIterator __last1,
_ForwardIterator __first2, _ForwardIterator __last2,
* or @p __last if no such iterator exists.
*/
template<typename _ForwardIterator>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
{
* exists.
*/
template<typename _ForwardIterator, typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
_BinaryPredicate __binary_pred)
* for which @c *i == @p __value
*/
template<typename _InputIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline typename iterator_traits<_InputIterator>::difference_type
count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
{
* for which @p __pred(*i) is true.
*/
template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
* @p [__first1,__last1-(__last2-__first2))
*/
template<typename _ForwardIterator1, typename _ForwardIterator2>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
*/
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
* equal to @p __val.
*/
template<typename _ForwardIterator, typename _Integer, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
search_n(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count, const _Tp& __val)
*/
template<typename _ForwardIterator, typename _Integer, typename _Tp,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
search_n(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count, const _Tp& __val,
*/
template<typename _InputIterator, typename _OutputIterator,
typename _UnaryOperation>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
transform(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, _UnaryOperation __unary_op)
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _BinaryOperation>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
transform(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _OutputIterator __result,
* @p __old_value then the assignment @c *i = @p __new_value is performed.
*/
template<typename _ForwardIterator, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
void
replace(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __old_value, const _Tp& __new_value)
* is true then the assignment @c *i = @p __new_value is performed.
*/
template<typename _ForwardIterator, typename _Predicate, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
void
replace_if(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred, const _Tp& __new_value)
* @p [__first,__last).
*/
template<typename _ForwardIterator, typename _Generator>
+ _GLIBCXX20_CONSTEXPR
void
generate(_ForwardIterator __first, _ForwardIterator __last,
_Generator __gen)
* Performs the assignment @c *i = @p __gen() for each @c i in the range
* @p [__first,__first+__n).
*
- * If @p __n is negative, the function does nothing.
+ * If @p __n is negative, the function does nothing and returns @p __first.
*/
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 865. More algorithms that throw away information
// DR 426. search_n(), fill_n(), and generate_n() with negative n
template<typename _OutputIterator, typename _Size, typename _Generator>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
{
* Assignable?
*/
template<typename _InputIterator, typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result)
*/
template<typename _InputIterator, typename _OutputIterator,
typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result,
* @p stable_partition() if this is needed.
*/
template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred)
* the range @p [__middle,__last) then *j<*i and *k<*i are both false.
*/
template<typename _RandomAccessIterator>
+ _GLIBCXX20_CONSTEXPR
inline void
partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
* are both false.
*/
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline void
partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
* holds that *j < *i is false.
*/
template<typename _RandomAccessIterator>
+ _GLIBCXX20_CONSTEXPR
inline void
nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last)
* holds that @p __comp(*j,*i) is false.
*/
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline void
nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Compare __comp)
* @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIterator>
+ _GLIBCXX20_CONSTEXPR
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
* @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__merge(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
* @param __last1 Another iterator.
* @param __last2 Another iterator.
* @param __result An iterator pointing to the end of the merged range.
- * @return An iterator pointing to the first element <em>not less
- * than</em> @e val.
+ * @return An output iterator equal to @p __result + (__last1 - __first1)
+ * + (__last2 - __first2).
*
* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
* the sorted range @p [__result, __result + (__last1-__first1) +
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
merge(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
* @param __last2 Another iterator.
* @param __result An iterator pointing to the end of the merged range.
* @param __comp A functor to use for comparisons.
- * @return An iterator pointing to the first element "not less
- * than" @e val.
+ * @return An output iterator equal to @p __result + (__last1 - __first1)
+ * + (__last2 - __first2).
*
* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
* the sorted range @p [__result, __result + (__last1-__first1) +
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
merge(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_union(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_union(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator,
typename _Compare>
+ _GLIBCXX20_CONSTEXPR
_OutputIterator
__set_symmetric_difference(_InputIterator1 __first1,
_InputIterator1 __last1,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
+ _GLIBCXX20_CONSTEXPR
inline _OutputIterator
set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,