2

オブジェクトのリストを維持する「マネージャー」クラスがあります。各オブジェクトには特定の「位置」がありますが、これはオブジェクトには知られていません。マネージャーだけがこれを知っています。マネージャーは、各オブジェクトに位置を割り当て、この「外部属性」に従ってソートされたオブジェクトのリストを維持する必要があります。

オブジェクトの位置はいつでも変更できることに注意してください。理想的には、位置 X の要素または要素 X の位置をいつでもすぐに取得できる必要があります。

これは C# コードです。これを行うためのクリーンまたは慣用的な方法は何でしょうか。

次のような内部クラスを作成することを考えました：

class SortedElement {
    public Element Elem { get; set; }
    public int Position { get; set; }
}

次に、SortedElements のリストを維持します。わかりません、不器用に思えます。たとえば、2 つの SortedElements が同じ位置を持つ可能性があります。私が見逃している明白でクリーンな解決策があるように感じます。Position を Elements 自体のプロパティにすることもできますが、意味的には意味がありません。つまり、私の生活を楽にする以外に、それについて知る理由はありません。

私をフェイスパームに行かせてください。

編集:私の要件をリストするというエリック・リッパートのアドバイスと、良い夜の睡眠に従って、私はaを選択しLinkedList<Element>、インデックスを位置として使用する必要があることに気付きました. 実際、ここでの最も一般的な操作は、最初の挿入とコンテナー内の任意の場所の削除であり、配列ベースのコンテナーではコストがかかります。すべての返信に感謝します。

4

4 に答える 4

2

あなたの要件をリストアップしましょう。次の操作を持つデータ構造 S が必要だと思います。

  • ContainsElement: 要素を取り、その要素が S にあるかどうかを示します
  • IsValidPosition: 位置を取り、その位置が S で使用可能かどうかを通知します
  • GetElementAt: 有効な位置を取り、要素を返します
  • GetPositionOf: S にある Element を取得し、Position を返します
  • InsertElementAt: S にない Element と有効な位置を取ります。要素をその位置に配置します。その位置の後のすべての要素は「1 つ上」に移動します。
  • RemoveElementAt: 有効な位置を取り、その位置にある要素を削除し、その位置の後のすべての要素を「1 つ下」に移動します。

それはあなたが望む操作の正しい要約ですか？(要素を新しい位置に移動することは、RemoveElementAt の後に InsertElementAt を実行することと同じであることに注意してください。)

これらが操作の正しい要約ではない場合、抽象データ型でサポートする一連の操作を正確にリストしていただけると助かります。

操作の要件の明確なリストができたら、次の質問は「漸近的なパフォーマンス要件は何か?」です。

たとえば、List<T>データ構造 S として a を使用できます。これらすべての操作をサポートします。ただし、リストが非常に長い場合、「含む」操作と同様に、リストの先頭での挿入と削除は非常にコストがかかります。

挿入と削除のモデル化に非常に効率的な、使用できるよりエキゾチックなデータ構造があります。このようなデータ構造を使用して、C# IDE のエディターの状態の変更をモデル化します。明らかに、各トークン、変数宣言などは「位置」を持つ「要素」であり、その位置は、入力するたびに常に変化します。これらの変更を効率的に処理することは非常に困難ですが、そのような問題領域にいる場合は、それをより明確に説明してください。調査できるデータ構造についての指針を提供できます。

于 2010-01-12T04:37:57.513 に答える
1

コレクションを要素の単純なシーケンスとして説明することを避けるために苦労しているように見えるので、List<T>位置としてインデックスを使用することは問題外であると想定します。はどうDictionary<int, Element>ですか？一意性を強制し、参照するこの「位置」が序数であると仮定して、適切な並べ替えを維持します。

于 2010-01-12T04:17:09.867 に答える
0

本当にSortedDictionaryを使うべきだと思います。

于 2010-01-12T13:42:37.627 に答える
0

ジェネリック リスト ( List<Element>) を使用して、要素のリストを "manager" クラスに内部的に保持できます。次に、クラスのSort()メソッドを使用して、必要に応じてリストを並べ替えることができます。List<T>例えば：

myList.Sort((elem1, elem2) => elem1.Name.CompareTo(elem2.Name));

この例では、要素はプロパティ「名前」でソートされていますが、「外部属性」を含め、比較には何でも使用できます。

于 2010-01-12T04:27:00.810 に答える