从数组中随机抽取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::vectorarr = {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 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::vectorarr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::vector 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，传::difference_type int可能触发隐式转换警告，建议显式转为decltype(arr.size()) - GCC 7+、Clang 5+、MSVC 2017+ 支持；低于此版本需自行实现或降级用
shuffle
手写蓄水池采样应对流式数据或内存受限场景
当数组太大无法全加载进内存（比如从文件逐行读）、或根本不知道总长度（数据流），就必须用经典蓄水池算法。它只需遍历一次、固定内存，且保证每个元素被选中概率严格为 k / n。
立即学习“C++免费学习笔记（深入）”；
核心逻辑：前 k 个元素直接入池；对第 i 个元素（i > k），以 k / i 概率决定是否替换池中某个随机位置。
std::vectorreservoir_sample(std::istream& is, size_t k) { std::vector res; int x; size_t i = 0; // 填充前 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_distributiondist; while (is >> x) { ++i; dist = std::uniform_int_distribution (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 判断——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包裹(0, n-1) std::mt19937，它会自动处理范围映射与偏差消除- 若必须兼容极老编译器（无 C++11），可用
arc4random_uniform(n)（BSD/macOS）或自己实现线性同余+拒绝采样实际项目中，优先选
std::sample；若需兼容旧标准或处理流式数据，才手写蓄水池；而任何涉及rand()或%取模的地方，基本都藏着概率偏差——这点最容易被忽略，也最难事后排查。
