蓄水池算法适合流式数据抽样，因为它只需单次遍历、空间复杂度O(k)、时间复杂度O(n)，且每个元素被选概率严格为k/n；无需预知数据总量，不依赖随机访问，适配单向迭代器如istream_iterator。
蓄水池算法为什么适合流式数据抽样
当你面对的是无法一次性加载到内存的超大数组（比如从磁盘逐块读取、网络流、或长度未知的迭代器），std::random_shuffle 或先打乱再取前 k 个的方式就失效了——它们要求完整访问所有元素。蓄水池算法（Reservoir Sampling）正是为这种场景设计的：只需遍历一次，空间复杂度固定为 O(k)，时间复杂度 O(n)，且每个元素被选中的概率严格为 k/n。
它不依赖数组总长度预先可知，也不需要额外存储整个数据集，特别适合 C++ 中处理 std::istream_iterator、文件行流、传感器采样序列等真实流式场景。
标准蓄水池算法的 C++ 实现要点
核心逻辑分两步：前 k 个元素直接入池；从第 k+1 个开始，对每个元素 i（索引从 0 开始，即第 i+1 个），以概率 k/(i+1) 决定是否替换池中某个随机位置。
- 必须用
std::mt19937配合std::uniform_int_distribution，避免rand()的低质量与线程不安全 - 替换时，生成
[0, k)范围内的随机索引，不是[0, i]—— 否则会破坏均匀性 - 若输入迭代器是单向的（如
std::istream_iterator），无法回退，必须边读边决策，不能事后修正 - 示例片段（抽取
k=3个）：
std::vector<int> reservoir(k);
std::mt19937 gen{std::random_device{}()};
std::uniform_int_distribution<int> dist;
// 前 k 个直接填入
for (int i = 0; i < k && it != end; ++i, ++it) {
reservoir[i] = *it;
}
// 后续每个元素按概率 k/(i+1) 替换
int i = k;
while (it != end) {
dist = std::uniform_int_distribution<int>(0, i); // 注意：范围是 [0, i]，对应第 i+1 个元素
if (dist(gen) < k) { // 等价于 rand() % (i+1) < k
reservoir[dist(gen) % k] = *it; // 这里要重新生成 [0,k) 索引
}
++i; ++it;
}
常见错误：用错随机范围导致偏差
最容易踩的坑是混淆“当前元素序号”和“索引下标”。比如把第 i 个元素（从 0 开始计数）的概率写成 k/i，或替换索引生成范围设为 [0, i)，都会让靠后的元素被选中概率偏高。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
正确做法始终基于“这是第几个元素”来算概率：第 1 个元素（i=0）必须入选；第 m 个元素（m 从 1 开始计）被选中概率是 k/m；替换位置必须在 [0, k) 内均匀选取。
- 错误：
std::uniform_int_distribution<int>(0, i-1)（当i是从 0 开始的下标）→ 实际对应第i+1个元素，但分布上限写成i-1少了 1 - 错误：
rand() % k直接替换 → 没有保证第m个元素整体入选概率为k/m - 正确：对第
m个元素（m = i+1），用dist(gen) 判断是否入选，再用独立的 <code>[0,k)分布选位置
当 k=1 时可以简化，但别误用 std::sample
C++17 引入了 std::sample，但它要求输入迭代器是 RandomAccessIterator，且必须知道总长度（通过 std::distance），本质是先随机选 k 个下标再取值——不适用于流式或长度未知场景。
k=1 时蓄水池退化为“只记录当前最优候选”，代码更轻量：
T result;
int count = 0;
for (const auto& x : range) {
++count;
if (std::bernoulli_distribution(1.0/count)(gen)) {
result = x;
}
}
注意：std::bernoulli_distribution 比手动比较更清晰，但底层仍是 uniform_real_distribution，别为了省一行代码改用浮点误差敏感的除法。
真正难的不是写对算法，而是确认你的数据源是否真的“不可预知长度”——如果只是普通 std::vector，直接用 std::shuffle + vector::begin() 截取更高效；只有当迭代器是 input_iterator、或内存受限时，蓄水池才不可替代。
