検索情報のための最速データ構造体C++

Question

私はDeveloppingクライアントアプリケーションです。これは、TCPクライアントのシミュレータであり、1000クライアントをシミュレートする必要があります。

各クライアントのステータス情報は、50バイトのサイズにすることができます。サーバーとクライアントのシミュレータが必要とする状態情報は、いくつかの場所に保存する必要があります。

サーバはステータス情報について任意のクライアントをリクエストできます。このシナリオでは、どのデータ構造が役立つかを知りたいと思っていました。

サーバはすでに実装されています。これらのクライアントステータス情報を管理する方法はありますか。私はboostやその他のサードパーティ製のlibを使用できないため、C++のみに依存しなければなりません。ステータス情報がどのように管理されるかについて

：

• シミュレートされたクライアントは、シミュレートされたサーバがシミュレートされたクライアントからのステータスを要求することができ
• 自分の状態を知っています。
• 各クライアントには一意の数値が固定されます。サーバーはこの番号を認識しています。クライアントが接続されると、サーバーはこの番号を持つソケットをマップしてクライアントを識別します。
• サーバーはクライアントの状態をポーリングするたびに、すべてのクライアントの状態をポーリングします。

このシナリオでは、どのSTL /またはその他のデータ構造を使用できますか。 ここでは第三者のlibパーティは許可されていません。

1は、私は、ハッシュ関数を用いてO（1）アクセスして、タイプ<key, value>のユーザー定義オブジェクトのベクターの使用をお勧めします

おかげ

Answer 1

それはあなたがそれをどうする必要があるかによって異なります。

単純な検索の場合は、stl :: mapを使用します（STLでは、これは通常、ツリーとして実装されているため、O（lg N）参照）。

もし1000しかなく、識別子を何らかの形で管理しているのであれば、配列を使わないのはなぜですか？これは（明らかに）キーが与えられた要素へのO（1）アクセスを与えます。識別子のセットがすべて前にわかっている場合は、Perfect Hashingを使用し、O（1）検索を取得することもできます。

正直言って、もしあなたが1000要素しか持っていないのであれば、コードの時間的に重要な部分でなければ、何かがかなり速く動くでしょう。

Answer 2

を使用して最適である私を提案してください。

Answer 3

一般に、は、O（1）であり、これは一定時間のルックアップです。これを達成する方法とそれが可能であるかどうかは、あなたが持っている特定の状況によって制約されます。

これまでの説明から、どのような制約があるか（サーバーが持つ）は不明であり、どのような情報がどのように動作するのかわかりません。

オープン質問：状況を知っている

• ？
• クライアントとサーバーの両方のステータスを知っているのは誰ですか？
• クライアントのステータスを知る前に、サーバーには「アクセス権があります」とは何ですか？
• サーバは毎回すべてのクライアントステータスを必要としますか？

  Serverは、クライアントのオブジェクトへのポインタを持っており、ステータスがクライアント上にある：

サーバがクライアントの状況を知りたいいくつかの例が。

int status = client->getStatus(); 

サーバーは、クライアントのIDを持っており、状況は配列に格納されています。クライアントIDは0-999です。

int status = clientStatus[clientId]; 

上記はどちらもO（1）です。

あなたが良いことを述べると、より良い回答が得られます。