Why is the iterator to the last element of the vector holding a corrupted value? (refer code)

Question

The below code throws heap-use-after-free error.

#include <iostream>

int main()
{
    unordered_map<int, vector<int>::iterator> mp;
    vector<int> num;

    auto insert = [&](int n)
    {
        if (mp.count(n) != 0)
            return false;

        num.push_back(n);
        mp[n] = prev(num.end());
        return true;    
    };

    insert(1);
    insert(2);
    insert(3);

    for (auto n : num)
        cout << n << endl;

    cout << endl;

    for (auto m : mp)
    {
        cout << m.first << " -> ";
        cout << distance(num.begin(), m.second) << endl; 
        // cout << *m.second << endl;
    }

    return 0;
}

The output of the above code is

1
2
3

3 -> 2
1 -> -16
2 -> -7

It obviously crashes if I try to access *m.second. Why are the iterator values seemingly corrupted here?

I have tried replacing vector with list and the above code works fine. I wonder if this has something to do with how vector expands on "push_back" maybe. I have tried other ways to get the iterator to the last element of the vector with indifferent results.

Answer 1

Iterators and references are invalidated in vector when push_back is called, see reference. Vector is implemented as one contiguous memory block. When you are pushing new elements and there is no space to keep them, new block of memory is allocated and new elem is added. Thus iterators (pointers) to old elements may be invalidated.

Your code works on std::list because list is implemented with using nodes. One node points to another and while adding new data into list location of nodes are not changed, so iterators are valid.

Your code with vector would work, but you need to estimate how many elements can be held in vector, after the vector was created call on it reserve(N) - it prepares vector to hold N items without invalidating iterators when push_back is invoked.