c++ - map 在什么尺寸下比 vector 更好？

Question

我有一个对象集合，每个对象都有一个标识符(字符串)。现在我想知道我应该将它们存储为 vector 还是 map ，所以 std::vector<cObject>或 std::map<std::string,cObject> .每个名称只能使用一次，因此我需要检查 vector/ map 是否出现了给定名称。使用 map 时，我将使用 find() 以对数方式缩放，而对于 vector ，我将迭代并测试 oObject.name == newname直到我找到名字或到达结尾，它是线性扩展的。映射的一个缺点是名称存储了两次，一次在对象内部，一次作为键。

虽然对于大型 vector/ map ， map 总是会获胜，但我想知道在什么情况下会出现这种情况，因为如果我只有最多 10 个对象要存储， map 似乎有点过分了。

这引出了我的问题:与普通 vector 相比， map 在什么时候变得有利(关于性能)？如果预期的对象数量约为 10、100、1000 甚至更大，我是否应该考虑使用 map ？我承认这个问题比较模糊，但我还是希望能得到一些建议，以了解何时使用哪个容器。

Answer 1

很难预测 map 比 vector 更有利的大小。但有几点您可以考虑:

1. map 基本上是作为二叉树实现的，而 vector 是作为数组实现的。因此，当有 10 到 12 个元素时，迭代数组 for let says 相对容易，因为这将是线性搜索。
2. map 比 vector 快这一点取决于处理器上的实现以及您尝试在其中存储的数据。我最好的猜测是，对于 5-20 个元素， map 会更快。(但这只是一个猜测，我建议您为自己创建一个基准)
3. “默认情况下，需要容器时使用 vector ”- Bjarne Stroustrup。

您可能还会找到这个 C++ Containers Cheat Sheet有用