使用std :: map而不是vector <pair <string,string >>>我会看到性能提升吗？

Question

我目前有一些代码,我使用的vector是pair<string,string>.这用于存储来自XML解析的一些数据,因此,该过程在某些地方非常慢.在试图加快整个过程中,我想知道是否有将是从交换任何性能方面的优势vector<pair<string,string> >来std::map<string,string>？我可以编写代码并运行一个分析器,但我想我会看到我是否能得到一个答案,表明首先会有一些明显的性能提升.我不需要进行任何排序,我只是将项添加到向量中,然后在稍后阶段迭代内容并进行一些处理 - 我不需要排序或任何这种性质.我猜也许我不会获得任何性能提升,但我从来没有真正使用过std::map,所以我不知道没有要求或编码全部.

Answer 1

不.如果(正如你所说)你只是迭代集合,你会看到一个小的(可能是不可测量的)性能降低使用a std::map.

地图用于通过其键访问值.如果你从不这样做,那么map对于容器来说是一个糟糕的选择.

Answer 2

如果你没有修改你的vector<pair<string,string> >- 只是一遍又一遍地重复 - 你将通过使用来降低性能map.这是因为典型map的对象是二进制树,每个对象都可以分配在不同的内存块中(除非你自己编写分配器).另外,每个节点都map管理指向邻居对象的指针,因此也是时间和内存开销.但是,按键搜索是O(log)操作.另一方面,vector将数据保存在一个块中,因此处理器缓存通常会感觉更好.在向量中搜索实际上是O(N)操作,这不是很好但可以接受.可以使用lower_bound等函数将已排序的向量中的搜索升级到O(日志).

这取决于您对此数据所做的操作.如果你做了很多搜索 - 可能最好使用散列容器,unordered_map因为在这个容器中按键搜索是O(1)操作.如上所述,迭代vector更快.

可能值得替换string你的pair,但这在很大程度上取决于你在那里持有什么以及如何访问容器.

Answer 3

答案取决于您对这些数据结构的处理方式以及它们的大小.如果您有数千个元素std::vector<std::pair<std::stringm std::string> >并且一直在不断地搜索first元素,则使用a std::map<std::string, std::string>可以提高性能(您可能需要考虑使用std::unordered_map<std::string, std::string>此用例).如果你的向量相对较小并且你不想过于频繁地将元素插入中间,那么使用向量可能会更快.如果你只是迭代元素,矢量比地图快很多:迭代并不是他们的力量之一.地图擅长查找,假设元素的数量不是很小,因为否则对矢量的线性搜索仍然更快.

确定花费时间的最佳方法是对代码进行分析:在预先花费时间的情况下,通常并不完全清楚.通常,可疑的热点实际上没有问题,其他区域显示出意想不到的性能问题.例如,您可能会将对象传递给我的值,而不是通过引用传递给某个不起眼的地方.