57 #ifndef _EXT_ALGORITHM
58 #define _EXT_ALGORITHM 1
60 #pragma GCC system_header
64 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
69 using std::input_iterator_tag;
70 using std::random_access_iterator_tag;
71 using std::iterator_traits;
76 template<typename _InputIterator, typename _Size, typename _OutputIterator>
77 pair<_InputIterator, _OutputIterator>
78 __copy_n(_InputIterator __first, _Size __count,
79 _OutputIterator __result,
82 for ( ; __count > 0; --__count)
88 return pair<_InputIterator, _OutputIterator>(__first, __result);
91 template<
typename _RAIterator,
typename _Size,
typename _OutputIterator>
92 inline pair<_RAIterator, _OutputIterator>
93 __copy_n(_RAIterator __first, _Size __count,
94 _OutputIterator __result,
95 random_access_iterator_tag)
97 _RAIterator __last = __first + __count;
98 return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
117 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
118 inline pair<_InputIterator, _OutputIterator>
119 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
122 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
123 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
124 typename iterator_traits<_InputIterator>::value_type>)
126 return __copy_n(__first, __count, __result,
130 template<
typename _InputIterator1,
typename _InputIterator2>
132 __lexicographical_compare_3way(_InputIterator1 __first1,
133 _InputIterator1 __last1,
134 _InputIterator2 __first2,
135 _InputIterator2 __last2)
137 while (__first1 != __last1 && __first2 != __last2)
139 if (*__first1 < *__first2)
141 if (*__first2 < *__first1)
146 if (__first2 == __last2)
147 return !(__first1 == __last1);
153 __lexicographical_compare_3way(
const unsigned char* __first1,
154 const unsigned char* __last1,
155 const unsigned char* __first2,
156 const unsigned char* __last2)
158 const ptrdiff_t __len1 = __last1 - __first1;
159 const ptrdiff_t __len2 = __last2 - __first2;
160 const int __result = __builtin_memcmp(__first1, __first2,
161 min(__len1, __len2));
162 return __result != 0 ? __result
163 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
167 __lexicographical_compare_3way(
const char* __first1,
const char* __last1,
168 const char* __first2,
const char* __last2)
170 #if CHAR_MAX == SCHAR_MAX
171 return __lexicographical_compare_3way((
const signed char*) __first1,
172 (
const signed char*) __last1,
173 (
const signed char*) __first2,
174 (
const signed char*) __last2);
176 return __lexicographical_compare_3way((
const unsigned char*) __first1,
177 (
const unsigned char*) __last1,
178 (
const unsigned char*) __first2,
179 (
const unsigned char*) __last2);
197 template<
typename _InputIterator1,
typename _InputIterator2>
200 _InputIterator1 __last1,
201 _InputIterator2 __first2,
202 _InputIterator2 __last2)
205 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
207 __glibcxx_function_requires(_LessThanComparableConcept<
208 typename iterator_traits<_InputIterator1>::value_type>)
209 __glibcxx_function_requires(_LessThanComparableConcept<
210 typename iterator_traits<_InputIterator2>::value_type>)
211 __glibcxx_requires_valid_range(__first1, __last1);
212 __glibcxx_requires_valid_range(__first2, __last2);
214 return __lexicographical_compare_3way(__first1, __last1, __first2,
220 template<
typename _InputIterator,
typename _Tp,
typename _Size>
222 count(_InputIterator __first, _InputIterator __last,
227 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
228 __glibcxx_function_requires(_EqualityComparableConcept<
229 typename iterator_traits<_InputIterator>::value_type >)
230 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
231 __glibcxx_requires_valid_range(__first, __last);
233 for ( ; __first != __last; ++__first)
234 if (*__first == __value)
238 template<typename _InputIterator, typename _Predicate, typename _Size>
240 count_if(_InputIterator __first, _InputIterator __last,
245 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
246 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
247 typename iterator_traits<_InputIterator>::value_type>)
248 __glibcxx_requires_valid_range(__first, __last);
250 for ( ; __first != __last; ++__first)
251 if (__pred(*__first))
262 template<typename _ForwardIterator, typename _OutputIterator,
266 _OutputIterator __out, const _Distance __n)
269 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
270 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
271 typename iterator_traits<_ForwardIterator>::value_type>)
272 __glibcxx_requires_valid_range(__first, __last);
275 _Distance __m =
min(__n, __remaining);
279 if ((std::rand() % __remaining) < __m)
296 template<
typename _ForwardIterator,
typename _OutputIterator,
297 typename _Distance,
typename _RandomNumberGenerator>
300 _OutputIterator __out,
const _Distance __n,
301 _RandomNumberGenerator& __rand)
304 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
305 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
306 typename iterator_traits<_ForwardIterator>::value_type>)
307 __glibcxx_function_requires(_UnaryFunctionConcept<
308 _RandomNumberGenerator, _Distance, _Distance>)
309 __glibcxx_requires_valid_range(__first, __last);
312 _Distance __m =
min(__n, __remaining);
316 if (__rand(__remaining) < __m)
328 template<
typename _InputIterator,
typename _RandomAccessIterator,
330 _RandomAccessIterator
331 __random_sample(_InputIterator __first, _InputIterator __last,
332 _RandomAccessIterator __out,
337 for ( ; __first != __last && __m < __n; ++__m, ++__first)
338 __out[__m] = *__first;
340 while (__first != __last)
343 _Distance __M = std::rand() % (__t);
345 __out[__M] = *__first;
351 template<
typename _InputIterator,
typename _RandomAccessIterator,
352 typename _RandomNumberGenerator,
typename _Distance>
353 _RandomAccessIterator
354 __random_sample(_InputIterator __first, _InputIterator __last,
355 _RandomAccessIterator __out,
356 _RandomNumberGenerator& __rand,
360 __glibcxx_function_requires(_UnaryFunctionConcept<
361 _RandomNumberGenerator, _Distance, _Distance>)
365 for ( ; __first != __last && __m < __n; ++__m, ++__first)
366 __out[__m] = *__first;
368 while (__first != __last)
371 _Distance __M = __rand(__t);
373 __out[__M] = *__first;
384 template<
typename _InputIterator,
typename _RandomAccessIterator>
385 inline _RandomAccessIterator
387 _RandomAccessIterator __out_first,
388 _RandomAccessIterator __out_last)
391 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
392 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
393 _RandomAccessIterator>)
394 __glibcxx_requires_valid_range(__first, __last);
395 __glibcxx_requires_valid_range(__out_first, __out_last);
397 return __random_sample(__first, __last,
398 __out_first, __out_last - __out_first);
406 template<
typename _InputIterator,
typename _RandomAccessIterator,
407 typename _RandomNumberGenerator>
408 inline _RandomAccessIterator
410 _RandomAccessIterator __out_first,
411 _RandomAccessIterator __out_last,
412 _RandomNumberGenerator& __rand)
415 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
416 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
417 _RandomAccessIterator>)
418 __glibcxx_requires_valid_range(__first, __last);
419 __glibcxx_requires_valid_range(__out_first, __out_last);
421 return __random_sample(__first, __last,
423 __out_last - __out_first);
431 template<
typename _RandomAccessIterator>
433 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
436 __glibcxx_function_requires(_RandomAccessIteratorConcept<
437 _RandomAccessIterator>)
438 __glibcxx_function_requires(_LessThanComparableConcept<
439 typename iterator_traits<_RandomAccessIterator>::value_type>)
440 __glibcxx_requires_valid_range(__first, __last);
442 return std::__is_heap(__first, __last - __first);
450 template<
typename _RandomAccessIterator,
typename _StrictWeakOrdering>
452 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
453 _StrictWeakOrdering __comp)
456 __glibcxx_function_requires(_RandomAccessIteratorConcept<
457 _RandomAccessIterator>)
458 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
459 typename iterator_traits<_RandomAccessIterator>::value_type,
460 typename iterator_traits<_RandomAccessIterator>::value_type>)
461 __glibcxx_requires_valid_range(__first, __last);
463 return std::__is_heap(__first, __comp, __last - __first);
475 template<
typename _ForwardIterator>
477 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
481 __glibcxx_function_requires(_LessThanComparableConcept<
482 typename iterator_traits<_ForwardIterator>::value_type>)
483 __glibcxx_requires_valid_range(__first, __last);
485 if (__first == __last)
488 _ForwardIterator __next = __first;
489 for (++__next; __next != __last; __first = __next, ++__next)
490 if (*__next < *__first)
500 template<
typename _ForwardIterator,
typename _StrictWeakOrdering>
502 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
503 _StrictWeakOrdering __comp)
506 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
507 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
508 typename iterator_traits<_ForwardIterator>::value_type,
509 typename iterator_traits<_ForwardIterator>::value_type>)
510 __glibcxx_requires_valid_range(__first, __last);
512 if (__first == __last)
515 _ForwardIterator __next = __first;
516 for (++__next; __next != __last; __first = __next, ++__next)
517 if (__comp(*__next, *__first))
522 _GLIBCXX_END_NAMESPACE