在平凡的密钥的情况下，是否有使用map over unordered_map的优点？ [英] Is there any advantage of using map over unordered_map in case of trivial keys?

问题描述

最近在C ++中关于 unordered_map 的讨论让我意识到，对于大多数情况下，我应该使用 unordered_map 之前使用 map ，因为查找的效率（分摊O（1）与 O（log n） ）。大多数时候，我使用地图我使用 int 或 std :: strings 作为键，因此我哈希函数的定义没有问题。我想到的越多，我越来越意识到，我找不到任何使用 std :: map 的原因，以便在 unordered_map - 我看了接口，没有发现会影响我的代码的任何重大差异。

所以问题 - 是否有真正的理由使用 std :: map over 无序地图在简单类型如 int 和 std :: string ？

我从一个严格的编程角度来询问 - 我知道这不是完全被认为是标准的，它可能会导致移植问题。

另外，我期望正确的答案之一可能是对于较小的数据集更有效，因为较小的开销这是真的吗？） - 因此，我想将问题限制在密钥数量不重要的情况下（> 1 024）。

编辑： 呃，我忘了这个明显的（感谢GMan！） - 是的，地图当然是有序的 - 我知道，正在寻找其他原因。

解决方案

不要忘记映射保留其元素的顺序。如果你不能放弃，显然你不能使用 unordered_map 。

还有什么要保留记住， unordered_map 通常使用更多的内存。一个地图只是有几个内存指针，然后是每个对象的内存。相反， unordered_map 有一个大数组（这些可以在一些实现中获得相当大的数量），然后为每个对象增加一个内存。如果您需要具有内存感知功能，那么映射应该证明更好，因为它缺少大数组。

所以，如果你需要纯查询检索，我会说一个 unordered_map 是要走的路。但总是有折衷的，如果你买不起，那么你不能使用它。

从个人经验来看，我发现了一个巨大的进步在主实体查找表中使用 unordered_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's or std::strings as keys, 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 in case of simple types over a unordered_map -- I took a look at the interfaces, and didn't find any significant differences that would impact my code.

Hence the question - is there any real reason to use std::map over unordered map in 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.

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).

Edit: duh, I forgot the obvious (thanks GMan!) -- yes, map's are ordered of course -- I know that, and am looking for other reasons.

解决方案

Don't forget the map's keep their elements ordered. If you can't give up that, obviously you can't use an unordered_map.

Something else to keep in mind is that unordered_map's generally use more memory. A map just has a few house-keeping pointers then memory for each object. Contrarily, unordered_map's have 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, a map should prove better, because it lacks the large array.

So, if you need pure lookup-retrieval, I'd say an 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.

Just from personal experience, I found an enormous improvement in performance (measured, of course) when using an unordered_map instead of a 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 over unordered_map的优点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！