Generate a unique numeric identifier for each instance of a class

Question

I want to generate a unique ID for every instance of a given class.

• The ID is of type unsigned long
• When an instance is deleted, the ID is freed (can be reused)

Now, I've come up with the following implementation:

Class Foo 
{
public:

  static unsigned std::set<unsigned long> s_usedID;

  static unsigned long generateID() // Generate a valid ID
  {
    static unsigned long id = 0;

     while (Foo::isIDUsed(id)) // If all ID are taken, create an infinite loop!
        ++id;

     return id;
  }

  static void addID(unsigned long id) // Add a given ID to the set of used ID
  {
    s_usedID.insert(id);
  }

  static void removeID(unsigned long id) // Remove a given ID from the set of used ID
  {
    s_usedID.erase(id);
  }

  static bool isIDUsed(unsigned long id)
  {
    return s_usedID.count(id) == 1 ? true:false;
  }

  explicit Foo() : m_id(Foo::generateID())
  {
    Foo::addID(m_id); // ID is now taken
  }

  virtual ~Foo()
  {
    Foo::removeID(m_id); // Free the ID
  }

private:

  unsigned long m_id;

};

Now for me, this logically works.

• Is there a better way to implement this?
• Are there any optimizations that I could make?

Answer 1

A few remarks:

1. The biggest obvious issue is the violation of encapsulation. All methods which allow you to modify the id set are public which means that outside code can change it and break the inherent assumption that each instance will have a unique id.

   The only code which should be able to modify the id set are the constructor and destructor.

   If you now say "ah, that won't matter it's just my code and I know not to do this" - programming is a skill and like any skill you get better at it through practice. Which typically means writing code. Therefore you should take any opportunity to practicing writing good code since that helps to form good habits. There is no excuse for being sloppy.

2. This:

   return s_usedID.count(id) == 1 ? true:false
   

   can be written more succinctly as:

   return s_usedID.count(id) == 1;
   

3. The implementation is obviously not thread-safe. Just something to be aware of.

4. One way to improve it, is to just use a variable to store the current maximum id and return the next one higher if you need a new one. If an id gets freed up then you could just not worry about it. If you really want to re-use returned id's then store them in a returnedIds set. The basic logic then becomes:

   • If returnedIds has any elements pop first element from set and return it
   • Else new id becomes current_max_id + 1

Answer 2

If your unsigned long is large enough, and the rate of ID generation is low enough, you can skip the isIDUsed check entirely and just never reuse an ID. For example, if your unsigned long is 64-bit, you could generate a million IDs per second for almost 600 000 years before you run out:

$$\frac{2^{64}}{1000000*(365*24*60*60)} \approx 584942$$

Answer 3

Maybe you don't need to generate the ID. Would it be enough for you to have an ID? This would be unique:

public:
    unsigned long getID() const
    {
        return (unsigned long)this;
    }

Answer 4

I can envision situations in which sharing the memory address of an object would be an unacceptable security hole. I want to offer an alternate solution for such cases. This uses a simple static counter to increment the GUID.

class HasGuid {
private:
  static unsigned long currentId = 1;
  unsigned long guid_;
protected:
  HasGuid() : guid_(currentId++) {}
public:
  unsigned long Guid() { return guid_; }
};

Any class that needs a GUID can simply inherit from HasGuid. The GUID, itself, is safely hidden and can't be changed. And the GUID will be unique across all instances of all classes that inherit from HasGuid.

A further option may be to use Adamski's solution. But hash the address with a secret key before returning it.

private:
  const unsigned long secretKey_ = {some random string of digits};
public:
  unsigned long getId() {
    return (unsigned long)this ^ secretKey_;
  }

Note: I know I'm a sinner for placing my braces on the same line as the function/class name. It's a habit I picked up from JavaScript.

Edit: I recently learned in a software development class that GUIDs are usually just 16 byte random numbers. The odds of two random 16 byte numbers being identical is so fantastically small, that it is safe to assume they will never be identical across any instance of any class in any applications in use across the universe. In fact, to call the odds astronomical would be giving too much credit to astronomy (anecdote stolen from this video by 3Blue1Brown). Also, most operating systems have a built in GUID tyoe that you can generate at any time by calling the appropriate API function.

Answer 5

First look -

generateID() should also addID() automatically. This will make c-tor much more simple.

---

One note for this:

  static unsigned long generateID() // Generate a valid ID
  {
    static unsigned long id = 0;

     while (Foo::isIDUsed(id)) // If all ID are taken, create an infinite loop!
        ++id;

     return id;
  }

id variable is static. This means it it accessed using lock + semaphore or probably is atomic.

Why not move the id inside the class?

---

About this:

  static bool isIDUsed(unsigned long id)
  {
    return s_usedID.count(id) == 1 ? true:false;
  }

you do not need "? true : false", this is just fine:

  static bool isIDUsed(unsigned long id)
  {
    return s_usedID.count(id) == 1;
  }

I am not std::set expert, but I think if you need to find if value is in set you can use:

  static bool isIDUsed(unsigned long id)
  {
    return s_usedID.find(id) != s_usedID.end();
  }

---

Finally, if you have C++11, you can clean up things some more, including you might remove constructor and use default generated constructor.

---

And really final notes - why not move this ID thing a separate class, then you include it in "user" class via inheritance or via static member. Then the user class will not need to have user destructor at all.

---

If you have questions, I can give you examples.

Answer 6

As I think it is impossible to have 2 instances of a class to be created in the very same nanosecond, I guess that unique identifiers can be generated using the chrono library:

 std::chrono::high_resolution_clock m_clock;
 long unique_ID = std::chrono::duration_cast<std::chrono::nanoseconds>(m_clock.now().time_since_epoch()).count();

You can then cast to unsigned long. You may also consider adding a small sleep time.