Erasing in a vector while iterating through it

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

I have some code where there's this vector of pointers to objects and
I need to delete and erase some of them, the problem is that to know
which I need to iterate through the vector and I'm trying to do this
as efficient as possible. The code is something like this:

struct Thing {
int value;
Thing* ptr;
Thing() : ptr(0) { }
};

// .....

std::vector<Thing*> vec;

So the vector contains pointers to Thing-objects, and for some of
those objects ptr might be set, in which case it will point to one of
the Things pointed to by the pointers in the vector. What I need to do
is to go through the vector and for each Thing where value has a
specific value I need to delete the Thing pointed to by ptr and erase
it from the vector. One way I could do that is to go through the
vector in one pass and collect all those pointers to some other
container and then make another pass and erase them but I'd prefer to
do it in one pass and was wondering if that is legal (something like
this):

std::sort(vec.begin(), vec.end()); // Sort one the address of the
Things

for (size_t i = 0; i < vec.size(); ++i) {
if (vec->value == SOME_VALUE) {
std::vector<Thing*>::iterator it =
std::::lower_bound(cells.begin(), cells.end(), vec->ptr);
vec->value = 0;
vec->ptr = 0;
delete *it;
--i; // Decrement if the Thing removed is before i in vec
vec.erase(it);
}
}

Since vector::erase will invalidate all references and iterators to
elements after the one removed there are two scenarios that I can
think of. The first is that the element is located after the i'th
element in which case I'll have to do some extra work (since I did --
i), or the element is before the i'th element (it can't be the i'th
element) in which case the i'th element (after the --i) should be the
same. Is this true?

 

[Victor Bazarov]

I have some code where there's this vector of pointers to objects and
I need to delete and erase some of them, the problem is that to know
which I need to iterate through the vector and I'm trying to do this
as efficient as possible.

The best way I know would be to iterate, set those you delete to null,
and then, after all the deletion, remove_if all of them at once.

The code is something like this:

struct Thing {
int value;
Thing* ptr;
Thing() : ptr(0) { }
};

// .....

std::vector<Thing*> vec;

So the vector contains pointers to Thing-objects, and for some of
those objects ptr might be set, in which case it will point to one of
the Things pointed to by the pointers in the vector. What I need to do
is to go through the vector and for each Thing where value has a
specific value I need to delete the Thing pointed to by ptr and erase
it from the vector. One way I could do that is to go through the
vector in one pass and collect all those pointers to some other
container and then make another pass and erase them but I'd prefer to
do it in one pass and was wondering if that is legal (something like
this):

std::sort(vec.begin(), vec.end()); // Sort one the address of the
Things

for (size_t i = 0; i < vec.size(); ++i) {
if (vec->value == SOME_VALUE) {
std::vector<Thing*>::iterator it =
std::::lower_bound(cells.begin(), cells.end(), vec->ptr);
vec->value = 0;
vec->ptr = 0;
delete *it;
--i; // Decrement if the Thing removed is before i in vec
vec.erase(it);
}
}

Since vector::erase will invalidate all references and iterators to
elements after the one removed

...and the one removed,...

there are two scenarios that I can
think of. The first is that the element is located after the i'th
element in which case I'll have to do some extra work (since I did --
i), or the element is before the i'th element (it can't be the i'th
element) in which case the i'th element (after the --i) should be the
same. Is this true?

You need to check the return value of 'erase'. RTFM.

But before you decide to fix your code for erasing each in the middle,
consider remove_if all of them at once after doing all deletions.

V

 

[Greg Herlihy]

I have some code where there's this vector of pointers to objects and
I need to delete and erase some of them, the problem is that to know
which I need to iterate through the vector and I'm trying to do this
as efficient as possible. The code is something like this:

struct Thing {
int value;
Thing* ptr;
Thing() : ptr(0) { }

};

// .....

std::vector<Thing*> vec;

So the vector contains pointers to Thing-objects, and for some of
those objects ptr might be set, in which case it will point to one of
the Things pointed to by the pointers in the vector. What I need to do
is to go through the vector and for each Thing where value has a
specific value I need to delete the Thing pointed to by ptr and erase
it from the vector. One way I could do that is to go through the
vector in one pass and collect all those pointers to some other
container and then make another pass and erase them but I'd prefer to
do it in one pass and was wondering if that is legal (something like
this):

std::sort(vec.begin(), vec.end()); // Sort one the address of the
Things

for (size_t i = 0; i < vec.size(); ++i) {
if (vec->value == SOME_VALUE) {
std::vector<Thing*>::iterator it =
std::::lower_bound(cells.begin(), cells.end(), vec->ptr);
vec->value = 0;
vec->ptr = 0;
delete *it;
--i; // Decrement if the Thing removed is before i in vec
vec.erase(it);
}

}

The usual solution is to combine std::remove() with an erase
operation:

vec.erase( std::remove( vec.begin(), vec.end(), value_to_erase),
vec.end());

Unfortunately, this line of code does not manually delete the items
before erasing them from the vector.

Therefore I would suggest eliminating the error-prone and laborious
manual deletion requirement and declare a
std::vector<shared_ptr<Thing> > instead of a std::vector<Thing *>.
With this one change, the one line of code illustrated above would
work as it should.

Greg

 

[Christopher Dearlove]

The usual solution is to combine std::remove() with an erase
operation:

That's almost certainly best. But in those cases where you do need to
walk through the vector (something more complicated than simple
removal) read Item 9 in Scott Meyers' Effective STL - which discusses
the issue for all the standard containers (which don't all have the same
solution).

While Items 1-8 and 10-50 are also very good, I think this one Item
made this book invaluable - it told me this just before I was about to
get it wrong. It also starts with the std::remove solution.