为什么在插入元素时（除了重新哈希发生时），std::unordered_map 迭代器不会失效？

Question

根据 stackoverflow 和 cppreference 中描述的迭代器失效规则，我知道除非重新哈希，否则 unordered_map 的迭代器不会失效。

如果我使用 std::vector 类比，那么这是否意味着所有插入都在迭代器当前指向位置之前进行？

我正在修改正在迭代的 unordered_map，并希望确保由于迭代器失效而导致的任何问题都不会发生。我至少正在使用 reserve 关键字避免重新哈希 unordered_map reserve。

这是我正在编写的示例代码：

// Function to return vector containing the subvector of inputVector with sum desiredSum, this function returns empty vector if sum not found
std::vector<int> sumVectorFunc(const std::vector<int>& inputVector, const int desiredSum){
    std::unordered_map< int,std::vector<int> > sumToSubVector{};
    sumToSubVector.reserve(desiredSum+1);
    // initialization with the zero sum
    sumToSubVector[0] = std::vector<int>{};


    for(auto itVector : inputVector){ // iterate over the vector of elements
        std::unordered_set<int> numbersAddedThisCycle{};    
        for(auto itSubVectors : sumToSubVector){ // iterate over constructed subVectors
            auto sum = itVector + itSubVectors.first;
            //the new sum constructed by adding this new vector element is not yet found and make sure that you are not adding the same element again and again to get new numbers
            if(sumToSubVector.find(sum) == sumToSubVector.end() && numbersAddedThisCycle.find(sum) == numbersAddedThisCycle.end()){   
                sumToSubVector[sum] = itSubVectors.second;
                sumToSubVector[sum].push_back(itVector);
                numbersAddedThisCycle.insert(sum);
            }
        }
    }

    // for(auto it : sumToSubVector){
    //     std::cout<<"FOr sum "<<it.first<<", we need the elements : ";
    //     for(auto it2 : it.second){
    //         std::cout<<it2<<" ";
    //     }std::cout<<"\n";
    // }

    return sumToSubVector[desiredSum];
}

我相信这个特定的实现即使在迭代器位置之前插入也不会出问题（即循环不会遍历在该插入周期中插入的元素）。

总结一下问题：插入发生在哪里？我的循环会如何处理这个插入？即使迭代器没有失效，unordered_map正在进行范围遍历时显然已经改变，这会影响循环吗？插入的元素是否会被跳过？

- Manish

---

我应该提到上面的代码在我的测试案例中运行良好。 - Manish

我可以在插入元素之前添加一个条件，即总和不大于desiredSum，同时假设所有数字都是正数（否则可能会重新散列）。 - Manish

你的问题一开始让我很困惑，所以我冒昧改了一下措辞，以便更清楚地表达你的意思。如果我误解了你的意图，请纠正我。 - bolov

迭代器失效并不是你真正关心的问题。重点是“我相信...循环不会遍历在特定插入周期中插入的元素”。这并没有得到保证 - 元素以不确定的顺序枚举（因此是unordered map），新插入的元素可能会或可能不会被迭代找到。这与迭代器失效的问题无关；你正在追逐一个红鲱鱼。 - Igor Tandetnik

Igor，我相信你的评论已经解决了我的疑惑。出于进一步的好奇，unordered_map的新元素是否采用链表式动态内存分配？ - Manish

Answer 1

为什么在向std :: unordered_map插入元素时（除了重新哈希发生时），迭代器不会失效？

这里在std :: unordered_map和std :: vector之间存在某种相似性，只有在超过容量并且数据移动到较大的分配存储时，所有迭代器才会失效。

如果我使用std :: vector类比，那么这是否意味着所有插入都发生在迭代器当前指向的位置之前？

这里std :: unordered_map的行为与std :: vector不同。实际上，使用push_back添加的std :: vector中的新元素出现在所有现有元素之后。但是在std :: unordered_map中，刚添加的元素可以出现在已经存在的元素之间（因此在评论中指出的无序映射）。

我的循环将如何处理此插入？

因此，您的循环将通过一些刚刚添加的元素，并且访问哪些添加的元素取决于库实现，哈希函数等。最可能您不喜欢它。因此，您可以先将元素放入临时向量中，然后仅在循环后将它们插入地图中。

- Fedor