removing from set - does it have to be so ugly?
Alfons
while ( current_item != stuff_set.end() )
{
if ( is_bad( *item ) )
{
std::set<Stuff>::iterator previous_item( --current_item );
stuff_set.erase( ++current_item );
current_item = previous_item;
}
++current_item;
}
Is this the best way I can structure this? I hate writing code like
this :(
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Ulrich Eckhardt
> std::set<Stuff>::iterator current_item( stuff_set.begin() );
> while ( current_item != stuff_set.end() )
> {
> if ( is_bad( *item ) )
> {
> std::set<Stuff>::iterator previous_item( --current_item );
> stuff_set.erase( ++current_item );
> current_item = previous_item;
> }
> ++current_item;
> }
iterator it = container.begin();
while(it!=container.end())
{
if(predicate(*it))
container.erase(it++);
else
++it;
}
Note the use of the postfix increment operator in the erase() call. This
strategy works for all containers where erasing an element only invalidates
iterators to that element but not to other elements (i.e. set and list but
not vector or deque).
Uli
--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
Seungbeom Kim
> std::set<Stuff>::iterator current_item( stuff_set.begin() );
> while ( current_item != stuff_set.end() )
> {
> if ( is_bad( *item ) )
> {
> std::set<Stuff>::iterator previous_item( --current_item );
> stuff_set.erase( ++current_item );
> current_item = previous_item;
> }
> ++current_item;
> }
>
> Is this the best way I can structure this? I hate writing code like
> this :(
'current_item' is too long a name for such a short-scoped variable;
'i' would just be fine.
In C++03, you can write:
std::set<Stuff>::iterator i(stuff_set.begin());
while (i != stuff_set.end()) {
if (is_bad(*i))
stuff_set.erase(i++);
else
++i;
}
In C++0x, you will be able to write:
std::set<Stuff>::iterator i(stuff_set.begin());
while (i != stuff_set.end()) {
if (is_bad(*i))
i = stuff_set.erase(i);
else
++i;
}
which works well both for sequences and associative containers.
--
Seungbeom Kim
Yechezkel Mett
> std::set<Stuff>::iterator current_item( stuff_set.begin() );
> while ( current_item != stuff_set.end() )
> {
> if ( is_bad( *item ) )
> {
> std::set<Stuff>::iterator previous_item( --current_item );
> stuff_set.erase( ++current_item );
> current_item = previous_item;
> }
> ++current_item;
>
> }
>
> Is this the best way I can structure this? I hate writing code like
> this :(
while ( current_item != stuff_set.end() )
if ( is_bad( *item ) )
current_item = stuff_set.erase( current_item );
else
++current_item;
or alternatively:
stuff_set.erase( std::remove_if( stuff_set.begin(), stuff_set.end(),
is_bad ),
stuff_set.end() );
Yechezkel Mett
Vaclav Haisman
> On Nov 12, 10:47 am, Alfons <alfonsvanwor...@gmail.com> wrote:
> or alternatively:
>
> stuff_set.erase( std::remove_if( stuff_set.begin(), stuff_set.end(),
> is_bad ),
> stuff_set.end() );
not a sequence.
--
VH
Seungbeom Kim
> Yechezkel Mett wrote, On 12.11.2009 14:27:
>> On Nov 12, 10:47 am, Alfons <alfonsvanwor...@gmail.com> wrote:
> [...]
>> or alternatively:
>>
>> stuff_set.erase( std::remove_if( stuff_set.begin(), stuff_set.end(),
>> is_bad ),
>> stuff_set.end() );
> The remove/erase idiom AFAIK does not work on std::set<> since std::set<> is
> not a sequence.
Correct, but is it explicitly stated in the standard? If so, where?
I couldn't find a statement in the standard that prevents non-sequences
from being used with std::remove, other than the title of the subclause
"Mutating /sequence/ operations" (25.2), but it's not that none of the
algorithms in that section can be used with associative containers.
--
Seungbeom Kim
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
dietma...@gmail.com
> Vaclav Haisman wrote:
> > The remove/erase idiom AFAIK does not work on std::set<> since std::set<> is
> > not a sequence.
>
> Correct, but is it explicitly stated in the standard?
The fact that 'std::remove_if()' cannot be used with a range defined
by 'std::set<T>::iterator's is implicit in the fact that the
'value_type' of the iterators used with 'std::remove_if()' has to be
assignable. For 'std::set<T>' (and 'std::map<K, T>') this is not the
case. For map's it is obvious that the 'value_type' is not assignable.
For set's I actually don't see this requirement! On the positive side:
there is an 'erase()' member taking a range, however.
--
Daniel Krügler
> Vaclav Haisman wrote:
> > Yechezkel Mett wrote, On 12.11.2009 14:27:
> >> On Nov 12, 10:47 am, Alfons <alfonsvanwor...@gmail.com> wrote:
> > [...]
> >> or alternatively:
>
> >> stuff_set.erase( std::remove_if( stuff_set.begin(), stuff_set.end(),
> >> is_bad ),
> >> stuff_set.end() );
> > The remove/erase idiom AFAIK does not work on std::set<> since std::set<> is
> > not a sequence.
>
> Correct, but is it explicitly stated in the standard? If so, where?
> I couldn't find a statement in the standard that prevents non-sequences
> from being used with std::remove, other than the title of the subclause
> "Mutating /sequence/ operations" (25.2), but it's not that none of the
> algorithms in that section can be used with associative containers.
The C++03 standard is open in this point, but for C++0x it is pretty
clear that
std::remove_if( stuff_set.begin(), stuff_set.end(), is_bad );
won't be well-formed code, because as of [associative.reqmts]/6
"[..] For associative containers where the value type is the same as the
key type, both iterator and const_iterator are constant iterators."
but remove_if requires mutable iterator types ([alg.remove]/1):
"Requires: The type of *first shall satisfy the MoveAssignable
requirements[..]"
For that matter it is completely irrelevant whether the underlying
container is a sequence container or not: All "non-modifying"
algorithms should work for std::set and friends, because the
iterator range [stuff_set.begin(), stuff_set.end()) represents
a sequential view even for a non-sequence container.
HTH & Greetings from Bremen,
Daniel Kr�gler
--
Nick Hounsome
> In C++0x, you will be able to write:
>
> std::set<Stuff>::iterator i(stuff_set.begin());
> while (i != stuff_set.end()) {
> if (is_bad(*i))
> i = stuff_set.erase(i);
> else
> ++i;
>
> }
Better yet you will be able to write:
auto i( stuff_set.begin() );
--
SeanW
> In C++0x, you will be able to write:
> std::set<Stuff>::iterator i(stuff_set.begin());
> while (i != stuff_set.end()) {
> if (is_bad(*i))
> i = stuff_set.erase(i);
> else
> ++i;
> }
Even less ugly with type inference:
auto i = stuff_set.begin();
while (i != stuff_set.end()) {
if (is_bad(*i))
i = stuff_set.erase(i);
else
++i;
}
Sean
--
dhruv
> std::set<Stuff>::iterator current_item( stuff_set.begin() );
> while ( current_item != stuff_set.end() )
> {
> if ( is_bad( *item ) )
> {
> std::set<Stuff>::iterator previous_item( --current_item );
> stuff_set.erase( ++current_item );
> current_item = previous_item;
> }
> ++current_item;
>
> }
>
> Is this the best way I can structure this? I hate writing code like
> this :(
Someone please correct me if I am wrong, but the code above seems
incorrect to me.
You are decrementing the iterator that is assigned container.begin();
I don't think that can be done.
Also, should "if ( is_bad( *item ) )" be "if ( is_bad
( *current_item ) )"?
Regards,
-Dhruv.
n00m
The code erases all odd elements from a set<int>....
but replace in "for(...; i <= 25; ...)" 25 with 55
now "7" stays UN-erased
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
using namespace std;
void print(int elem) {
cout << elem << endl;
}
int main() {
set<int> r;
for (int i = 0; i <= 25; i += 5) r.insert(i);
r.insert(3);
r.insert(7);
r.insert(9);
r.insert(11);
// r = {0, 3, 5, 7, 9, 10, 11, 15, 20, 25}
set<int>::iterator rit = r.begin();
while (rit != r.end()) {
if (*rit % 2 == 1)
r.erase(rit);
///else
++rit;
}
for_each(r.begin(), r.end(), print);
system("pause");
return 0;
Ulrich Eckhardt
> I think in-place-erasing totally corrupt the iterator.
Right, whenever you use an iterator to erase an element, the iterator is
invalidated. Further, all iterators referring to the same element are
invalidated. With some containers, even all iterators could be invalidated.
However, all the iterator invalidation rules are documented. While not
mandatory for the C++ standard library, the STL's documentation (available
online) still correctly describes those rules, IIRC.
> // r = {0, 3, 5, 7, 9, 10, 11, 15, 20, 25}
> set<int>::iterator rit = r.begin();
> while (rit != r.end()) {
> if (*rit % 2 == 1)
> r.erase(rit);
> ///else
> ++rit;
> }
Yes, this code is wrong. After erasing an element, you are still using the
iterator. Note that even incrementing it means using it. The correct code
requires careful use of a postfix increment operator:
set<int>::iterator rit = r.begin();
while (rit != r.end()) {
if (*rit % 2 == 1)
r.erase(rit++);
else
++rit;
}
Uli
--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
n00m
> The correct code
> requires careful use of a postfix increment operator:
>
> set<int>::iterator rit = r.begin();
> while (rit != r.end()) {
> if (*rit % 2 == 1)
> r.erase(rit++);
> else
> ++rit;
> }
Seems you are goddam right
but ouch I can't still tell the difference
and personally I'd better use the commented method:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
using namespace std;
void print(int elem) {cout << elem << endl;}
bool is_odd(int x) {return x % 2 != 0;}
int main() {
set<int> r;
int tmp[] = {0,1,-5,-3,8,3,2,4,5,6,7,8,9,11,22,44,55};
r.insert(tmp, tmp + sizeof(tmp)/sizeof(int));
set<int>::iterator rit = r.begin();
while (rit != r.end()) {
if (is_odd(*rit))
r.erase(rit++);
else
++rit;
}
/*
while (true) {
set<int>::iterator rit = find_if(r.begin(), r.end(), is_odd);
if (rit == r.end()) break;
r.erase(rit);
}
*/
for_each(r.begin(), r.end(), print);
system("pause");
return 0;
}
--
Ulrich Eckhardt
> On Nov 23, 11:42 pm, Ulrich Eckhardt <eckha...@satorlaser.com> wrote:
>> The correct code
>> requires careful use of a postfix increment operator:
>>
>> set<int>::iterator rit = r.begin();
>> while (rit != r.end()) {
>> if (*rit % 2 == 1)
>> r.erase(rit++);
>> else
>> ++rit;
>> }
>
> Seems you are goddam right
> but ouch I can't still tell the difference
Maybe this helps:
while (rit != r.end()) {
iterator next = rit;
++next;
if (*rit % 2 == 1)
r.erase(rit);
rit = next;
}
Alternatively, just to illustrate how the postfix increment operator works:
set<int>::iterator rit = r.begin();
while (rit != r.end()) {
if (*rit % 2 == 1) {
set<int>::iterator tmp = rit;
++rit;
r.erase(tmp);
} else
++rit;
}
> and personally I'd better use the commented method:
[...]
> while (true) {
> set<int>::iterator rit = find_if(r.begin(), r.end(), is_odd);
> if (rit == r.end()) break;
> r.erase(rit);
> }
This has the disadvantage that the number of calls to is_odd is much
greater, as every time it finds an odd element it restarts scanning the
entire sequence. You can avoid this by only scanning the remaining
sequence, but then you are again bitten by the invalidation rules, unless
you pay attention again:
iterator it = find_if(r.begin(), r.end(), is_odd);
while(it!=r.end()) {
r.erase(it++);
it = find_if(it, r.end(), is_odd);
}
This IMHO has the disadvantage that the predicate (is_odd) is specified
twice.
Uli
--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
peter koch larsen
The problem with your solution is that you traverse the set once for
each element deleted and then one more time. If the number of elements
to delete is proportional to the total number of elements, your
solution becomes O(n*n) instead of O(n).
/Peter
Vidar Hasfjord
> std::set<Stuff>::iterator current_item( stuff_set.begin() );
> while ( current_item != stuff_set.end() )
> {
> if ( is_bad( *item ) )
> {
> std::set<Stuff>::iterator previous_item( --current_item );
> stuff_set.erase( ++current_item );
> current_item = previous_item;
> }
> ++current_item;
>
> }
>
> Is this the best way I can structure this? I hate writing code like
> this :(
Consider a non-mutating solution:
set <Stuff> t;
remove_copy_if (stuff_set.begin (), stuff_set.end (),
inserter (t, t.end ()), is_bad);
swap (t, stuff_set);
If the number of erased elements is high and the cost of copying is
low then it may be more efficient to build a new set than to mutate
the source.
Regards,
Vidar Hasfjord
Vidar Hasfjord
> [...]
>
> iterator it = find_if(r.begin(), r.end(), is_odd);
> while(it!=r.end()) {
> r.erase(it++);
> it = find_if(it, r.end(), is_odd);
> }
>
> This IMHO has the disadvantage that the predicate (is_odd) is specified
> twice.
Actually, your rewrite introduced the repetition needlessly. Use a
loop with a stop condition in the middle; just like the original code:
for (iterator it = r.begin ();;) {
it = find_if (it, r.end (), is_odd);
if (it == r.end ()) break;
r.erase (it++);
}
Regards,
Vidar Hasfjord
--
Peter Dimov
> In C++0x, you will be able to write:
>
> std::set<Stuff>::iterator i(stuff_set.begin());
> while (i != stuff_set.end()) {
> if (is_bad(*i))
> i = stuff_set.erase(i);
> else
> ++i;
>
> }
>
> which works well both for sequences and associative containers.
This loop is O(N^2) for sequences such as vector and deque. C++03 was
better in not allowing one to write it, IMO.
--