Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 850
user997112 Avatar asked Aug 09 '16 15:08

user997112


2 Answers

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()).

like image 69
Karl Nicoll Avatar answered Sep 21 '22 13:09

Karl Nicoll


erase() invalides the iterator you're erasing. When you subsequently increment it in the for loop, you get undefined behavior. The assert() is likely triggering on the second iteration of your loop, not your first.

You'll have to restructure your loop like:

for(auto it = my_umap.begin(); it != my_umap.end(); /* nothing */){

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

    if(deleteEntry) {
        // either use the return
        it = my_umap.erase(it); // NB: erase by it, not by key, why
                                // do an extra lookup?       

        // or post-increment
        my_umap.erase(it++);
    }
    else {
        ++it;
    }
}

Personally, I prefer it = map.erase(it) to map.erase(it++) but YMMV.

I'd just wrap that in a function template so you don't have to keep rewriting this sort of thing:

template <class Container, class F>
void erase_if(Container& c, F&& f) {
    for (auto it = c.begin(); it != c.end(); ) {
        if (f(*it)) {
            it = c.erase(it);
        }
        else {
            ++it;
        }
    }
}

and then:

erase_if(my_umap, [](const auto& pr){
    MyStruct& myStruct = pr.second; 
    return myStruct.ts.IsElapsed(std::chrono::seconds(5));
});
like image 35
Barry Avatar answered Sep 18 '22 13:09

Barry