unordered_mapを使用した場合のメモリ割り当て

Question

std::unordered_map<int,...>がほぼ同じサイズのままアイテムを継続的に追加および削除する場合、メモリを連続的に割り当てて解放したり、メモリをキャッシュして再利用しますか（プールやベクターなど）？ライブラリの近代的な標準MS実装を想定しています。

Answer 1

標準はこれらの側面に固有のものではないため、実装上定義されています。特に、あなたのようなキャッシングの動作は通常カスタムアロケータ（たとえばmemory pool allocator）を使用することで実現されるため、通常はコンテナの実装から切り離す必要があります。

順不同コンテナ約the standard, ~p874の関連ビット：

順不同連想コンテナの要素が バケットに編成されます。同じハッシュコードを持つキーは同じバケットに表示されます。 のバケット数は、要素が の順序付けられていない連想コンテナに追加されると自動的に増加し、バケットあたりの平均数は になります。

と挿入：

インサートとメンバーが イテレータの有効性に影響を及ぼさないもの据え付ける場合（N + N）Nは 内の要素の数である< = Zの*のB、挿入操作の前に、容器は、n個の要素 挿入の数は、Bは、コンテナのバケット数であり、zは、コンテナの 最大負荷率である

行間を読んで、イテレータの有効性には影響しないので、おそらくメモリの割り当ては行われません。これは決して保証されるものではありません（バケットデータ構造がリンクリストである場合は、イテレータを無効化せずに追加することができます）。標準では、要素が削除されたときに何が起こるべきかを指定していないようですが、上記の制約を無効にできないため、メモリを解放する理由は見当たりません。

具体的な実装方法を確認する最も簡単な方法は、ソースコードを読んでコードをプロファイルすることです。 また、rehashとresizeのメソッドを使用し、マップのload_factorを調整することで、この動作（実際に必要な場合）を制御することもできます。