最近关于 C++ 中 unordered_map
的讨论让我意识到我应该在大多数我之前使用 map
的情况下使用 unordered_map
,因为查找的效率(摊销 O(1) 与 O(log n)).大多数时候我使用地图,我使用 int
或 std::string
作为键类型;因此,我对散列函数的定义没有任何问题.我想得越多,我就越意识到我找不到任何理由在 std::unordered_map
上使用 std::map
具有简单类型的键的情况——我查看了接口,并没有发现任何会影响我的代码的显着差异.
A recent talk about unordered_map
in C++ made me realize that I should use unordered_map
for most cases where I used map
before, because of the efficiency of lookup ( amortized O(1) vs. O(log n) ). Most times I use a map, I use either int
or std::string
as the key type; hence, I've got no problems with the definition of the hash function. The more I thought about it, the more I came to realize that I can't find any reason of using a std::map
over a std::unordered_map
in the case of keys with simple types -- I took a look at the interfaces, and didn't find any significant differences that would impact my code.
因此问题是:对于像 int这样的简单类型,是否有任何真正的理由使用
std::map
而不是 std::unordered_map
code> 和 std::string
?
Hence the question: is there any real reason to use std::map
over std::unordered_map
in the case of simple types like int
and std::string
?
我是从严格的编程角度提出问题的——我知道这不是完全被认为是标准的,并且可能会导致移植问题.
I'm asking from a strictly programming point of view -- I know that it's not fully considered standard, and that it may pose problems with porting.
此外,我希望正确的答案之一可能是它对较小的数据集更有效",因为开销较小(这是真的吗?)——因此我想将问题限制在密钥数量非平凡 (>1 024) 的情况下.
Also, I expect that one of the correct answers might be "it's more efficient for smaller sets of data" because of a smaller overhead (is that true?) -- hence I'd like to restrict the question to cases where the amount of keys is non-trivial (>1 024).
呃,我忘记了显而易见的(感谢 GMan!)——是的,地图当然是订购的——我知道这一点,正在寻找其他原因.
不要忘记 map
保持其元素有序.如果你不能放弃,显然你不能使用unordered_map
.
Don't forget that map
keeps its elements ordered. If you can't give that up, obviously you can't use unordered_map
.
还有一点要记住的是,unordered_map
通常使用更多的内存.map
只有几个管家指针,以及每个对象的内存.相反,unordered_map
有一个大数组(在某些实现中这些数组会变得非常大),然后每个对象都有额外的内存.如果您需要了解内存,map
应该会更好,因为它缺少大数组.
Something else to keep in mind is that unordered_map
generally uses more memory. map
just has a few house-keeping pointers, and memory for each object. Contrarily, unordered_map
has a big array (these can get quite big in some implementations), and then additional memory for each object. If you need to be memory-aware, map
should prove better, because it lacks the large array.
因此,如果您需要纯粹的查找-检索,我会说 unordered_map
是最佳选择.但总有取舍,如果你买不起,那么你就不能使用它.
So, if you need pure lookup-retrieval, I'd say unordered_map
is the way to go. But there are always trade-offs, and if you can't afford them, then you can't use it.
仅凭个人经验,我发现在主要实体查找表中使用 unordered_map
而不是 map
时,性能(当然是测量的)有巨大的改进.
Just from personal experience, I found an enormous improvement in performance (measured, of course) when using unordered_map
instead of map
in a main entity look-up table.
另一方面,我发现重复插入和删除元素要慢得多.它非常适合相对静态的元素集合,但是如果您要进行大量的插入和删除操作,散列 + 分桶似乎会加起来.(注意,这是经过多次迭代.)
On the other hand, I found it was much slower at repeatedly inserting and removing elements. It's great for a relatively static collection of elements, but if you're doing tons of insertions and deletions the hashing + bucketing seems to add up. (Note, this was over many iterations.)
这篇关于在关键的情况下,使用 map 比 unordered_map 有什么优势吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持跟版网!