蓄水池采样适用于无法预知数据长度且仅能单次遍历的场景，如流式数据、文件逐行读取或前向迭代器；其空间复杂度O(k)、时间复杂度O(n)，std::sample在非随机访问迭代器下自动退化为该策略。
蓄水池采样适合什么场景
当你无法预知数组长度（比如数据来自流、文件逐行读取、或迭代器只允许单次遍历），又需要等概率随机抽取 k 个元素时，std::random_shuffle 或先转 std::vector 再用 std::sample 就不适用了。蓄水池采样（Reservoir Sampling）正是为此设计：空间复杂度 O(k)，时间复杂度 O(n)，且只需遍历一次。
标准库已有实现但要注意版本
C++17 引入了 std::sample，它底层可使用蓄水池逻辑（标准未强制实现方式，但主流 STL 实现如 libstdc++ 和 libc++ 对输入迭代器类型会自动退化为蓄水池策略）。关键看你的迭代器是否满足 RandomAccessIterator：
- 如果是
std::vector::iterator（支持随机访问），std::sample可能用更高效的洗牌+截断，不是严格蓄水池 - 如果是
std::istream_iterator、std::forward_list::iterator等仅前向迭代器，std::sample必须用蓄水池逻辑，且行为符合算法要求
示例（安全用于任意流）：
#include <algorithm>
#include <vector>
#include <iterator>
#include <random>
std::vector<int> reservoir(k);
std::sample(istream_iter, std::istream_iterator<int>{},
reservoir.begin(), reservoir.end(),
std::mt19937{std::random_device{}()});
手写蓄水池要避开的三个坑
自己实现时常见错误集中在边界、随机数范围和状态更新上：
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 第
i个元素（从 0 开始计数）被选中的概率必须是k / (i + 1)，不是k / i（i=0 会除零） - 生成随机索引时，要用
std::uniform_int_distribution<int>(0, i)，而非(0, i-1)—— 否则第i个元素永远没机会替换自己 - 替换操作必须在判定“是否入选”后立即完成，不能延迟到循环外；否则当
i < k时，应无条件填满蓄水池，而不是跳过
正确片段（k=1 简化版）：
int sample = 0;
int count = 0;
for (int x : data_stream) {
if (++count == 1) sample = x;
else {
std::uniform_int_distribution<int> dist(1, count);
if (dist(gen) == count) sample = x;
}
}
多线程或高频调用时的性能注意点
蓄水池本身计算轻量，但随机数生成器（std::mt19937）若全局共享且频繁调用，可能成为瓶颈。尤其在高并发场景下：
- 避免在循环内重复构造
std::mt19937或分布对象（构造开销大） - 不要跨线程共享同一个
std::mt19937实例（非线程安全） - 对小
k（如 k=1），可考虑用std::bernoulli_distribution替代整数分布，减少模运算
实际中，一个线程一个 std::mt19937 + 复用分布对象，比每次 new 一个快 3–5 倍。
蓄水池真正难的不是代码几行，而是确认你的数据源是否真的“不可回溯”——如果只是普通数组，直接用 std::sample 配合 std::shuffle 更稳；只有当迭代器只能前进、内存受限、或数据规模远超可用 RAM 时，才需要认真对待它的边界条件和随机源配置。
