Deleting from vector while iterating allowed?
cornelis van der bent
for (vector<set<int>>::iterator i = mySets.begin(); i != mySets.end();
i++)
{
if (<some-condition>)
{
mySets.erase(i);
}
}
Thanks,
Case
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Ulrich Eckhardt
> Is the code below correct, or will it mess up the vector?
>
> for (vector<set<int>>::iterator i = mySets.begin();
> i != mySets.end();
> i++)
> {
> if (<some-condition>)
> {
> mySets.erase(i);
> }
> }
erase() always invalidates the iterator. That means you can't use it any
more, not for dereferencing but also not for iteration. 'it++' is
iteration, so this code is broken.
Depending on what you want, it might be easier to move/copy elements you
want to keep to a new container and swap with the old one. Another way
would be to use a std::list<>, where you can at keep iterating with a trick
(see the recent thread "removing from a set - does it have to be so
ugly?").
Uli
--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
Thomas Maeder
> Is the code below correct, or will it mess up the vector?
Primarily, the code messes up the iterators.
> for (vector<set<int>>::iterator i = mySets.begin(); i != mySets.end();
> i++)
> {
> if (<some-condition>)
> {
> mySets.erase(i);
> }
> }
The correct idiom is:
typedef vector<set<int> > sets_type;
sets_type::iterator i = mySets.begin();
while (i!=mySets.end())
if (<some-condition>)
i = mySets.erase(i);
else
++i;
This way, you make sure that i remains valid until it reaches the end
position of the container. Even if sets_type is a different kind of
sequence container (e.g. list or deque).
Jeff Flinn
No it's not correct, it could mess up more than the vector.
>
> for (vector<set<int>>::iterator i = mySets.begin(); i != mySets.end();
> i++)
> {
> if (<some-condition>)
> {
> mySets.erase(i);
> }
> }
The accepted idiom is:
mySets.erase( std::remove_if( mySets.begin()
, mySets.end()
, <some-condition-function>)
, mySets.end());
Jeff
Stephen Howe
>
>mySets.erase( std::remove_if( mySets.begin()
> , mySets.end()
> , <some-condition-function>)
> , mySets.end());
Only for vectors, deques and lists
It wont work for sets.
Stephen Howe
cornelis van der bent
> The correct idiom is:
>
> typedef vector<set<int> > sets_type;
> sets_type::iterator i = mySets.begin();
> while (i!=mySets.end())
> if (<some-condition>)
> i = mySets.erase(i);
> else
> ++i;
>
> This way, you make sure that i remains valid until it reaches the end
> position of the container. Even if sets_type is a different kind of
> sequence container (e.g. list or deque).
Thanks for the solution! I like this better than having yet another
condition-function laying around.
Jeff Flinn
>> The accepted idiom is:
>>
>> mySets.erase( std::remove_if( mySets.begin()
>> , mySets.end()
>> , <some-condition-function>)
>> , mySets.end());
>
> Only for vectors, deques and lists
> It wont work for sets.
Yes, and that's what the user's implied definition of mySets is:
for (vector<set<int>>::iterator i = mySets.begin(); i != mySets.end();
i++)
Just happens to be a vector of set's, again assuming that vector and set
above are due to using namespace std;
Jeff
SeanW
> erase() always invalidates the iterator. That means you can't use it any
> more, not for dereferencing but also not for iteration. 'it++' is
> iteration, so this code is broken.
Is anyone aware of any decent compile-time tools to
detect this kind of error? Preferably one that doesn't
cost a dime per line.
Thanks,
Sean
--
Markus Donath
> The correct idiom is:
>
> typedef vector<set<int> > sets_type;
> sets_type::iterator i = mySets.begin();
> while (i!=mySets.end())
> if (<some-condition>)
> i = mySets.erase(i);
> else
> ++i;
>
> This way, you make sure that i remains valid until it reaches the end
> position of the container. Even if sets_type is a different kind of
> sequence container (e.g. list or deque).
>
or:
mySets.erase(i++);
instead of
i = mySets.erase(i);
Markus
Alex Strickland
> Is the code below correct, or will it mess up the vector?
>
> snip
void CompressVariables( std::vector<SPSSVariableInfo> & Variables )
{
size_t VIndex = 1;
while ( VIndex < Variables.size() ) {
if (<some-condition>) {
Variables.erase( Variables.begin() + VIndex );
}
VIndex++;
}
}
I am new with the STL and something like the code above didn't seem to work - is
there a reason? My diagnosis of "didn't work" may be faulty, I was tired, in a
hurry etc and just copied the data to a new vector.
Regards
Alex
Ulrich Eckhardt
> void CompressVariables( std::vector<SPSSVariableInfo> & Variables )
> {
> size_t VIndex = 1;
> while ( VIndex < Variables.size() ) {
> if (<some-condition>) {
> Variables.erase( Variables.begin() + VIndex );
> }
> VIndex++;
> }
> }
>
> I am new with the STL and something like the code above didn't seem to
> work - is there a reason?
Firstly, indices are zero-based in C++, so your initial index is wrong.
Secondly, the expression "it + n" (it being an iterator, n being a number)
is only valid for random-access iterators like those of std::vector<> or
std::deque<>, but not e.g. of std::set. Similarly, the size() function can
actually have some overhead when it must count the elements.
Lastly, imagine the sequence s[0, 1, 3, 4] where you remove all odd
elements. Above code would use these steps:
1. i=0, s[0]==0 is not odd
2. i=1, s[1]==1 is odd, so the new s becomes [0, 3, 4]
3. i=2, s[2]==4 is not odd
4. i=3, stop the loop
As you see, you should have remained at index[1] after removing the element
at position on.
> My diagnosis of "didn't work" may be faulty, I
> was tired, in a hurry etc and just copied the data to a new vector.
Actually, that is not a bad idea when you need to remove several elements
from the middle or beginning of a vector. Just copy those you want to keep
to a new vector and then swap with the original. This avoids lots of
copying.
Otherwise, the 'remove_if' function combined with an 'erase' call helps,
too!
Uli
--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
Ulrich Eckhardt
> On Nov 24, 3:39 pm, Ulrich Eckhardt <eckha...@satorlaser.com> wrote:
>> erase() always invalidates the iterator. That means you can't use it any
>> more, not for dereferencing but also not for iteration. 'it++' is
>> iteration, so this code is broken.
>
> Is anyone aware of any decent compile-time tools to
> detect this kind of error? Preferably one that doesn't
> cost a dime per line.
Any halfway modern implementation of the C++ standard library has a
diagnostic mode. This mode sacrifices some performance and some of the
complexity guarantees coming from the STL in order to verify at runtime
that a used iterator is actually used correctly.
If your implementation doesn't have such a diagnostic mode, you might want
to take a look at an alternative implementation. I know that both STLport
and Dinkumware have such a mode and they both can replace the native
standard library of many compilers.
Uli
--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
Alex Strickland
> Firstly, indices are zero-based in C++, so your initial index is wrong.
Actually I always want to keep the first member - I should have made that clear
though.
> As you see, you should have remained at index[1] after removing the element
> at position on.
Thank you, I see it now.
> Actually, that is not a bad idea when you need to remove several elements
> from the middle or beginning of a vector. Just copy those you want to keep
> to a new vector and then swap with the original. This avoids lots of
> copying.
It seemed sub-optimal, but what you say makes sense.
> Otherwise, the 'remove_if' function combined with an 'erase' call helps,
> too!
I'll try it.
Thanks
Alex
--
SeanW
> SeanW wrote:
> > Is anyone aware of any decent compile-time tools to
> > detect this kind of error? Preferably one that doesn't
> > cost a dime per line.
>
> Any halfway modern implementation of the C++ standard library has a
> diagnostic mode.
I know, which is why I specified "compile-time". It seems
that a compiler/linty-thing could readily detect the
container's invariants being broken in code like:
std::vector<int>::iterator i = mySets.begin();
mySets.erase(i);
++i;
, so I was wondering what tools could do so.
Sean
--
itaj sherman
> The accepted idiom is:
>
> mySets.erase( std::remove_if( mySets.begin()
> , mySets.end()
> , <some-condition-function>)
> , mySets.end());
>
std::remove_if may explicitly create multiple copies of elements in
the container (the kept elements are copied to the begining of the
container, not swapped). For non-primitive elements swap is considered
faster than copy (assignment), because it saves constructing an extra
instance.
I its possible to have a swap version, instead of copy, so that the
total work is
O( <Container::erase> + ( <container size> * ( <swap two elements> +
<predicate> ) ) )
using the function like egCollectIf instead if remove_if:
mySets.erase( egCollectIf( mySets.begin(), mySets.end(), <some-
condition-function>),
mySets.end());
egCollectIf swaps the elements that confirm the predicate to the
begining of the container.
I don't know boost enough to tell whether has anything like this.
Here's example implementation for egCollectIf:
//forgive my specific naming convention
template< class rcIterator, class rcPredicate >
rcIterator egCollectIf( rcIterator rFirst, rcIterator rLast,
rcPredicate rPred )
{
rcIterator aCurrent( rFirst );
while( aCurrent != rLast )
{
if( !rPred(*aCurrent) ) {
rcIterator aAhead( aCurrent );
++aAhead;
while( aAhead != rLast ) {
if( rPred(*aAhead) ) {
std::swap( *aCurrent, *aAhead );
++aCurrent;
}
++aAhead;
}
return aCurrent;
}
++aCurrent;
}
return aCurrent;
}
itaj
Dave Harris
> void CompressVariables( std::vector<SPSSVariableInfo> & Variables )
> {
> size_t VIndex = 1;
> while ( VIndex < Variables.size() ) {
> if (<some-condition>) {
> Variables.erase( Variables.begin() + VIndex );
> }
> VIndex++;
> }
> }
>
> I am new with the STL and something like the code above didn't seem
> to work - is there a reason?
The main reason is that you increment VIndex even if erase() is called;
the erase() will copy the next item into the VIndex position, so
incrementing VIndex causes that item to be skipped. Adding an "else"
would fix it.
This code also suffers from being O(N*N), ie slow. Erase() is O(N)
because it has to copy all the remaining items, and it's potentially
called N times. Remove_if() encapsulates a better algorithm, but since I
am not keen on predicates I usually just write it out:
iterator wp = v.begin();
for (iterator rp = v.begin(); rp != v.end(); ++rp)
if (keep( *rp ))
*wp++ = rp;
v.erase( wp, v.end() );
This calls erase() just once (and avoids the overhead of creating a new
vector).
-- Dave Harris, Nottingham, UK.
Maxim Yegorushkin
> On Nov 24, 3:39 pm, Ulrich Eckhardt<eckha...@satorlaser.com> wrote:
>> erase() always invalidates the iterator. That means you can't use it any
>> more, not for dereferencing but also not for iteration. 'it++' is
>> iteration, so this code is broken.
>
> Is anyone aware of any decent compile-time tools to
> detect this kind of error? Preferably one that doesn't
> cost a dime per line.
Valgrind is good at reporting this type of error.
It runs your application on a software CPU so that the application runs
~30 times slower. For this reason valgrind'ing release builds of the
application works better.
--
Max
Frank Birbacher
Markus Donath schrieb:
> or:
>
> mySets.erase(i++);
>
> instead of
>
> i = mySets.erase(i);
The point was that erase will invalidate the iterator. But erase also
returns a new valid iterator. So you cannot replace the code in the was
you showed here. Your code will break.
Frank