user997112 user997112 - 3 months ago 17
C++ Question

unordered_map element being deleted

I'm inserting a

{string, MyStruct}
object in to an unordered_map, later iterating through the unordered_map and choosing to erase the element. However, before erasing the element I have an assert which is showing the unordered_map is empty.

This is my insert:

my_umap.insert(std::make_pair(key.toString(), my_struct));


The struct contains a member recording the time at which it was inserted. I then periodically check the map and remove elements which have been in the unordered_map for too long:

for(auto it = my_umap.begin(); it != my_umap.end(); ++it){

MyStruct& myStruct = it->second;
const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5));

if(deleteEntry){
const string& key = it->first; // Cannot access memory for 'key'
assert(my_umap.size() >= 1); // This is failing
my_umap.erase(key);
}
}


I am running the code in gdb and the assert fails. When I query the value of
key
it says


cannot access memory


When I query the size of
my_umap
it says the size is zero.

How can the for loop detect an element if the size of the unordered_map is zero? There are no other threads accessing this container. I thought
unordered_map::insert()
copies the object in to the container, so the original object being deleted shouldn't matter?

Answer

After you call my_umap.erase(...), your iterator becomes invalid:

cppreference.com says:

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

This means that once the item is erased, the iterators that pointed to it are no longer valid.

You've got a couple of options:

1. Use the iterator to erase, and use the return value of erase()

Since C++11, erasing by iterator will return an iterator pointing to the next item in the map. So you can use this to keep your iterator valid:

auto it = my_umap.begin();

while (it != my_umap.end()) {

    MyStruct& myStruct = it->second;
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5));

    if(deleteEntry){
        assert(my_umap.size() >= 1);
        it = my_umap.erase(it);  // <-- Return value should be a valid iterator.
    }
    else{
        ++it;  // Have to manually increment.
    }
}

2. Store your iterators in a list object and erase after iteration.

Alternatively, you can store delete candidates in a list object (e.g. vector and delete them after your initial iteration:

std::vector<MapType::iterator> deleteCandidates;

for(auto it = my_umap.begin(); it != my_umap.end(); ++it){

    MyStruct& myStruct = it->second;
    const bool deleteEntry = myStruct.ts.IsElapsed(std::chrono::seconds(5));

    if(deleteEntry)
        deleteCandidates.push_back(it);
}

for (auto it : deleteCandidates) {
    my_umap.erase(it);
}

As for why your assertion is failing, you're probably encountering undefined behaviour by accessing an invalid iterator, making your for loop believe that the map is still not empty (because invalidIterator != my_umap.end()).

Comments