Idiomatic "guaranteed-unique" identifiers in C++

Question

Is there an idiomatic C++ way to reserve and recycle identifiers that are guaranteed to be unique? My requirements are:

1. Assuming there exists an ID not currently reserved, reserve_id(void) returns me that ID.
2. In an unbroken sequence of reserve_id() calls, no single identifier will be returned twice
3. There exists a function recycle(id_type) that returns an identifier to the available pool.

I have, for instance, seen Boost::Uuid, but a) I see no documentation which asserts the guaranteed uniqueness of two UUIDs and b) I'm constrained to an earlier version of Boost (1.40), for the time being. I could push to upgrade, if this were particularly perfect for the task.

Answer 1

I think you've already solved this problem for most practical purposes by finding Boost::Uuid, with the exception of your requirement to recycle identifiers already generated.

From the documentation you linked to in the question:

When UUIDs are generated by one of the defined mechanisms, they are either guaranteed to be unique, different from all other generated UUIDs (that is, it has never been generated before and it will never be generated again), or it is extremely likely to be unique (depending on the mechanism).

If you're hell-bent on recycling and re-using existing identifiers, I suppose you could maintain build up a pool of UUIDs over time, generating new ones only when you need one and find that the pool is empty. But I can't imagine a scenario where that would be preferable to generating a new UUID.

EDIT: You've commented that you need a guarantee as to uniqueness. Realistically, you're never going to get one when programatically generating a unique identifier. In practice, you're going to store the generated ID in a data type which has finite size, and so the possible set of IDs you can generate is finite too. IMHO, the best you can achieve then is to simulate uniqueness within a tolerance threshold.

You could do this by

• Using a technique that makes the chances of getting a duplicate UUID very remote (this is what Boost::UUID will do);

• Wrapping the generation of the highly-probably-to-be-unique UUID in some other logic that looks up the newly-generated UUID in a list of already-generated UUIDs to eliminate that tiny chance that the new one is a duplicate. Obviously, the practicality of doing this becomes decreases as you approach very large quantities of UUIDs in your list. How many do you anticipate generating?

• If you want truly huge quantities of unique IDs, bigger than would fit in a native type, you could implement a type that manages the memory and does the necessary maths, and just produce sequential Ids, or you could perhaps use something like the GNU Bignum Library to do it for you.

Answer 2

How long do the IDs live? Do you REALLY need to recycle them, or can you live with them being unique forever? How many do you need to generate all at once? How many bits can you devote to the id?

Here's a simple recipe: Take your ethernet card's mac address (which is globally unique baring hardware issues), mix in the time/date (to millisecond resolution) and an incrementing integer counter (increments once per id generated) and you'd have an id that's unique within the span of your time/date range, as long as you don't generate MAXINT of them in a single millisecond on this machine. Now it's NOT random looking, and it's EASY for an attacker to predict, so don't use it for security, and it's sure not the most efficient use of bits out there, but it IS globally unique.