Q:

map better than sparse vector?

I have 2 objects:
vector<string> v(999999);
map<int, string> m;

I need to store some index-string pairs, though it's very sparse (say only 20 pairs). I was wondering if the vector takes much more memory than map? If so, how much memory is vector taking up? And why is it bad to use vector in this case?

A:

Yes, the vector will take up at least 999999 * (sizeof(string) + C) + sizeof(vector) bytes in practice (where C is any dynamic allocation automatically performed by string).  The map will have overhead, but it definitely won't be anywhere near the order of 999999.

