Идиоматические "гарантированно-уникальные" идентификаторы в C ++ - PullRequest
Новая
       7

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

4 голосов
/ 14 апреля 2011

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

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

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

Ответы [ 5 ]

3 голосов
/ 14 апреля 2011

Как долго живут идентификаторы? Вам ДЕЙСТВИТЕЛЬНО нужно утилизировать их, или вы можете жить с ними навсегда? Сколько вам нужно генерировать все сразу? Сколько бит вы можете посвятить идентификатору?

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

3 голосов
/ 14 апреля 2011

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

Из документации , на которую вы ссылались в вопросе:

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

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

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

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

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

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

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

2 голосов
/ 14 апреля 2011

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

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

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

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

Это можно легко обернуть в такой класс: 

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

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

0 голосов
/ 14 апреля 2011

Проблема, похоже, не связана с 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;
}
...