Deleting std::vector Item(s)

[MikeCopeland]

I'm having difficulty deleting items from a vector, and I suspect
it's a problem with how I'm using my iterator.
I my vector populated, and after some logic I wish to scan the vector
and erase certain items as I go. Below is the actual code I use, and
the program aborts when I execute the first "erase" call. In my
application, I can't do the delete "outside" of the loop.
Given the code below, is there a way to delete object from a vector
in this manner...or how might I do it? Please advise. TIA

for(vIter = defVect.begin(), iii = 0; vIter != defVect.end(); vIter++,
iii++)
{
defWork = *vIter;
if(defWork.recVal >= uuu)
defVect.erase(vIter+iii);
}



---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com

[Ian Collins]

MikeCopeland wrote:
> I'm having difficulty deleting items from a vector, and I suspect
> it's a problem with how I'm using my iterator.
> I my vector populated, and after some logic I wish to scan the vector
> and erase certain items as I go. Below is the actual code I use, and
> the program aborts when I execute the first "erase" call. In my
> application, I can't do the delete "outside" of the loop.
> Given the code below, is there a way to delete object from a vector
> in this manner...or how might I do it? Please advise. TIA
>
> for(vIter = defVect.begin(), iii = 0; vIter != defVect.end(); vIter++,
> iii++)
> {
> defWork = *vIter;
> if(defWork.recVal >= uuu)
> defVect.erase(vIter+iii);
> }

A (simplified) alternative is:

for( vIter = defVect.begin(); vIter != defVect.end(); )
{
if( condition_to_erase )
{
vIter = defVect.erase( vIter );
}
else
{
++vIter;
}
}

--
Ian Collins

[Barry Schwarz]

On Mon, 22 Sep 2014 20:18:32 -0700, MikeCopeland <mrc...@cox.net>
wrote:

> I'm having difficulty deleting items from a vector, and I suspect
>it's a problem with how I'm using my iterator.
> I my vector populated, and after some logic I wish to scan the vector
>and erase certain items as I go. Below is the actual code I use, and
>the program aborts when I execute the first "erase" call. In my
>application, I can't do the delete "outside" of the loop.
> Given the code below, is there a way to delete object from a vector
>in this manner...or how might I do it? Please advise. TIA
>
> for(vIter = defVect.begin(), iii = 0; vIter != defVect.end(); vIter++,
>iii++)
> {
> defWork = *vIter;
> if(defWork.recVal >= uuu)
> defVect.erase(vIter+iii);
> }

Since you increment vIter even when you do an erase, you will skip
over the next element after each erase. Consider the case where your
vector contains 0,1,2,3,4. If you delete the element when the
iterator points to 2, the vector becomes 0,1,3,4 and your iterator
points to 3. You then increment the iterator for the next iteration
and it points to 4. You never process the element containing 3.

As soon as vIter points past the halfway point of the vector elements,
vIter+iii will point beyond the end of the vector. In the above
example, if 3 is the first element you choose to delete, vIter+iii is
an invalid iterator value (well beyond the end of the vector).

Ian's post shows you how to solve the first problem. Since we don't
know what vIter+iii is supposed to be, it's a little harder to suggest
a solution for the second.

--
Remove del for email

[MikeCopeland]

In article <43u12a93nfdqub26r...@4ax.com>,
schw...@dqel.com says...

