Search code examples
c++uuididioms

Idiomatic "guaranteed-unique" identifiers in C++

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.

Solution

  • 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.