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<int> 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<int> result(nums.begin(), nums.begin() + 10); // 取前 10 个不重复随机数
如果范围极大（比如 1e9 中选 1000 个），不能建完整 vector 怎么办？
内存不允许预分配全部候选值时，改用「拒绝采样 + 集合去重」是合理妥协，但必须控制策略：
立即学习“C++免费学习笔记（深入）”；
- 只在
k << N（例如N=1e9, k=1e3）时启用，此时碰撞概率极低 - 用
std::unordered_set替代std::set，平均O(1)插入 - 务必用
std::uniform_int_distribution保证均匀性，禁用%运算 - 加个简单保护：循环上限设为
2*k，防止意外卡死（理论上期望迭代次数 ≈ k，2k 足够覆盖 99.9% 场景）
std::unordered_set<long long> seen;
std::random_device rd;
std::mt19937_64 g(rd());
std::uniform_int_distribution<long long> dist(0, 1000000000LL);
std::vector<long long> result;
while (result.size() < 1000 && seen.size() < 2000) {
long long x = dist(g);
if (seen.insert(x).second) { // insert 返回 pair<iter, bool>，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 到底差几个数量级。
