c++ - Random element from unordered_set in O(1)

Question

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);

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.

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

Answer 1

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

"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.

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