Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Strange behaviors of Iterator for set (http://www.velocityreviews.com/forums/t645165-strange-behaviors-of-iterator-for-set.html)

Bo Yang 11-19-2008 02:17 AM

Strange behaviors of Iterator for set
 
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 11-19-2008 09:24 AM

Re: Strange behaviors of Iterator for set
 
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 09:57 AM

Re: Strange behaviors of Iterator for set
 
What'z up Bo?

Bo Yang 11-20-2008 01:24 AM

Re: Strange behaviors of Iterator for set
 
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 01:25 AM

Re: Strange behaviors of Iterator for set
 
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 08:50 AM

Re: Strange behaviors of Iterator for set
 
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 oriente objet/
Beratung in objektorientierter Datenverarbeitung
9 place Smard, 78210 St.-Cyr-l'cole, France, +33 (0)1 30 23 00 34


James Kanze 11-20-2008 08:57 AM

Re: Strange behaviors of Iterator for set
 
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 oriente objet/
Beratung in objektorientierter Datenverarbeitung
9 place Smard, 78210 St.-Cyr-l'cole, France, +33 (0)1 30 23 00 34


All times are GMT. The time now is 06:39 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.