代码之家 › 专栏 › 技术社区 › Johann Gerell

在std::map和std::unordered_map之间选择[重复]

unordered-map map hash c++11 c++

125

Johann Gerell · 技术社区 · 14 年前

这个问题已经有了答案:

Is there any advantage of using map over unordered_map in case of trivial keys? 12答

既然 std 有一个真正的哈希图 unordered_map ,为什么(或什么时候)我还想使用好的旧的 map 结束 无序映射 在实际存在的系统上?有什么明显的情况我看不见吗?

5 回复 | 直到 8 年前

103

Community CDub 7 年前

AS already mentioned , map 允许按排序方式迭代元素,但 unordered_map 没有。这在许多情况下非常重要,例如显示集合(例如通讯簿)。这也以其他间接方式表示,例如:(1)从返回的迭代器开始迭代 find() 或(2)成员函数的存在,如 lower_bound() .

另外,我认为 最坏情况 搜索复杂性。

为了 地图 ,是O(lg n)
为了 无序映射 ,它是O(N)[这个可以当哈希函数不好导致太多哈希冲突时发生。]

同样适用于 最坏情况 删除复杂性。

Emil Laine 9 年前

除上述答案外,您还应注意,仅仅因为 unordered\u map is constant speed( o(1) )并不意味着它比 map (of order log(n) )。常数可能大于 log(n). 尤甚,因为 n. is limited by 2 ^{32 ^{(or 2 ^{64 ^).}}}


   
    
     
      
       
        
         
          
           因此,除了其他答案(
           
            map
            
             maintained order and hash functions may be difficuble)之外,可能是
             
              map
              
               is more performant.
              
             
            
           
          
          
           
            
             
              
              
             
            
           
          
          
           
            
             
              
               例如,在一个程序中,我运行了一个
               
                blog post
               
               
                I saw that for vs10
                
                 std::unordered_map
                 
                  was slower than
                  
                   std::map
                   
                    (虽然
                    
                     boost::unordered_map
                     
                      was faster than both.)。
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
          
           
            
             
              
               
                
                 
                  
                   
                    
                     
                      
                     
                     
                      注意第3到第5条。
                     
                     
                      埃克斯顿
                      
                       unordered_map
                      
                      是恒定速度(
                      
                       O(1)
                      
                      )并不意味着它比
                      
                       map
                      
                      (指秩序)
                      
                       log(N)
                      
                      )常数可能大于
                      
                       日志(n)
                      
                      尤其是自
                      
                       N
                      
                      受2限制
                      ^三十二
                      (或2)
                      ^六十四
                      )
                     
                     
                      所以除了其他答案(
                      
                       地图
                      
                      维护顺序和散列函数可能很困难)。
                      
                       地图
                      
                      更具表现力。
                     
                    
                   
                  
                 
                
               
              
              
               
                
                 
                  
                   例如,在一个程序中,我为
                  
                  
                   blog post
                  
                  我在VS10上看到的
                  
                   std::unordered_map
                  
                  比
                  
                   std::map
                  
                  (尽管
                  
                   boost::unordered_map
                  
                  比两者都快)。
                 
                 
                  
                 
                 
                 
                 
                  注意第3到第5条。

Community CDub 7 年前

_{这是因为谷歌的钱德勒·卡拉斯

CppCon 2014 lecture}

std::map 对于以性能为导向的工作来说(很多人认为)是不有用的:如果你想要O(1)-分期访问,使用一个适当的关联数组(或者缺少一个, std::unorderded_map );如果需要排序的顺序访问,请使用基于向量的方法。

也, STD::地图 是一棵平衡的树;你必须穿过它,或者重新平衡它,难以置信的频繁。这些分别是缓存杀手和缓存天启操作…所以说不 STD::地图 .

你可能对 this SO question 在高效的哈希图实现上。

(PS) std::unordered_map 缓存不友好,因为它使用链接列表作为存储桶。)

Ken Bloom 14 年前

我想很明显你会用 std::map 您需要按排序顺序迭代映射中的各个项。

当您希望编写比较运算符(直观的)而不是哈希函数(通常非常不直观)时,也可以使用它。

Martin G 8 年前

比如说你有很大的钥匙,也许还有大串。要为大字符串创建哈希值,需要从头到尾遍历整个字符串。它至少需要线性时间到键的长度。但是,当您仅使用 > 当发现第一个不匹配时,每个字符串比较都可以返回键的运算符。对于大型字符串来说,这通常是非常早的。

这种推理可以应用于 find 功能 std::unordered_map 和 std::map . 如果键的性质使得生成哈希需要更长的时间(在 标准:无序地图 )比使用二进制搜索(在 STD::地图 ,应该可以更快地在 STD::地图 . 很容易想到这样的场景,但我相信在实践中它们是非常罕见的。