It's clever, but it doesn't sound random to me.
Suppose your initial list is 0 to 100 and the first random
number picks 5. So 5 is one of your random numbers, but in the
list 5 gets replaced with the next higher number, i.e. 6. So
now you have two sixes in the list. And if either of those
sixes gets hit you'll have three sevens, etc.
I think you'll will get more bunching than you would with a
straightforward random pick.
If the OP really gave a crap about randomness he wouldn't be
worried about getting duplicates. ;-)
Anyhow, I took a stab at it, using a rotating translation table.
And, err, rand_expensive needs to be *really* expensive before
adopting this solution.
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <ctime>
using namespace std;
int rand_expensive()
{
/* Spend millions of resources somehow doing the following: */
return rand()%101;
}
struct counter
{
int c_;
counter(int c): c_(c) { }
int operator()()
{
return c_++;
}
};
int main()
{
srand(time(0));
vector<int> nums;
vector<int> range(101);
generate_n(range.begin(), 101, counter(0));
for (int i = 0; i < 10; ++i) {
int r = rand_expensive();
while (find(nums.begin(), nums.end(), range[r]) != nums.end())
{
rotate(range.begin(), range.begin()+1, range.end());
}
nums.push_back(range[r]);
}
copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
