リスト内のオブジェクトの「注文」プロパティのデータ構造

Question

データベースに格納され、ORM（具体的にはDjangoのORM）を介してアクセスできる順序付けられたオブジェクトのリストがあります。リストはユーザーによって任意にソートされており、私はそれを追跡するために何らかの方法が必要です。そのために、各オブジェクトには、他のオブジェクトとの関係でその順序を指定する「順序」プロパティがあります。

この注文フィールドでソートするために使用するデータ構造は、リクエスト時に再作成する必要がありますので、作成は安価でなければなりません。私はしばしば複数のオブジェクト間の比較を使用します。また、挿入では、データベースのすべての行を更新する必要はありません。

どのようなデータ構造を使用しますか？

Answer 1

ヒープ

例えば、（格納された値に依存する）値に比較してstd::set（c++）によって実装されるように値による整数、文字列による順序付けなどがあります。注文やアクセスには適していますが、並べ替えを行う必要があるときは確実ではありません。挿入中は常にそうです。

他にどのような制約があるのか​​を指定していません。要素の数が分かっていて、メモリ内に固定配列を保持することが合理的または可能である場合、各位置はインデックスによって指定されます。固定数の要素を仮定します。

操作を頻繁に実行するかどうかを指定していません。 値を一度ロードしてから変更せずにアクセスすると、作成に1つのアルゴリズムを使用して、インデックスまたはトランスフォームストレージを使用して高速アクセスを使用できるようになります...

Answer 2

リンクされたリスト（二重）？

Answer 3

私はあなたが一定の時間（しかし、償却された一定の時間？）。

私はバイナリツリーを使用し、パスを記述するビットシーケンスを "注文プロパティ"として使用できます。