0

C++ では、各要素が int で表される独自の ID を持つある種の動的配列が必要です。

データ型には次の関数が必要です。

  • int Insert() - ID を返す
  • 削除(int ID)
  • Get(ID) - 要素を返す

どのデータ型を使用すればよいですか? Vector と List を調べましたが、ID が見つからないようです。また、map と hastable も調べましたが、これらは役に立つかもしれません。ただし、何を選択すればよいかわかりません。

4

4 に答える 4

2

おそらくベクトルとフリー ID リストを使用して削除を処理します。インデックスは ID です。これは、挿入と取得が非常に高速で、管理も非常に簡単です (唯一の秘訣は、削除されたアイテムの空きリストです)。

それ以外の場合は、おそらくマップを使用して、未使用の最小 ID を追跡し、挿入時に割り当てることをお勧めします。

于 2011-07-27T15:20:54.753 に答える
1

これstd::mapにより、キーを値に関連付けることができます。キーはID ですが、要素をマップに追加するときに自分で指定する必要があります。

ハッシュ テーブルは、順序付けられていないマップを実装するために使用できる一種の基本的なメカニズムです。std::unordered_map に対応しています。

于 2011-07-27T15:15:33.407 に答える
1

Avectorは一定時間のランダム アクセスを提供します。" id" は単にベクトルへのオフセット (インデックス) にすることができます。Adequeも同様ですが、すべてのアイテムを連続して格納するわけではありません。

ID 値が 0 から開始できる場合 (または 0 からの既知のオフセットで単調に増加する場合)、これらのいずれかが適切です。時間の経過とともに大量の削除がある場合、vectorまたはdeque人口がまばらになる可能性があり、これは有害な場合があります。

std::map人口がまばらになるという問題はありませんが、ルックアップは一定時間から対数時間に移行するため、パフォーマンスに影響を与える可能性があります。

boost::unordered_mapハッシュテーブルとしての最良のケースのシナリオは、質問に与えられた全体的なパフォーマンス特性が最も優れている可能性が高いため、これまでで最高の可能性があります。ただし、boost ライブラリの使用が必要になる場合がありますが、STL 実装で使用できる場合は、unorderedコンテナー タイプもあります。std::tr1

于 2011-07-27T15:29:40.613 に答える
1

使用するのに最適なコンテナーは unordered_map のようです。ハッシュに基づいています。O(n) 内の要素を挿入、削除、または検索できます。

現在 unordered_map は STL にありません。STL コンテナーを使用する場合は、std::map を使用します。木を基調としています。O(n*log(n)) 内の要素を挿入、削除、および検索します。

それでも、容器の選択は使用頻度に大きく依存します。たとえば、まれな要素が見つかった場合は、ベクターとリストで問題ありません。これらのコンテナーには find メソッドがありませんが、<algorithm>ライブラリには含まれています。

于 2011-07-27T15:08:50.943 に答える