Генерация уникального идентификатора в С++

Простое решение — использовать 64-битное целое число, где младшие 16 бит — первая координата вершины, следующие 16 бит — вторая и так далее. Это будет уникальным для всех ваших вершин, хотя и не очень компактным.

Итак, вот какой-то недоработанный код для этого. Надеюсь, я правильно понял броски.

uint64_t generateId( uint16_t v1, uint16_t v2, uint16_t v3, uint16_t v4)
{ 
   uint64_t id;
   id = v1 | (((uint64_t)v2) << 16) | (((uint64_t)v3) << 32) | (((uint64_t)v4) << 48);
   return id;
}

При желании это можно сделать с помощью союза (отличная идея от Леона Тиммерманса, см. комментарий). Очень чисто так:

struct vertex
{
    uint16_t v1;
    uint16_t v2;
    uint16_t v3;
    uint16_t v4;
};

union vertexWithId
{
    vertex v;
    uint64_t id;
};

int main()
{
    vertexWithId vWithId;
    // Setup your vertices
    vWithId.v.v1 = 2;
    vWithId.v.v2 = 5;

    // Your id is automatically setup for you!
    std::cout << "Id is " << vWithId.id << std::endl;
    return 0;
}

Иногда самые простые вещи работают лучше всего.

Можете ли вы просто добавить поле id в объект Vertex и присвоить ему номер в порядке построения?

static int sNextId = 0;
int getNextId() { return ++sNextId; }

используйте длинный длинный, чтобы вы могли сохранить все 4 возможности, а затем побитовый сдвиг каждого короткого:

((long long)shortNumberX) ‹‹ 0, 4, 8 или 12

убедитесь, что вы бросаете перед переключением, иначе ваши данные могут упасть в конце.

Редактировать: забыл добавить, вы должны ИЛИ их вместе.

Если вы предпочитаете переносимость, тогда boost::tuple красиво:

Вам нужен кортеж из 4 элементов:

typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID;

Вы можете назначить так:

VertexID id = boost::make_tuple(1,2,3,4);

Кортеж boost уже поддерживает сравнение, равенство и т. д., поэтому его легко использовать в контейнерах и алгоритмах.

Определение «ID» в вопросе не очень ясно: вам нужно использовать его в качестве ключа для быстрого поиска вершин? Вы можете определить компаратор для std::map (см. пример ниже)

Вам нужно иметь возможность различать два объекта Vertex с одинаковыми координатами (но разными в другом поле)? Определите некую «фабрику идентификаторов» (см. шаблон singleton), которая генерирует, например. последовательность целых чисел, не связанная со значениями объектов Vertex. - Во многом так, как предлагает Fire Lancer (но остерегайтесь проблем с потокобезопасностью!)

На мой взгляд, две вершины с одинаковыми координатами идентичны. Так зачем вам вообще нужно дополнительное удостоверение личности?

Как только вы определите 'строгий слабый порядок' для этого типа, вы можете использовать его как ключ, например std::map,

struct Vertex {
  typedef short int Value;
  Value v1, v2;

  bool operator<( const Vertex& other ) const {
    return v1 < other.v1 || ( v1 == other.v1 && v2 < other.v2 ) ;
};

Vertex x1 = { 1, 2 };
Vertex x2 = { 1, 3 };
Vertex y1 = { 1, 2 }; // too!

typedef std::set<Vertex> t_vertices;

t_vertices vertices;
vertices.insert( x1 );
vertices.insert( x2 );
vertices.insert( y1 ); // won't do a thing since { 1, 2 } is already in the set.

typedef std::map<Vertex, int> t_vertex_to_counter;
t_vertex_to_counter count;
count[ x1 ]++;
assert( count[x1] == 1 );
assert( count[y1] == 1 );
count[ x2 ]++;
count[ y1 ]++; 
assert( count[x1] == 2 );
assert( count[y1] == 2 );

Если вы работаете в Windows, вы можете использоватьCoCreateGUID API, в Linux вы можете использовать /proc/sys/kernel/random/uuid, вы также можете посмотреть «libuuid».

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

1. Создавайте идентификаторы непосредственно из входных данных, не отбрасывая биты, и используйте хеш-таблицу, которая достаточно велика, чтобы вместить все возможные идентификаторы. С 64-битными идентификаторами последнее будет крайне проблематично: вам придется использовать таблицу, которая меньше вашего диапазона идентификаторов, поэтому вам придется бороться с коллизиями. Даже с 32-битными идентификаторами вам потребуется более 4 ГБ ОЗУ, чтобы справиться с этим без коллизий.
2. Генерируйте идентификаторы последовательно по мере считывания вершин. К сожалению, это сильно удорожает поиск ранее прочитанных вершин с целью обновления их вероятностей, поскольку генератор последовательных идентификаторов не является хэш-функцией. Если объем данных, используемых для построения цепи Маркова, значительно меньше, чем объем данных, для генерации которых используется цепь Маркова (или если они оба малы), это может не быть проблемой.

В качестве альтернативы вы можете использовать реализацию хеш-таблицы, которая обрабатывает коллизии за вас (например, unordered_map/hash_map) и сосредоточьтесь на остальной части вашего приложения.

Ну, единственный способ гарантировать, что идентификатор уникален, - это создать больше комбинаций идентификаторов, чем ваши идентификаторы получения.

например, для 2 шорт (при условии 16 бит) вы должны использовать 32-битный int

int ID = ((int)short1 << 16) | short2;

а для 4 шорт вам понадобится 64-битный int и т. д.

По сути, коллизии с чем-либо еще (несколько вещей могут получить один и тот же идентификатор) в значительной степени гарантированы.

Однако другой подход (который, я думаю, был бы лучше) для получения идентификаторов состоял бы в том, чтобы раздавать их по мере вставки вершин:

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

Это также позволяет вам добавлять больше/разные данные в каждую вершину. Однако, если вы планируете создать более 2^32 вершин без сброса, это, вероятно, не лучший метод.

Попробуйте использовать это:

int generateID()
{
    static int s_itemID{ 0 };
    return s_itemID++; // makes copy of s_itemID,
                         increments the real s_itemID, 
                         then returns the value in the copy
}

Это взято здесь.

Реализация собственного хеширования может быть утомительной и подверженной некоторым проблемам, которые трудно отладить и решить, когда вы развернули или частично развернули свою систему. Гораздо лучшая реализация уникальных идентификаторов уже присутствует в Windows API. Подробнее см. здесь ;

https://docs.microsoft.com/en-us/windows/win32/api/guiddef/ns-guiddef-guid

навскидку я бы сказал использовать простые числа,

id = 3 * value1 + 5 * value2 + .... + somePrime * valueN

Убедитесь, что вы не переполняете свое пространство идентификатора (длинное? длинное, длинное?). Поскольку у вас есть фиксированное количество значений, просто испортите несколько случайных простых чисел. Не утруждайте себя их созданием, в списках их достаточно, чтобы вы могли работать какое-то время.

Однако я немного схематичен в доказательстве, может быть, кто-то более математический сможет меня зацепить. Вероятно, это как-то связано с уникальной простой факторизацией числа.