c++ - c++ unordered_map 最大サイズが事前にわかっている場合、要素にメモリを事前に割り当てる方法はありますか

Question

予約/再ハッシュ関数は、挿入される要素(キー、値)のペアのメモリではなく、バケットの数を事前に割り当てるだけのようです。

要素にもメモリを事前に割り当てる方法はありますか?そのため、低レイテンシのアプリは動的なメモリ割り当てに時間を浪費する必要がありません。

Answer 1

1 つの可能性は、独自のアロケーターを作成することです。これは、テーブルに入る可能性のあるアイテムの数について少なくともかなりのアイデアがあり (したがって、それらすべてにスペースを事前に割り当てることができます)、次の場合にアイテムにスペースを再利用することを気にしない場合に特に効果的です。それらはテーブルから削除されます (したがって、簿記は簡単です)。

このような場合、基本的に N 個のオブジェクトにスペースを事前に割り当て、次のアイテムの割り当て位置を追跡するだけです。オブジェクトの割り当ては、次のように、アドレスを返し、ポインターをインクリメントするだけで構成されます。return *next++;

もちろん、これは動的割り当てを真に排除するものではありません。おそらく、おそらくもう気にしないほど安価になるだけです (また、テンプレート パラメータとして提供されるため、インラインで展開される可能性が高くなります)。 、そのため、プロセス内の関数呼び出しのオーバーヘッドも発生しません。

アロケーターの制限に我慢できない場合でも、固定サイズのオブジェクト用の汎用アロケーターは、通常、可変サイズのオブジェクト用のアロケーターよりも (少なくとも多少は) 高速です。それでも動的割り当てがなくなるわけではありませんが、速度が十分に向上し、目的に対してかなりうまく機能する可能性があります。