c++ - C++ 中的 unordered_map 插入是如何工作的？

Question

int main() 
{
    auto n=0, sockNumber=0, pairs=0;
    unordered_map<int, int> numberOfPairs;
    cin >> n;

    for(int i=0; i<n; ++i)
    {
        cin >> sockNumber;
        numberOfPairs.insert({sockNumber, 0}); // >>>>>> HERE <<<<<<
        numberOfPairs.at(sockNumber) += 1;
        if(numberOfPairs.at(sockNumber) % 2 == 0)
        {
            pairs += 1;
        }
    }

    cout << pairs;

    return 0;
}

此代码计算给定输入中的对数并打印它。我想知道 unordered_map 的 insert 方法是如何工作的。每次我看到一个数字时，我都会将其插入值“0”。

当插入方法再次看到相同的数字时，是否会跳过插入值“0”？它是如何工作的？

Input -

9

10 20 20 10 10 30 50 10 20

Output -

3

Answer 1

1. Does the insert method skip inserting the value '0' when it sees the same number again?

是的，确实如此。

来自cpp.reference.com unordered_map :

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

来自cpp.reference.com unordered_map::insert :

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

How does it work?

我认为某些工作原则很大程度上取决于特定的STL实现。

基本上，unordered_map 是作为哈希表实现的，其中元素被组织到与相同哈希相对应的存储桶中。当您尝试插入键值对时，会计算键哈希值。如果哈希表中不存在此类哈希，或者与计算的哈希相对应的存储桶中不存在此类键值对，则新对将插入到unordered_map中。