deleting vector elements while looping thru it

[kaferro]

What is the typical way to loop through a vector while deleting
certain elements during the loop process? The code below works, but I
am wondering if there is a better solution.
vector<intvTmp;
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(1);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x]==1)
{
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

[Victor Bazarov]

ka*****@hotmail.com wrote:

What is the typical way to loop through a vector while deleting
certain elements during the loop process? The code below works, but I
am wondering if there is a better solution.
vector<intvTmp;
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(1);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x]==1)
{
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[none]

Victor Bazarov a écrit :

ka*****@hotmail.com wrote:

>What is the typical way to loop through a vector while deleting
certain elements during the loop process? The code below works, but I
am wondering if there is a better solution.
vector<intvTmp;
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(1);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x]==1)
{
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));

V

std::remove_if(vTmp.begin(), vTmp.end(), 1);
should be enough...
--
JF

[Pete Becker]

none wrote:

Victor Bazarov a écrit :

>ka*****@hotmail.com wrote:

>>What is the typical way to loop through a vector while deleting
certain elements during the loop process? The code below works, but I
am wondering if there is a better solution.
vector<intvTmp;
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(1);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x]==1)
{
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));

V

std::remove_if(vTmp.begin(), vTmp.end(), 1);
should be enough...

remove_if doesn't actually remove things, it just reshuffles the
sequence so that the rejected elements are at the end. Having done that,
you have to tell the vector that those elements are no longer part of
the controlled sequence. You do that with erase, passing the iterator
that was returned by remove_if as the start of the sequence to be
erased, and the vector's end iterator as the end.

The proposed code isn't quite right. It should use remove (since its
third argument is a value; remove_if takes a predicate), and it's
missing an end iterator. Should be:

vTmpl.erase(std::remove(vTmp.begin(), vTmp.end(), 1), vTmp.end());

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[Victor Bazarov]

none" <""jf\"@(none) wrote:

Victor Bazarov a écrit :

>ka*****@hotmail.com wrote:

>>What is the typical way to loop through a vector while deleting
certain elements during the loop process? The code below works,
but I am wondering if there is a better solution.
vector<intvTmp;
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(1);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x]==1)
{
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

vTmp.erase(std::remove_if(vTmp.begin(), vTmp.end(), 1));

V

std::remove_if(vTmp.begin(), vTmp.end(), 1);
should be enough...

No, '1' in that case is not a valid predicate. I messed up. It
ought to be

vTmp.erase(std::remove(vTmp.begin(), vTmp.end(), 1));

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[kaferro]

I oversimplified my question because I take actions before I erase the
element from the vector.

Revised example code:

vector<cObjvTmp;
vector<cObjvErrors;
vTmp.push_back(obj1);
vTmp.push_back(obj2);
vTmp.push_back(obj3);
vTmp.push_back(obj4);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x].returnName=="NA")
{
vErrors.push_back(vTmp[x]);
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

[Victor Bazarov]

ka*****@hotmail.com wrote:

I oversimplified my question because I take actions before I erase the
element from the vector.

Revised example code:

vector<cObjvTmp;
vector<cObjvErrors;
vTmp.push_back(obj1);
vTmp.push_back(obj2);
vTmp.push_back(obj3);
vTmp.push_back(obj4);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x].returnName=="NA")
{
vErrors.push_back(vTmp[x]);
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

struct retNameIs
{
const char* name;
retNameIs(const char* n) : name(n) {}
bool operator()(cObj const& o) {
return o.returnName == name;
}
};

...
vector<cObjvTmp;
vTmp.push_back(obj1);
vTmp.push_back(obj2);
vTmp.push_back(obj3);
vTmp.push_back(obj4);

vector<cObj>::iterator it =
std::remove_if(vTmp.begin(), vTmp.end(), retNameIs("NA"));
vector<cObjvErrors(it, vTmp.end());
vTmp.erase(it, vTmp.end());

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Roland Pibinger]

