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

Question

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

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

我正在修改正在迭代的 unordered_map ，并希望确保不会因迭代器失效而导致任何中断。我至少确保避免使用保留关键字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迭代的范围明显改变了，这会对循环产生什么影响？插入的元素是否可以在范围内跳过？

Answer 1

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

std::unordered_map这里和 之间存在一定的相似性std::vector，其中只有超出容量并且数据被移动到更大的分配存储中时，所有迭代器才会失效。

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

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

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

因此，您的循环将经过一些刚刚添加的元素，而将访问哪些添加的元素取决于库实现、哈希函数等。很可能你不喜欢它。因此，您可以std::unordered_map不立即在循环中添加元素，而是首先将它们放入临时向量中，然后仅在循环之后将它们插入到映射中。