插入到std :: unordered_map在MSVC++的STL中调​​用哈希函数两次,设计不好还是特殊原因？

Question

对于此代码:

#include<unordered_map>
#include<iostream>
using namespace std;
struct myhash {
    unsigned operator()(const unsigned&v)const {
        cout<<"Hash function is called:"<<v<<endl;
        return v;
    }
};
unordered_map<unsigned,unsigned,myhash>mp;
int main() {
    for (unsigned i=0;i<3;++i) {
        cout<<"Visiting hash table:"<<i<<endl;
        ++mp[i];
    }
}

使用g ++时,输出并不奇怪:

Visiting hash table:0
Hash function is called:0
Visiting hash table:1
Hash function is called:1
Visiting hash table:2
Hash function is called:2

但MSVC++(2015)的输出震惊了我:

Visiting hash table:0
Hash function is called:0
Hash function is called:0
Visiting hash table:1
Hash function is called:1
Hash function is called:1
Visiting hash table:2
Hash function is called:2
Hash function is called:2

进一步的测试表明,MSVC++的STL在unordered_map中插入新元素时调用哈希函数两次,如果元素已经在map中,则调用一次.

我觉得这种行为很奇怪,因为我认为缓存结果比在大多数情况下再次调用哈希函数要快得多(如果实现真的需要使用哈希值两次).或者更好的是,我认为只需使用哈希函数一次就可以找到该元素的存储桶,并且以下例程与哈希值无关.

但是,由于STL的作者在C++中比我更有经验,我不知道他们是否有一些特殊的理由来实现这个？这只是一个糟糕的设计还是由于我不知道的某些原因造成的？

Answer 1

在发布模式下，VS2012 也观察到了相同的行为。

区别在于 un_orderedmap 的实现。如果您调试并进入：Microsoft Visual Studio 11.0\VC\include\unordered_map，则对函数调用运算符的第一次调用是检查 key 是否已存在于映射中。第二次调用是在插入映射期间进行的（假设未找到键） - 经过 3 次迭代后，映射具有 ((0,1), (1,1), (2,1))