6

From iterator invalidation rules described at stackoverflow and cppreference, I know that iterator is not invalidated for unordered_map unless rehashing is occurring.

If I use std::vector analogy, then does this means that all the insertion takes place ahead of the location where the iterator is currently pointing too ?

I am modifying the unordered_map on which I am iterating and wanted to make sure that nothing breaks due to iterator invalidation. I am atleast making sure to avoid rehashing using reserve keyword unordered_map reserve

This is the example code that I am writing :

// 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];
}

I believe that this particular implementation will not break even if the insertion will happen before the iterator position (i.e. the loop will not be iterating through the element inserted in that particular insertion cycle)

To sum up the question: Where is the insertion happening ? How will my loop behave to this insertion? Even if the iterators are not invalidated, the unordered_map on which the range for is iterating is clearly changed, how will this affect the loop? Could the inserted elements be skipped in the range for or not?

Fedor
  • 17,146
  • 13
  • 40
  • 131
Manish
  • 668
  • 1
  • 6
  • 13
  • I should have mentioned that the above code is working fine in my test case. – Manish Oct 18 '18 at 18:03
  • I can add one more condition before inserting the element that the sum is not greater than the desiredSum, also the assumption is that all the numbers are positive( or else the rehash may occur ) – Manish Oct 18 '18 at 18:11
  • you question was very confusing to me at first, so I took the liberty to rephrase it so that it's more clear what you mean. If I changed your intention please correct me. – bolov Oct 20 '18 at 04:40
  • 4
    Iterator invalidation is not what you are really concerned about. The money quote is *"I believe ... the loop will not be iterating through the element inserted in that particular insertion cycle"*. That is not at all guaranteed - elements are enumerated in indeterminate order (hence *unordered* map), and the newly inserted element may or may not be encountered by the iteration. This is unrelated to the issue of iterator invalidation; you are chasing a red herring. – Igor Tandetnik Oct 21 '18 at 14:08
  • Igor, I believe that your comment have cleared my initial doubt. Out of further curiosity, Is it a linked list style dynamic memory allocation happening for new elements of unordered_map ? – Manish Oct 22 '18 at 16:17

1 Answers1

1

Why is std::unordered_map iterator not invalidated when we insert an element (apart from when rehashing occurs)?

Here there is certain similarity between std::unordered_map and std::vector, where all iterators are invalidated only if the capacity is exceeded and the data are moved in a larger allocated storage.

If I use std::vector analogy, then does this means that all the insertion takes place ahead of the location where the iterator is currently pointing too ?

And here std::unordered_map behaves unlike std::vector. Indeed, new elements in std::vector added with push_back appear after all existing elements. But in std::unordered_map just added element can appear in-between of already present ones (hence unordered map, as pointed in the comments).

How will my loop behave to this insertion?

So your loop will pass via some elements just added, and which added elements will be visited depends on the library implementation, hash function and so on. Most probably you do not like it. So you could add elements in std::unordered_map not immediately in the loop, but first put them in a temporary vector and insert them in the map only after the loop.

Fedor
  • 17,146
  • 13
  • 40
  • 131