在关键的情况下,使用 map 比 unordered_map 有什么优势吗?

2021-12-08 00:00:00 dictionary performance c++ unordered-map

最近关于 C++ 中 unordered_map 的讨论让我意识到我应该在大多数我之前使用 map 的情况下使用 unordered_map,因为查找的效率(摊销 O(1) 与 O(log n)).大多数时候我使用地图,我使用 intstd::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.

因此问题是:对于像 intstd::map 而不是 std::unordered_mapcode> 和 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.)

相关文章