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<int> vTmp;
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]

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<int> vTmp;
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

 

[none]

Victor Bazarov a écrit :

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<int> vTmp;
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...

 

[Pete Becker]

Victor Bazarov a écrit :

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<int> vTmp;
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]

Victor Bazarov a écrit :

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<int> vTmp;
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

 

[kaferro]

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

Revised example code:

vector<cObj> vTmp;
vector<cObj> vErrors;
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]

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

Revised example code:

vector<cObj> vTmp;
vector<cObj> vErrors;
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<cObj> vTmp;
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<cObj> vErrors(it, vTmp.end());
vTmp.erase(it, vTmp.end());

V

 

[Roland Pibinger]

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.

 

[Victor Bazarov]

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

 

[Pete Becker]

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]

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]

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

 

[red floyd]

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]

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]

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

 

[Pete Becker]

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]

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<int> vTmp;
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.)