On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:

>remove_if doesn't actually remove things, it just reshuffles the
sequence so that the rejected elements are at the end.

The Standard doesn't specify that 'rejected' elements can be found at
the end of the sequence.

--
Roland Pibinger
"The best software is simple, elegant, and full of drama" - Grady Booch

[Victor Bazarov]

Roland Pibinger wrote:

On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:

>remove_if doesn't actually remove things, it just reshuffles the
sequence so that the rejected elements are at the end.

The Standard doesn't specify that 'rejected' elements can be found at
the end of the sequence.

The algorithm is called "in-place". What besided "reshuffles" can
that mean? 'remove_if' returns the iterator that points to the _end_
of the resulting sequence. What besides placing the "removed"
elements of the sequence beyond the new end could it mean? IOW, if
you apply all the definitions of what 'remove' ('remove_if') does,
it results in moving the rejected elements within the same sequence
beyond what it returns as new end of the sequence.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Pete Becker]

Victor Bazarov wrote:

Roland Pibinger wrote:

>On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:

>>remove_if doesn't actually remove things, it just reshuffles the
sequence so that the rejected elements are at the end.

The Standard doesn't specify that 'rejected' elements can be found at
the end of the sequence.

The algorithm is called "in-place". What besided "reshuffles" can
that mean?

Actually, he's right, although it's irrelevant to this particular
discussion. remove and remove_if leave whatever junk they fell like at
the end of the original sequence. Typically it's the elements that were
there before, not necessarily the ones that were rejected. So for the
example under discussion, the tail of the array would not hold all 1's
unless they were there to begin with. Typically you'd see a vector
holding, say, 1,3,1,5,7,1 turning into 3,5,7,5,7,1. The last three
elements are the leftovers.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[Pete Becker]

Pete Becker wrote:

Victor Bazarov wrote:

>Roland Pibinger wrote:

>>On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:
remove_if doesn't actually remove things, it just reshuffles the
sequence so that the rejected elements are at the end.
The Standard doesn't specify that 'rejected' elements can be found at
the end of the sequence.

The algorithm is called "in-place". What besided "reshuffles" can
that mean?

Actually, he's right, although it's irrelevant to this particular
discussion. remove and remove_if leave whatever junk they fell like at
the end of the original sequence. Typically it's the elements that were
there before, not necessarily the ones that were rejected. So for the
example under discussion, the tail of the array would not hold all 1's
unless they were there to begin with. Typically you'd see a vector
holding, say, 1,3,1,5,7,1 turning into 3,5,7,5,7,1. The last three
elements are the leftovers.

Forgot to mention: those last two sentences refer to the problem under
discussion, i.e. removing 1's from the vector.

Oh, and the "in-place" is in distinction to "copying", which leaves the
original sequence intact.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[Victor Bazarov]

Pete Becker wrote:

Pete Becker wrote:

>Victor Bazarov wrote:

>>Roland Pibinger wrote:
On Wed, 11 Apr 2007 11:17:51 -0400, Pete Becker wrote:
remove_if doesn't actually remove things, it just reshuffles the
sequence so that the rejected elements are at the end.
The Standard doesn't specify that 'rejected' elements can be found
at the end of the sequence.

The algorithm is called "in-place". What besided "reshuffles" can
that mean?

Actually, he's right, although it's irrelevant to this particular
discussion. remove and remove_if leave whatever junk they fell like
at the end of the original sequence. Typically it's the elements
that were there before, not necessarily the ones that were rejected.
So for the example under discussion, the tail of the array would not
hold all 1's unless they were there to begin with. Typically you'd
see a vector holding, say, 1,3,1,5,7,1 turning into 3,5,7,5,7,1. The
last three elements are the leftovers.

Forgot to mention: those last two sentences refer to the problem under
discussion, i.e. removing 1's from the vector.

Oh, and the "in-place" is in distinction to "copying", which leaves
the original sequence intact.

So, I was wrong.

