std::sample() 算法

自 C++17 起

// (1)
template< class PopulationIterator, class SampleIterator,
          class Distance, class URBG >
SampleIterator sample( PopulationIterator first, PopulationIterator last,
                       SampleIterator out, Distance n,
                       URBG&& g );

从序列 [first; last) 中选择 n 个元素（不重复），使得每个可能的样本出现的概率相等，并将这些选定的元素写入输出迭代器 out。

使用随机数生成器 g 生成随机数。

如果 n 大于序列中的元素数量，则选择 last - first 个元素。

仅当 PopulationIterator 满足 LegacyForwardIterator 的要求时，该算法才是稳定的（保留选定元素的相对顺序）。

未定义行为

行为未定义

如果 out 在 [first; last) 中。

参数

first last	从中进行采样的元素范围（总体）。
out	写入样本的输出迭代器。
n	样本数量。
g	用作随机性来源的随机数生成器。

类型要求

PopulationIterator	LegacyInputIterator
SampleIterator	LegacyOutputIterator
SampleIterator	LegacyRandomAccessIterator 仅当 PopulationIterator 不满足 LegacyForwardIterator 时
Distance	必须是整数类型。

当 URBG_NoRef 定义为 std::remove_reference_t<URBG>

URBG_NoRef	UniformRandomBitGenerator
URBG_NoRef 的返回类型	可转换为 Distance

PopulationIterator::value_type 必须可写入到 out。

返回值

返回 out 在最后一个样本输出之后的副本，即样本范围的末尾。

复杂度

std::distance(first, last) 的线性时间复杂度；

异常

(无)

备注

此函数可能实现选择采样或水塘采样。

Main.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <string>

int main()
{
    std::string in {"ABCDEFGHIJK"}, out;
    std::sample(in.begin(), in.end(), std::back_inserter(out), 4,
                std::mt19937 {std::random_device{}()});
    std::cout << "Four random letters out of " << in << " : " << out << '\n';
}

可能的输出

Four random letters out of ABCDEFGHIJK: ACID