c++ - 映射比稀疏向量更好？

Question

我有 2 个对象：

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

我需要存储一些索引字符串对，尽管它非常稀疏（比如只有 20 对）。我想知道vector是否比map占用更多的内存？如果是这样，向量占用了多少内存？为什么在这种情况下使用向量不好？

Answer 1

是的，向量在实践中至少会占用999999 * (sizeof(string) + C) + sizeof(vector)字节（C任何动态分配都是由 自动执行的string）。map会有开销，但绝对不会接近 999999 的顺序。

Answer 2

如果查找时间绝对关键，我想你可以使用向量，因为它在向量上是常数，有效的指针算术，因为你已经知道索引，但随着地图上的大小（O（log n））增长。但是，对于这种权衡，情况确实很糟糕。

Answer 3

对于大约 20 个元素，创建具有 10^6 个元素的向量是没有意义的。使用地图将有更好的内存占用，甚至可能比矢量更快。您还可以考虑使用包含std::pair<int,std::string>键/值对的向量的混合方法，并对向量进行线性搜索（20 个元素非常少，足够少，您可以将成本视为常数，并且更简单的算法可能会补偿额外的操作数）。