c++ - STL マップはどのように割り当てられますか? スタックまたはヒープ？

Question

mapC ++のSTLに連続したメモリがあるかどうか、またはメモリがヒープに割り当てられているかどうかを知りたいですか?

Answer 1

mapは動的コンテナであるため、その要素のメモリは動的に割り当てられます(それが何を意味するにせよ (構成可能なアロケータに依存します)!)。

さらに、mapはノードベースのコンテナーであるため、各要素は別個の別個の割り当てになります (最大のイテレーターと参照の非無効化を許可するため)。要素はほぼ確実にメモリ内で連続しておらず、追加した方法を反映して散在している可能性があります。

実際には、対数的なルックアップ、挿入、および削除時間を達成するために、マップはある種のバランスの取れたツリーとして実装されます。

(連続したストレージと対数検索時間を持つデータ構造が必要な場合は、並べ替えられたベクトルを検討してください。)

Answer 2

これはおそらく実装固有であり、STLコンテナのアロケータを変更することはできますが、これは気の弱い人向けではなく、使用している標準ライブラリのドキュメントを参照する必要があります。

いずれにせよ、マップは通常、赤黒木として実装され、ツリーノードはヒープ上にあります。

（私が正しく理解している場合、ツリーノードには、マップのキーと値のペアであるvalue_typeのインスタンスが含まれています）。

スタックは希少なリソースと見なされるべきであるため、スタックはどのコンテナにとっても悪いストレージのアイデアであることに注意してください。