namespace std::ranges {
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); // (1) C++20
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); // (2) C++20
}
概要
範囲から指定された個数の要素をランダムに抽出する。
- (1): イテレータ範囲を指定する
- (2): Rangeを直接指定する
事前条件
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;
}
}
xxxxxxxxxx#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 ✅