5

我正在尝试比较某些操作的 stl map 和 stl unordered_map。我在网上看了看，它只会增加我对哪个整体更好的怀疑。所以我想根据它们执行的操作来比较两者。

哪一个执行得更快

插入、删除、查找

哪一个需要更少的内存和更少的时间来从内存中清除它。任何解释都受到热烈欢迎！

提前致谢

4

4 回答 4

13

哪一个在插入、删除、查找中执行得更快？哪一个需要更少的内存和更少的时间来从内存中清除它。任何解释都受到热烈欢迎！

对于特定用途，您应该尝试使用您的实际数据和使用模式，看看哪个实际上更快......有足够的因素假设任何一个总是“获胜”是很危险的。

无序映射/哈希表的实现和特点

学术上——随着元素的数量向无穷大增加，在std::unordered_map（这是 C++ 库提供的计算科学术语“哈希图”或“哈希表”）上的操作将倾向于继续花费相同的时间 O （1）（忽略内存限制/缓存等），而对于std::map（平衡二叉树），每次元素数量翻倍时，它通常需要进行额外的比较操作，因此它会逐渐变慢 O(log 2 n ）。

std::unordered_map实现必须使用开放散列：基本期望是会有一个连续的“桶”数组，每个在逻辑上都是散列到其中的任何值的容器。

它通常用于将哈希表描述为vector<list<pair<key,value>>>从向量元素到一个值的位置，当您跟随存储在存储桶中的列表头指针到初始列表节点时，至少需要一个指针解引用；插入/查找/删除操作的性能取决于列表的大小，平均等于unordered_map's load_factor。

如果max_load_factor降低 （默认值为 1.0），那么在插入过程中会发生更少的冲突，但会发生更多的重新分配/重新散列，并且会浪费更多的内存（这会通过增加缓存未命中来损害性能）。

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

尽管如此，C++ 标准还是为现实世界的实现留出了空间，让他们自己做出一些性能/内存使用决策。例如，他们可以在分配一个新的更大的数组后将旧的连续桶数组保留一段时间，因此可以逐渐将值重新散列到后者中，以降低最坏情况下的性能，但会以平均情况性能为代价在操作期间会咨询这两个阵列。

map/平衡二叉树的实现和特点

Amap是一棵二叉树，可以预期使用指向不同调用返回的不同堆内存区域的指针new。除了键/值数据，树中的每个节点都需要父、左和右指针（如果丢失，请参阅维基百科的二叉树文章）。

比较

因此，两者都unordered_map需要map为键/值对分配节点，前者通常具有两个指针/迭代器开销用于上一个/下一个节点链接，而后者具有三个用于父/左/右。但是，unordered_map它还具有用于存储桶的单个连续分配bucket_count()(== size()/ load_factor())。

对于大多数用途而言，内存使用量的差异并不大，而且一个额外区域的释放时间差异不太可能引起注意。

另一种选择

对于容器预先填充然后重复搜索而没有进一步插入/擦除的情况，有时使用排序向量可能是最快的，使用标准算法搜索binary_search, equal_range, lower_bound, upper_bound。这具有单个连续内存分配的优点，这对缓存更加友好。它总是优于map，但unordered_map可能仍然更快 - 如果您关心，请衡量。

于 2012-09-12T02:14:41.040 回答
3

两者兼有的原因是两者都不是整体更好。

使用任何一个。如果另一个证明更适合您的使用，请切换。

  • std::map 为更糟糕的时间提供了更好的空间。
  • std::unordered_map 为更差的空间提供了更好的时间。
于 2012-09-12T02:00:03.740 回答
1

您的问题的答案在很大程度上取决于您使用的特定 STL 实现。确实，您应该查看您的 STL 实现的文档——它可能包含大量有关性能的信息。

不过一般来说，根据 cppreference.com，地图通常实现为红黑树并支持时间复杂度为 O(log n) 的操作，而unordered_maps通常支持恒定时间操作。cppreference.com 几乎没有提供关于内存使用情况的信息；但是，另一个 StackOverflow 答案表明地图通常比 unordered_maps 使用更少的内存。

对于带有 Visual Studio 2012 的 STL 实现 Microsoft 包，看起来map在摊销 O(log n) 时间内支持这些操作，而unordered_map在摊销常数时间内支持它们。但是，文档没有明确说明内存占用。

于 2012-09-12T01:44:49.460 回答
1

地图：

插入：

  1. 对于第一个版本（ insert(x) ），对数。
  2. 对于第二个版本（ insert(position,x) ），通常是对数，但如果 x 插入到 position 指向的元素之后，则为摊销常数。
  3. 对于第三个版本（ insert (first,last) ），通常为 Nlog(size+N) （其​​中 N 是 first 和 last 之间的距离，并且 size 是插入前容器的大小），但如果元素之间是线性的first 和 last 已经根据容器使用的相同排序标准进行排序。

删除：

  1. 对于第一个版本（擦除（位置）），摊销常数。
  2. 对于第二个版本（ erase(x) ），容器大小的对数。
  3. 对于最后一个版本（erase(first,last)），容器大小的对数加上第一个和最后一个之间的距离的线性。

抬头：

  1. 大小为对数。

无序地图：

插入：

  1. 单元素插入：
    1. 平均情况：恒定。
    2. 最坏的情况：容器大小呈线性关系。
  2. 多个元素插入：
    1. 平均情况：与插入的元素数量呈线性关系。
    2. 最坏情况：N*(size+1)：插入的元素数乘以容器大小加一。

删除：

  1. 平均情况：移除的元素数量呈线性关系（仅移除一个元素时保持不变）
  2. 最坏情况：容器大小呈线性关系。

抬头：

  1. 平均情况：恒定。
  2. 最坏的情况：容器大小呈线性关系。

知道了这些，你就可以根据实现的类型来决定使用哪个容器了。

来源：www.cplusplus.com

于 2012-09-13T15:34:26.823 回答