code code - 11 days ago 4
C++ Question

Iterator validity

I'm looking for a more in depth explanation here, not just how to get working code. I know how to write much shorter code to erase elements. I wrote this test code here to pinpoint points of failure upon deletion. It would seem that not only the i iterator becomes invalid but also the .end() iterator... and that is interesting.

Why is that this works?

deque<shared_ptr<Vehicle>> data;
data.push_back( shared_ptr<Vehicle>(new Vehicle("porsche")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("fiat")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("fiat")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("bmw")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("fiat")) );

auto end = data.end();
for(auto i = data.begin(); i != end;)
{

if( (*i)->getName() == "fiat" )
{
auto ti = i;
++ti;
end = data.end(); //above erase, works but not logical
data.erase(i);
i=ti;
}
else
{
++i;
end = data.end();
}
}


but this does not work?

deque<shared_ptr<Vehicle>> data;
data.push_back( shared_ptr<Vehicle>(new Vehicle("porsche")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("fiat")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("fiat")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("bmw")) );
data.push_back( shared_ptr<Vehicle>(new Vehicle("fiat")) );

auto end = data.end();
for(auto i = data.begin(); i != end;)
{

if( (*i)->getName() == "fiat" )
{
auto ti = i;
++ti;
data.erase(i);
end = data.end(); //Bellow erase...more logical but crashes
i=ti;
}
else
{
++i;
end = data.end();
}
}


I'm guessing that there is some implementation level issue here. Perhaps a compiler bug. Using GCC 4.8.2.

Answer

You're invoking Undefined Behavior. From the language spec, about deque::erase:

An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque.

In your case, your end iterator is always getting clobbered, and it's just luck that it works at all. The crash in the second case is likely due to operations on i, not the data.end call.