std::discrete_distribution 是加权随机选择最稳妥的标准库方案，内部用别名法实现 O(1) 平均查询，自动归一化、支持浮点权重，构造后复用即可；手写前缀和+二分仅适用于需动态更新或无 STL 的特殊场景。
用 std::discrete_distribution 做加权随机选择最稳妥
标准库已经提供了现成、高效、线程安全的实现，不需要手写轮盘赌或前缀和二分。只要权重是正数（支持浮点），std::discrete_distribution 就能直接用。
它内部维护累积概率分布，每次 operator() 调用是 O(1) 平均时间复杂度（底层通常用别名法 alias method 或查表优化），比手动二分查找更优。
- 权重可以是整数或浮点数，自动归一化，不强制要求和为 1
- 构造时传入迭代器范围（如
vector、数组），不能传单个值 - 生成的是
size_t类型索引，不是原始元素，需自行映射 - 若权重全为 0，会抛出
std::invalid_argument
std::vector weights = {1.0, 3.0, 2.0}; // 比例 1:3:2 std::vector items = {"apple", "banana", "cherry"}; std::discrete_distribution dist(weights.begin(), weights.end()); std::mt19937 gen(std::random_device{}()); size_t idx = dist(gen); // 得到 0, 1 或 2 std::string selected = items[idx];
手写前缀和 + 二分查找适合调试或特殊场景
当需要完全控制逻辑（比如动态更新权重、复用已有数组、或嵌入无 STL 环境）时，可手动构建前缀和并用 std::lower_bound 查找。
注意：前缀和必须严格递增，且搜索目标要落在 [0, total) 范围内；用 std::lower_bound 找第一个 ≥ 随机值的位置，等价于轮盘赌选中区间。
立即学习“C++免费学习笔记（深入）”；
- 随机值应取
[0, total)，不是[0, total]，否则可能越界 - 权重含负数或 NaN 会导致前缀和异常，必须提前过滤
- 如果频繁修改单个权重，每次重建前缀和是 O(n)，不如换用平衡树或 Fenwick 树
std::vector weights = {1, 3, 2}; std::vector prefix = {weights[0]}; for (size_t i = 1; i < weights.size(); ++i) { prefix.push_back(prefix.back() + weights[i]); } int total = prefix.back(); std::uniform_int_distribution uni(0, total - 1); int r = uni(gen); auto it = std::lower_bound(prefix.begin(), prefix.end(), r + 1); int idx = std::distance(prefix.begin(), it); // idx ∈ [0, weights.size())
常见错误：用 rand() % n 加权根本不起作用
很多人误以为“对每个元素按权重重复添加进数组，再用 rand() % size”是加权，但这是典型误区——它只在权重为整数且较小时可行，一旦权重是小数、极大、或需高频调用，就会爆炸式消耗内存或精度丢失。
-
rand()本身周期短、低位随机性差，c++11 后应弃用 - 重复填充法空间复杂度 O(Σ|wᵢ|)，权重为 1e6 就分配百万项，不可控
- 无法处理浮点权重，也不能做归一化缩放
- 即使强行转整数（如 ×1000），也会因截断引入系统性偏差
权重归一化与数值稳定性要点
std::discrete_distribution 内部会把输入权重求和后做除法归一，所以极端值会影响精度。若权重跨度超过 1e15（如同时存在 1 和 1e16），小权重可能被舍入为 0。
- 建议预处理：平移+缩放使最大权重为 1.0，或用
long double构造分布（部分标准库支持） - 避免使用
double表示超大整数权重（如 2^53 以上），会丢失精度 - 调试时可用
dist.probabilities()检查归一化后的实际概率数组
真正难的不是选中逻辑，而是权重来源是否可信、更新是否原子、以及多线程下 discrete_distribution 对象是否共享。后者尤其容易被忽略：它是无状态的，但构造开销不小，应复用而非每次重造。