3

我正在研究一个要求，其中请求应该具有从 -2 到 -101 的唯一编号，即一次有唯一的 100 个请求。如果在给定时间有超过 100 个请求，那么我应该发送错误。最初我没有任何要求。一旦我发送请求，我将使用唯一编号，例如 -2 、 -3 等等。这里的要求是我可能会从客户端获取命令不要向服务器发送请求，例如 -2 所以我应该删除这个请求，并且我应该将此数字用于将来的请求。

在 C++ 中实现这一点的最佳方法是什么？

另外，我不应该使用 Boost。

4

4 回答 4

3

扩展我的std::bitset评论：

您可以使用 id 作为 bitset 的索引，使用 value ( 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);
    }

}

请注意，这是在课堂上输入的，这不是我的想法。检查文档

于 2012-12-04T14:16:12.130 回答
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初始值。当然，您也可以制作usedabitset但请注意，这需要在编译时知道从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

于 2012-12-04T12:26:18.847 回答
1

只有 100 个数字可能没有显着的性能差异，您可以使用集合或数组；普通的旧数组id_used[100]可能会在性能测量中获胜。

如果您需要可扩展的解决方案，请尝试使用“free-set”和“used-set”，其中 free-set 存储 id 可供使用，并且 used-set 和 id 已在使用中。使用 id 后，将其存储回自由集。

对于允许的 id 与并发使用的足够大的比率，只使用“used-set”，并使用拒绝抽样来找到一个空闲的 id：

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

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

于 2012-12-04T11:56:05.987 回答
0

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

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);
于 2012-12-04T11:59:40.370 回答