c++ - まばらなベクトルよりもよくマップしますか?

Question

私は2つのオブジェクトを持っています:

vector<string> v(999999);
map<int, string> m;

非常にまばらですが、いくつかのインデックスと文字列のペアを保存する必要があります (たとえば、20 ペアのみ)。vectorがmapよりもはるかに多くのメモリを消費するかどうか疑問に思っていましたか? もしそうなら、ベクトルはどのくらいのメモリを占有していますか? そして、この場合にベクトルを使用するのはなぜ悪いのでしょうか?

Answer 1

はい、ベクトルは実際には少なくとも999999 * (sizeof(string) + C) + sizeof(vector)バイトを占有します (C動的割り当ては によって自動的に実行されますstring)。オーバーヘッドは発生しますが、999999のmapオーダーには絶対に近づきません。

Answer 2

ルックアップ時間が絶対に重要な場合は、ベクターを使用できると思います。これは、ベクターでは一定であるため、インデックスが既にわかっているため効果的にポインター演算ですが、マップのサイズに応じて大きくなります (O(log n))。ただし、そのようなトレードオフのためには、状況は本当に悲惨である必要があります。

Answer 3

約 20 要素の場合、10^6 要素のベクトルを作成しても意味がありません。マップを使用すると、メモリ フットプリントが大幅に改善され、ベクトルよりも高速になる場合もあります。std::pair<int,std::string>また、キーと値のペアを保持するベクトルを使用して混合アプローチを検討し、ベクトルで線形検索を実行することもできます (20 個の要素は非常に少なく、コストを一定と見なすことができるほど少なく、単純なアルゴリズムはおそらく追加の操作数)。