namespace std::ranges {
// (1)
template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Gen>
requires (forward_iterator<I> || random_access_iterator<O>) && indirectly_copyable<I, O> && uniform_random_bit_generator<remove_reference_t<Gen>>
O sample(I first, S last, O out, iter_difference_t<I> n, Gen&& g);
// (2)
template<input_range R, weakly_incrementable O, class Gen>
requires (forward_range<R> || random_access_iterator<O>) && indirectly_copyable<iterator_t<R>, O> && uniform_random_bit_generator<remove_reference_t<Gen>>
O sample(R&& r, O out, range_difference_t<R> n, Gen&& g);
}
概要
範囲から指定された個数の要素をランダムに抽出する。
- (1): イテレータペアで範囲を指定する
- (2): 範囲を直接指定する
事前条件
out
は範囲[first, last)
に含まれてはならない
効果
範囲[first, last)
を母集団 (population) とし、そこからmin(last - first, n)
個の要素を標本 (sample) として out
にコピーする (n
が入力範囲の要素数より大きい場合は、最大で入力範囲の要素数がコピーされる)。
戻り値
出力範囲の最後のイテレータが返る
計算量
範囲[first, last)
の要素数に対して線形時間
備考
このアルゴリズムの実装には、以下の2つのバージョンが使用される:
- 出力をランダムアクセスで行うバージョン : KnuthのAlgorithm R (Reservoir sampling)
- 出力を前から順番に行うバージョン : KnuthのAlgorithm S (Selection sampling)
これらのアルゴリズムは、イテレータカテゴリによって、コンパイル時に自動的に選択されることになる。
例
#include <iostream>
#include <string>
#include <iterator>
#include <random>
#include <algorithm>
int main()
{
// 乱数生成器を用意する
std::random_device seed_gen;
std::mt19937 engine {seed_gen()};
// 文字列中から3文字をランダム抽出する
{
const std::string input = "abcdef";
const int n = 3;
std::string result;
std::ranges::sample(input, std::back_inserter(result), n, engine);
std::cout << result << std::endl;
}
// 配列から3要素をランダム抽出する
{
const std::vector<int> input = {0, 1, 2, 3, 4, 5};
const int n = 3;
std::vector<int> result;
std::ranges::sample(input, std::back_inserter(result), n, engine);
for (int x : result) {
std::cout << x;
}
std::cout << std::endl;
}
}
出力例
bcd
235
バージョン
言語
- C++20
処理系
- Clang: ??
- GCC: 10.1.0
- ICC: ??
- Visual C++: 2019 Update 10