Przejdź do głównej zawartości

std::ranges::sample() algorithm

// (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)

  • (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 }
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::sample() algorithm

// (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)

  • (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 }
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.