How to select a random element in std::set?

Question

How can I select a random element in an std::set?

I naively tried this:

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  return *(s.begin() + r); // compile error
}

But the operator+ is not allowed in this way.

Answer 1

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  std::set<int>::iterator it = s.begin();
  for (; r != 0; r--) it++;
  return *it;
}

would be one way of doing it, although not pretty;

Answer 2

You could use the std::advance method.

#include <set>
#include <algorithm>

int main() {
  using namespace std;
  // generate a set...
  set<int> s;
  for( int i = 0; i != 10; ++i ) s.insert(i);

  set<int>::const_iterator it(s.begin());

  // 'advance' the iterator 5 times
  advance(it,5);
}

Answer 3

C++17 std::sample

This will be a convenient, although not very efficient (O(n)) method:

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

int main() {
    std::set<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                3, std::mt19937{std::random_device{}()});
    for (auto i : out)
        std::cout << i << std::endl;
}

But I think that for efficiency you just need to copy to another type of structure: How to select a random element in std::set in less than O(n) time?

Answer 4

First Solution : O(log n) in time / O(1) in space (not uniform !)

A hypothesized in a comment above, it can be done in O(log(n)) (vs O(n) for std::advance) without a vector (using O(n) more space) by using the method I describe here.

Essentially, you :

• check if the set is empty (if it is, there is no hope)
• generate a random value
• if already there return it else insert it
• get one iterator it on it
• get the random element as *(it++) or *(set.begin()) if it at the end
• return it not before deleting the element you inserted

n.b : As pointed out by Aaron the element is not chosen uniformly at random. You need to build the random element with the same distribution than the elements in the set to approach a uniform polling.

Second Solution : O(1) in time / O(n) in space (uniform)

davidhigh already gave the solution with a vector but there is a problem because when you pop an element of your stack, you will have to perform a linear search in O(n) or you can rebuild your vector each time you want to retrieve a random element but that is O(n) too.

To avoid this problem and keep the insert/delete to O(log n), you can keep an std::unordered_set and use a similar method to the first solution to get a random element in O(1).

p.s : If your elements are large you can use an unordered set of pointers (with a modified hasher) to spare some memory.

Answer 5

If the random access is important and you can live with O(N) average effort for the insertion, then the workaround given in this paper might be convenient.

The main idea there is to use a sorted vector, and then for lookup the function std::lower_bound. This, the lookup takes O(log N) just as in a normal set. Further, (random) insertion takes O(N), as all following elements must be shifted just like in a normal vector (and possibly a reallocation is performed). Insertion at the back, however, is constant (except for the reallocation. You can avoid this by calling reserve() with a large enough storage).

Finally, the main point of the question: Random access is O(1). Just draw a random number i from a uniform distribution in [0, V.size()-1], and return the corresponding element V[i].

Here is the code basis out of the paper, which implements this sorted vector. Extend it as needed:

template <class T, class Compare = std::less<T> >
struct sorted_vector {
 using std::vector;
 using std::lower_bound;
 vector<T> V;
 Compare cmp; 
 typedef typename vector<T>::iterator iterator;
 typedef typename vector<T>::const_iterator const_iterator;
 iterator begin() { return V.begin(); }
 iterator end() { return V.end(); }
 const_iterator begin() const { return V.begin(); }
 const_iterator end() const { return V.end(); }

 //...if needed, implement more by yourself

 sorted_vector(const Compare& c = Compare()) : V(), cmp(c) {}
 template <class InputIterator>
 sorted_vector(InputIterator first, InputIterator last, Const Compare& c = Compare())
 : V(first, last), cmp(c)
 {
 std::sort(begin(), end(), cmp);
 }

 //...

 iterator insert(const T& t) {
     iterator i = lower_bound(begin(), end(), t, cmp);
     if (i == end() || cmp(t, *i))
        V.insert(i, t);
      return i;
 }
 const_iterator find(const T& t) const {
     const_iterator i = lower_bound(begin(), end(), t, cmp);
      return i == end() || cmp(t, *i) ? end() : i;
 }
};

For a more sophisticated implementation, you might also consider this page.

EDIT: or even better, use boost::container::flat_set, which implements the set using the idea above, i.e. as a sorted vector.