[解決済み] std::unordered_mapの実装方法

引用された文章について。

いいえ、それはほとんどの一般的な用途のためのハッシュマップを実装する最も効率的な方法では全くありません。残念ながら、unordered_map の仕様における小さな見落としが、この動作を要求しているのです。要求される動作は、他の要素を挿入または削除するときに、要素へのイテレータが有効であり続けることです。

見落としはありません...行われたことは非常に意図的であり、十分な認識を持って行われました。 他の妥協点があったことは事実ですが、オープン ハッシュ/チェーン方式は一般的な使用における妥当な妥協点であり、平凡なハッシュ関数による衝突に合理的に対処でき、キー/値の型の大小にかかわらず無駄がなく、任意の数の insert / erase のペアを、多くの閉じたハッシュの実装のように、徐々にパフォーマンスを低下させることなく使用できます。

意識の証拠に Matthew Austernの提案はこちら :

私は、汎用的なフレームワークでオープンアドレッシングを満足に実装したものを知りません。オープンアドレッシングは多くの問題を提示します。

- 空いている位置と占められた位置を区別することが必要です。

- ハッシュテーブルをデフォルトコンストラクタを持つ型に限定し、すべての配列要素を前もって構築しておくか、あるいはその要素のいくつかがオブジェクトで他のいくつかが生のメモリである配列を維持することが必要である。

- オープンアドレッシングは衝突管理を難しくします。ハッシュコードがすでに占有されている場所にマップされる要素を挿入する場合、次に試す場所を指示するポリシーが必要です。これは解決済みの問題ですが、最もよく知られている解決策は複雑です。

- 要素の消去が許可されている場合、衝突管理は特に複雑です。(議論のために Knuth を参照してください。) 標準ライブラリのコンテナ クラスは、消去を許可する必要があります。

- オープンアドレッシングのための衝突管理スキームは、最大N個の要素を保持できる固定サイズの配列を仮定する傾向があります。標準ライブラリのコンテナクラスは、利用可能なメモリの限界まで、新しい要素が挿入されたときに必要に応じて大きくすることができるはずです。

これらの問題を解決することは興味深い研究プロジェクトかもしれませんが、C++のコンテキストでの実装経験がない場合、オープンアドレスのコンテナクラスを標準化することは不適切でしょう。

具体的には、バケットに直接格納できるほど小さなデータ、未使用のバケット用の便利なセンチネル値、および優れたハッシュ関数を持つ挿入専用のテーブルの場合、閉じたハッシュアプローチはおよそ1桁速く、劇的に少ないメモリを使用するかもしれませんが、これは汎用的ではありません。

ハッシュ テーブルの設計オプションとその意味の完全な比較と詳細な説明は、ここで適切に扱うには広すぎるため、S.O. のトピックからは外れています。