从数组中随机抽取k个不重复元素，首选std::sample（C++17），时间复杂度O(n)、空间O(k)；若不可用则用std::shuffle配合mt19937引擎打乱后截取；流式数据需手写蓄水池算法。
用 std::shuffle 实现等概率随机采样
如果目标是「从数组中随机抽取 k 个不重复元素」，最直接可靠的方式不是手写洗牌再截取，而是先用 std::shuffle 打乱整个容器，再取前 k 个——前提是 k 远小于数组长度时性能可接受。
关键点在于：必须用高质量随机数引擎（如 std::mt19937），不能用 std::random_device() 直接当引擎传给 shuffle（它不是引擎类型）。
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::random_device rd;
std::mt19937 g(rd()); // 必须包装成引擎
std::shuffle(arr.begin(), arr.end(), g);
std::vector<int> sample(arr.begin(), arr.begin() + 3); // 取前3个-
std::shuffle是 Fisher–Yates 原地实现，时间复杂度O(n)，但若只采k个却 shuffle 全量，空间局部性好但有冗余计算 - 若原数组不能修改，需先
copy再 shuffle，多一次O(n)拷贝 - Windows MSVC 下注意：旧版
std::shuffle在 debug 模式可能触发迭代器调试开销，Release 下无影响
用 std::sample 做高效不放回采样（C++17 起）
当 k 明显小于 n（比如百万级数组里抽 10 个），std::sample 是更优解——它内部使用 reservoir sampling（蓄水池算法），时间复杂度 O(n)、空间复杂度仅 O(k)，且不修改原容器。
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> sample(3);
std::random_device rd;
std::mt19937 g(rd());
std::sample(arr.begin(), arr.end(), sample.begin(), sample.size(), g);- 第三个参数必须是指向足够空间的输出迭代器，
sample容器需预先分配大小（不能是空vector） - 第四个参数是采样数量，类型为
std::iterator_traits<it>::difference_type</it>，传int可能触发隐式转换警告，建议显式转为decltype(arr.size()) - GCC 7+、Clang 5+、MSVC 2017+ 支持；低于此版本需自行实现或降级用
shuffle
手写蓄水池采样应对流式数据或内存受限场景
当数组太大无法全加载进内存（比如从文件逐行读）、或根本不知道总长度（数据流），就必须用经典蓄水池算法。它只需遍历一次、固定内存，且保证每个元素被选中概率严格为 k / n。
立即学习“C++免费学习笔记（深入）”；
让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限
核心逻辑：前 k 个元素直接入池；对第 i 个元素（i > k），以 k / i 概率决定是否替换池中某个随机位置。
std::vector<int> reservoir_sample(std::istream& is, size_t k) {
std::vector<int> res;
int x;
size_t i = 0;
<pre class='brush:php;toolbar:false;'>// 填充前 k 个
while (i < k && is >> x) {
res.push_back(x);
++i;
}
if (i < k) return res; // 不足 k 个，返回全部
// 蓄水池更新
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<size_t> dist;
while (is >> x) {
++i;
dist = std::uniform_int_distribution<size_t>(0, i - 1);
size_t j = dist(gen);
if (j < k) res[j] = x;
}
return res;}
- 注意
std::uniform_int_distribution构造必须在循环外，否则每次重建分布对象会严重拖慢性能 - 若输入是随机访问容器（如
vector），该算法反而比std::sample慢，因多了分支和分布调用开销 - 浮点误差风险：不要用
(double)rand() / RAND_MAX 判断——<code>rand()周期短、分布差，且 double 除法引入精度偏差
常见错误：用 rand() % n 实现索引随机导致偏差
这是 C++ 新手最常踩的坑：用 rand() % n 生成 [0, n) 随机索引，结果分布不均。因为 RAND_MAX 很少是 n 的整数倍，余数区间被“截断”，小索引出现概率略高。
例如 RAND_MAX == 32767，n == 10000，则索引 0~2767 出现概率为 4/32768，而 2768~9999 仅为 3/32768。
- 永远不要用
rand()，尤其在需要统计严谨性的采样中 - 用
std::uniform_int_distribution<int>(0, n-1)</int>包裹std::mt19937，它会自动处理范围映射与偏差消除 - 若必须兼容极老编译器（无 C++11），可用
arc4random_uniform(n)（BSD/macOS）或自己实现线性同余+拒绝采样
实际项目中，优先选 std::sample；若需兼容旧标准或处理流式数据，才手写蓄水池；而任何涉及 rand() 或 % 取模的地方，基本都藏着概率偏差——这点最容易被忽略，也最难事后排查。
