[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

Strange behaviors of Iterator for set

Bo Yang

11/19/2008 2:17:00 AM

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
10 Answers

Victor Bazarov

11/19/2008 2:35:00 AM

0

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

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

James Kanze

11/19/2008 9:25:00 AM

0

On Nov 19, 3:35 am, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
> Bo Yang wrote:

[...]
> > ms.erase(it);

This action invalidates "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.

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.

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

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.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Brian Luk

11/19/2008 9:57:00 AM

0

What'z up Bo?

Victor Bazarov

11/19/2008 2:22:00 PM

0

James Kanze wrote:
> On Nov 19, 3:35 am, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
>> 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

11/19/2008 4:26:00 PM

0

On 2008-11-19 09:22:25 -0500, Victor Bazarov <v.Abazarov@comAcast.net> said:

> James Kanze wrote:
>> On Nov 19, 3:35 am, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
>>> 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

11/20/2008 1:24:00 AM

0

On Nov 20, 12:25 am, Pete Becker <p...@versatilecoding.com> wrote:
> On 2008-11-19 09:22:25 -0500, Victor Bazarov <v.Abaza...@comAcast.net> said:
>
>
>
> > James Kanze wrote:
> >> On Nov 19, 3:35 am, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
> >>> 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

11/20/2008 1:26:00 AM

0

On Nov 19, 5:24 pm, James Kanze <james.ka...@gmail.com> wrote:
> On Nov 19, 3:35 am, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
>
> > Bo Yang wrote:
>
>     [...]
>
> > >  ms.erase(it);
>
> This action invalidates "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.
>
> 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.
>
> > > 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.
>
> 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

11/20/2008 8:51:00 AM

0

On Nov 19, 3:22 pm, Victor Bazarov <v.Abaza...@comAcast.net> wrote:
> James Kanze wrote:
> > On Nov 19, 3:35 am, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
> >> 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:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

James Kanze

11/20/2008 8:57:00 AM

0

On Nov 20, 2:25 am, Bo Yang <struggl...@gmail.com> wrote:
> On Nov 19, 5:24 pm, James Kanze <james.ka...@gmail.com> wrote:
> > On Nov 19, 3:35 am, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:

[...]
> 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:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Pete Becker

11/20/2008 12:58:00 PM

0

On 2008-11-20 03:50:41 -0500, James Kanze <james.kanze@gmail.com> said:

>
> 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<int> you 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)