Bil*_*eal 3 c++ stl vector map
集合必须有多大才能使std :: map超过排序的std :: vector>？
我有一个系统,我需要几千个关联容器,并且std::map在CPU缓存方面似乎带来了很多开销.我听说过某些地方对于小型集合std :: vector可以更快 - 但我想知道那条线在哪里....
编辑:我在一个给定的结构中一次谈论5个项目或更少.我最担心的是执行时间,而不是存储空间.我知道像这样的问题本质上是特定于平台的,但我正在寻找一个"经验法则"来使用.
Billy3
这不是一个大小问题,而是使用问题.
当使用模式是您读取数据时,排序后的矢量运行良好,然后您在数据中进行查找.
当使用模式涉及修改数据(添加或删除项目)或对数据进行查询时或多或少的任意混合时,映射很有效.
原因很简单:映射在单个查找上的开销较高(感谢使用链接节点而不是单片存储块).然而,维持顺序的插入或删除具有仅O(lg N)的复杂度.保持向量中的顺序的插入或删除具有O(N)的复杂度.
当然,还有各种混合结构也可以考虑.例如,即使数据是动态更新的,您通常也会从大量数据开始,并且每次都会进行相对较少的更改.在这种情况下,您可以将数据加载到内存中,形成一个已排序的向量,并将(少量)添加的对象保存在单独的向量中.由于第二个向量通常非常小,所以您根本不需要对它进行排序.当/如果它变得太大,你将它排序并将其与主数据集合并.
Edit2 :(响应有问题的编辑).如果你说的是5件或更少,你可能最好忽略以上所有.只需保留未排序的数据,然后进行线性搜索.对于这个小的集合,线性搜索和二分搜索之间实际上几乎没有区别.对于线性搜索,您希望平均扫描一半项目,进行~2.5次比较.对于二进制搜索,你说的是log 2 N,(如果我的数学工作在早上的这个时间)可以达到~2.3 - 关注或注意的差异太小(事实上,二进制搜索已经足够的开销,它可以很容易地结束更慢).
| 归档时间： |
|
| 查看次数： |
1832 次 |
| 最近记录： |