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]

BCC wrote:

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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[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]

BCC wrote:

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

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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[David Fisher]

"Kevin Goodsell" <us*********************@neverbox.com> wrote:

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...er/000168.html

(code near the bottom of the page)

David F

[Kevin Goodsell]

David Fisher wrote:

"Kevin Goodsell" <us*********************@neverbox.com> wrote:

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++);

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...er/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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[David Fisher]

"Kevin Goodsell" <us*********************@neverbox.com> wrote:

David Fisher wrote:

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'.

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]

David Fisher wrote:

"Kevin Goodsell" <us*********************@neverbox.com> wrote:

David Fisher wrote:

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'.

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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[David Fisher]

"Kevin Goodsell" <us*********************@neverbox.com> wrote:

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.

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[i].GetCutoff() < high_cutoff) temp.push_back(CUnit[i];
}
if(!temp.empty()) CUnit.swap(temp);