c++ - STL C++ のコンテナー

Question

100 要素の場合、map、set、list、vector のどのコンテナーがメモリの最小スペースを占めるでしょうか? つまり、コンテナのマップ、セット、リスト、ベクトルに 100 個の要素を push_back すると、メモリ内のスペースが最も少ないのはどれでしょうか? たとえば、sizeof(int) は 4 バイト、sizeof(short) は 2 バイトです。問題は、このコンテナーのどれが最もメモリを消費しないかです (メモリのコストが最も低いことが私にとって最も重要です)。前もって感謝します。

Answer 1

通常、サイズに合わせて縮小するとvector、いくつかのポインターやカウンターを除いて、要素自体のスペース (およびアロケーターによって使用されるスペース) だけがスペース オーバーヘッドになるため、シーケンス コンテナーのスペース オーバーヘッドが最も低くなります。 、これはあなたが説明する STL コンテナーでは避けられないでしょう)。 map、set、およびlistすべては、追加された各要素に対する追加のポインターを保持します。(そして、 amapは、値の型とともにキーの型も保持する必要があります。) 衒学的なことを言うと、実際push_backには asetまたは amapに入ることができますが、それらに入ることができinsertます。

一方、vectorサイズに合わせて縮小されていない a は、通常、追加のコストを償却するために、必要なスペースの最大 2 倍 (一部の実装ではそれ以上) まで、通常は 1.5 程度過剰に割り当てられます。list、set、またはのようなノードベースのコンテナmapは通常そうではありません。

これが懸念される場合は、dequeユニットごとのオーバーヘッド (通常、要素ごとに 1 つのポインターよりもはるかに少ない) があるものの、オーバーアロケーションの制限がはるかに厳しく、順序。

vectorただし、通常、コンテナーのスペース オーバーヘッドは、 、set、list、またはなどのコンテナーを決定するために使用される主要な基準ではありませんmap。多くの場合、使用パターンの要件はより重要です。たとえば、一定時間内に任意の要素を削除できる必要があるか、イテレータや参照を無効にすることなく削除できる必要がありますか? もしそうなら、vector不適切です。イテレータや参照を無効にすることなく挿入/追加できる必要がありますか? もしそうなら、vector不適切です。効率的なルックアップが必要ですか (特に、挿入と削除が混在している場合)。もしそうなら、それlistは不適切であり、vectorシーケンスを再ソートすることが使用パターンで実行可能でない限り、おそらく不適切です。シーケンスの順序を制御する必要がありますか? もしそうなら、mapandsetはあなたのために要素を並べ替えますが、おそらく不適切です。