57#define _EXT_ALGORITHM 1
60#pragma GCC system_header
67namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
69_GLIBCXX_BEGIN_NAMESPACE_VERSION
74 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
76 __copy_n(_InputIterator __first, _Size __count,
77 _OutputIterator __result,
78 std::input_iterator_tag)
80 for ( ; __count > 0; --__count)
89 template<
typename _RAIterator,
typename _Size,
typename _OutputIterator>
91 __copy_n(_RAIterator __first, _Size __count,
92 _OutputIterator __result,
93 std::random_access_iterator_tag)
95 _RAIterator __last = __first + __count;
115 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
117 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
120 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
121 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
124 return __gnu_cxx::__copy_n(__first, __count, __result,
128 template<
typename _InputIterator1,
typename _InputIterator2>
130 __lexicographical_compare_3way(_InputIterator1 __first1,
131 _InputIterator1 __last1,
132 _InputIterator2 __first2,
133 _InputIterator2 __last2)
135 while (__first1 != __last1 && __first2 != __last2)
137 if (*__first1 < *__first2)
139 if (*__first2 < *__first1)
144 if (__first2 == __last2)
145 return !(__first1 == __last1);
151 __lexicographical_compare_3way(
const unsigned char* __first1,
152 const unsigned char* __last1,
153 const unsigned char* __first2,
154 const unsigned char* __last2)
156 const std::ptrdiff_t __len1 = __last1 - __first1;
157 const std::ptrdiff_t __len2 = __last2 - __first2;
158 const int __result = __builtin_memcmp(__first1, __first2,
160 return __result != 0 ? __result
161 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
165 __lexicographical_compare_3way(
const char* __first1,
const char* __last1,
166 const char* __first2,
const char* __last2)
168#if CHAR_MAX == SCHAR_MAX
169 return __lexicographical_compare_3way((
const signed char*) __first1,
170 (
const signed char*) __last1,
171 (
const signed char*) __first2,
172 (
const signed char*) __last2);
174 return __lexicographical_compare_3way((
const unsigned char*) __first1,
175 (
const unsigned char*) __last1,
176 (
const unsigned char*) __first2,
177 (
const unsigned char*) __last2);
196 template<
typename _InputIterator1,
typename _InputIterator2>
199 _InputIterator1 __last1,
200 _InputIterator2 __first2,
201 _InputIterator2 __last2)
204 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
205 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
206 __glibcxx_function_requires(_LessThanComparableConcept<
208 __glibcxx_function_requires(_LessThanComparableConcept<
210 __glibcxx_requires_valid_range(__first1, __last1);
211 __glibcxx_requires_valid_range(__first2, __last2);
213 return __lexicographical_compare_3way(__first1, __last1, __first2,
219 template<
typename _InputIterator,
typename _Tp,
typename _Size>
221 count(_InputIterator __first, _InputIterator __last,
226 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
227 __glibcxx_function_requires(_EqualityComparableConcept<
229 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
230 __glibcxx_requires_valid_range(__first, __last);
232 for ( ; __first != __last; ++__first)
233 if (*__first == __value)
237 template<typename _InputIterator, typename _Predicate, typename _Size>
239 count_if(_InputIterator __first, _InputIterator __last,
244 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
245 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
247 __glibcxx_requires_valid_range(__first, __last);
249 for ( ; __first != __last; ++__first)
250 if (__pred(*__first))
261 template<typename _ForwardIterator, typename _OutputIterator,
265 _OutputIterator __out, const _Distance __n)
268 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
269 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
271 __glibcxx_requires_valid_range(__first, __last);
274 _Distance __m = (
std::min)(__n, __remaining);
278 if ((std::rand() % __remaining) < __m)
295 template<
typename _ForwardIterator,
typename _OutputIterator,
296 typename _Distance,
typename _RandomNumberGenerator>
299 _OutputIterator __out,
const _Distance __n,
300 _RandomNumberGenerator& __rand)
303 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
304 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
306 __glibcxx_function_requires(_UnaryFunctionConcept<
307 _RandomNumberGenerator, _Distance, _Distance>)
308 __glibcxx_requires_valid_range(__first, __last);
311 _Distance __m = (
std::min)(__n, __remaining);
315 if (__rand(__remaining) < __m)
327 template<
typename _InputIterator,
typename _RandomAccessIterator,
329 _RandomAccessIterator
330 __random_sample(_InputIterator __first, _InputIterator __last,
331 _RandomAccessIterator __out,
336 for ( ; __first != __last && __m < __n; ++__m, ++__first)
337 __out[__m] = *__first;
339 while (__first != __last)
342 _Distance __M = std::rand() % (__t);
344 __out[__M] = *__first;
350 template<
typename _InputIterator,
typename _RandomAccessIterator,
351 typename _RandomNumberGenerator,
typename _Distance>
352 _RandomAccessIterator
353 __random_sample(_InputIterator __first, _InputIterator __last,
354 _RandomAccessIterator __out,
355 _RandomNumberGenerator& __rand,
359 __glibcxx_function_requires(_UnaryFunctionConcept<
360 _RandomNumberGenerator, _Distance, _Distance>)
364 for ( ; __first != __last && __m < __n; ++__m, ++__first)
365 __out[__m] = *__first;
367 while (__first != __last)
370 _Distance __M = __rand(__t);
372 __out[__M] = *__first;
383 template<
typename _InputIterator,
typename _RandomAccessIterator>
384 inline _RandomAccessIterator
386 _RandomAccessIterator __out_first,
387 _RandomAccessIterator __out_last)
390 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
391 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
392 _RandomAccessIterator>)
393 __glibcxx_requires_valid_range(__first, __last);
394 __glibcxx_requires_valid_range(__out_first, __out_last);
396 return __random_sample(__first, __last,
397 __out_first, __out_last - __out_first);
405 template<
typename _InputIterator,
typename _RandomAccessIterator,
406 typename _RandomNumberGenerator>
407 inline _RandomAccessIterator
409 _RandomAccessIterator __out_first,
410 _RandomAccessIterator __out_last,
411 _RandomNumberGenerator& __rand)
414 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
415 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
416 _RandomAccessIterator>)
417 __glibcxx_requires_valid_range(__first, __last);
418 __glibcxx_requires_valid_range(__out_first, __out_last);
420 return __random_sample(__first, __last,
422 __out_last - __out_first);
425#if __cplusplus >= 201103L
433 template<
typename _RandomAccessIterator>
435 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
438 __glibcxx_function_requires(_RandomAccessIteratorConcept<
439 _RandomAccessIterator>)
440 __glibcxx_function_requires(_LessThanComparableConcept<
441 typename
std::iterator_traits<_RandomAccessIterator>::value_type>)
442 __glibcxx_requires_valid_range(__first, __last);
444 return
std::__is_heap(__first, __last - __first);
452 template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
454 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
455 _StrictWeakOrdering __comp)
458 __glibcxx_function_requires(_RandomAccessIteratorConcept<
459 _RandomAccessIterator>)
460 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
461 typename
std::iterator_traits<_RandomAccessIterator>::value_type,
462 typename
std::iterator_traits<_RandomAccessIterator>::value_type>)
463 __glibcxx_requires_valid_range(__first, __last);
465 return
std::__is_heap(__first, __comp, __last - __first);
469#if __cplusplus >= 201103L
470 using std::is_sorted;
481 template<
typename _ForwardIterator>
483 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
486 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
487 __glibcxx_function_requires(_LessThanComparableConcept<
489 __glibcxx_requires_valid_range(__first, __last);
491 if (__first == __last)
494 _ForwardIterator __next = __first;
495 for (++__next; __next != __last; __first = __next, ++__next)
496 if (*__next < *__first)
506 template<typename _ForwardIterator, typename _StrictWeakOrdering>
508 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
509 _StrictWeakOrdering __comp)
512 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
513 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
516 __glibcxx_requires_valid_range(__first, __last);
518 if (__first == __last)
521 _ForwardIterator __next = __first;
522 for (++__next; __next != __last; __first = __next, ++__next)
523 if (__comp(*__next, *__first))
541 template<
typename _Tp>
543 __median(
const _Tp& __a,
const _Tp& __b,
const _Tp& __c)
546 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
575 template<
typename _Tp,
typename _Compare>
577 __median(
const _Tp& __a,
const _Tp& __b,
const _Tp& __c, _Compare __comp)
580 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,
bool,
582 if (__comp(__a, __b))
583 if (__comp(__b, __c))
585 else if (__comp(__a, __c))
589 else if (__comp(__a, __c))
591 else if (__comp(__b, __c))
597_GLIBCXX_END_NAMESPACE_VERSION
const _Tp & __median(const _Tp &__a, const _Tp &__b, const _Tp &__c)
Find the median of three values.
_OutputIterator random_sample_n(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __out, const _Distance __n)
_RandomAccessIterator random_sample(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __out_first, _RandomAccessIterator __out_last)
std::pair< _InputIterator, _OutputIterator > copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
Copies the range [first,first+count) into [result,result+count).
int lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
memcmp on steroids.
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
GNU extensions for public use.
Traits class for iterators.