home | help 
std::ranges::sample(3)	       C++ Standard Libary	  std::ranges::sample(3)

NAME
     std::ranges::sample - std::ranges::sample

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::input_iterator I, std::sentinel_for<I> S,

		  std::weakly_incrementable O, class Gen >
	requires (std::forward_iterator<I> || std::random_access_iterator<O>) &&
		  std::indirectly_copyable<I,		     O> 	      &&
     (1) (since
										     C++20)
	std::uniform_random_bit_generator<std::remove_reference_t<Gen>>

	O sample( I first, S last, O out, std::iter_difference_t<I> n, Gen&& gen
	);
	template< ranges::input_range R, std::weakly_incrementable O, class Gen
	>

	requires (ranges::forward_range<R> || std::random_access_iterator<O>) &&
     (since
		  std::indirectly_copyable<ranges::iterator_t<R>,     O>      &&
     (2) C++20)

	std::uniform_random_bit_generator<std::remove_reference_t<Gen>>

	O sample( R&& r, O out, ranges::range_difference_t<R> n, Gen&& gen );

	1)  Selects  M = min(n, last - first) elements from the sequence [first,
     last)
	(without replacement) such that each possible sample has equal probabil-
     ity of
	appearance, and writes those selected elements into the range  beginning
     at out.
	The  algorithm	is  stable (preserves the relative order of the selected
     elements) only
	if I models std::forward_iterator.
	The behavior is undefined if out is in [first, last).
	2) Same as (1), but uses r as the source range, as if using  ranges::be-
     gin(r) as
	first, and ranges::end(r) as last.

	The  function-like  entities  described on this page are niebloids, that
     is:

	  * Explicit template argument lists cannot be	specified  when  calling
     any of them.
	  * None of them are visible to argument-dependent lookup.
	  *  When any of them are found by normal unqualified lookup as the name
     to the left
	    of the function-call operator, argument-dependent lookup  is  inhib-
     ited.

	In  practice,  they may be implemented as function objects, or with spe-
     cial compiler
	extensions.

Parameters
	first1, last1 - the range from which to make the sampling  (the  popula-
     tion)
	r	       -  the range from which to make the sampling (the popula-
     tion)
	out	      - the output iterator where the samples are written
	n	      - number of samples to take
	gen	      - the random number generator used as the source	of  ran-
     domness

Return value
	An  iterator  equal  to out + M, that is the end of the resulting sample
     range.

Complexity
	Linear: dh(last - first).

Notes
	This function may implement selection sampling or reservoir sampling.

Possible implementation
	struct sample_fn
	{
	    template<std::input_iterator I, std::sentinel_for<I> S,
		     std::weakly_incrementable O, class Gen>
	    requires (std::forward_iterator<I> or
		      std::random_access_iterator<O>) &&
		      std::indirectly_copyable<I, O> &&
		      std::uniform_random_bit_generator<std::remove_refer-
     ence_t<Gen>>
	    O operator()(I first, S last, O  out,  std::iter_difference_t<I>  n,
     Gen&& gen) const
	    {
		using diff_t = std::iter_difference_t<I>;
		using distrib_t = std::uniform_int_distribution<diff_t>;
		using param_t = typename distrib_t::param_type;
		distrib_t D{};

		if constexpr (std::forward_iterator<I>)
		{
		    // this branch preserves "stability" of the sample elements
		    auto rest{ranges::distance(first, last)};
		    for (n = ranges::min(n, rest); n != 0; ++first)
			if (D(gen, param_t(0, --rest)) < n)
			{
			    *out++ = *first;
			    --n;
			}
		    return out;
		}
		else
		{
		    // O is a random_access_iterator
		    diff_t sample_size{};
		    //	copy [first, first + M) elements to "random access" out-
     put
		    for (; first != last && sample_size != n; ++first)
			out[sample_size++] = *first;
		    // overwrite some of the copied elements with  randomly  se-
     lected ones
		    for  (auto	pop_size{sample_size};	first  != last; ++first,
     ++pop_size)
		    {
			const auto i{D(gen, param_t{0, pop_size})};
			if (i < n)
			    out[i] = *first;
		    }
		    return out + sample_size;
		}
	    }

	    template<ranges::input_range R, std::weakly_incrementable  O,  class
     Gen>
	    requires   (ranges::forward_range<R>   or  std::random_access_itera-
     tor<O>) &&
		      std::indirectly_copyable<ranges::iterator_t<R>, O> &&
		      std::uniform_random_bit_generator<std::remove_refer-
     ence_t<Gen>>
	    O operator()(R&& r, O out,	ranges::range_difference_t<R>  n,  Gen&&
     gen) const
	    {
		return (*this)(ranges::begin(r), ranges::end(r), std::move(out),
     n,
			       std::forward<Gen>(gen));
	    }
	};

	inline constexpr sample_fn sample {};

Example
     // Run this code

      #include <algorithm>
      #include <iomanip>
      #include <iostream>
      #include <iterator>
      #include <random>
      #include <vector>

      void print(auto const& rem, auto const& v)
      {
	  std::cout << rem << " = [" << std::size(v) << "] { ";
	  for (auto const& e : v)
	      std::cout << e << ' ';
	  std::cout << "}\n";
      }

      int main()
      {
	  const auto in = {1, 2, 3, 4, 5, 6};
	  print("in", in);

	  std::vector<int> out;
	  const int max = in.size() + 2;
	  auto gen = std::mt19937{std::random_device{}()};

	  for (int n{}; n != max; ++n)
	  {
	      out.clear();
	      std::ranges::sample(in, std::back_inserter(out), n, gen);
	      std::cout << "n = " << n;
	      print(", out", out);
	  }
      }

Possible output:
      in = [6] { 1 2 3 4 5 6 }
      n = 0, out = [0] { }
      n = 1, out = [1] { 5 }
      n = 2, out = [2] { 4 5 }
      n = 3, out = [3] { 2 3 5 }
      n = 4, out = [4] { 2 4 5 6 }
      n = 5, out = [5] { 1 2 3 5 6 }
      n = 6, out = [6] { 1 2 3 4 5 6 }
      n = 7, out = [6] { 1 2 3 4 5 6 }

See also
	ranges::shuffle randomly re-orders elements in a range
	(C++20) 	(niebloid)
	sample		selects N random elements from a sequence
	(C++17) 	(function template)

http://cppreference.com 	   2024.06.10		  std::ranges::sample(3)
home | help