c++ - C++ stl unordered_map 実装、参照の妥当性

Question

std::mapとの両方についてstd::tr1::unordered_map、標準から次のことがわかります。

unordered_map コンテナー内の要素への参照は、再ハッシュ後でも、すべての場合で有効なままです。

彼らはどのようにそれを行っていますか（実装に関して）？彼らはすべてのエントリを一種のリンクされたリストとして維持していて、ハッシュテーブルは要素へのポインタを格納しているだけですか?

Answer 1

はい、あなたが提案する方法ではありませんが、リンクされたリストが関係しています。

2011 年の標準では (23.2.5 パラ 8)、「順序付けられていない連想コンテナーの要素はバケットに編成されます。同じハッシュ コードを持つキーは同じバケットに表示されます。」

各バケット内で、要素はリンクされたリスト (コンテナー全体の 1 つの大きなリストではなく、バケットごとに個別のリスト) にあります。コンテナーが再ハッシュされると、要素は新しいバケットに割り当てられますが、各要素へのポインターは有効なままです。新しい各バケット内のリンクされたリストは、最終的にそのバケット内にある既存の要素へのポインタから組み立てられます。

イテレーターは要素とそのバケットの両方へのポインターを保持する必要があるため、再ハッシュによってイテレーターが無効になります (そのため、1 つのバケットの最後の要素から次のバケットの最初の要素にステップすることができます)。要素ポインターは有効なままなので、既存のポインターと要素への参照は引き続き有効ですが、バケット ポインターは再ハッシュによって無効になるため、反復子は使用できません。

(順序付けされた連想コンテナーでサポートされる双方向イテレーターではなく、順序付けられていないコンテナーが順方向イテレーターのみをサポートするのもこのためです。各バケットの要素は単方向にリンクされたリストにあるため、それらを逆方向にステップ実行することはできません。)