vector.erase() ?

[BCC]

I have the following code, where good_list is a vector of CUnits:

int high_cutoff = 10;
vector<CUnit>::iterator it;
for (it = good_list.end(); it != good_list.begin(); --it) {
CUnit* ccu = it;
if (ccu->GetCutoff() >= high_cutoff) {
good_list.erase(it);
}
}

Doesn't give any errors, but also does not seem to be removing the element
correctly from good_list.

There something wrong with the above code?

Thanks

 

[Kevin Goodsell]

I have the following code, where good_list is a vector of CUnits:

int high_cutoff = 10;
vector<CUnit>::iterator it;
for (it = good_list.end(); it != good_list.begin(); --it) {

Note that good_list.end() is an iterator that you can't do much with.
Dereferencing it is an error. If you really need to go backwards, you
probably want to use reverse iterators instead.

CUnit* ccu = it;

This may be an invalid conversion. An implementation may or may not
implement vector iterators as plain pointers. There's not really any
reason to need a pointer when you've already got an iterator. Just use
the iterator.

if (ccu->GetCutoff() >= high_cutoff) {

One problem is that ccu isn't valid the first time through.

good_list.erase(it);

'it' is no longer valid after this. I don't know if you are allowed to
apply -- to it. I don't think this is your problem, but you should
probably do something like this:

for (/* init */; /* cond */; /* EMPTY! */)
if (/* condition */)
it = good_list.erase(it);
else
++it;

I'm using ++ instead of --, figuring that you'll want to use reverse
iterators.

}
}

Doesn't give any errors, but also does not seem to be removing the element
correctly from good_list.

There something wrong with the above code?

Yup.

Here's the entire replacement I'd recommend (untested):

int high_cutoff = 10;
vector<CUnit>::reverse_iterator it;
for (it = good_list.rbegin(); it != good_list.rend(); ) {
if (it->GetCutoff() >= high_cutoff) {
it = good_list.erase(it);
}
else {
++it;
}
}

-Kevin

 

[BCC]

Here's the entire replacement I'd recommend (untested):

int high_cutoff = 10;
vector<CUnit>::reverse_iterator it;
for (it = good_list.rbegin(); it != good_list.rend(); ) {
if (it->GetCutoff() >= high_cutoff) {
it = good_list.erase(it);
}
else {
++it;
}
}

Makes sense.... but one problem is that erase() returns an iterator, not a
reverse_iterator...

Ill see if I can iron it out, thanks!
B

 

[Kevin Goodsell]

Makes sense.... but one problem is that erase() returns an iterator, not a
reverse_iterator...

Oh, yeah...

Well, that was kind of dumb, actually. You don't even *want* the
iterator returned by erase of you are going backward. Make them forward
iterators instead - there's no obvious reason to go backward.

On the other hand, if there *is* a reason that you need to go backward,
which just isn't apparent to me, then you can do something like this:

vector<CUnit>::reverse_iterator tmp = it;
++tmp;
good_list.erase(it);
it = tmp;

inside the 'if' block.

Another alternative is to use algorithms. std::remove_if should work, I
think. But remember that it doesn't really remove anything, it just
shuffles the "removed" elements to the end for you to erase().

-Kevin

 

[David Fisher]

On the other hand, if there *is* a reason that you need to go backward,
which just isn't apparent to me, then you can do something like this:

vector<CUnit>::reverse_iterator tmp = it;
++tmp;
good_list.erase(it);
it = tmp;

inside the 'if' block.

You can also say:

good_list.erase(it++);

This is safe because the variable "it" is incremented while it is still
valid; see:

http://mail.worldforge.org/pipermail/protocols/2001-December/000168.html

(code near the bottom of the page)

David F

 

[Kevin Goodsell]

You can also say:

good_list.erase(it++);

Yeah, if they are reverse iterators. That whole going backwards thing
got me confused. This method doesn't work if 'it' is a regular (not
reverse) iterator though, because the erase would invalidate the new
value of 'it'.

This is safe because the variable "it" is incremented while it is still
valid; see:

http://mail.worldforge.org/pipermail/protocols/2001-December/000168.html

(code near the bottom of the page)

That is a bit different because the container is a std::list. In that
case, no iterators are invalidated by the erase, so the method you
showed should be safe whether it's a reverse iterator or not.

-Kevin

 

[David Fisher]

Yeah, if they are reverse iterators. That whole going backwards thing
got me confused. This method doesn't work if 'it' is a regular (not
reverse) iterator though, because the erase would invalidate the new
value of 'it'.

It works in either direction - post increment operators do something like
this:

temp = (the next value after x);
someFunction(x);
x = temp;

The increment is not applied to the invalidated iterator, it is applied to
the original value. It does not do this:

someFunction(x);
x = (the next value after x);

If you write your own post increment operator, you need to return a value
and not a reference to "this", because of these semantics.

David F

 

[Kevin Goodsell]

It works in either direction - post increment operators do something like
this:

I think you misunderstand. The container in question is a vector.
erase() on a vector invalidates all iterators to elements that follow
the erased element(s).

temp = (the next value after x);
someFunction(x);

In the specific case we are talking about (where someFunction is the
vector erase() function, or calls that function), temp becomes invalid
here...

x = temp;

....and therefore this is a problem. Maybe. I'm not actually sure what
the restrictions on invalidated iterators are.

-Kevin

 

[David Fisher]

I think you misunderstand. The container in question is a vector.
erase() on a vector invalidates all iterators to elements that follow
the erased element(s).


In the specific case we are talking about (where someFunction is the
vector erase() function, or calls that function), temp becomes invalid
here...


...and therefore this is a problem. Maybe. I'm not actually sure what
the restrictions on invalidated iterators are.

Sorry, I was focusing on the wrong thing (the iterator rather than the
container) - I think you're probably right.

David F

 

[Duane Hebert]

...and therefore this is a problem. Maybe. I'm not actually sure what

the restrictions on invalidated iterators are.

This is more of a question than a suggestion but given that it's a vector
and the reallocation happening on an erase() call, would this be any less
efficient:

int high_cutoff = 10;
vector<CUnit> temp;
size_t VSize = CUnit.size();
temp.reserver(VSize());
for(size_t i = 0; i < VSize; ++i) {
if(CUnit.GetCutoff() < high_cutoff) temp.push_back(CUnit;
}
if(!temp.empty()) CUnit.swap(temp);

 

[ntg]

using reverse iterators

I think this should do the trick in an efficient way...
its even using the faster ++it....

int high_cutoff = 10;
vector<CUnit>::reverse_iterator it;
for (it = good_list.rbegin(); it != good_list.rend(); ) {
if (it->GetCutoff() >= high_cutoff) {
it = good_list.erase(it.base()-1);
}
else {
++it;
}
}

any thoughts?