std::sample是C++17引入的无放回随机抽样标准算法，时间复杂度接近O(n)、单次遍历、内存开销固定；需传入已seed的随机引擎、目标容器预先分配空间，且不检查抽样数超源大小；对流式或超大数组应改用蓄水池算法；有放回抽样应直接随机索引访问。
用 std::sample 做无放回随机抽样最省心
标准库从 C++17 开始提供了 std::sample，专为这类需求设计，比手写 shuffle + subvector 更高效、更安全。它在时间复杂度上接近 O(n)，且只遍历一次源容器，内存开销固定。
常见错误是误用 std::random_shuffle（已弃用）或对整个大数组调用 std::shuffle——哪怕只要 10 个样本，也得打乱上百万元素，纯属浪费。
-
std::sample需要传入一个合法的随机数引擎，比如std::mt19937{std::random_device{}()}，不能传std::default_random_engine这类未显式 seed 的引擎，否则每次运行结果相同 - 目标容器（如
std::vector）必须预留足够空间（reserve(k)或构造时指定大小），否则反复push_back可能触发多次重分配 - 源迭代器范围必须有效，且
std::sample不检查k > distance(first, last)；若抽样数量超过源大小，它只会复制全部元素，不会报错也不会抛异常
std::vector<int> data = {1,2,3,4,5,6,7,8,9,10};
std::vector<int> samples;
samples.reserve(3);
std::sample(data.begin(), data.end(),
samples.begin(), 3,
std::mt19937{std::random_device{}()});
// samples 现在包含 3 个不重复的随机元素
抽样数量远小于数组长度时，用蓄水池算法（Reservoir Sampling）更省内存
当数据来自流式输入（比如文件逐行读取、网络包逐个到达）、或数组大到无法一次性加载进内存时，std::sample 就不适用了——它要求源迭代器支持随机访问，且需遍历完整范围。
这时用经典蓄水池算法：只需 O(k) 空间和单次遍历，就能等概率抽取 k 个样本。C++ 实现简单，核心逻辑就三行。
立即学习“C++免费学习笔记（深入）”；
- 第 i 个元素（i 从 0 开始）被选中的概率是
min(k, i+1)分之一；一旦入选，就随机替换蓄水池中某个已有元素 - 务必用
std::uniform_int_distribution<int>(0, i)而不是(0, k-1)，否则破坏等概率性 - 如果源数据本身是
std::vector但长度极大（比如上亿），而 k 很小（比如 100），蓄水池比std::sample更快——避免了迭代器算术和 cache 不友好访问
std::vector<int> reservoir(k);
for (int i = 0; i < n; ++i) {
int x = get_next_element(); // 从流读一个
if (i < k) reservoir[i] = x;
else {
std::uniform_int_distribution<int> dist(0, i);
int j = dist(gen);
if (j < k) reservoir[j] = x;
}
}
需要有放回抽样？别用 std::sample，直接索引随机访问
std::sample 是无放回的，它内部保证不重复。如果有放回（即允许同一元素被多次选中），最高效方式就是生成 k 个 [0, n) 范围内的随机索引，然后查表。
这比任何“模拟放回”的变通方法（比如把原数组复制 k 次再 shuffle）快得多，且内存零额外开销。
- 索引生成必须用
std::uniform_int_distribution<size_t>(0, n-1)，注意上限是n-1，不是n，否则越界 - 若原数组是
std::vector，直接用data[index]访问；若是原始指针（int*），确保指针非空且n > 0 - 不要用
rand() % n——低比特周期短，分布不均，尤其当n接近RAND_MAX时偏差明显
性能陷阱：引擎初始化和分布对象复用
很多人把随机数引擎和分布对象放在循环里创建，导致每次抽样都重新 seed、重建内部状态，不仅慢，还可能因 std::random_device 耗尽熵源而降级为确定性行为。
- 引擎（如
std::mt19937）应定义在作用域外或作为类成员，只初始化一次 - 分布对象（如
std::uniform_int_distribution）虽轻量，但复用比每次构造略快；更重要的是，避免在 tight loop 中隐式转换（比如传int给期望size_t的分布） - 在多线程环境下，每个线程必须持有自己的引擎实例；共享引擎需加锁，会成为瓶颈
真正影响效率的往往不是算法本身，而是随机数设施的误用。抽样逻辑写对只是第一步，引擎生命周期和复用方式决定了它能不能跑得起来。
