我目前有一些我正在使用的vector代码pair<string,string>。这用于存储来自 XML 解析的一些数据，因此，该过程在某些地方非常缓慢。vector<pair<string,string> >在尝试加快整个过程方面，我想知道从 切换到是否会有任何性能优势std::map<string,string>？我可以对其进行编码并运行分析器，但我想我会看看我是否能得到一个答案，首先表明一些明显的性能提升。我不需要进行任何排序，我只需将项目添加到向量中，然后在稍后阶段迭代内容并进行一些处理 - 我不需要排序或任何类似性质的东西。我猜也许我不会获得任何性能提升，但我从未真正使用过std::map之前所以我不知道没有询问或编码。
问问题
3028 次
5 回答
11
不。如果（如您所说）您只是在集合上进行迭代，您会看到使用std::map.
映射用于通过其键访问值。如果您从不这样做，那么 map 对于容器来说是一个糟糕的选择。
于 2012-10-02T18:38:46.460 回答
6
如果您不修改您的vector<pair<string,string> >- 只是一遍又一遍地迭代它 - 您将使用map. 这是因为典型map是用对象的二叉树组织的，每个对象都可以分配在不同的内存块中（除非您编写自己的分配器）。此外，每个节点都map管理指向相邻对象的指针，因此也需要时间和内存开销。但是，按键搜索是 O(log) 操作。另一方面，vector将数据保存在一个块中，因此处理器缓存通常感觉更好。在向量中搜索实际上是 O(N) 操作，不是很好但可以接受。可以使用 lower_bound 等函数将排序向量中的搜索升级到 O(log)。
这取决于您对这些数据执行的操作。如果您进行多次搜索 - 可能最好使用散列容器，unordered_map因为在此容器中按键搜索是 O(1) 操作。如前所述，迭代vector更快。
可能值得string在您的pair.
于 2012-10-02T18:47:54.453 回答
5
答案取决于您对这些数据结构所做的工作以及它们的大小。如果您有数千个元素，并且您不断地反复std::vector<std::pair<std::stringm std::string> >搜索元素，则使用 a可能会提高性能（您可能要考虑将其用于此用例）。如果您的向量相对较小，并且您不经常尝试将元素插入中间，那么使用向量可能会更快。如果你只是迭代元素，向量比映射要快得多：迭代并不是它们的真正优势之一。地图擅长查找事物，假设元素的数量并不小，否则对向量的线性搜索仍然更快。firststd::map<std::string, std::string>std::unordered_map<std::string, std::string>
确定时间花在哪里的最好方法是分析代码：通常并不完全清楚时间花在哪里。通常，可疑热点实际上是没有问题的，而其他区域则显示出意想不到的性能问题。例如，您可能将您的对象传递给我的值，而不是在某个不起眼的地方通过引用。
于 2012-10-02T18:45:54.627 回答
1
如果您的使用模式是在执行任何查找之前执行许多插入，那么您可能会受益于实现元素按需排序的“惰性”映射（即，当您获取迭代器、执行查找等时）。
于 2012-10-02T18:49:54.677 回答
0
正如 C++ 所说std::vector的对线性内存中的项目进行排序，所以首先它分配一个具有初始容量的内存块，然后当你想将新项目插入向量时，它会检查它是否有更多空间，如果没有，它将分配一个新的缓冲区有更多空间，将所有项目复制到新缓冲区中，然后删除源缓冲区并将其设置为新缓冲区。
当您刚开始将项目插入vector其中并且有很多项目时，您会遭受过多的重新分配、复制构造和析构函数调用。
为了解决这个问题，如果你现在计算输入项（不精确，但它通常的长度），你可以reserve为向量提供一些内存并避免重新分配和所有事情。如果您不知道大小，您可以使用像std::list女巫这样的集合，永远不要重新分配其内部项目。
于 2012-10-02T18:57:35.647 回答