0

I am iterating through a std::unordered_map

    std::unordered_map<int, char> mp;
    mp[0] = 'a';
    int i = 1;
    for(auto it=mp.begin();it!=mp.end();it++)
    {
        cout<<it->second<<" ";
        mp[i++] = (char)(97+i);
    }

Output

a

Now as a new element is being added at the end of each iteration I assumed this would run into an infinite loop however as shown in the output it did not.

  1. By seeing this link I realized that the iteration of std::unordered_map occurs by iterating through the buckets. So does that mean that in my code, the new value inserted into my map pair<int,char>(1,'b') was hashed to a bucket before the bucket of the value pair<int,char>(0,'a')"
  2. If yes then what happens if load factor exceeds max_load_factor and the unordered_map rehashes? Does the whole unordered_map iterate again?
asmmo
  • 6,922
  • 1
  • 11
  • 25
Jash Jain
  • 119
  • 6
  • 3
    If `operator[]` call causes rehashing, then all iterators are invalidated and the program exhibits undefined behavior as soon as it executes `it++`. If `operator[]` does not cause rehashing, then iterators remain valid. But since `unordered_map` is, well, unordered, there's no telling whether the new element is inserted before or after the one the iterator points to, and so the loop may or may not encounter it on subsequent iterations. – Igor Tandetnik Aug 15 '20 at 22:51
  • 1
    If `size() < max_load_factor()*bucket_count()` it's safe to insert and the iterator will remain valid, no matter if the insertion is done before or after the one the iterator points to. – Ted Lyngmo Aug 15 '20 at 23:13
  • @TedLyngmo That's what I said, didn't I? – Igor Tandetnik Aug 15 '20 at 23:15
  • @IgorTandetnik Oh, I misread, sorry - I removed your name-tag – Ted Lyngmo Aug 15 '20 at 23:15

1 Answers1

2

Inserting new elements invalidates your iterators at some point, however, you use them again, hence UB

For details, See Iterator invalidation rules and iterator invalidation in map C++

To see such behavior, use the following code

#include <iostream>
#include <unordered_map>


int main(){
    std::unordered_map<int, char> mp;
    mp[0] = 'a';
    int i = 1;
    for(auto it = mp.begin(); it!= mp.end();)
    {
        it = mp.insert({i++, (char)(97+i)}).first;
        std::cout<<it->second<<" ";

    }
}
asmmo
  • 6,922
  • 1
  • 11
  • 25
  • do you mean inserting elements or just when inserting elements leads to rehashing as Igor said above? – Jash Jain Aug 15 '20 at 23:07
  • 3
    "_Inserting elements invalidates your iterators_" isn't exactly what it says in the link you shared: "_The `insert` and `emplace` members shall not affect the validity of iterators if `(N+n) <= z * B`, where `N` is the number of elements in the container prior to the insert operation, `n` is the number of elements inserted, `B` is the container’s bucket count, and `z` is the container’s maximum load factor._" - That is, iterators are only invalidated if the new `size()` is greater than `max_load_factor()*bucket_count()`. – Ted Lyngmo Aug 15 '20 at 23:44
  • @TedLyngmo I think the answer doesn't have to include everything. – asmmo Aug 16 '20 at 06:42
  • I agree but it's good if what is included is correct. – Ted Lyngmo Aug 16 '20 at 08:07