To be entirely correct, instead of extracting the "left-overs" after
'remove_if', I ought to use 'copy_if' along with 'erase'. Except there
is no 'copy_if', is there?

So, there is no decent way.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[red floyd]

Victor Bazarov wrote:

To be entirely correct, instead of extracting the "left-overs" after
'remove_if', I ought to use 'copy_if' along with 'erase'. Except there
is no 'copy_if', is there?

You could use remove_copy_if with a negated predicate. remove_copy_if
will copy a range, removing those that match the predicate. So if you
negate the predicate, you will copy only those that do match the
original predicate.

Anyone know if C++0x is going to have copy_if?

[Pete Becker]

Victor Bazarov wrote:

>
To be entirely correct, instead of extracting the "left-overs" after
'remove_if', I ought to use 'copy_if' along with 'erase'. Except there
is no 'copy_if', is there?

So, there is no decent way.

No, what you had was basically right. remove or remove_if, followed by
erase to kill off the leftovers. So remove(begin(), end(), 1) turns
1,3,1,5,7,1 into 3,5,7,x,x,x (where the x's are unspecified, but most
likely are 5,7,1) and returns an iterator pointing to the first x.
erase(iterator, end()) removes the junk at the end.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[Victor Bazarov]

Pete Becker wrote:

Victor Bazarov wrote:

>>
To be entirely correct, instead of extracting the "left-overs" after
'remove_if', I ought to use 'copy_if' along with 'erase'. Except
there is no 'copy_if', is there?

So, there is no decent way.

No, what you had was basically right. remove or remove_if, followed by
erase to kill off the leftovers. So remove(begin(), end(), 1) turns
1,3,1,5,7,1 into 3,5,7,x,x,x (where the x's are unspecified, but most
likely are 5,7,1) and returns an iterator pointing to the first x.
erase(iterator, end()) removes the junk at the end.

Right. I know. The OP also wanted to extract the removed elements
into a separate vector. That's where 'copy_if' would come handy.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Pete Becker]

Victor Bazarov wrote:

Pete Becker wrote:

>Victor Bazarov wrote:

>>To be entirely correct, instead of extracting the "left-overs" after
'remove_if', I ought to use 'copy_if' along with 'erase'. Except
there is no 'copy_if', is there?

So, there is no decent way.

No, what you had was basically right. remove or remove_if, followed by
erase to kill off the leftovers. So remove(begin(), end(), 1) turns
1,3,1,5,7,1 into 3,5,7,x,x,x (where the x's are unspecified, but most
likely are 5,7,1) and returns an iterator pointing to the first x.
erase(iterator, end()) removes the junk at the end.

Right. I know. The OP also wanted to extract the removed elements
into a separate vector. That's where 'copy_if' would come handy.

Okay, I see what you're saying.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[James Kanze]

On Apr 11, 4:50 pm, "[e-mail]" <[e-mail]:

What is the typical way to loop through a vector while deleting
certain elements during the loop process? The code below works, but I
am wondering if there is a better solution.

vector<intvTmp;
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(2);
vTmp.push_back(1);
vTmp.push_back(1);

for(int x=0; x<vTmp.size(); x++)
{
if(vTmp[x]==1)
{
vTmp.erase(vTmp.begin()+x,vTmp.begin()+x+1);
x--; //to account for new size
}
}

Others have pointed out the solution using remove or remove_if,
which handles this specific case. More generally, if you're
possibly doing a number of other things, or for some other
reason prefer writing the loop yourself:

std::vector<int>::iterator current = v.begin() ;
while ( current != v.end() ) {
// ...
if ( shouldBeDeleted ) {
current = v.erase( current ) ;
} else {
++ current ;
}
}

can be used. (Note that in the case of vector, this is likely
to result in a lot more copying than using std::remove. If the
container is a list, however, it's probably more efficient. And
of course, unless the container is very big, and the types
expensive to copy, it generally doesn't matter.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]