在C++中生成和重复使用唯一ID

Question

我正在处理一个需求，要求请求的编号在 -2 到 -101 之间是唯一的，即每次有100个独特的请求。如果在给定时间内有超过100个请求，则应返回错误。最初，我没有任何请求。一旦发送请求，我将获得独特的号码，比如 -2，-3 等等。这里的要求是，我可能会收到客户端的命令，要求不要向服务器发送例如 -2 的请求，因此我应该删除这个请求，并且我应该重用这个编号以供将来的请求使用。

最好的实现方式是什么？此外，我不应该使用 Boost。

- venkysmarty

---

使用std::list来保存可用的ID。初始情况下，列表中包含所有数字。之后根据需要添加和删除。 - atoMerz

@AtoMerZ，您能否举个例子来说明如何实现这个想法？ - venkysmarty

如果不使用Boost，那么标准库怎么样呢？比如像std::map这样的？或者只是一个数组bool id_used[100]，如果使用了一个ID就将其设置为true？ - Some programmer dude

@mah：我真的不明白那个常见问题解答怎么会适用于这里。这既不是闲聊也不是开放性问题。虽然这不是最复杂的问题，但它绝对不是“毫无建设性”的。 - bitmask

@mah：不是这样的。基于主观意见进行辩论和提出可以客观评估效率的不同解决方案是有区别的。仅仅因为一个问题得到了几个不同的答案，并不意味着它是开放性的。 - bitmask

Answer 1

关于我的std::bitset评论的进一步解释：

您可以使用id作为位集的索引，而值(true/false)表示id的可用性。

class IdStorage {
    const int N = 100;
   std::bitset<N> ids;

   bool allIdsUsed() { 
       return ids.all();
   }

   int getId() {
     if(allIdsUsed())
         throw "Error";

     for(int i = 0; i < N; ++i )
        if(ids.test(i))
            return i - 2;
   }

   void releaseId(int i) {
       ids.set(i + 2);
    }

}

请注意，这是我在课堂上凭记忆打出的。查看文档以获取更多信息。涉及到it技术相关内容。

- TeaOverflow

Answer 2

您需要至少维护一个未使用的id集合。此外，我建议添加一个查找表来验证是否分配了id（以提高健壮性）。对于这两个功能，我建议使用std::vector而不是列表。

首先，在std::vector<int>中存储未使用的集合，您可以非常轻松地初始化：

class IdStore {
  private:
    std::vector<int> unused;
    static int const MIN_ID = -101;
    static int const MAX_ID = -2;
  public:
    IdStore::IdStore()
    : unused(MAX_ID - MIN_ID + 1) {
      for (auto i = 0; i <= MAX_ID-MIN_ID; ++i) {
        unused[i] = i;
      }
    }
    int getId();
    void releaseId(int);
};

此外，您可能希望跟踪使用的ID，以便可以验证它们是否已经分配；我会使用一个std :: vector <bool> used;成员来实现，您可以通过used(MAX_ID - MIN_ID +1)简单地初始化它，因为它的值最初都将默认为false。当然，您也可以将used作为bitset，但请注意，这需要在编译时知道从MIN_ID到MAX_ID的距离。

从那里开始分配东西相当简单：

int IdStore::getId() {
  if (unused.empty())
    throw "error"; // put something better here
  auto r = unused.back();
  used[r] = true;
  unused.pop_back();
  return MIN_ID + r;
}

释放它们，还有：

void IdStore::releaseId(int id) {
  if (id < MIN_ID || id > MAX_ID)
    throw "error"; // put something better here
  id -= MIN_ID;
  if (!used[id])
    throw "error"; // put something better here
  used[id] = false;
  unused.push_back(id);
}

请注意，不会进行任何重新分配！与使用列表的方法相比，向量将保持其大小，getId和releaseId都不需要昂贵的malloc或free调用。请参考此处。

- bitmask

---

使用向量比列表更好。感谢您的帮助。 - venkysmarty

请注意，vector<bool>是一种奇怪的东西。有些人避免使用它，认为它是邪恶的。 - TeaOverflow

@Evgeni：谢谢你的留言。是的，我知道std::vector<bool>的特化，但我认为在这种情况下应该没问题。 - bitmask

@bitmask 是的，我认为人们对此过于紧张了。但是，如果您没有意识到特化，它可能会给您带来难以跟踪的奇怪错误。不过，我不喜欢的是它会产生运行时开销。对于静态大小，我认为std::bitset是最好的选择。 - TeaOverflow

Answer 3

对于仅有的100个数字，可能没有显著的性能差异，您可以使用集合或数组；普通老式数组，例如id_used [100] 在性能测试中可能会胜出。

如果您需要可扩展的解决方案，请尝试使用“自由集”和“已使用集”，其中自由集存储空闲可用的ID，已使用集存储已经在使用中的ID。使用ID后，请将其存回到自由集中。

对于允许ID与并发使用比之间足够大的情况，请仅使用“已使用集”，并使用拒绝采样找到空闲的ID：

do {
    id = generate_id();
} while(std::end != used_set.find(id));

无论如何，没有明确的答案。

- Sebastian Mach

Answer 4

我还没有编译它，但应该是这样的：

std::list<int> list;
for(int i=start; i<=end; ++i)
  list.insert(i);

//when get Id request
Id2send = list.first();
list.remove(list.first());

//when delete id request
list.remove(id);

//when add id request (this happens when an id is freed or other times)
list.add(id);

- atoMerz