Doesn't that line nullify all advantages of this approach ?
How?
Seriously, before you read further, how does needing an operation to confirm an empty slot nullify the advantages of a correctly randomized guess queue?
Well, the best way I can think of implementing that function is binary search but that would require a sorting after each turn.
You are apparently too close to the problem.
Before reading further, consider the problem outside of this context. You have an set of slots that can be randomly accessed in constant time and need to know if a specifically chosen slot is free for use? Do you still perceive that as a binary search?
Determining if a slot has been used is a constant operation in that context.
Let's replace the implied function with a simple bit of code and add the slot array. (I adapted this "in place" from the code posted by iMalc; beware of bad formatting, weird offers, and typos.)
Code:
// Set up
unsigned int b[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
std::vector<int> y = {1,2,3,4,5,6,7,8,9};
std::random_shuffle(y.begin(),y.end());
int g(0);
int c = 0;
// reinit
std::random_shuffle(y.begin(),y.end());
g = 0;
for(int i(1); i < 10; ++i)
{
b[i] = 0;
}
// Execute this code to do the picking each time:
do {
c = y[g++];
} while(b[c] != 0);
b[c] = 1;
Soma