必须同时使用std::unordered_map和std::vector：前者实现O(1)查找，后者支持O(1)随机访问；通过哈希表记录值到下标的映射，数组存储值，并在删除时交换末尾元素以避免移动，从而保证两种操作均摊O(1)。
为什么不能只用 std::unordered_map 或 std::vector
单独用 std::unordered_map 可以 O(1) 查找，但无法 O(1) 随机取元素（因为没有连续索引）；单独用 std::vector 能靠 rand() % size() O(1) 随机访问，但查找某个值得遍历 —— 平均 O(n)。要同时满足两个条件，必须把「值到位置的映射」和「位置到值的存储」耦合起来维护。
核心思路：哈希表 + 动态数组 + 尾部删除
用 std::vector 存所有值（保证随机访问下标合法），用 std::unordered_map 记录每个值当前在 vector 中的下标。插入时直接 push_back；删除时，把待删元素和 vector 末尾元素交换，再 pop_back，并更新哈希表里两个元素的下标。这样避免了 vector 中间删除导致的大段内存搬移。
关键点：
- 值必须可哈希、可比较（如
int、string），且容器内无重复值（否则 map 的 key 冲突） - 删除操作中，若待删元素就是末尾元素，不用交换，直接 pop 并 erase map
- 随机获取用
vec[rand() % vec.size()]，但注意rand()已废弃，生产环境建议用std::random_device+std::mt19937
一个最小可行实现（支持 int）
#include <vector>
#include <unordered_map>
#include <random>
<p>class RandomizedSet {
std::vector<int> nums;
std::unordered_map<int, int> val2idx; // value → index
std::mt19937 gen{std::random_device{}()};</p><p>public:
bool insert(int val) {
if (val2idx.count(val)) return false;
val2idx[val] = nums.size();
nums.push_back(val);
return true;
}</p><pre class='brush:php;toolbar:false;'>bool remove(int val) {
if (!val2idx.count(val)) return false;
int idx = val2idx[val];
// 把最后一个元素挪到 idx 位置
int last = nums.back();
nums[idx] = last;
val2idx[last] = idx; // 更新最后一个元素的新下标
nums.pop_back();
val2idx.erase(val);
return true;
}
int getRandom() {
std::uniform_int_distribution<> dist(0, nums.size() - 1);
return nums[dist(gen)];
}};
立即学习“C++免费学习笔记（深入）”；
容易踩的坑
常见错误现象：remove 后 getRandom 崩溃或返回旧值、重复插入后 insert 返回 true 却没生效、多线程下数据不一致。
- 删除前没检查
nums.empty()，nums.back()会 UB - 交换后忘了更新
val2idx[last]，下次查last会得到已失效的下标 - 用
rand() % n时，若n不是 2 的幂，会产生轻微偏差（对一般业务影响小，但算法题可能卡） - 没加锁就多线程调用 —— 这个结构天然非线程安全，
vector::push_back和unordered_map::insert都不是原子操作
真正难的不是写出来，而是删掉一个元素后，确保 vector 下标、map 映射、随机分布三者始终严格同步 —— 错一步，后续所有操作都不可信。
