在关键的情况下，使用 map 比 unordered_map 有什么优势吗?
最近关于 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.
因此问题是:对于像 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.)
相关文章