我在某处读到,对于当前的编译器,std::map 仍然是我们在 STL 中拥有的最高效的关联容器,即使是 std::unsorted_map ——从我在某处读到的,我不是确定在哪里 - 仅当有很多条目(例如超过 40k)时 find() 才会变得更有效率。
所以现在我不太确定了,因为我一直认为 HashMap 至少在字符串键的情况下更有效。
简而言之:
如果我必须选择一个具有未知条目数并以std::string 作为键的关联容器,那会是什么(至少在理论上)寻找更有效(速度)的选择?
最佳答案
个人资料,个人资料,个人资料......
将字符串作为键的问题是比较它们非常慢(想想 1000 个字符的字符串的最后一个字符的差异)。具有字符串键的 unordered_map
的优势至少部分来自于这样一个事实,即只有固定宽度的 hash 值必须进行比较,因此在实践中无序映射可能会快很多。
哈希实现可能会选择,例如,仅使用固定数量的分散数字来计算哈希值,从而最终将一些几乎相同的字符串放在同一个桶中,因此这是一种权衡。您可能会编造一组键值,这两个容器的性能都非常差,但对于“随机”或“典型”字符串集合,我的赌注是哈希容器。
关于c++ - 以 std::string 为键的最有效关联容器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8789944/