typename _Size, typename _UniformRandomBitGenerator> _RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator ___out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator&& __g) { using __distrib_type = uniform_int_distribution<_Size>; using __param_type = typename __distrib_type::param_type; __distrib_type __d{}; _Size __sample_sz = 0; while (__first != __last && __sample_sz != __n) { ___out[__sample_sz++] = *__first; ++__first; } for (auto __pop_sz = __sample_sz; __first != __last; ++__first, (void) ++__pop_sz) { const auto __k = __d(__g, __param_type{0, __pop_sz}); if (__k < __n) ___out[__k] = *__first; } return ___out + __sample_sz; }

/// Selection sampling algorithm. template<typename _ForwardIterator, typename _OutputIterator, typename _Cat, typename _Size, typename _UniformRandomBitGenerator> _OutputIterator __sample(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag, _OutputIterator ___out, _Cat, _Size __n, _UniformRandomBitGenerator&& __g) { using __distrib_type = uniform_int_distribution<_Size>; using __param_type = typename __distrib_type::param_type; using _USize = make_unsigned_t<_Size>; using _Gen = remove_reference_t<_UniformRandomBitGenerator>; using __uc_type = common_type_t<typename _Gen::result_type, _USize>;

  __distrib_type __d{};
  _Size __unsampled_sz = std::distance(__first, __last);
  __n = std::min(__n, __unsampled_sz);

  // If possible, we use __gen_two_uniform_ints to efficiently produce
  // two random numbers using a single distribution invocation:

  const __uc_type __urngrange = __g.max() - __g.min();
  if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
    // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
// wrapping issues.
    {
  while (__n != 0 && __unsampled_sz >= 2)
    {
      const pair<_Size, _Size> __p =
	__gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);

      --__unsampled_sz;
      if (__p.first < __n)
	{
	  *___out++ = *__first;
	  --__n;
	}

      ++__first;

      if (__n == 0) break;

      --__unsampled_sz;
      if (__p.second < __n)
	{
	  *___out++ = *__first;
	  --__n;
	}

      ++__first;
    }
    }

  // The loop above is otherwise equivalent to this one-at-a-time version:

  for (; __n != 0; ++__first)
if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
  {
    *___out++ = *__first;
    --__n;
  }
  return ___out;
}

#if __cplusplus > 201402L #define __cpp_lib_sample 201603 /// Take a random sample from a population. template<typename _PopulationIterator, typename _SampleIterator, typename _Distance, typename _UniformRandomBitGenerator> _SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator ___out, _Distance __n, _UniformRandomBitGenerator&& __g) { using __pop_cat = typename std::iterator_traits<_PopulationIterator>::iterator_category; using __samp_cat = typename std::iterator_traits<_SampleIterator>::iterator_category;

  static_assert(
  __or_<is_convertible<__pop_cat, forward_iterator_tag>,
	is_convertible<__samp_cat, random_access_iterator_tag>>::value,
  "output range must use a RandomAccessIterator when input range"
  " does not meet the ForwardIterator requirements");

  static_assert(is_integral<_Distance>::value,
	    "sample size must be an integer type");

  typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
  return _GLIBCXX_STD_A::
__sample(__first, __last, __pop_cat{}, ___out, __samp_cat{}, __d,
	 std::forward<_UniformRandomBitGenerator>(__g));
}

#endif // C++17 #endif // C++14

_GLIBCXX_END_NAMESPACE_ALGO _GLIBCXX_END_NAMESPACE_VERSION } // namespace std

#endif /* _STL_ALGO_H */