std::ranges::sample() algorithm

od C++20

Simplified

// (1)
O sample( I first, S last, O out, std::iter_difference_t<I> n, Gen&& gen );

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

The type of arguments are generic and have the following constraints:

• I - std::input_iterator
• S - std::sentinel_for<I>
• O - std::weakly_incrementable
• R - std::ranges::input_range
• Gen - (none)

Additionally, each overload has the following constraints:

• (1):

  (forward_iterator<I> || random_access_iterator<O>)
  && indirectly_copyable<I, O>
  && uniform_random_bit_generator<remove_reference_t<Gen>>
• (2):

  (ranges::forward_range<R> || random_access_iterator<O>)
  && indirectly_copyable<ranges::iterator_t<R>, O>
  && uniform_random_bit_generator<remove_reference_t<Gen>>

(The std:: namespace was omitted for readability)

Detailed

// (1)
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> &&
            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 );

// (2)
template<
  ranges::input_range R,
  std::weakly_incrementable O,
  class Gen
>
  requires (ranges::forward_range<R> || std::random_access_iterator<O>) &&
            std::indirectly_copyable<ranges::iterator_t<R>, O> &&
            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 probability 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.

  Undefined Behaviour

  The behavior is undefined if out is in [first; last).

• (2) Same as (1), but uses r as the range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first last	The range of elements from which to make the sampling (the population).
r	The range of elements from which to make the sampling (the population).
out	The output iterator to which the samples are written.
n	The number of samples to take.
gen	The random number generator used as the source of randomness.

Return value

With M defined as min(n, last - first).

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

Complexity

Linear in (last - first).

Exceptions

(none)

Possible implementation

sample(1) and sample(2)

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_reference_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" output
            for (; first != last && sample_size != n; ++first)
                out[sample_size++] = *first;
            // overwrite some of the copied elements with randomly selected 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_iterator<O>) &&
              std::indirectly_copyable<ranges::iterator_t<R>, O> &&
              std::uniform_random_bit_generator<std::remove_reference_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 {};

Examples

Main.cpp

#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 }