Идиоматические «гарантированные уникальные» идентификаторы в C++

Question

Есть ли идиоматический способ C++ для резервирования и повторного использования идентификаторов, которые гарантированно будут уникальными? Мои требования:

1. Предполагая, что существует идентификатор в настоящее время не защищены, reserve_id (Недействительными) возвращает мне этот идентификатор.
2. В непрерывной последовательности reserve_id() вызывает, ни один идентификатор не будет возвращен в два раза
3. Там существует функция рецикла (id_type), который возвращает идентификатор доступного пула.

Я, например, видел Boost::Uuid, но) я не вижу никакой документации, которая утверждает, гарантированную уникальность двух UUID, и б) я с ограничениями на более раннюю версию Boost, (1.40), в течение времени, бытия. Я мог бы нажать, чтобы обновить, если это было особенно хорошо для этой задачи.

Answer 1

Я думаю, что вы уже решили эту проблему для большинства практических целей, набрав Boost :: Uuid, за исключением вашего требования перегенерировать уже созданные идентификаторы.

От documentation you linked to в вопросе:

Когда UUID, порождены одной из определенных механизмов , они либо гарантированно быть уникальным, отличается от всех других генерируемых UUID, (что есть, он никогда не генерировался до , и он больше никогда не будет сгенерирован), или он, скорее всего, будет уникальным (в зависимости от механизма).

Если вы одержимы переработки и повторного использования существующих идентификаторов, я полагаю, вы могли бы поддерживать создать пул UUID, со временем, создавая новые только тогда, когда он вам нужен, и найти то, что бассейн пустой. Но я не могу представить сценарий, где было бы предпочтительнее генерировать новый UUID.

EDIT: Вы отметили, что вам нужна гарантия уникальности. Реально, вы никогда не получите его при программном создании уникального идентификатора. На практике вы собираетесь хранить сгенерированный идентификатор в типе данных, который имеет конечный размер, и поэтому возможный набор идентификаторов, которые вы можете сгенерировать, также является конечным. ИМХО, лучшее, что вы можете достичь, это имитировать уникальность в пределах порога допуска.

Вы можете сделать это

• Используя методику, которая делает шансы на получение дубликата UUID очень отдаленное (это то, что Повысьте :: UUID будет делать);

• Обертывание поколения очень вероятно уникального UUID в некоторой другой логике, которая ищет вновь созданный UUID в списке уже созданных UUID, чтобы устранить эту крошечную вероятность того, что новый дубликат. Очевидно, что практичность этого становится уменьшающейся по мере приближения к большому количеству UUID в вашем списке. Сколько вы ожидаете генерации?

• Если вы хотите поистине огромное количество уникальных идентификаторов, больше, чем подходит для родного типа, вы можете реализовать тип, который управляет памятью и выполняет необходимые математические вычисления, и просто создавать последовательные идентификаторы, или вы могли бы использовать что-то вроде GNU Bignum Library, чтобы сделать это за вас.

Answer 2

Какая уникальность вам нужна?
Просто уникально для жизни программы или уникально в нескольких сериях/кросс-процессах?

Если это первый, то вы можете просто new байт памяти, затем используйте адрес этой памяти в качестве вашего идентификатора. Это будет гарантировано уникальным до тех пор, пока вы не запомните память, после чего она может быть переработана.

Это может быть легко завернутые в классе, как это:

#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; 
}; 

Возможно немного необычный, но оно отвечает вашим требованиям, если вам нужно только на процесс единственность :)

Answer 3

Проблема похоже, не связан с C++, это скорее фундаментальная проблема. Сколько идентификаторов ожидается в любой момент? Если вы ожидаете иметь несколько действительных идентификаторов в любой момент времени, просто поместите их в контейнер, такой как связанный список, вектор или набор, в зависимости от ваших требований к производительности и относительной частоты рециркуляции/резервирования. Сортированный связанный список, вероятно, является лучшим вариантом, так как в O (n) будут выполняться как перезагрузка, так и резервное действие. Вектор имеет O (n), O (n log n), а множество имеет O (n log n), O (n) соответственно (может быть, ошибочно, я думал очень быстро).

void recycle(ID) { 
    container.remove(ID); 
    // abort if unsuccessiful (= invalid ID) 
} 

ID reserve() { 
    static ID last = 0; 
    while(container.find(last)) { 
     last++; 
    } 
    return last; 
} 

Answer 4

Сколько времени должны делать идентификаторы? Вам действительно нужно перерабатывать их, или вы можете жить с ними, будучи уникальными навсегда? Сколько вам нужно, чтобы создать все сразу? Сколько бит вы можете посвятить id?

Вот простой рецепт: возьмите MAC-адрес вашей локальной сети (который является глобально уникальным проблемным аппаратным обеспечением), смешайте время/дату (до миллисекундного разрешения) и инкрементирующий целочисленный счетчик (увеличивается один раз на каждый генерируемый идентификатор), и вы 'd имеет уникальный идентификатор в пределах диапазона вашего времени/даты, если вы не генерируете MAXINT из них за одну миллисекунду на этой машине. Теперь это НЕ случайный взгляд, и это просто для того, чтобы злоумышленник мог предсказать, поэтому не используйте его для обеспечения безопасности, и это, конечно, не самое эффективное использование битов там, но оно глобально уникально.

Answer 5

Да, это просто.

1. reserve_id функция operator new(0).
2. Это выделяет нулевые байты, но с уникальным адресом.
3. recycle функция конечно operator delete