c++ - C++ std::map 代替コンテナーを推奨できる人はいますか?

Question

マップは物事を簡単に行うのに最適ですが、メモリを大量に消費し、キャッシュの問題に悩まされます。また、マップがクリティカル ループに陥っている場合は、問題が発生する可能性があります。

したがって、同じ API を持ち、ツリー実装の代わりにベクトルまたはハッシュ実装を使用する別のコンテナを誰かが推奨できるかどうか疑問に思っていました。ここでの私の目標は、コンテナーを交換し、マップに依存するすべてのユーザー コードを書き直す必要がないようにすることです。

更新: パフォーマンスに関する最善の解決策は、std::vector でテストされたマップ ファサードです。

Answer 1

ほとんどの STL 実装に既に存在し、C++0x 標準の一部である std::tr1::unordered_map を使用できます。

現在の署名は次のとおりです。

template <class Key,
          class T,
          class Hash = std::tr1::hash<Key>,
          class Pred = std::equal_to<Key>,
          class Alloc = std::allocator<std::pair<const Key, T> > >
class unordered_map;

Answer 2

多分Google SparseHashがあなたを助けることができますか?

Answer 3

Loki :: AssocVectorおよび/またはhash_mapを参照してください（ほとんどのSTL実装にはこれがあります）。

Answer 4

キーが非常にすばやく比較できる単純なタイプであり、エントリが数千個しかない場合は、ペアをに入れてstd::vector繰り返して値を見つけるだけで、パフォーマンスが向上する可能性があります。