c++ - 如何以 O(1) 的时间从 C++ 哈希表中随机检索元素

Question

有没有一种方法可以在 O(1) 平均时间内从 C++ unordered_set 中随机检索元素？而不是做

std::unordered_set<int> s;
// initialize s
auto start = s.begin();
for (int i = 0; i < rand()%s.size()-1; ++i, ++start) {}
int randomNumber = *start;

更新:

我需要争取这个职位，所以我添加了我需要上述功能的原因。

我正在尝试实现一个迷宫生成器。不知何故，我需要一个支持的数据结构:

1. 插入/删除时间复杂度为 O(1)
2. 在 O(1) 时间内从数据结构中随机检索元素

std::vector 具有随机访问，但插入/删除成本较高

std::list 没有随机访问

std::set 支持 O(logN) 随机访问和 O(logN) 插入/删除，这很棒，但我的初始化是一个排序序列，很容易打破它的平衡.

所以我认为哈希表是最好的选择，但是随机检索一个元素将是不平凡的。

感谢您的宝贵时间。

Answer 1

您无法从 unordered_set 中选择随机元素在 O(1) 时间内。迭代器是 ForwardIterator s，不是RandomAccessIterator s。您将不得不使用不同的容器。要么 boost::container::flat_set<int> 或者自己编写一个类似 vector 的内容内部:

template <typename T>
class set_with_random_access
{
    std::vector<T*> vec;
    std::unordered_set<T> set;
};

为此，我们提供了使它们保持一致的功能，例如插入:

void insert(const T& value) {
    auto pr = set.insert(value);
    if (pr.second) {
        vec.push_back(&*pr.first);
    }
}

和随机性:

template <typename GEN>
T& random(GEN& gen) {
    std::uniform_int_distribution<size_t> dist(0, vec.size() - 1);
    return *vec[dist(gen)];
}

坦率地说，这需要做很多工作，所以可能会使用 boost 。