c++ - 以 std::string 为键的最有效关联容器？

Question

我在某处读到，对于当前的编译器，std::map 仍然是我们在 STL 中拥有的最高效的关联容器，即使是 std::unsorted_map ——从我在某处读到的，我不是确定在哪里 - 仅当有很多条目(例如超过 40k)时 find() 才会变得更有效率。

所以现在我不太确定了，因为我一直认为 HashMap 至少在字符串键的情况下更有效。

简而言之:

如果我必须选择一个具有未知条目数并以std::string 作为键的关联容器，那会是什么(至少在理论上)寻找更有效(速度)的选择？

Answer 1

个人资料，个人资料，个人资料......

将字符串作为键的问题是比较它们非常慢(想想 1000 个字符的字符串的最后一个字符的差异)。具有字符串键的 unordered_map 的优势至少部分来自于这样一个事实，即只有固定宽度的 hash 值必须进行比较，因此在实践中无序映射可能会快很多。

哈希实现可能会选择，例如，仅使用固定数量的分散数字来计算哈希值，从而最终将一些几乎相同的字符串放在同一个桶中，因此这是一种权衡。您可能会编造一组键值，这两个容器的性能都非常差，但对于“随机”或“典型”字符串集合，我的赌注是哈希容器。