1

各要素に特定のインデックスがあり、キーを使用して取得できるデータ構造が必要です。

Qt でモデル ビュー プログラミングを行うには、そのデータ構造が必要です。一方では、View は特定の行の要素を要求します。一方、モデルは特定のキーで要素を挿入および変更したいと考えています。どちらの操作も O(1) で実行する必要があります。

これが私が欲しいものの例です：

ビューには次のものが表示されます。

list[0]: "Alice", aged 22
list[1]: "Carol", aged 15
list[2]: "Bob", aged 23

モデルは以下を見ます：

hash["Alice"]: "Alice", aged 22
hash["Bob"]: "Bob", aged 23
hash["Carol"]: "Carol", aged 15

私の考えは次のとおりQList<Value>ですQHash<Key, Value*>。ハッシュは、対応する要素が格納されているリスト内の場所を指します。これは、値を挿入/編集するコードです。

if (hash.contains(key))
    *hash[key] = value;
else
{
    int i = list.size();
    list << value;
    hash[key] = &list[i];
}

問題は、このコードが常に機能するとは限らないことです。期待どおりに動作することもありますが、データ構造が一貫していないことがあります。
QListが新しいスペースなどを割り当てるため、メモリを介してコンテンツを移動するためだと思います。

重要な操作 (予想される O(1) で実行する必要があります):

  • キーと値のペアを挿入します (リストの最後に値を追加します)
  • キーを使用して値を検索および変更する
  • インデックスを使用して値を検索および変更する

可能でなければならないが、一定の実行時間で可能である必要はないその他の操作:

  • インデックスによる要素の削除
  • キーによる要素の削除
  • 配列の途中に挿入
  • 配列内の要素を入れ替える / 配列をソートする
  • キーのインデックスを取得する

私の2つの質問は次のとおりです。

  • 私が望むことをするデータ構造はありますか?
  • そうでない場合、どうすればこれを修正できますか、またはより良いアプローチがありますか?
4

1 に答える 1

2

アプローチ 1:ポインターの代わりに、リスト インデックスをハッシュに格納できます。次に、もう 1 つの間接化があります (ハッシュからインデックスを取得し、リストから取得します) が、それでも O(1) です。速度の差はそれほど大きくないはずです。

アプローチ 2:リストとハッシュの両方がポインターで動作します。その後、それらは有効なままになります。ただし、インデックスまたはキーに基づいて削除すると、対応しないコンテナーでオブジェクトを手動で見つける必要があるため、O(n) になります。

とにかく、インデックスによる削除または途中での挿入の問題をどのように解決したいのだろうか。どちらの場合も、ハッシュは間違ったエントリを指します (アプローチとアプローチ 1 の両方で)。ここでは、アプローチ 2 を使用する必要があります。

于 2012-07-31T11:16:46.477 に答える