namespace std {
template <class PopulationIterator,
class SampleIterator,
class Distance,
class UniformRandomBitGenerator>
SampleIterator
sample(PopulationIterator first,
PopulationIterator last,
SampleIterator out, Distance n,
UniformRandomBitGenerator&& g);
}
概要
イテレータ範囲[first, last)
から指定された個数の要素をランダムに抽出する。
テンプレートパラメータ制約
PopulationIterator
はInputIterator
の要件を満たしていることSampleIterator
はOutputIterator
の要件を満たしていることPopulationIterator
がForwardIterator
の要件を満たさない限り、SampleIterator
はRandomAccessIterator
の要件を満たさなければならないPopulationIterator
の値型はout
に対して書き込めなければならないDistance
は整数型であることUniformRandomBitGenerator
は uniform random bit generator の要件を満たさなければならず、その戻り値の型はDistance
型へ変換可能でなければならない
事前条件
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::sample(input.begin(),
input.end(),
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::sample(input.begin(),
input.end(),
std::back_inserter(result),
n,
engine);
for (int x : result) {
std::cout << x;
}
std::cout << std::endl;
}
}
出力例
bcd
235
バージョン
言語
- C++17
処理系
- Clang: 4.0 ✅
- GCC: 7.2 ✅
- Visual C++: ??