56 #ifndef _EXT_ALGORITHM
57 #define _EXT_ALGORITHM 1
59 #pragma GCC system_header
63 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
65 _GLIBCXX_BEGIN_NAMESPACE_VERSION
70 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
72 __copy_n(_InputIterator __first, _Size __count,
73 _OutputIterator __result,
76 for ( ; __count > 0; --__count)
85 template<
typename _RAIterator,
typename _Size,
typename _OutputIterator>
87 __copy_n(_RAIterator __first, _Size __count,
88 _OutputIterator __result,
91 _RAIterator __last = __first + __count;
111 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
113 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
116 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
117 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
120 return __gnu_cxx::__copy_n(__first, __count, __result,
124 template<
typename _InputIterator1,
typename _InputIterator2>
126 __lexicographical_compare_3way(_InputIterator1 __first1,
127 _InputIterator1 __last1,
128 _InputIterator2 __first2,
129 _InputIterator2 __last2)
131 while (__first1 != __last1 && __first2 != __last2)
133 if (*__first1 < *__first2)
135 if (*__first2 < *__first1)
140 if (__first2 == __last2)
141 return !(__first1 == __last1);
147 __lexicographical_compare_3way(
const unsigned char* __first1,
148 const unsigned char* __last1,
149 const unsigned char* __first2,
150 const unsigned char* __last2)
152 const std::ptrdiff_t __len1 = __last1 - __first1;
153 const std::ptrdiff_t __len2 = __last2 - __first2;
154 const int __result = __builtin_memcmp(__first1, __first2,
156 return __result != 0 ? __result
157 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
161 __lexicographical_compare_3way(
const char* __first1,
const char* __last1,
162 const char* __first2,
const char* __last2)
164 #if CHAR_MAX == SCHAR_MAX
165 return __lexicographical_compare_3way((
const signed char*) __first1,
166 (
const signed char*) __last1,
167 (
const signed char*) __first2,
168 (
const signed char*) __last2);
170 return __lexicographical_compare_3way((
const unsigned char*) __first1,
171 (
const unsigned char*) __last1,
172 (
const unsigned char*) __first2,
173 (
const unsigned char*) __last2);
192 template<
typename _InputIterator1,
typename _InputIterator2>
195 _InputIterator1 __last1,
196 _InputIterator2 __first2,
197 _InputIterator2 __last2)
200 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
201 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
202 __glibcxx_function_requires(_LessThanComparableConcept<
204 __glibcxx_function_requires(_LessThanComparableConcept<
206 __glibcxx_requires_valid_range(__first1, __last1);
207 __glibcxx_requires_valid_range(__first2, __last2);
209 return __lexicographical_compare_3way(__first1, __last1, __first2,
215 template<
typename _InputIterator,
typename _Tp,
typename _Size>
217 count(_InputIterator __first, _InputIterator __last,
222 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
223 __glibcxx_function_requires(_EqualityComparableConcept<
224 typename std::iterator_traits<_InputIterator>::value_type >)
225 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
226 __glibcxx_requires_valid_range(__first, __last);
228 for ( ; __first != __last; ++__first)
229 if (*__first == __value)
233 template<typename _InputIterator, typename _Predicate, typename _Size>
235 count_if(_InputIterator __first, _InputIterator __last,
240 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
241 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
242 typename std::iterator_traits<_InputIterator>::value_type>)
243 __glibcxx_requires_valid_range(__first, __last);
245 for ( ; __first != __last; ++__first)
246 if (__pred(*__first))
257 template<typename _ForwardIterator, typename _OutputIterator,
261 _OutputIterator __out, const _Distance __n)
264 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
265 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
267 __glibcxx_requires_valid_range(__first, __last);
270 _Distance __m = (
std::min)(__n, __remaining);
274 if ((std::rand() % __remaining) < __m)
291 template<
typename _ForwardIterator,
typename _OutputIterator,
292 typename _Distance,
typename _RandomNumberGenerator>
295 _OutputIterator __out,
const _Distance __n,
296 _RandomNumberGenerator& __rand)
299 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
300 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
302 __glibcxx_function_requires(_UnaryFunctionConcept<
303 _RandomNumberGenerator, _Distance, _Distance>)
304 __glibcxx_requires_valid_range(__first, __last);
307 _Distance __m = (
std::min)(__n, __remaining);
311 if (__rand(__remaining) < __m)
323 template<
typename _InputIterator,
typename _RandomAccessIterator,
325 _RandomAccessIterator
326 __random_sample(_InputIterator __first, _InputIterator __last,
327 _RandomAccessIterator __out,
332 for ( ; __first != __last && __m < __n; ++__m, ++__first)
333 __out[__m] = *__first;
335 while (__first != __last)
338 _Distance __M = std::rand() % (__t);
340 __out[__M] = *__first;
346 template<
typename _InputIterator,
typename _RandomAccessIterator,
347 typename _RandomNumberGenerator,
typename _Distance>
348 _RandomAccessIterator
349 __random_sample(_InputIterator __first, _InputIterator __last,
350 _RandomAccessIterator __out,
351 _RandomNumberGenerator& __rand,
355 __glibcxx_function_requires(_UnaryFunctionConcept<
356 _RandomNumberGenerator, _Distance, _Distance>)
360 for ( ; __first != __last && __m < __n; ++__m, ++__first)
361 __out[__m] = *__first;
363 while (__first != __last)
366 _Distance __M = __rand(__t);
368 __out[__M] = *__first;
379 template<
typename _InputIterator,
typename _RandomAccessIterator>
380 inline _RandomAccessIterator
382 _RandomAccessIterator __out_first,
383 _RandomAccessIterator __out_last)
386 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
387 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
388 _RandomAccessIterator>)
389 __glibcxx_requires_valid_range(__first, __last);
390 __glibcxx_requires_valid_range(__out_first, __out_last);
392 return __random_sample(__first, __last,
393 __out_first, __out_last - __out_first);
401 template<
typename _InputIterator,
typename _RandomAccessIterator,
402 typename _RandomNumberGenerator>
403 inline _RandomAccessIterator
405 _RandomAccessIterator __out_first,
406 _RandomAccessIterator __out_last,
407 _RandomNumberGenerator& __rand)
410 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
411 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
412 _RandomAccessIterator>)
413 __glibcxx_requires_valid_range(__first, __last);
414 __glibcxx_requires_valid_range(__out_first, __out_last);
416 return __random_sample(__first, __last,
418 __out_last - __out_first);
421 #if __cplusplus >= 201103L
429 template<
typename _RandomAccessIterator>
431 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
434 __glibcxx_function_requires(_RandomAccessIteratorConcept<
435 _RandomAccessIterator>)
436 __glibcxx_function_requires(_LessThanComparableConcept<
437 typename std::iterator_traits<_RandomAccessIterator>::value_type>)
438 __glibcxx_requires_valid_range(__first, __last);
440 return std::__is_heap(__first, __last - __first);
448 template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
450 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
451 _StrictWeakOrdering __comp)
454 __glibcxx_function_requires(_RandomAccessIteratorConcept<
455 _RandomAccessIterator>)
456 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
457 typename std::iterator_traits<_RandomAccessIterator>::value_type,
458 typename std::iterator_traits<_RandomAccessIterator>::value_type>)
459 __glibcxx_requires_valid_range(__first, __last);
461 return std::__is_heap(__first, __comp, __last - __first);
465 #if __cplusplus >= 201103L
466 using std::is_sorted;
477 template<
typename _ForwardIterator>
479 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
482 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
483 __glibcxx_function_requires(_LessThanComparableConcept<
484 typename std::iterator_traits<_ForwardIterator>::value_type>)
485 __glibcxx_requires_valid_range(__first, __last);
487 if (__first == __last)
490 _ForwardIterator __next = __first;
491 for (++__next; __next != __last; __first = __next, ++__next)
492 if (*__next < *__first)
502 template<typename _ForwardIterator, typename _StrictWeakOrdering>
504 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
505 _StrictWeakOrdering __comp)
508 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
509 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
510 typename std::iterator_traits<_ForwardIterator>::value_type,
511 typename std::iterator_traits<_ForwardIterator>::value_type>)
512 __glibcxx_requires_valid_range(__first, __last);
514 if (__first == __last)
517 _ForwardIterator __next = __first;
518 for (++__next; __next != __last; __first = __next, ++__next)
519 if (__comp(*__next, *__first))
537 template<
typename _Tp>
539 __median(
const _Tp& __a,
const _Tp& __b,
const _Tp& __c)
542 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
571 template<
typename _Tp,
typename _Compare>
573 __median(
const _Tp& __a,
const _Tp& __b,
const _Tp& __c, _Compare __comp)
576 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,
bool,
578 if (__comp(__a, __b))
579 if (__comp(__b, __c))
581 else if (__comp(__a, __c))
585 else if (__comp(__a, __c))
587 else if (__comp(__b, __c))
593 _GLIBCXX_END_NAMESPACE_VERSION
_RandomAccessIterator random_sample(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __out_first, _RandomAccessIterator __out_last)
const _Tp & __median(const _Tp &__a, const _Tp &__b, const _Tp &__c)
Find the median of three values.
int lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
memcmp on steroids.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_OutputIterator random_sample_n(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __out, const _Distance __n)
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
std::pair< _InputIterator, _OutputIterator > copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
Copies the range [first,first+count) into [result,result+count).
Random-access iterators support a superset of bidirectional iterator operations.
Traits class for iterators.
Struct holding two objects of arbitrary type.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.