This question with an added constraint.
I'm willing to allow not-uniform selection as long as it's not to lop sided.
Given that "sets are typically implemented as binary search trees" and I expect they will contain some kind of depth or size information for balancing, I would expect you could do some sort of weighted random walk of the tree. However I don't know of any remotely portable way to do that.
Edit: The constraint is NOT for the amortized time.
I don't see how to do it with just
std::set
, so you probably need a different data structure. Like Victor Sorokin said, you can combine a set with a vector. Instead ofset<T>
, usemap<T, size_t>
, plusvector< map<T, size_t>::iterator >
. The value for each key is an index into the vector, and each element of the vector points back to the map element. The vector elements have no particular order. When you add an element, put it at the end of the vector. When you remove an element and it's not the last one in the vector, move the last element to the deleted element's position.You may be able to make a randomly-ordered copy of the map by using this constructor
..and passing a comparator that compares hashes of the keys (or some other deterministic spreading function.) Then take the "smallest" keys according to this new map.
You could construct the map once and amortize the cost across several requests for a "random" element.
For
std::unordered_set<int> s
:1) take random
R
inmin(s)..max(s)
2) if
R
ins
: return R3)
For ordered set (std::set) probability would depend on distance between elements. unordered_set is randomized by hash.
I hope this can help.
PS converting
std::set<V>
intostd::set<std::pair<int, V>>
(where first element in pair is a hash of second) makes this method suitable for any hashable V.Introduce array with size equal to set. Make array elements hold addresses of every element in set. Generate random integer
R
bounded by array/set size, pick address in array's element indexed byR
and dereference it to obtain set's element.IF you know the distribution of the elements in the set, you can randomly select key (with that same distribution) and use
std::set::lower_bound
. That's a lot of if though.