CodeGuru : Thinking in C++

Nontype template arguments

Here is a random number generator class that always produces a unique number and overloads operator( ) to produce a familiar function-call syntax:

//: C19:Urand.h
// Unique random number generator
#ifndef URAND_H
#define URAND_H
#include <cstdlib>
#include <ctime>

template<int upperBound>
class Urand {
  int used[upperBound];
  bool recycle;
public:
  Urand(bool recycle = false);
  int operator()(); // The "generator" function
};

template<int upperBound>
Urand<upperBound>::Urand(bool recyc) 
  : recycle(recyc) {
  memset(used, 0, upperBound * sizeof(int));
  srand(time(0)); // Seed random number generator
}

template<int upperBound>
int Urand<upperBound>::operator()() {
  if(!memchr(used, 0, upperBound)) {
    if(recycle)
      memset(used,0,sizeof(used) * sizeof(int));
    else
      return -1; // No more spaces left
  }
  int newval;
  while(used[newval = rand() % upperBound])
    ; // Until unique value is found
  used[newval]++; // Set flag
  return newval;
}

#endif // URAND_H ///:~

The uniqueness of Urand is produced by keeping a map of all the numbers possible in the random space (the upper bound is set with the template argument) and marking each one off as it’s used. The optional second constructor argument allows you to reuse the numbers once they’re all used up. Notice that this implementation is optimized for speed by allocating the entire map, regardless of how many numbers you’re going to need. If you want to optimize for size, you can change the underlying implementation so it allocates storage for the map dynamically and puts the random numbers themselves in the map rather than flags. Notice that this change in implementation will not affect any client code.