• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(UTC):
    が更新

    履歴 編集

    function template
    <algorithm>

    std::sample

    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)から指定された個数の要素をランダムに抽出する。

    テンプレートパラメータ制約

    • PopulationIteratorInputIterator の要件を満たしていること
    • SampleIteratorOutputIterator の要件を満たしていること
    • PopulationIteratorForwardIterator の要件を満たさない限り、SampleIteratorRandomAccessIteratorの要件を満たさなければならない
    • PopulationIteratorの値型はoutに対して書き込めなければならない
    • Distanceは整数型であること
    • UniformRandomBitGenerator は uniform random bit generator の要件を満たさなければならず、その戻り値の型はDistance型へ変換可能でなければならない

    事前条件

    効果

    イテレータ範囲[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

    処理系

    参照