vectorとmap、どちらを使うか？

質問

コンテナ内の想定要素数が比較的少ない場合は std::vector の代わりに std::map の代わりに コンテナを使用します。

この背後にある本当の理由は何でしょうか？

明らかに、ルックアップのパフォーマンスは std::map よりも悪くなることはありえません。 std::vector (ナノ秒/マイクロ秒の差はあるかもしれませんが)なので、メモリ使用量と関係があるのでしょうか？

は std::vector よりも良いのか悪いのか std::map と比べて良いのか悪いのか？

Visual Studioに付属しているSTLライブラリ（つまりMicrosoftの実装）を使用しています。 これは、他の実装と比較して何か違いがあるのでしょうか?

どのように解決するのですか?

あなたが比較しているのは map<A, B> と vector<pair<A, B> > .

まず、非常に小さなベクトルで項目を見つけることは、マップの同じものよりも簡単に速くなります。ベクトル内のすべてのメモリは常に連続しており（そのため、コンピュータのキャッシュなどとうまく連携しています）、ベクトルで何かを見つけるために必要な比較の数はマップの場合とほぼ同じかもしれないためです。マップ内の要素を見つけるには、非常に大きなコンテナの制限内でより少ない操作が必要です。

マップがベクトルより速くなるポイントは、実装、プロセッサ、マップ内のデータ、プロセッサのキャッシュにあるメモリなどの微妙なものに依存します。一般的に、マップが高速になるポイントは、5～30要素程度でしょう。

別の方法として、ハッシュコンテナを使用することもできます。これらはしばしば hash_map または unordered_map . という名前のクラスは hash_map という名前のクラスは公式な標準の一部ではありません (そして、そこにはいくつかの亜種があります)。 std::tr1::unordered_map です。ハッシュマップは要素の数に関係なく、ルックアップのために通常のマップよりも速いことがよくありますが、実際に速いかどうかは、キーが何か、どのようにハッシュ化されるか、どんな値を扱う必要があるか、そして std::map でキーがどのように比較されるかに依存します。std::mapのように特定の順序で保持することはできませんが、あなたはそのことを気にしないと言っています。キーが整数やポインタの場合は特にハッシュマップをお勧めします。