Strange behaviors of Iterator for set

[Bo Yang]

Hi,
Today, I make some test on the C++ STL iterators of set containers
with GNU g++ compiler. The code is:

#include <set>
#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
set<int> ms;
int i;
for (i=1; i<10; i++)
ms.insert(i);

set<int>::iterator it = ms.begin();
it++;

ms.erase(it);
cout << "Deleted: " << *(it) << endl;
set<int>::iterator ii = it;
cout << "++: " << *(++ii) << endl;
cout << "+2: " << *(++ii) << endl;
cout << "--: " << *(--it) << endl;
it++;
cout << "--++: " << *(it) << endl;

ms.insert(2);
it = ms.begin();
it++;
it++;
it++;
it++;

ms.erase(it);
cout << "Deleted: " << *(it) << endl;
ii = it;
cout << "++: " << *(++ii) << endl;
cout << "+2: " << *(++ii) << endl;
cout << "--: " << *(--it) << endl;
it++;
cout << "--++: " << *(it) << endl;

it = ms.end();
it--;
ms.erase(it);
cout << "Deelted: " << *(it) << endl;
cout << "++: " << *(++it) << endl;
cout << "+2: " << *(++it) << endl;

return 0;
}

and the output is:
Deleted: 2
++: 1
+2: 3
--: 1
--++: 3
Deleted: 5
++: 6
+2: 7
--: 6
--++: 7
Deelted: 9
++: 8
+2: 7

I find that, when I erase something, the whole iterator's behavior is
unpredicted. I can't make sure what is a next ++ is in a set unlike I
am sure with a vector...
Does this a right behaviors? And when I use the remove_if and many
other algorithm on set, it will make some crash, why?

Thanks a lot!

Regards!
Bo

 

[James Kanze]

Bo Yang wrote:

[...]
This action invalidates "it".

Undefined behaviour. You're trying to dereference an invalid
iterator.

You're constructing another iterator and initialising it from
the invalid iterator; the 'ii' becomes invalid immediately.

Actually, I think this statement is also undefined behavior,
even if you never use ii later. The concept of iterators is
designed so that a pointer into an array is an iterator, and
just copying an invalid pointer is undefined behavior, so
presumably the same holds for iterators.

Don't know. Show the code, then we can talk.

It shouldn't compile, if your library implementation and
compiler are conformant. You can't modify members of a set,
which means that none of the mutating algorithms can be used on
it. remove_if is a mutating algorithm.

Note that historically, there was some discussion about this,
and many early implementations of std::set allowed mutating its
members, as long as the mutations didn't affect the
ordering---if they did, it was undefined behavior. (The
mutations done by remove_if will definitely affect the
ordering.) It's highly likely that some implementations
continue with this policy, despite the standard, in order to
avoid breaking existing code. The behavior he describes would
seem to correspond to the behavior of such an implementation; a
core dump is certainly one possibility of undefined behavior.

 

[Brian Luk]

What'z up Bo?

 

[Bo Yang]

Bo Yang wrote:
    [...]
And when I use the remove_if and many other algorithm on
set, it will make some crash, why?
Don't know.  Show the code, then we can talk.
It shouldn't compile, if your library implementation and
compiler are conformant.  You can't modify members of a set,
which means that none of the mutating algorithms can be used on
it.  remove_if is a mutating algorithm.

It's mutating to the sequence, not to the elements.  Removing from a
set is well-defined and it keeps the set in stable state, doesn't it?

remove_if, like all the standalone algorithms, operates on the elements
of a sequence and not on the underlying data structure. That's the
essential abstraction that iterators present. Think of how remove_if
would work on a vector: copy elements downward, but don't copy elements
that should be removed.

The key thing here is that algorithms operate on sequences, not on
containers. Containers are a way of producing sequences, but algorithms
don't know where the sequence came from, so cannot apply operations
like removing an element from a set. And that's why list has its own
sort member function: the generic sort algorithm doesn't work for a
list, so you need a container-specific sort function.

Ah, that is a good point. If STL algorithms operate on sequences, I
understand why my program failing. Thanks!

Regards!
Bo

 

[Bo Yang]

Bo Yang wrote:

    [...]

This action invalidates "it".

Undefined behaviour.  You're trying to dereference an invalid
iterator.
You're constructing another iterator and initialising it from
the invalid iterator; the 'ii' becomes invalid immediately.

Actually, I think this statement is also undefined behavior,
even if you never use ii later.  The concept of iterators is
designed so that a pointer into an array is an iterator, and
just copying an invalid pointer is undefined behavior, so
presumably the same holds for iterators.

Don't know.  Show the code, then we can talk.

It shouldn't compile, if your library implementation and
compiler are conformant.  You can't modify members of a set,
which means that none of the mutating algorithms can be used on
it.  remove_if is a mutating algorithm.

Note that historically, there was some discussion about this,
and many early implementations of std::set allowed mutating its
members, as long as the mutations didn't affect the
ordering---if they did, it was undefined behavior.  (The
mutations done by remove_if will definitely affect the
ordering.)  It's highly likely that some implementations
continue with this policy, despite the standard, in order to
avoid breaking existing code.  The behavior he describes would
seem to correspond to the behavior of such an implementation; a
core dump is certainly one possibility of undefined behavior.

Do you mean all associative containers such as set/multiset/map/
multimap can't be dealt with mutating algorithms? And that is to say
that only vector/list/deque can be applied by this algorithm? Thanks!

Regards!
Bo

 

[James Kanze]

Bo Yang wrote:

[...]

And when I use the remove_if and many other algorithm on
set, it will make some crash, why?
Don't know. Show the code, then we can talk.

It shouldn't compile, if your library implementation and
compiler are conformant. You can't modify members of a set,
which means that none of the mutating algorithms can be used
on it. remove_if is a mutating algorithm.

It's mutating to the sequence, not to the elements. Removing
from a set is well-defined and it keeps the set in stable
state, doesn't it?

Removing elements from a set is well defined, but the standard
library changes the meanings of some common English words, so
remove (and remove_if) don't mean remove (which is spelled erase
in the standard), but reorder. And any attempt to reorder a set
is going to cause problems somewhere, because in the standard,
set doesn't mean set, but is a list ordered on some specified
criterion.

 

[James Kanze]

[...]

Do you mean all associative containers such as
set/multiset/map/ multimap can't be dealt with mutating
algorithms?

No. It is only the key_type which can't be mutated. In set and
multiset, the key_type is the entire element, but in map and
multimap, it's only part of the element. (Internally, the
associative containers maintain their elements ordered on the
key_type; if you mutate the key_type, you can violate the
invariants maintaining the ordering.)

Of course, remove_if reassigns the entire element, so it can't
be used on any of the associative containers. (From a quick
glance, I think that this is true for all of the mutating
algorithms. But you could write an algorithm of your own for
std::map which only mutated the mapped_type.)

And that is to say that only vector/list/deque can be applied
by this algorithm?

Or any container of your own which allows mutation of a complete
element through an iterator.