std::sample是C++17起标准库提供的无放回随机采样算法，基于Fisher–Yates变种，时间复杂度O(n)且不修改原容器，为首选方案；采样需保留原始下标时宜用std::vector<std::pair<size_t, T>>存储索引与值。
用 std::sample 做无放回随机采样最稳妥
标准库从 C++17 开始提供了 std::sample，它专为“从容器中随机抽取 k 个不重复元素”设计，底层使用 Fisher–Yates 变种，时间复杂度 O(n)，且不修改原数组。这是绝大多数场景的首选。
常见错误是手动写循环 + std::rand() 或反复调用 std::shuffle，既易出错又低效；还有人误用 std::random_shuffle（C++14 已弃用）或对整个数组打乱再截取——当 k 时纯属浪费。
- 必须传入合法的随机数引擎，比如
std::mt19937{std::random_device{}()}，不能用默认构造的std::mt19937{}（种子为 0，每次结果相同） - 输出目标必须有足够空间：若用
std::vector接收，要先reserve(k)或resize(k)，否则迭代器失效 -
std::sample不保证输出顺序与原数组一致，也不保证有序——如需升序，采样后单独std::sort
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> samples;
samples.reserve(3);
std::sample(arr.begin(), arr.end(),
std::back_inserter(samples),
3,
std::mt19937{std::random_device{}()});
// samples 现在包含 3 个不重复的随机元素
需要有放回采样？自己写 std::uniform_int_distribution 循环
标准库没有内置“有放回采样”，但实现极简单：用均匀分布随机生成 [0, n) 范围内的索引，重复 k 次即可。关键点不在逻辑，而在避免常见陷阱。
- 分布对象（
std::uniform_int_distribution<size_t>）应定义在循环外，否则频繁构造可能影响性能（尤其在热循环中） - 务必用
arr.size()作为上界，而不是硬编码数字，否则arr为空时arr.size()-1会变成极大正数（size_t下溢） - 如果采样量
k很大（比如百万级），考虑用std::vector::data()+ 指针算术替代operator[]，减少边界检查开销（仅在-O2且禁用调试检查时有效）
std::vector<int> arr = {10, 20, 30};
std::vector<int> samples;
samples.reserve(5);
std::mt19937 gen{std::random_device{}()};
std::uniform_int_distribution<size_t> dist(0, arr.size() - 1); // 注意：arr非空才安全
for (int i = 0; i < 5; ++i) {
samples.push_back(arr[dist(gen)]);
}
小数组或嵌入式环境？避免 <random> 的轻量替代方案
如果项目禁用 <random>（例如某些裸机或实时系统），或数组长度固定且很小（≤ 16），可以用 XORShift 或线性同余（LCG）手写简易 PRNG，配合模运算取索引。
立即学习“C++免费学习笔记（深入）”；
但注意：% 运算在 size 不是 2 的幂时会引入轻微偏差（bias），当 arr.size() 和 PRNG 周期不可公约时更明显。对精度要求不高的日志抽样、UI 动画等场景可接受；做统计推断则不行。
- 不要用
rand() % n：RAND_MAX通常为 32767，当n > 32767时直接崩，且低位周期短 - 若必须用 LCG，推荐系数
a=1664525, c=1013904223, m=2^32（Numerical Recipes 风格），比教科书a=1103515245更均衡 - 手写 PRNG 时，种子别用
time(nullptr)——秒级精度在快速重复调用时大概率重复
采样后还要保持原始下标？别只存值，改用 std::vector<std::pair<size_t, T>>
很多实际需求不是“取几个数”，而是“取几个样本，并知道它们原来在第几行/第几个传感器/哪个时间戳”。这时候只复制值会丢失上下文。
最直接的办法是先构造索引数组，采样索引，再映射回原值。但若原数组很大而 k 很小，构造完整索引数组（O(n) 空间）不划算。
- 更省内存的做法：用
std::vector<std::pair<size_t, int>>存{index, value}，采样时对这个 vector 操作——空间仍是O(k) - 如果后续要按原始位置排序，直接对 pair 的
first字段std::sort即可，无需额外映射表 - 切忌用
std::map或std::unordered_map存索引映射：哈希/红黑树开销远大于线性扫描k个 pair
真正容易被忽略的是：采样本身不耗时，但跨 cache line 访问原始数组（尤其大结构体）可能成为瓶颈。如果原始数据是分散的指针数组，采样后批量访问其指向内容前，考虑预取（__builtin_prefetch）或重排访问顺序。
