以下情况下，哪一个更好：stl map 还是 unordered_map？（涉及到 IT 技术）

Question

以下情况下，哪一个更好：stl map 还是 unordered_map？（涉及到 IT 技术）

c++visual-c++stl

5

我正在尝试比较STL map和STL unordered_map在某些操作中的表现。我在网上查了一下，但只是增加了我关于哪个整体更好的疑虑。因此，我希望从它们执行的操作的基础上比较这两者。

哪一个在以下方面的表现更快：

插入、删除、查找

哪一个占用更少的内存，并且清除内存所需的时间更短。欢迎任何解释！

谢谢！

- Anurag Sharma

1

一个通常具有对数复杂度，另一个具有常数（摊销）复杂度。你的键是什么数据类型？它的哈希函数有多快？ - ildjarn

@ildjarn 我正在寻找类型为字符串的键。 - Anurag Sharma

4个回答

3

之所以有这两种选择，是因为它们各有优劣。

可以使用任意一种。如果另一种对您的使用更好，请切换到另一种。

std::map提供更好的空间而时间较差。
std::unordered_map提供更好的时间而空间较差。

- Drew Dormann

@LokiAstari 我不认为这种权衡是标准保证的。一个实现是否能够提供比 map 更好内存使用的 unordered_map 是可以想象的吗？ - Andrew Durward

@AndrewDurward：是的，总有可能。但在一般情况下，您是在用空间换时间。 - Martin York

1

你的问题的答案很大程度上取决于你使用的特定STL实现。实际上，你应该查看你的STL实现文档 - 它可能会有很多关于性能的信息。

总的来说，根据cppreference.com的说法，maps通常被实现为red-black trees并支持时间复杂度为O(log n)的操作，而unordered_maps通常支持常数时间操作。cppreference.com对内存使用提供了很少的见解; 然而，另一个StackOverflow答案表明，相比unordered_maps，maps通常使用更少的内存。

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

- Benjamin Barenblat

2

你的问题的答案严重依赖于你所使用的STL实现。不是这样的。复杂性保证是标准所要求的，而不是可选的。 - Nicol Bolas

1

@NicolBolas：复杂度保证只是其中一部分——OP还问到了内存使用情况。 - ildjarn

4

复杂度的保证不到一半。实践中常数因素很重要。标准基本上对小集合和映射的性能没有什么说明。性能是复杂的。 - Jason Orendorff

@JasonOrendorff：小型集合/映射的性能不太可能成为瓶颈。大型集合/映射的性能则会成为瓶颈。因此，大O()符号对此非常有用。这使得常数因素变得不那么重要（少于一半）。复杂度保证超过一半。否则，如果它们像您所建议的那样重要，标准将会提到它们。 - Martin York

@LokiAstari 一个应用程序可能会使用许多小的集合和映射，它们的性能可能很重要。当然，在Python中，实际程序中绝大多数字典都相当小；以至于字典代码包含了针对小表的特殊性能优化技巧。 - Jason Orendorff

常数因子肯定很重要。“X和Y都是O(n log n)的，但是X比Y快了三十倍”这是一个常数因子的例子。标准没有为几个原因指定特定的常数因子；其中之一是这些常数因子取决于硬件和操作系统性能的细节，这已经超出了C++实现者的控制范围。 - Jason Orendorff

1

映射：

插入：

对于第一个版本（insert(x)），时间复杂度为对数级别。
对于第二个版本（insert(position,x)），一般情况下时间复杂度为对数级别，但如果x插入在position指向的元素之后，则平均常数时间复杂度。
对于第三个版本（insert(first,last)），一般情况下时间复杂度为Nlog(size+N)（其中N是first和last之间的距离，size是插入前容器的大小），但如果first和last之间的元素已经按照容器使用的相同排序准则排序，则时间复杂度为线性。

删除：

对于第一个版本（erase(position)），平均常数时间复杂度。
对于第二个版本（erase(x)），时间复杂度为对数级别。
对于最后一个版本（erase(first,last)），时间复杂度为对数级别加上first和last之间的距离的线性。

查找：

时间复杂度为对数级别。

无序映射：

插入：

单个元素插入： 1. 平均情况：常数时间。 2. 最坏情况：与容器大小成线性关系。

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

删除： 1. 平均情况：与删除的元素数量成线性关系（当只删除一个元素时为常数时间）。 2. 最坏情况：与容器大小成线性关系。

查找： 1. 平均情况：常数时间。 2. 最坏情况：与容器大小成线性关系。

了解这些，您可以根据实现类型决定使用哪种容器。

来源：www.cplusplus.com

- Rontogiannis Aristofanis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tony Delroy · Accepted Answer

“在插入、删除和查找方面，哪个更快？哪个占用的内存更少，从内存中清除所需的时间更短。欢迎任何解释！”

“对于特定的用途，您应该尝试使用实际数据和使用模式，并查看哪个实际上更快...有足够多的因素，危险的是假设其中一个总会“赢得”胜利。”

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

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

std::unordered_map的实现必须使用开放式哈希：基本期望是将有一个连续的"桶"数组，每个逻辑上都是任何值的容器。

通常将哈希表视为一个vector<list<pair<key,value>>>，其中从向量元素到值的获取涉及至少一个指针解引用，因为您跟随存储在桶中的列表头指针到初始列表节点；插入/查找/删除操作的性能取决于列表的大小，这平均等于unordered_map的load_factor。

如果降低max_load_factor（默认值为1.0），则会发生更少的冲突，但在插入期间会发生更多的重新分配/重新哈希和浪费内存（可能通过增加高速缓存未命中来损害性能）。

这个最显而易见的unordered_map实现的内存使用情况包括bucket_count()个列表头迭代器/指针大小的连续数组和每个键值对的一个双向链表节点。通常，会有bucket_count()+2*size()额外指针开销，根据实现可能会对动态内存分配请求大小进行舍入调整。例如，如果您请求100字节，则可能获得128、256或512字节。实现的动态内存例程可能还会使用一些内存来跟踪已分配/可用区域。

不过，C++标准为实际实现留出了一些性能/内存使用决策的余地。例如，它们可以在分配新的更大的数组后保留旧的连续桶数组，以便逐渐将值重新散列到后者中，从而减少最坏情况下的性能损失，但会牺牲平均情况下的性能，因为在操作期间需要同时查询两个数组。

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

map是一种二叉树，通常使用指针链接由不同的new调用返回的不同堆内存区域。除了键/值数据外，树中的每个节点还需要父、左和右指针（如果迷失，请参见维基百科的二叉树文章）。

比较

因此，无序unordered_map和map都需要为键/值对分配节点，前者通常具有两个指针/迭代器开销以进行prev/next-node链接，后者则具有三个指针以进行parent/left/right链接。但是，unordered_map还具有单个连续分配的bucket_count()桶（== size() / load_factor()）。

对于大多数目的来说，这在内存使用方面并没有明显的差异，而为一个额外区域释放内存的时间差异不太可能引起注意。

另一种选择

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