std::sample

来自cppreference.com
< cpp‎ | algorithm
 
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法: std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
Partitioning operations
划分操作
排序操作
(C++11)
二分搜索操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

排列
数值运算
未初始化存储上的操作
(C++17)
(C++17)
(C++17)
C 库
 
在标头 <algorithm> 定义
template< class PopulationIterator, class SampleIterator,

          class Distance, class URBG >
SampleIterator sample( PopulationIterator first, PopulationIterator last,
                       SampleIterator out, Distance n,

                       URBG&& g);
(C++17 起)

从序列 [first; last) (不重复地)选择 n 个元素,使得每个样本拥有相等的出现概率,并写入这些被选择元素到输出迭代器 out 。用随机数生成器 g 生成随机数。

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

算法仅若 PopulationIterator 满足老式向前迭代器 (LegacyForwardIterator) 要求才稳定(保持被选择元素 的顺序)。

out[first; last) 中则行为未定义。

参数

first, last - 一对组成自其采样的范围(总体)的迭代器
out - 写入样本的输出迭代器
n - 要抽取的样本数
g - 用作随机源的随机数生成器
类型要求
-
PopulationIterator 必须符合老式输入迭代器 (LegacyInputIterator) 的要求。
-
SampleIterator 必须符合老式输出迭代器 (LegacyOutputIterator) 的要求。
-
PopulationIterator 不满足老式向前迭代器 (LegacyForwardIterator) ,则 SampleIterator 还必须满足老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求
-
PopulationIterator的 value_type 必须可写入到 out
-
Distance 必须是整数类型
-
std::remove_reference_t<URBG> 必须满足均匀随机位生成器 (UniformRandomBitGenerator) ,且其返回类型必须可转换为 Distance

返回值

在输出最后样本后返回 out 的副本,即采样范围的结尾。

复杂度

std::distance(first,last) 成线性

注解

此函数可以实现选择抽样或蓄水池抽样。

可能的实现

参阅 libstdc++libc++MSVC STL 中的实现。

示例

#include <iostream>
#include <random>
#include <string>
#include <iterator>
#include <algorithm>
 
int main()
{
    std::string in = "hgfedcba", out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                5, std::mt19937{std::random_device{}()});
    std::cout << "five random letters out of " << in << " : " << out << '\n';
}

可能的输出:

five random letters out of hgfedcba: gfcba

参阅

(C++17 前)(C++11)
随机重排范围中的元素
(函数模板)