C++如何实现一个支持O(1)查找和随机获取的容器-C++-PHP中文网

必须同时使用std::unordered_map和std::vector：前者实现o(1)查找，后者支持o(1)随机访问；通过哈希表记录值到下标的映射，数组存储值，并在删除时交换末尾元素以避免移动，从而保证两种操作均摊o(1)。

c++如何实现一个支持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 中间删除导致的大段内存搬移。

关键点：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

值必须可哈希、可比较（如 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{}()};</int></int></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)];
}

};