Drew Dormann Drew Dormann -4 years ago 101
C++ Question

How to efficiently select a random element from a std::set

How can I efficiently select a random element from a

std::set
?

A
std::set::iterator
is not a random access iterator. So I can't directly index a randomly chosen element like I could for a
std::deque
or
std::vector


I could take the iterator returned from
std::set::begin()
and increment it
0
to
std::set::size()-1
times, but that seems to be doing a lot of unnecessary work. For an "index" close to the set's size, I would end up traversing the entire first half of the tree, even though it's already known the element won't be found there.

Is there a better approach?

In the name of efficiency, I am willing to define "random" as less random than whatever approach I might have used to choose a random index in a vector. Call it "reasonably random".

Edit...

Many insightful answers below.

The short version is that even though you can find a specific element in log(n) time, you can't find an arbitrary element in that time through the
std::set
interface.

Answer Source

Use boost::container::flat_set instead:

boost::container::flat_set<int> set;
// ...
auto it = set.begin() + rand() % set.size();

Insertions and deletions become O(N) though, I don't know if that's a problem. You still have O(log N) lookups, and the fact that the container is contiguous gives an overall improvement that often outweighs the loss of O(log N) insertions and deletions.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download