順序付けされていない連想コンテナ（C++）

C++では、順序なし連想コンテナまたは順序なし連想コレクションは、ハッシュテーブルのバリアントを実装するC++ 標準ライブラリのクラステンプレートのグループです。テンプレートであるため、整数やカスタムクラスなどの任意の要素を格納するために使用できます。他のすべての標準ライブラリコンポーネントと同様に、名前空間に存在します。std

C++標準の現行版では、以下のコンテナが定義されています。

• std::unordered_set<T>
• std::unordered_map<K, V>
• std::unordered_multiset<T>
• std::unordered_multimap<K, V>。

これらのコンテナはそれぞれ、要素に課せられる制約のみが異なる。

std::unordered_setと はstd::unordered_multisetヘッダーで宣言され<unordered_set>、std::unordered_mapと はstd::unordered_multimapヘッダーで宣言されます<unordered_map>。

これらのコレクションには、名前空間std::pmr（ポリモーフィックなメモリ リソース用）にもバージョンがあります。これらのバージョンでは、オプションのテンプレート パラメーターAllocatorを として指定しますstd::pmr::polymorphic_allocator。

順序なし連想コンテナは、C++標準ライブラリの連想コンテナと似ていますが、制約が異なります。名前が示すように、順序なし連想コンテナ内の要素は順序付けられていません。これは、オブジェクトの格納にハッシュを使用しているためです。ただし、通常の連想コンテナと同様に、コンテナを反復処理することは可能です。

std::unordered_mapは、それぞれJavaのと、.NETの、またはRustのとstd::unordered_setに本質的に相当します。java.util.HashMapjava.util.HashSetSystem.Collections.Generic.DictionarySystem.Collections.Generic.HashSetstd::collections::HashMapstd::collections::HashSet

C++ 言語で最初に広く使われたハッシュテーブルの実装はhash_map、シリコングラフィックスhash_set( SGI)標準テンプレートライブラリhash_multimap(STL) のクラスhash_multisetテンプレートでした。^{[ 1 ]}その有用性から、後に他のいくつかの C++ 標準ライブラリの実装 (例えば、GNU コンパイラコレクション(GCC) のlibstdc++ ^{[ 2 ]}やVisual C++ (MSVC) 標準ライブラリ) にも含まれるようになりました。

クラステンプレートは、 C++テクニカルレポート1hash_* （C++ TR1）で提案され、という名前で採用されました。^{[ 3 ]}その後、 C++標準のC++11改訂版に組み込まれました。 ^{[ 4 ]} Boost C++ライブラリにも、として実装されています。^{[ 5 ]}unordered_*<boost/unordered_map.hpp>

コンテナは、コンテナ名と同じ名前のヘッダーファイルで定義されます。たとえば、unordered_setはヘッダーファイル で定義されます。すべてのコンテナは、コンテナの概念<unordered_set>の要件を満たしており、、 、、、、メソッドを備えています。begin()end()size()max_size()empty()swap()

でカスタムオブジェクトを使用するにはstd::unordered_map、カスタムハッシャーを定義する必要があります。この関数は、カスタム型への定数参照を受け取り、 を返しますsize_t。

import std ;using std :: hash ; struct Vector3 { int i ; int j ; int k ; };struct HashVector3 { size_t operator ()( const Vector3 & x ) const { return hash < int > ()( x . i ) ^ hash < int > ()( x . j ) ^ hash < int > ()( x . k ); } };

std::unordered_mapユーザー定義関数は、テンプレートパラメータとして渡すことで、そのまま使用できます。

unordered_map < Vector3 , int , HashVector3 > myPointToIntMap ;

または、特殊化することでデフォルトのハッシュ関数として設定できますstd::hash。

namespace std { template <> class hash < Vector3 > { public : size_t operator ()( const Vector3 & x ) const { return hash < int > ()( x . i ) ^ hash < int > ()( x . j ) ^ hash < int > ()( x . k ); } }; }//... unordered_map < Vector3 , int > myPointToIntMap ;

• シーケンスコンテナ（C++）
• 連想コンテナ（C++）