对于以下情况,哪一个是更好的stl map或unordered_map

Question

我试图比较stl map和stl unordered_map进行某些操作.我在网上看了一下,这只会增加我对哪一个整体更好的疑虑.所以我想根据他们执行的操作来比较这两者.

哪一个表现得更快

插入,删除,查找

哪一个占用更少的内存,更少的时间从内存中清除它.任何解释都热烈欢迎!

提前致谢

Answer 1

哪一个在插入,删除,查找中表现得更快？哪一个占用更少的内存,更少的时间从内存中清除它.任何解释都热烈欢迎!

对于特定用途,你应该尝试使用你的实际数据和使用模式,看看哪个实际上更快...有足够的因素,假设任何一个总是"赢"是危险的.

无序映射/散列表的实现和特性

在学术上 - 随着元素数量向无穷大方向增加,那些std::unordered_map(对于计算科学所称的"哈希映射"或"哈希表")的C++库提供的操作将倾向于继续花费相同的时间O (1)(忽略内存限制/缓存等),而对于std::map(平衡二叉树),每次元素数量加倍时,通常需要进行额外的比较操作,因此逐渐变慢O(log ₂ n ).

std::unordered_map实现必然使用开放散列:基本的期望是存在一个连续的"桶"数组,每个逻辑上都是任何值的容器.

它通常用于将散列表描绘为vector<list<pair<key,value>>>从向量元素到值的位置,当您按照存储在存储桶中的list-head-pointer到达初始列表节点时,至少有一个指针取消引用; 插入/查找/删除操作的性能取决于列表的大小,平均等于unordered_map's load_factor.

如果max_load_factor降低(默认值为1.0),那么在插入期间会有更少的冲突但更多的重新分配/重新散列以及更多的内存浪费(这可能会通过增加缓存未命中而损害性能).

这个最明显的unordered_map实现的内存使用涉及bucket_count()list-head-iterator /指针大小的桶的连续数组和每个键/值对的一个双链接列表节点.通常,bucket_count()+ 2*size()额外的开销指针,针对实现可能执行的动态内存分配请求大小的任何舍入进行调整.例如,如果要求100个字节,则可能会得到128或256或512.实现的动态内存例程也可能使用一些内存来跟踪已分配/可用的区域.

尽管如此,C++标准为实际实现留出了空间,可以做出一些自己的性能/内存使用决策.例如,在分配一个新的更大的阵列之后,它们可以将旧的连续桶阵列保持一段时间,因此可以逐步地将值重新组合到后者中,以便以平均情况性能为代价来降低最坏情况的性能.在操作期间咨询两个阵列.

地图/平衡二叉树的实现和特征

A map是二叉树,可以期望使用指针链接由不同调用返回的不同堆内存区域new.除了键/值数据,树中的每个节点都需要父指针,左指针和右指针(如果丢失,请参阅维基百科的二叉树文章).

对照

所以,无论是unordered_map和map需要与前通常有两个指针/迭代器的开销上/下一个节点联动分配的键/值对的节点,而后者具有三个父/左/右.但是,unordered_map另外还有针对bucket_count()桶的单个连续分配(== size()/ load_factor()).

对于大多数目的而言,内存使用量并没有显着差异,并且一个额外区域的释放时间差异不太可能引人注意.

另一种选择

对于这些场合,当容器的填充了前面然后重复搜索无需进一步插入/擦除,它有时可以最快使用排序矢量,搜索使用标准算法binary_search,equal_range,lower_bound,upper_bound.这具有单个连续内存分配的优点,其更加缓存友好.它总是表现优异map,但unordered_map可能仍然更快 - 如果你关心的话可以衡量.