C++のハッシュテーブル?

Question

私は通常、特定のタイプの値 (キー値 - 例:文字列または他のオブジェクト)。stdlib マップの実装は、標準の配列または stdlib ベクトルよりも優れたパフォーマンス (O(log n)) を提供するツリーに基づいています。

私の質問は、さらに優れたパフォーマンス (O(1)) を提供する C++ の「標準」ハッシュテーブル実装をご存知ですか?Java API の Hashtable クラスで利用できるものと似たもの。

Answer 1

C++11 を使用している場合は、 <unordered_map> そして <unordered_set> ヘッダー。これらはクラスを提供します std::unordered_map そして std::unordered_set.

TR1 で C++03 を使用している場合は、クラスにアクセスできます。 std::tr1::unordered_map そして std::tr1::unordered_set, 、同じヘッダーを使用します (GCC を使用している場合を除きます。その場合、ヘッダーは <tr1/unordered_map> そして <tr1/unordered_set> その代わり）。

すべての場合において、対応するものがあります unordered_multimap そして unordered_multiset タイプも。

Answer 2

unowned_map または unowned_set をまだ持っていない場合、それらは次の一部です。 ブースト.
両方のドキュメントは次のとおりです.

Answer 3

があります ハッシュマップ ここで多くの人が言及しているオブジェクトですが、stl の一部ではありません。これは SGI 拡張機能なので、STL で何かを探していた場合は、運が悪いと思います。

Answer 4

std::tr1::unowned_map、内 <unordered_map>

TR1をお持ちでない場合は、ブーストを取得し、boost :: unordered_mapを使用してください <boost/unordered_map.hpp>

Answer 5

Visual Studioにはクラスがあります stdext::hash_map ヘッダーにある <hash_map>, 、gcc にはクラスがあります __gnu_cxx::hash_map 同じヘッダー内にあります。

Answer 6

見る std::hash_map SGIから。

これは、 STLポート 配布も。

Answer 7

hash_map は GNU でもサポートされています libstdc++.

ディンカムウェアも サポートします これは、多くの実装に hash_map があることを意味します (Visual C++ でも Dinkumware で提供されると思います)。

Answer 8

コンパイラで利用可能な TR1 拡張機能がある場合は、それを使用してください。そうでない場合は、std:: を除いて、boost.org によく似たバージョンがあります。名前空間。その場合は、using 宣言を入れて std:: に切り替えられるようにします。後で。

Answer 9

std::hash_map