JohnnyFinn JohnnyFinn - 2 months ago 8
C++ Question

Differences in erasing an entity from a list in C++

I am trying to erase an entity from a list in two cases. In the first case the following worked just fine, where I have a list of pairs from which I want to erase a certain one:

bool remove(std::list<std::pair<std::string, size_t>>& myList, std::string const& name) {

for (auto i = myList.begin(); i != myList.end(); i++) {
if(i->first == name) {
myList.erase(i);
return true;
}
}
return false;
}


Here the pair gets removed from the list as it should, but when I have a list of structs it does not work as in the following:

void remove(std::list<myStruct>& myList , const std::string& name) {

for (auto i = myList.begin(); i != myList.end(); i++) {
if(i->name == name) {
myList.erase(i);
}
}


The program crashes in the erase part. Only if I plug in
myList.erase(i++)
then it works. Why is this??

Have I done something foul in the first case and it just happened to work, but then in the second case it does not? I can not understand the reason.

Answer

Your first loop removes an entry from the list and stops.

for (auto i = myList.begin(); i != myList.end(); i++) {
    if(i->first == name) {
        myList.erase(i);
        return true;
    }
}

while your second loop continues looking for matching elements:

for (auto i = myList.begin(); i != myList.end(); i++) {
    if(i->name == name) {
        myList.erase(i);
    }
}

When you erase i from myList, i becomes invalid - we have no idea what it references now that the element it was talking about has gone away and may have been deleted, returned to the os and it's memory used by another thread.

The very next thing you do is i++ which is undefined behavior, since i is an invalid iterator.

The erase operator returns the next valid iterator, so you could write this:

for (auto i = myList.begin(); i != myList.end();) {
    if(i->name == name)
        i = myList.erase(i);
    else
        i++;
}

Or you could write:

void remove(std::list<myStruct>& myList , const std::string& name) {
    myList.remove_if([&](const myStruct& it) { return it.name == name; });
}

or if your compiler supports C++14

void remove(std::list<myStruct>& myList , const std::string& name) {
    myList.remove_if([&](auto& it) { return it.name == name; });
}

As in

#include <iostream>
#include <list>
#include <string>

struct A {
    std::string name_;
    A(const char* name) : name_(name) {}
};

void dump(const std::list<A>& list) {
    for (auto&& a : list) {
        std::cout << a.name_ << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::list<A> myList { { "hello", "pizza", "world", "pizza" } };
    dump(myList);
    const std::string name = "pizza";
    myList.remove_if([&](const A& it){ return it.name_ == name; });
    dump(myList);
    return 0;
}

Live demo: http://ideone.com/SaWejv

Comments