Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > vector.erase() ?

Reply
Thread Tools

vector.erase() ?

 
 
BCC
Guest
Posts: n/a
 
      01-21-2004
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


 
Reply With Quote
 
 
 
 
Kevin Goodsell
Guest
Posts: n/a
 
      01-21-2004
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.
 
Reply With Quote
 
 
 
 
BCC
Guest
Posts: n/a
 
      01-21-2004
>
> 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


 
Reply With Quote
 
Kevin Goodsell
Guest
Posts: n/a
 
      01-21-2004
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.
 
Reply With Quote
 
David Fisher
Guest
Posts: n/a
 
      01-21-2004
"Kevin Goodsell" <(E-Mail Removed)> 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


 
Reply With Quote
 
Kevin Goodsell
Guest
Posts: n/a
 
      01-21-2004
David Fisher wrote:

> "Kevin Goodsell" <(E-Mail Removed)> 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.
 
Reply With Quote
 
David Fisher
Guest
Posts: n/a
 
      01-21-2004
"Kevin Goodsell" <(E-Mail Removed)> 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


 
Reply With Quote
 
Kevin Goodsell
Guest
Posts: n/a
 
      01-21-2004
David Fisher wrote:

> "Kevin Goodsell" <(E-Mail Removed)> 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.
 
Reply With Quote
 
David Fisher
Guest
Posts: n/a
 
      01-21-2004
"Kevin Goodsell" <(E-Mail Removed)> 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


 
Reply With Quote
 
Duane Hebert
Guest
Posts: n/a
 
      01-23-2004
> ...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);


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments