3

私は、リクエストが -2 から -101 までの一意の番号を持つ必要があるという要件に取り組んでいます。つまり、一度に 100 個の一意のリクエストがあります。特定の時間に 100 を超えるリクエストがある場合は、エラーを送信する必要があります。最初はリクエストはありません。リクエストを送信したら、 -2 、 -3 などの一意の番号を取得します。ここでの要件は、クライアントからコマンドを取得してサーバーに要求を送信しない場合があることです (例: -2)。したがって、この要求を削除し、将来の要求でこの番号を再利用する必要があります。

これを C++ で実装する最良の方法は何ですか?

また、ブーストを使用することは想定されていません。

4

4 に答える 4

3

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

}

これはクラスで頭から離れて入力したことに注意してください。ドキュメントを確認する

于 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 を追跡して、ID が配布されたかどうかを確認することもできます。そのためのメンバーを使用します。これは、その値がすべてデフォルトで最初に設定されるため、std::vector<bool> used;簡単に初期化できます。もちろん、a を作成することもできますが、コンパイル時に to の距離を知る必要があることに注意してください。used(MAX_ID - MIN_ID +1)falseusedbitsetMIN_IDMAX_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ん。releaseIdmallocfree

于 2012-12-04T12:26:18.847 に答える
1

数値が 100 個しかない場合、パフォーマンスに大きな違いはない可能性があり、セットまたは配列を使用できます。id_used[100]おそらくパフォーマンス測定で勝つような単純な古い配列。

スケーラブルなソリューションが必要な場合は、「free-set」と「used-set」を使用してみてください。free-set は使用のために開かれている ID を格納し、id を持つ used-set はすでに使用されています。ID を使用した後、それをフリー セットに戻します。

許可された ID と同時使用の十分な比率を得るには、「使用済みセット」のみを使用し、拒否サンプリングを使用して空き 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 に答える