469,160 Members | 1,830 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,160 developers. It's quick & easy.

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
Jul 22 '05 #1
9 3108
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.
Jul 22 '05 #2
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
Jul 22 '05 #3
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.
Jul 22 '05 #4
"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
Jul 22 '05 #5
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.
Jul 22 '05 #6
"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
Jul 22 '05 #7
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.
Jul 22 '05 #8
"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
Jul 22 '05 #9
> ...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);
Jul 22 '05 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Steve Hill | last post: by
3 posts views Thread by Jonathan | last post: by
9 posts views Thread by david wolf | last post: by
5 posts views Thread by Billy Patton | last post: by
14 posts views Thread by cayblood | last post: by
9 posts views Thread by Amadeus W. M. | last post: by
4 posts views Thread by Christian Bruckhoff | last post: by
3 posts views Thread by =?iso-8859-1?q?Erik_Wikstr=F6m?= | last post: by
3 posts views Thread by chsalvia | last post: by
1 post views Thread by CARIGAR | last post: by
1 post views Thread by Mortomer39 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.