C ++中的惯用语“保证唯一”标识符

|| 是否有惯用的C ++方式来保留和回收保证唯一的标识符？我的要求是：假设存在一个当前未保留的ID，reserve_id（void）向我返回该ID。在未中断的reserve_id（）调用序列中，没有单个标识符将返回两次存在一个功能recycle（id_type），该功能将标识符返回到可用池。例如，我见过Boost :: Uuid，但是a）我看不到任何文档可以断言两个UUID的保证唯一性，并且b）目前我只限于早期版本的Boost（1.40）。如果这对任务特别完美，我可以推动升级。

已邀请:

5 个回复

屑凉赦

我认为您已经找到了Boost :: Uuid来解决大多数实际问题，除了需要回收已经生成的标识符。从您在问题中链接到的文档：当UUID由以下之一生成时定义的机制，它们要么是保证与众不同从所有其他生成的UUID（即是，它从来没有产生过它将不再生成），或极有可能是独一无二的（取决于机制）。如果您想回收再利用现有的标识符，我想您可以随着时间的推移维持建立一个UUID池，仅在需要一个UUID并发现该池为空时才生成新的UUID。但是我无法想象这样一种场景，该场景比生成新的UUID更可取。编辑：您评论说，您需要保证唯一性。实际上，以编程方式生成唯一标识符时，您永远都不会得到。实际上，您将要将生成的ID存储在大小有限的数据类型中，因此可以生成的ID可能也是有限的。恕我直言，那么您可以做到的最好的就是在公差阈值内模拟唯一性。你可以这样做使用一种使获得重复的UUID的机会非常遥远的技术（Boost :: UUID将会这样做）；将高度可能成为唯一的UUID包裹在其他逻辑中，该逻辑在已生成的UUID列表中查找新生成的UUID，以消除新副本是重复的可能性很小。显然，当您处理列表中的大量UUID时，这样做的实用性就会降低。您预计会产生多少？如果您想要大量独特的ID（比本机类型大），则可以实现一种类型来管理内存并进行必要的数学运算，并产生顺序的ID，或者可以使用类似GNU Bignum的类型图书馆为您服务。

泪琉踞檄

这些ID可以居住多长时间？您是否真的需要回收它们，还是可以让它们永远独一无二？您一次需要生成多少个？您可以为ID分配多少位？这是一个简单的方法：拿出以太网卡的mac地址（这是全球唯一的裸机硬件问题），混入时间/日期（以毫秒为单位）和一个递增的整数计数器（每个生成的id递增一次），然后只要您没有在这台机器上的一毫秒内生成MAXINT，就可以在时间/日期范围内拥有唯一的ID。现在，它不是随机查找的，而且攻击者也很容易预测，因此请不要将其用于安全性，并且肯定不是最有效地使用比特的方法，但是它确实是全球唯一。

恋卡

您需要哪种独特性？在程序的整个生命周期中是唯一的还是在多个运行/跨进程中是唯一的？如果是前者，则您可以只“ 0”个字节的内存，然后使用该内存的地址作为标识符。在您“ 1”保留内存之前，可以保证它是唯一的，此时可以将其回收。这可以很容易地包装在这样的类中：

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

可能有点不寻常，但是如果您仅需要每个进程的唯一性，它就可以满足您的要求：)

郡晒景沧

是的，这很简单。 reserve_id功能是operator new(0)。这分配零字节，但具有唯一地址。 recycle功能当然是operator delete

丧泉缝锋

该问题似乎与C ++无关，它更多是一个基本问题。在任何给定时间，预期有多少个ID有效？如果您希望在任何给定时间只有很少的有效ID，则可以根据性能要求和相对的回收/保留频率将它们放在诸如链表，向量或容器之类的容器中。排序链表可能是最好的选择，因为您将在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;
}

要回复问题请先登录或注册

C ++中的惯用语“保证唯一”标识符

5 个回复

发起人

uuid

idioms

c++

问题状态

C ++中的惯用语“保证唯一”标识符

与内容相关的链接

5 个回复

发起人

uuid

idioms

c++

问题状态