c++ - 在 MSVC++ 的 STL 中插入 std::unordered_map 两次调用散列函数，糟糕的设计还是特殊原因？

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

进一步的测试表明，当在 unordered_map 中插入一个新元素时，MSVC++ 的 STL 调用哈希函数两次，如果该元素已经在映射中则调用一次。

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

不过，由于STL的作者在C++方面的经验比我丰富很多，不知道他们这样实现是不是有什么特殊的原因？这只是一个糟糕的设计还是由我不知道的某些原因造成的？

Answer 1

在 Release 模式下也观察到 VS2012 的相同行为。

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