| 27 | #include <__undef_macros> |
| 28 | |
| 29 | _LIBCPP_BEGIN_NAMESPACE_STD |
| 30 | |
| 31 | template <class _AlgPolicy, |
| 32 | class _PopulationIterator, |
| 33 | class _PopulationSentinel, |
| 34 | class _SampleIterator, |
| 35 | class _Distance, |
| 36 | class _UniformRandomNumberGenerator> |
| 37 | _LIBCPP_HIDE_FROM_ABI _SampleIterator __sample( |
| 38 | _PopulationIterator __first, |
| 39 | _PopulationSentinel __last, |
| 40 | _SampleIterator __output_iter, |
| 41 | _Distance __n, |
| 42 | _UniformRandomNumberGenerator& __g, |
| 43 | input_iterator_tag) { |
| 44 | _Distance __k = 0; |
| 45 | for (; __first != __last && __k < __n; ++__first, (void)++__k) |
| 46 | __output_iter[__k] = *__first; |
| 47 | _Distance __sz = __k; |
| 48 | for (; __first != __last; ++__first, (void)++__k) { |
| 49 | _Distance __r = uniform_int_distribution<_Distance>(0, __k)(__g); |
| 50 | if (__r < __sz) |
| 51 | __output_iter[__r] = *__first; |
| 52 | } |
| 53 | return __output_iter + std::min(__n, __k); |
| 54 | } |
| 55 | |
| 56 | template <class _AlgPolicy, |
| 57 | class _PopulationIterator, |
| 58 | class _PopulationSentinel, |
| 59 | class _SampleIterator, |
| 60 | class _Distance, |
| 61 | class _UniformRandomNumberGenerator> |
| 62 | _LIBCPP_HIDE_FROM_ABI _SampleIterator __sample( |
| 63 | _PopulationIterator __first, |
| 64 | _PopulationSentinel __last, |
| 65 | _SampleIterator __output_iter, |
| 66 | _Distance __n, |
| 67 | _UniformRandomNumberGenerator& __g, |
| 68 | forward_iterator_tag) { |
| 69 | _Distance __unsampled_sz = _IterOps<_AlgPolicy>::distance(__first, __last); |
| 70 | for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first) { |
| 71 | _Distance __r = uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); |
| 72 | if (__r < __n) { |
| 73 | *__output_iter++ = *__first; |
| 74 | --__n; |
| 75 | } |
| 76 | } |
| 77 | return __output_iter; |
| 78 | } |
| 79 | |
| 80 | template <class _AlgPolicy, |
| 81 | class _PopulationIterator, |