17370845950

C++中生成不重复随机数应优先用std::shuffle打乱vector，而非while+set查重；因后者在高密度选取时碰撞严重、效率低且分布不均，而shuffle基于Fisher-Yates算法，O(n)稳定高效、无偏差、无风险。

直接说结论：C++ 中生成不重复随机数，核心是「打乱序列」而非「反复校验」——用 std::shuffle 配合 std::vector 初始化最可靠、最高效。

为什么不能用 while 循环 + set 查重？

这是新手最常写的写法：不断 rand() 或 std::mt19937 生成数，插入 std::set，直到 size 达到目标。问题很实在：

• 当范围接近所需数量时（比如从 100 个数里选 95 个），碰撞概率飙升，可能卡住几十次甚至上百次迭代
• std::set 插入和查找带 O(log n) 开销，整体退化成 O(k·log k)（k 是最终数量），还不可预测
• 如果误用 rand() % N 且 N 不整除 RAND_MAX+1，底层就已存在偏差，再叠加重试，分布更不均匀

标准做法：先建序列，再打乱（Fisher–Yates）

std::shuffle 底层就是 Fisher–Yates 洗牌算法，时间复杂度稳定 O(n)，无重复、无偏差、无循环风险。关键三步：

• 用 std::vector 构造完整候选集（如 0 到 N-1）
• 用 std::random_device 和 std::mt19937 初始化真随机种子（别用 time(0)）
• 调用 std::shuffle，然后取前 k 个元素即可

std::vector nums;
for (int i = 0; i < 100; ++i) nums.push_back(i); // 0~99 共 100 个数

std::random_device rd;
std
::mt19937 g(rd()); // 注意：g 是 generator 实例，不是类型

std::shuffle(nums.begin(), nums.end(), g);
std::vector result(nums.begin(), nums.begin() + 10); // 取前 10 个不重复随机数

如果范围极大（比如 1e9 中选 1000 个），不能建完整 vector 怎么办？

内存不允许预分配全部候选值时，改用「拒绝采样 + 集合去重」是合理妥协，但必须控制策略：

• 只在 k （例如 N=1e9, k=1e3）时启用，此时碰撞概率极低
• 用 std::unordered_set 替代 std::set，平均 O(1) 插入
• 务必用 std::uniform_int_distribution 保证均匀性，禁用 % 运算
• 加个简单保护：循环上限设为 2*k，防止意外卡死（理论上期望迭代次数 ≈ k，2k 足够覆盖 99.9% 场景）

std::unordered_set seen;
std::random_device rd;
std::mt19937_64 g(rd());
std::uniform_int_distribution dist(0, 1000000000LL);

std::vector result;
while (result.size() < 1000 && seen.size() < 2000) {
    long long x = dist(g);
    if (seen.insert(x).second) { // insert 返回 pair，second 为 true 表示新插入
        result.push_back(x);
    }
}

容易被忽略的坑：generator 复用与线程安全

常见错误是把 std::mt19937 声明为全局或静态变量后多处调用 operator() —— 它不是 const，内部状态会变，但多个线程并发调用会 UB。

• 每个线程应持有独立的 generator 实例（推荐 thread_local）
• 不要把同一个 generator 实例传给多个 std::shuffle 调用后还指望结果可复现；若需可重现，保存并复用 generator 的 seed() 值
• C++17 起，std::shuffle 第三个参数要求是 UniformRandomBitGenerator，std::mt19937 符合，但旧式 rand 不符合，编译不过

真正难的不是写出能跑的代码，而是想清楚「我要的是均匀随机抽样，不是伪随机生成器的裸输出」——打乱、拒绝采样、分段构造，本质都是为这个目标服务。选哪种，取决于你手上的 N 和 k 到底差几个数量级。