There is a straightforward algorithm for picking an item at random, where items have individual weights:
1) calculate the sum of all the weights
2) pick a random number that is 0 or greater and is less than the sum of the weights
3) go through the items one at a time, subtracting their weight from your random number, until you get the item where the random number is less than that item’s weight
Pseudo-code illustrating this:
int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
if(rnd < choice_weight[i])
return i;
rnd -= choice_weight[i];
}
assert(!"should never get here");
This should be straightforward to adapt to your boost containers and such.
If your weights are rarely changed but you often pick one at random, and as long as your container is storing pointers to the objects or is more than a few dozen items long (basically, you have to profile to know if this helps or hinders), then there is an optimisation:
By storing the cumulative weight sum in each item you can use a binary search to pick the item corresponding to the pick weight.
If you do not know the number of items in the list, then there’s a very neat algorithm called reservoir sampling that can be adapted to be weighted.