47

を初期化したいと思いますstd::map。今のところ使用して::insertいますが、割り当てたいサイズが既にわかっているため、計算時間を無駄にしていると感じています。固定サイズのマップを割り当ててからマップを埋める方法はありますか?

4

5 に答える 5

50

いいえ、マップのメンバーは内部的にツリー構造に格納されています。保存するキーと値がわかるまで、ツリーを構築する方法はありません。

于 2012-10-24T12:43:45.317 に答える
25

簡単に言えば、はい、これは可能ですが、簡単ではありません。マップのカスタム アロケーターを定義する必要があります。基本的な考え方は、カスタム アロケータがマップ用に単一のメモリ ブロックを確保するというものです。マップには新しいノードが必要なため、アロケータは事前​​に割り当てられたブロック内のアドレスを単純に割り当てます。このようなもの：

std::map<KeyType, ValueType, std::less<KeyType>, MyAllocator> myMap;

myMap.get_allocator().reserve( nodeSize * numberOfNodes );

ただし、対処しなければならない問題がいくつかあります。

まず、各マップ ノードのサイズや、マップが実行する割り当ての数がよくわかりません。これらは内部実装の詳細です。実験して調べることはできますが、結果が異なるコンパイラ (または同じコンパイラの将来のバージョン) でも保持されるとは限りません。したがって、「固定」サイズのマップの割り当てについて心配する必要はありません。むしろ、あなたの目標は、必要な割り当ての数を一握りに減らすことです。

次に、削除をサポートしたい場合、この戦略はかなり複雑になります。

第 3 に、メモリ アラインメントの問題を忘れないでください。アロケータが返すポインタは、メモリに格納されるさまざまなタイプのオブジェクトに対して適切に配置されている必要があります。

そうは言っても、これを試す前に、それが必要であることを確認してください。メモリの割り当ては非常にコストがかかる可能性がありますが、それでもプログラムの問題であると想定すべきではありません。測定して調べます。また、事前割り当てをより自然に許可する代替戦略も検討する必要があります。たとえば、ソートされたリストまたは std::unordered_map です。

于 2012-10-24T14:13:12.683 に答える
3

これがあなたの質問に答えるかどうかはわかりませんが、Boost.Containerにはflat_mapスペースを予約できる があります。基本的に、これは (キー、値) ペアの並べ替えられたベクトルとして見ることができます。ヒント: 入力がソートされていることもわかっている場合は、insert とヒントを使用して最大のパフォーマンスを得ることができます。

于 2016-02-26T09:51:27.453 に答える
2

あなたはについて話しているblock allocators。しかし、実装するのは難しいです。そのような難しいことを考える前に測定してください。とにかくBoostには、ブロックアロケータの実装に関する記事がいくつかあります。または、すでに実装されている事前に割り当てられたマップStreeを使用します

于 2012-10-24T12:44:15.473 に答える