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 a random number of times in the range [`0`,`std::set::size()`), 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 internal tree structure, 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.