stl map和unordered_map的区别 [英] stl map and unordered_map difference

问题描述

我想了解C ++中map和unordered_map之间的主要区别。





我想使用哪一个和哪一个最好？

i want to understand that major difference between map and unordered_map in C++.


which one i suppose to use and which one is best?

推荐答案

有序地图通常是在有序树的基础上实现的，例如STL案例中的红黑树。树操作相对昂贵，但树使用的存储空间很小。



无序地图通常实现为哈希表;较新的STL实现也提供了这样的地图。哈希表非常快，但有一些存储开销，只能在它们效率低下之前增长到一定数量的节点。



所以如果你有一组值您可以为其估算最大节点数，并且无需以有序方式迭代节点，无序地图通常是最佳选择。在所有其他情况下，您最好使用有序（基于树）的地图。



[修改 - pasztorpisti的评论]



根据场景和使用中的分配器，树可以极大地分段内存，而简单但有效的散列映射只有2个阵列。大多数时候我只使用散列图和一种特殊的有序映射（构建在有序集之上），这是一个总是排序的数组。根据不同操作的频率和项目数量，树木可能会成为更好的解决方案，但在我看来这是相对罕见的。

An ordered map is usually implemented on the basis of an ordered tree, for example red-black-tree in STL's case. Tree manipulations are relatively expensive, but the tree uses very little storage.

An unordered map is usually implemented as a hash table; the newer STL implementation offer such a map as well. Hash table are very fast, but have some storage overhead and can only grew to a certain number of nodes before they become inefficient.

So if you have a set of values for which you can estimate the maximum number of nodes and for which you don't need to iterate through the nodes in an ordered fashion, the unordered map is usually the best choice. In all other cases you better use an ordered (tree-based) map.

[AMENDMENT - A comment by pasztorpisti]

Depending on the scenario and the allocators in use trees can extremely fragment memory while a simple yet effective hashmap is only 2 arrays. Most of the time I use only hashmaps and a special kind of ordered map (built on top of an orderedset) that is an array that is always sorted. Depending on the frequency of different operations and the number of items trees may become the better solution but in my opinion that is relatively rare.

使用Google [ ^ ]？

map：



- 通常使用红黑树实现。

- 元素排序。

- 相对较小的内存使用量（哈希表不需要额外的内存。）

- 相对较快的查找：O（log N）。



unordered_map：



- 通常使用哈希表实现。

- 元素未排序。

- 需要额外的内存保持哈希表。

- 快速查找O（1），但是常量时间取决于has h函数可能相对较慢。



refrence：（ http://learninger.com [ ^ ]）

这篇关于stl map和unordered_map的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！