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>
#include <vector>

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: 16.0.6 ✅
• GCC: 10.1.0 ✅
• Visual C++: 2019 Update 10 ✅

参照

• N4861 25 Algorithms library