在 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;
}

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

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

Input -

9

10 20 20 10 10 30 50 10 20

Output -

3

Answer 1

一个std::unordered_map holds unique keys as values. If you want to keep inserting the same key, then use std::unordered_multimap.

另外，你应该意识到std::unordered_map::insert returns一个表示插入是否成功的值。

if ( !numberOfPairs.insert({sockNumber, 0}).second )
{
   // insertion didn't work 
}

您可以使用上面的方法来确认项目没有被插入，因为地图中已经存在相同的键。

Answer 2

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

是的，确实如此。

来自cpp.reference.comunordered_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 实现为散列table，其中元素被组织到对应于相同散列的桶中。当您尝试插入 key-value 对时，会计算 key 哈希。如果散列 table 中没有这样的散列，或者在与计算散列相对应的存储桶中没有这样的 key-value 对，则将新对插入到 unordered_map。

Answer 3

unordered_map 不允许键重复，因此如果您尝试使用 .insert() 方法插入相同的键，它将失败并跳过该操作。但是，如果您使用 unorderedMap[key] = value 插入重复的键，它不会跳过，而是将与键匹配的值更新为新值。

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

How does insertion in an unordered_map in C++ work?

c++

stl

unordered-map

insert

c++11