在C ++中生成唯一ID
从C ++中的两个(或者更多)短整数生成唯一ID的最佳方法是什么？我试图唯一地标识图中的顶点。顶点包含2到4个短整数作为数据，理想情况下，ID是它们的某种哈希。相对于速度或者易用性，更喜欢可移植性和独特性。
这里有很多很棒的答案，我今晚将尝试所有答案，以找出最适合我的问题的方法。关于我在做什么的几句话。
该图是来自音频文件的样本的集合。我将图形用作马尔可夫链，从旧文件生成新的音频文件。由于每个顶点都存储了几个样本并指向另一个样本，并且这些样本都是短整数，因此从数据生成ID似乎很自然。将它们组合成很长的声音听起来不错，但是我只需要一个像0 1 2 3generateID这样简单的东西。不知道要保证唯一性需要多少空间，如果每个顶点存储2个16位样本，那么2 ^ 32种可能的组合正确吗？因此，如果每个顶点存储4个样本，那么有2 ^ 64种可能的组合吗？
特定于库和平台的解决方案与该问题并不真正相关。我不希望其他可能会编译我的程序的人下载其他库或者更改代码以适合他们的操作系统。
解决方案
回答
唯一可以确保ID唯一的方法是使ID组合比我们获取ID的组合更多
例如对于2短裤(假设16位)，我们应该使用32位整数
int ID = ((int)short1 << 16) | short2;
对于4短裤，我们将需要64bit整数，等等。
基本上可以确保其他任何冲突(多个事物可能具有相同的ID)。
但是，获取id的另一种方法(我认为会更好)是在插入顶点时将它们分发出去：
unsigned LastId = 0;//global
unsigned GetNewId(){return ++LastId;}
这还具有允许我们向每个顶点添加更多/不同数据的效果。但是，如果我们希望创建多个2 ^ 32个顶点而不进行重置，则这可能不是最佳方法。
回答
使用long long，这样就可以存储所有4种可能性，然后对每种short进行位移位：
((long long)shortNumberX)<< 0、4、8或者12
请确保在转换之前先进行投射，否则数据可能会丢失。
编辑：忘记添加，我们应该将它们或者在一起。
回答
一个简单的解决方案是使用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;
}
可选地，这可以通过工会来完成(Leon Timmermans的伟大想法，请参见评论)。这样很干净：
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;
}
回答
有时最简单的方法效果最好。
我们可以仅向Vertex对象添加一个id字段并按构造顺序为其分配一个数字吗？
static int sNextId = 0;
int getNextId() { return ++sNextId; }
回答
我会说使用质数，
id = 3 * value1 + 5 * value2 + .... + somePrime * valueN
确保我们没有溢出ID空间(长？长长？)。由于我们拥有固定数量的值，所以只需要填充一些随机素数即可。不用担心生成它们，列表中有足够的可用空间让我们暂时离开。
不过，我对证明还有些粗略，也许有一些数学家可以帮助我。可能与数字的唯一素数分解有关。
回答
如果我们更喜欢可移植性，那么boost :: tuple很不错：
我们需要一个包含4个项目的元组：
typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID;
我们可以这样分配：
VertexID id = boost::make_tuple(1,2,3,4);
boost元组已经支持比较，相等等，因此很容易在容器和算法中使用。
回答
问题中" ID"的定义还不清楚：我们是否需要将其用作快速Vertex查找的键？我们可以为std :: map定义一个比较器(请参见下面的示例)
我们是否需要能够区分两个具有相同坐标(但在另一个字段中却不同)的顶点对象？定义一些生成例如一系列与Vertex对象的值无关的整数。 Fire Lancer的建议方式很多(但请注意线程安全性问题！)
在我看来，两个具有相同坐标的顶点是相同的。那么，为什么还要一个额外的ID？
一旦我们为此类型定义了"严格弱排序"，我们就可以将其用作关键字，例如一个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"。
回答
如果我们要建立一个用于存储顶点的哈希表，我可以想到几种避免冲突的方法：
- 直接从输入数据生成ID，而不会丢掉任何位，并使用足够大的哈希表来容纳所有可能的ID。对于64位ID，后者将是非常成问题的：我们将不得不使用小于ID范围的表，因此必须处理冲突。即使使用32位ID，我们也需要超过4GB的RAM才能顺利实现这一目标。
- 在顶点读取时，顺序生成ID。不幸的是，这使得搜索先前读取的顶点以更新其概率非常昂贵，因为顺序ID生成器不是哈希函数。如果用于构造马尔可夫链的数据量明显小于用于马尔可夫链生成的数据量(或者它们都很小)，那么这可能不是问题。
另外，我们可以使用哈希表实现为我们处理冲突(例如unordered_map / hash_map)，然后集中精力处理应用程序的其余部分。
