CODEWITHSUNDEEP
c++loopsunordered-map
JhonRM
JhonRM

Reputation: 215

C++ - unordered_map operator [], unexpected behavior

This is a simple script I was working on, but I failed to understand why it was behaving unexpectedly.

Basically, I had an array of integers with duplicates, and I wanted to store the number of times an element occurred in the array along with the element's value in an unordered_map,

Then, for each entry in the map {k, v}, I needed to determine if k + 1 existed in the array, and if so, do something with it. Below you can see the code.

vector<int> A = {1, 1, 3, 2, 5, 3};

for (int i = 0; i < A.size(); ++i) m[A[i]]++;

int ans = 0;

for (const auto& e: m) {
    if (m[e.first + 1] > 0) ans = max(ans, e.second + m[e.first + 1]);
}

Everything seemed to work. However, when k + 1 did not exist in the unordered_map, the loop would just terminate, and I do not understand why.

According to c++ documentation, the operator [] inserts a new element if it does not exist . But that does not tell me anything about the loop just not working.

I suspect it has something to do with the fact that I am modifying the unordered_map inside the loop. If this is the case, could you guys elaborate more on that?

I really appreciate your help.

Upvotes: 2

Views: 239

Answers (1)

Remy Lebeau
Remy Lebeau

Reputation: 596592

Using m[e.first + 1] inside your loop will insert a new element into m if it does not exist, which will cause problems for the loop itself because a range-based for loop uses iterators internally, and altering a std::unordered_map while you are iterating through it with iterators is undefined behavior, as an insertion may invalidate the iterators:

If an insertion occurs and results in a rehashing of the container, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated. Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count().

To avoid that, use the map's find() method instead to check for a key's existence without inserting it:

for (const auto& e: m) {
    auto iter = m.find(e.first + 1);
    if (iter != m.end()) ans = max(ans, e.second + iter->second);
}

Upvotes: 6

Related Questions