# C++: roulette wheel selection using map or boost

Well, the task is neither new nor unsolved. I was particularly interested in the fancy possibility to use a map container for binary search. Of course, boost offers better (read: faster and shorter) ways. Both of them can be implemented in a few lines.

```#include <map>
#include <boost/random.hpp>

#define CHOICES 10000
#define SPINS 10000000
using namespace std;

struct wheelcomp {
bool operator()(const pair<double, double> &a, const pair<double, double> &b) {
if (b.first == -1) {
if (b.second >= a.first && b.second < a.second)
return false;
return (b.second >= a.second);
}
if (a.first == -1) {
if (a.second >= b.first && a.second < b.second)
return false;
return (a.second >= b.second);
}
return a.first < b.first;
}
};

class wheel {
double sum;
map<pair<double, double>, int, wheelcomp> ranges;

public:
wheel(double * p, int l) {
sum = 0;
for (int i = 0; i < l; i++) {
ranges[pair<double, double>(sum, p[i]+sum)] = i;
sum += p[i];
}
}

int spin(double random) {
return ranges.find(pair<double, double>(-1, random*sum))->second;
}
};

int main(void) {
// init random numbers
boost::mt19937 mt;
boost::uniform_real<> uniform(0,1);
boost::variate_generator<boost::mt19937&,boost::uniform_real<> > rng(mt, uniform);

// build_probabilities
vector<double> p(CHOICES, 0);
for (int i = 0; i < CHOICES; i++)
p[i] = rng();

// perform selections
int k;
wheel w(&p, CHOICES);
for (int i = 0; i < SPINS; i++)
k = w.spin(rng());

// the boost way
boost::random::discrete_distribution<> dist(p);
for (int i = 0; i < SPINS; i++)
k= dist(mt);

return k;
}```

Without any further optimization, the code has been compiled with gcc. The boost version takes two seconds for ten million selections, whereas the std::map version needs 6.1 seconds for the same amount of selections. 