std::ranges::sample() algorithm
- od C++20
- Simplified
- Detailed
// (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)
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 atout
.The algorithm is stable (preserves the relative order of the selected elements) only if
I
modelsstd::forward_iterator
.Undefined BehaviourThe behavior is undefined
if out is in [first
;last
). -
(2) Same as (1), but uses
r
as the range, as if usingranges::begin(r)
asfirst
andranges::end(r)
aslast
.
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
#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);
}
}
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 }
Hover to see the original license.