データ構造

Question

私は、次のような構造のデータを扱うアプリケーションがあります。

9:00:00 Bob <Info> 
9:01:00 John <Info> 
9:05:00 Bob <Info> 
9:11:00 Mary <Info> 
9:17:00 John <Info> 
9:25:00 Mary <Info> 
9:30:00 Bob <Info> 

：

struct Message 
{ 
    int time; 
    string name; 
    string details; 
}; 

例えば、私は次のようなデータセットを持っていることを

そして私は、データセット内の各行を表すMessage構造体のリストを持っています。私はこのデータに行う必要があります

一部の操作が含まれます：

• は年代順にすべてのデータを収集し、dostuff()
• はJohn（または誰でも）からのすべてのデータを収集し、時系列順とdostuff()

で

だから、私は年代順にすべてのメッセージを渡すことはなく、また、人を選択し、年代順にだけ彼らのメッセージを通過することができるようにリストをトラバースする方法が必要です。 message->nameに属し次Nodeに年代順に次のNodeにnext_timeポイントで

struct Node 
{ 
    Message* message; 
    Node* next_time; 
    Node* next_name; 
}; 

、およびnext_nameポイント：

私の考えでは、このような構造体を持っています。そしてRoot構造は、各タイプの最初を指します。

struct Root 
{ 
    Node* first_time; 
    Node* first_bob; 
    Node* first_john; 
    Node* first_mary; 

    Node* last_time; 
    Node* last_bob; 
    Node* last_john; 
    Node* last_mary; 
}; 

ここにポイントを説明する画像があります。

この構造はしかし、私は多分これはそれよりも複雑であることを心配して、私はかなり簡単にすべてのメッセージを通して、またはなどのみボブのメッセージ、またはのみジョンズを通じて

を横断することができます必要があります。私はまた、メンテナンスについて懸念があります（下記参照）。私は、検索/選択/私は、彼らがいると思うれ、非常に高速であることを読み取り操作を必要としています。そして、私は合理的に速いために挿入操作が必要です。しかし今は、私が挿入するすべてのMessageのために、私はいくつかのnext_timeポインタを更新し、（2）いくつかnext_nameポインタを更新する必要があります。

私の質問は すでにこの種の機能を提供するデータ構造が存在していますか？そうでない場合、私はこの問題に正しく遭遇していますか？

可能であれば、C++またはC＃でコードサンプルを提供してください。

ありがとうございました。

追加：後で私のMessage構造体に追加したいとします。 Cityというフィールドを追加したとします。今、私はこれをやってみたいことがあります。

• は年代順に特定Cityからすべてのデータを収集し、dostuff()

これはnext_cityを追加することが必要になり、その後、すべての挿入のために、私がしなければなりません更新next_time,next_name、およびnext_city。

• が、私はこれは非常に多くの困難な問題になると思う特定のCityと時系列順に特定nameとdostuff()

からすべてのデータを収集します。また、

は、私はこれをしたいと仮定します私はすべてのMessageをトラバースし、私が気にしないものを飛ばすことを選択しない限り。

Answer 1

すべてのメッセージの単純なリンクリスト（時間でソート）。

struct Node 
{ 
    Message* message; 
    Node* next_name; 
}; 

これは、（1）

Oにキーと値としてノード*のリストなどユーザーとの個別のハッシュマップを追加することができます。1.（REQを満たす）とのgetAll（）します。

Hashmap 
{key = User, value = List(Message*)} 

これは、あなたが特定のユーザOのリストの最後に新しいエントリを追加することができますREQ 2を満たす（1）とgetAllOfUserは（）もOで実行することができます（1）

Answer 2

私はたぶんユーザーを表すクラスを作成し、名前のような識別子でハッシュテーブルにユーザーを格納し、各ユーザーに年代順にソートされたリストを保持させます。誰もがMessageを時間順に保持しているグローバルリスト。追加されたすべてのデータに対して、Messageを追加すると、データ構造に応じて、log n時間、またはnのように悪い可能性があります。