"iii" is used within the for loop to point to the offset of the item
to be deleted. However, I see the error in my code here: it should have
been "vIter.begin()+iii". My bad... 8<{{
Your post helped me see that. <sigh>

[Ian Collins]

Why do you need an offset when you have an iterator?

--
Ian Collins

[MikeCopeland]

In article <c8cf8o...@mid.individual.net>, ian-...@hotmail.com
says...

> >> Ian's post shows you how to solve the first problem. Since we
don't
> >> know what vIter+iii is supposed to be, it's a little harder to suggest
> >> a solution for the second.
> >
> > "iii" is used within the for loop to point to the offset of the item
> > to be deleted. However, I see the error in my code here: it should have

> > been "defVect.begin()+iii". My bad... 8<{{

> > Your post helped me see that. <sigh>
>
> Why do you need an offset when you have an iterator?

I had played with this problem and tried to make it work, I guessed
that the way I was using the iterator probably wasn't right. I looked
at Google and found examples which used "iterator.begin()+offset" to
erase and thought it would work. My post of last night (which I've
corrected here) was all wrong, so I've misled you there. My apologies.
Note to self: don't post late at night when the old brain is barely
functioning. 8<}}

[Barry Schwarz]

On Mon, 22 Sep 2014 22:24:17 -0700, MikeCopeland <mrc...@cox.net>
wrote:

I assume you meant defVect.begin()+iii.

If that is what you want to do, then Ian's post shows you how without
bothering with the offset. Note that defVect.begin()+iii and vIter
both point to the same element.

[Andreas Dehmel]

On Mon, 22 Sep 2014 20:18:32 -0700
MikeCopeland <mrc...@cox.net> wrote:

> I'm having difficulty deleting items from a vector, and I suspect
> it's a problem with how I'm using my iterator.
> I my vector populated, and after some logic I wish to scan the
> vector and erase certain items as I go. Below is the actual code I
> use, and the program aborts when I execute the first "erase" call.
> In my application, I can't do the delete "outside" of the loop.
> Given the code below, is there a way to delete object from a
> vector in this manner...or how might I do it? Please advise. TIA
>
> for(vIter = defVect.begin(), iii = 0; vIter != defVect.end();
> vIter++, iii++)
> {
> defWork = *vIter;
> if(defWork.recVal >= uuu)
> defVect.erase(vIter+iii);
> }

Modifying the size of a vector may invalidate all iterators pointing to
it, so of course your code has a high likelihood of crashing. Furthermore,
even if you rewrote it to use indices rather than iterators and got
the iteration logic right, that code would degrade into quadratic
complexity because a single erase in a vector is already O(N). A much
better approch is to iterate from start to finish and copy all elements
you want to keep so they'll all end up at the start, then after the
iteration truncate the vector to its new size; this is O(N) no matter
how much you erase. So basically (untested)

for (vIter = defVect.begin(), vDest = vIter; vIter != defVect.end(); ++vIter)
{
if (!deletePredicate(*vIter))
{
*vDest = *vIter;
++vDest;
}
}
defVect.erase(vDest, defVect.end());


Alternatively, use e.g. a list where simultaneous iteration and insertion/
deletion is legal.



Andreas
--
Dr. Andreas Dehmel Ceterum censeo
FLIPME(ed.enilno-t@nouqraz) Microsoft esse delendam
http://www.zarquon.homepage.t-online.de (Cato the Much Younger)

[peter koch]

Den tirsdag den 23. september 2014 05.19.21 UTC+2 skrev MikeCopeland:
> I'm having difficulty deleting items from a vector, and I suspect
> it's a problem with how I'm using my iterator.
> I my vector populated, and after some logic I wish to scan the vector
> and erase certain items as I go. Below is the actual code I use, and
> the program aborts when I execute the first "erase" call. In my
> application, I can't do the delete "outside" of the loop.
> Given the code below, is there a way to delete object from a vector
> in this manner...or how might I do it? Please advise. TIA
>
> for(vIter = defVect.begin(), iii = 0; vIter != defVect.end(); vIter++,
> iii++)
> {
> defWork = *vIter;
> if(defWork.recVal >= uuu)
> defVect.erase(vIter+iii);
> }
>

I would partition the vector (look up partition/stable_partition), do a delete on the erasable items (all in the end of the vector) and finally do an erase of the last elements. Only one loop left. Probably you will not be able to get it more efficient than that.

/Peter

[MikeCopeland]

In article <td532atp38u5mnkae...@4ax.com>,
schw...@dqel.com says...

>
> > "iii" is used within the for loop to point to the offset of the
item
> >to be deleted. However, I see the error in my code here: it should have
> >been "vIter.begin()+iii". My bad... 8<{{
> > Your post helped me see that. <sigh>
>
> I assume you meant defVect.begin()+iii.

Yes. I posted that (error) late at night when my brain had mostly
gone to sleep. 8<{{

>
> If that is what you want to do, then Ian's post shows you how without
> bothering with the offset. Note that defVect.begin()+iii and vIter
> both point to the same element.

Which works just fine. Thanks both!

[Ike Naar]

On 2014-09-23, MikeCopeland <mrc...@cox.net> wrote:
> I'm having difficulty deleting items from a vector, and I suspect
> it's a problem with how I'm using my iterator.
> I my vector populated, and after some logic I wish to scan the vector
> and erase certain items as I go. Below is the actual code I use, and
> the program aborts when I execute the first "erase" call. In my
> application, I can't do the delete "outside" of the loop.
> Given the code below, is there a way to delete object from a vector
> in this manner...or how might I do it? Please advise. TIA
>
> for(vIter = defVect.begin(), iii = 0; vIter != defVect.end(); vIter++,
> iii++)
> {
> defWork = *vIter;
> if(defWork.recVal >= uuu)
> defVect.erase(vIter+iii);
> }

Have you already looked at remove_if() from <algorithm> ?

[Jorgen Grahn]

Isn't that just a complicated way to write this?

auto end = std::remove_if(defVect.begin(), defVect.end(), deletePredicate);
defVect.erase(end, defVect.end());

In either case, I too warmly recommend the "move, then erase" approach.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[peter koch]

You can't do that as you do not know what is between end and defVect.end().

My solution was a 3-liner:
auto end = std::stable_partition(defVect.begin(), defVect.end(), deletePredicate);
std::for_each(end, defVect.end(),[](xx val) {delete val;});
defVect.erase(end,defVect.end());

Ike had a two-liner solution - something like:

auto end = std::remove_if(defVect.begin(), defVect.end(), [](xx val) { if (deletePredicate(val) { delete val; return true;}; return false; });
defVect.erase(end, defVect.end());

This solution is perhaps better than mine. It is just that it to me smells a little that I delete in the predicate.

Perhaps you overlooked that the vector consisted of raw pointers that had to be deleted?

/Peter

[Jorgen Grahn]

[...]

> Perhaps you overlooked that the vector consisted of raw pointers that had to be deleted?

I assumed the vector contained something more "normal", yes. But
AFAICT both MikeCopeland or Andreas Dehmel make the same assumption?
I admit that I didn't read the full thread.

[peter koch]

Well, I just reread Mike Copelands original post and I see that there was no mention of pointers, so I do not know how that idea got stuck in my head. Perhaps because Mike wrote something like "delete object from a vector"?
Sorry about the noise.

/Peter

[Jorgen Grahn]

On Wed, 2014-10-01, peter koch wrote:
> Den mandag den 29. september 2014 11.33.35 UTC+2 skrev Jorgen Grahn:
>> On Fri, 2014-09-26, peter koch wrote:
>> > Perhaps you overlooked that the vector consisted of raw pointers that had to be deleted?
>>
>> I assumed the vector contained something more "normal", yes. But
>> AFAICT both MikeCopeland or Andreas Dehmel make the same assumption?
>> I admit that I didn't read the full thread.

> Well, I just reread Mike Copelands original post and I see that there was no mention of pointers,
> so I do not know how that idea got stuck in my head.
> Perhaps because Mike wrote something like "delete object from a vector"?
> Sorry about the noise.

If it was noise, it was of a useful kind. Never hurts to remind
people what std::remove_if() does and doesn't do!