C++のSTL unordered_mapの実装、参照妥当性

Question

、私は標準から見ていること：unordered_mapコンテナ内の要素への参照は、さえ焼き直した後、 すべての場合に有効なまま

。

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

Answer 1

はい、リンクリストが関係していますが、あなたの提案はあまりありません。

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

各バケット内では、要素はリンクされたリスト（各バケットの個別のリストであり、コンテナ全体の大きなリストではありません）にあります。コンテナが再ハッシュされると、要素は新しいバケットに割り当てられますが、各要素へのポインタは有効なままです。各新しいバケット内のリンクされたリストは、そのバケット内で終わる既存の要素へのポインタからアセンブルされます。

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

（順不同のコンテナが順方向の反復子をサポートしているのは、順序付きの関連コンテナでサポートされている双方向の反復子ではなく、それぞれのバケットの要素が単一リンクリストになっているためです。 ）