Idiomatic "guaranteed unique" identifiers in C ++

Question

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

• Assuming there is an identifier that is not currently reserved, reserve_id (void) returns this identifier to me.
• In a continuous sequence of calls to reserve_id (), no identifier will be returned twice
• There is a recycle (id_type) function that returns the identifier of an available pool.

For example, I saw Boost :: Uuid , but a) I do not see any documentation that assures the guaranteed uniqueness of two UUIDs and b) At the moment, I am limited to an earlier version of Boost (1.40). I could click to update if it was especially good for this task.

Answer 1

I think that you have already solved this problem for most practical purposes by typing Boost :: Uuid, except for your requirement to dispose of already generated identifiers.

From the documentation related to in question:

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

If you are struggling to recycle and reuse existing identifiers, I suppose you could maintain the UUID assembly over time, generating new ones only when you need it, and find that the pool is empty. But I can’t imagine a scenario where it would be preferable to generate a new UUID.

EDIT . You commented that you need a guarantee of uniqueness. In fact, you will never get it when programmatically creating a unique identifier. In practice, you are going to store the generated identifier in a data type that has a finite size, and therefore the possible set of identifiers that you can generate is also finite. IMHO, the best you can achieve is to simulate uniqueness within the tolerance threshold.

You can do it with

• Using a technique that makes it possible to get a duplicate UUID very remotely (Boost :: UUID will do this);

• A wrapper for generating a highly vulnerable UUID may be unique in some other logic that looks for a newly created UUID in the list of already created UUIDs to eliminate this tiny possibility that the new one is a duplicate. Obviously, the practicality of this decreases as you approach the large number of UUIDs on your list. How much do you expect generation?

• If you want a really huge number of unique identifiers, more than suitable for the native type, you can implement a type that manages memory and performs the necessary mathematical calculations, and just create sequential identifiers, or you could use something like the GNU Bignum Library , to do it for you.

Answer 2

How long do identifiers live? Do you really need to recycle them, or can you live with them, being unique forever? How much do you need to create everything at once? How many bits can you devote to id?

Here is a simple recipe: take the MAC address of your local network (which is a globally unique problematic hardware), mix the time / date (up to a millisecond resolution) and incrementing integer counter (incremented once for each generated identifier) ​​d has an identifier unique within your time / date range if you do not generate MAXINT of them in one millisecond on this computer. Now this is NOT a random look, and it is EASY for an attacker to predict, so do not use it for security, and this, of course, is not the most efficient use of bits there, but it is globally unique.

Answer 3

What uniqueness do you need?
Just unique to a program’s lifetime or unique to multiple launches / cross-processes?

If this is the first, you can just new bytes of memory, and then use the address of that memory as your identifier. This will be guaranteed to be unique until you delete memory, after which it can be recycled.

This can be easily wrapped in a class as follows:

 #include <stdint.h> class UID { public: typedef uint64_t id_type; static const id_type reserve_id() { uint8_t* idBlock = new uint8_t; *idBlock = validId; return (id_type)idBlock; } static void recycle(id_type id) { uint8_t* idBlock = (uint8_t*)id; if (*idBlock == validId) { *idBlock = 0; delete idBlock; } } private: static const uint8_t validId = 0x1D; }; 

This may be a little unusual, but it meets your requirements if you only need the uniqueness of each process :)

Answer 4

Yes, that’s easy.

• reserve_id operator new(0) function.
• Null bytes are allocated here, but with a unique address.
• recycle function, of course, operator delete

Answer 5

The problem does not seem to be related to C ++, it is rather a fundamental problem. How many identifiers are expected at any time? If you expect to have multiple valid identifiers at any given time, just put them in a container, such as a linked list, vector, or set, depending on your performance requirements and the relative recycle / backup frequency. A sorted linked list is probably the best option, as in O (n) both a reboot and a backup action will be performed. The vector has O (n), O (n log n), and the set has O (n log n), O (n), respectively (maybe wrong, I thought very quickly).

 void recycle(ID) { container.remove(ID); // abort if unsuccessiful (= invalid ID) } ID reserve() { static ID last = 0; while(container.find(last)) { last++; } return last; }