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<intms;
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

[Victor Bazarov]

Bo Yang wrote:

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<intms;
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;

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

set<int>::iterator ii = it;

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

cout << "++: " << *(++ii) << endl;
cout << "+2: " << *(++ii) << endl;
cout << "--: " << *(--it) << endl;
it++;
cout << "--++: " << *(it) << endl;

All this is undefined behaviour, by itself and due to the
preceding undefined behaviour.

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

This is all fine. 'it' is valid still, because your set
contains more than 4 values.

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

Here you go again...

>
it = ms.end();
it--;

That's fine. 'it' refers to the last element in the set.

ms.erase(it);

'it' now is invalid.

cout << "Deelted: " << *(it) << endl;
cout << "++: " << *(++it) << endl;
cout << "+2: " << *(++it) << endl;

And again, you're using an invalid iterator. Undefined
behaviour.

>
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.

Of course. When you erase the element through an iterator, the
iterator becomes *invalid*. It has no behavior defined by the
language.

I can't make sure what is a next ++ is in a set unlike I
am sure with a vector...

I don't understand that sentence. With all standard containers
if you erase the object, the iterator that used to refer to the
deleted object becomes *invalid*. What ++, what vector?

Does this a right behaviors?

Yes, it does, I guess.

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.

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

[Brian Luk]

What'z up Bo?

[Victor Bazarov]

James Kanze wrote:

On Nov 19, 3:35 am, "Victor Bazarov" <[e-mail]:

>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?

[..]

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]

On 2008-11-19 09:22:25 -0500, Victor Bazarov <v.********@comAcast.netsaid:

James Kanze wrote:

>On Nov 19, 3:35 am, "Victor Bazarov" <[e-mail]:

>>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.

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

[Bo Yang]

On Nov 20, 12:25*am, Pete Becker <[e-mail]:

On 2008-11-19 09:22:25 -0500, Victor Bazarov <[e-mail]:

James Kanze wrote:

On Nov 19, 3:35 am, "Victor Bazarov" <[e-mail]:
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

[James Kanze]

On Nov 19, 3:22 pm, Victor Bazarov <[e-mail]:

James Kanze wrote:

On Nov 19, 3:35 am, "Victor Bazarov" <[e-mail]:

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 (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]

[James Kanze]

On Nov 20, 2:25 am, Bo Yang <[e-mail]:

On Nov 19, 5:24 pm, James Kanze <[e-mail]:

On Nov 19, 3:35 am, "Victor Bazarov" <[e-mail]:

[...]

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.

--
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]

[Pete Becker]

On 2008-11-20 03:50:41 -0500, James Kanze <ja*********@gmail.comsaid:

>
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.

This muddles the fundamental distinction between sequences and
containers. The global algorithm remove_if operates on sequences. erase
operates on containers. Containers are a way to manage sequences, but
they are not sequences.

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.

remove_if doesn't reorder. It removes elements. If you call remove_if
to remove 2's from the input sequence

1 2 3 2 4 5 2 6

the result, designated by the start iterator of the original input
sequence and the end iterator returned by remove_if, is the sequence

1 3 4 5 6

If you got the input sequence by calling begin() and end() on a
vector<intyou can look at the elements of the vector that come after
the result sequence (i.e. the elements beginning at the iterator that
remove_if returned), and you'll see whatever junk was left over. If you
want to have the vector hold the result sequence you have to erase
those junk elements, because the algorithm can't. But now you're
dealing with the vector that manages the sequence, and not with the
sequence itself.

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