std::ranges::sample
std::ranges
<algorithm>
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>>
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>>
[
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.I
models std::forward_iterator .[
first,
last)
.The function-like entities described on this page are algorithm function objects (informally known as 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 inhibited.
Contents
[edit] Parameters
[edit] Return value
An iterator equal to out + M, that is the end of the resulting sample range.
[edit] Complexity
Linear: O(last - first).
[edit] Notes
This function may implement selection sampling or reservoir sampling.
[edit] 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_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 {};
[edit] Example
#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 }