来自O（1）中unordered_set的随机元素 [英] Random element from unordered_set in O(1)

问题描述

我见过有人提到可以在O（1）的时间从unordered_set中获取随机元素。我试图这样做：

I've seen people mention that a random element can be grabbed from an unordered_set in O(1) time. I attempted to do so with this:

std::unordered_set<TestObject*> test_set;

//fill with data

size_t index = rand() % test_set.size();
const TestObject* test = *(test_set.begin() + index);

但是，无序集合迭代器不支持整数+。可以给 begin 一个size_t参数，但这是存储区的索引，而不是元素的索引。随机选择一个存储桶，然后随机选择其中的一个元素将导致非常不均衡的随机分布。

However, unordered_set iterators don't support + with an integer. begin can be given a size_t param, but it is the index of a bucket rather than an element. Randomly picking a bucket then randomly picking an element within it would result in a very unbalanced random distribution.

正确进行O（1）随机访问的秘诀是什么？如果重要的话，这是在VC ++ 2010中。

What's the secret to proper O(1) random access? If it matters, this is in VC++ 2010.

推荐答案

我相信您误解了随机访问的含义，因为它

I believe you have misinterpreted the meaning of "random access", as it was used in those cases you're referring to.

随机访问与随机性无关。这意味着随机访问元素，即访问容器中任何位置的任何元素。直接访问元素，例如使用 std :: vector :: operator [] 是随机访问，但在容器上进行迭代则不是。

"Random access" doesn't have anything to do with randomness. It means to access an element "at random", i.e. access any element anywhere in the container. Accessing an element directly, such as with std::vector::operator[] is random access, but iterating over a container is not.

将其与RAM进行比较，RAM是随机存取存储器的缩写。

Compare this to RAM, which is short for "Random Access Memory".

这篇关于来自O（1）中unordered_set的随机元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！