動的配列の幅のID？

Question

私は、各要素がintで表される独自のidを持つC++で何らかの並べ替えをする必要があります。 - リターンID

は（int型のID）を削除

取得（ID） - どのようなデータ型の要素

を返す必要があります

• int型インサート（）：データ型は、これらの機能を必要とする

  私が使う？私はVectorとListを見ましたが、IDの種類を見つけることはできません。また、私は地図を見て、hastable、これらは有用かもしれません。私はしかし、何を選ぶか分からない。

Answer 1

std::mapを使用すると、キーに値を関連付けることができます。 キーがあなたのIDになりますが、マップに要素を追加するときは、自分で入力してください。

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

Answer 2

使用するのに最適なコンテナは、unordered_mapと思われます。 ハッシュに基づいています。 O（n）の要素を挿入、削除、検索することができます。

現在、unordered_mapはSTLにありません。 STLコンテナを使用する場合は、std :: mapを使用します。 木をベースにしています。 O（n * log（n））の要素を挿入、削除、検索します。

なお、容器の選択は使用強度に大きく依存します。たとえば、希少な要素が見つかると、vectorとlistは問題ありません。これらのコンテナにはfindメソッドがありませんが、<algorithm>ライブラリに含まれています。

Answer 3

私はたぶん、削除を処理するためにベクトルと空きIDリストを使用します。インデックスはidです。これは挿入と取得が非常に高速で、管理が簡単です（削除されたアイテムの空きリストのみです）。

それ以外の場合は、マップを使用して、最も未使用のIDを追跡し、挿入時に割り当てたいと思うかもしれません。

Answer 4

vectorは、一定時間ランダムアクセスを提供します。「id」は、単にベクトルへのオフセット（インデックス）にすることができます。 dequeは似ていますが、すべての項目を連続して保存するわけではありません。

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

std::mapにはまばらになる問題はありませんが、ルックアップは一定の時間から対数時間に移動し、パフォーマンスに影響する可能性があります。

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