llvm dev - Dec 2007 - [LLVMdev] SmallPtrSet Iterator Behavior

What are the rules regarding iterator stability for SmallPtrSet?
I'm running into a problem where erasing an element seems
to invalidate iterators that are not pointing at the erased element.

Specifically, the set is in small mode, I advance an iterator to the last 
element in the set (not end(), but one before) and then erase the 
second-to-last element.  I understand that the last element will replace
the element at the erased location and I would think that the advanced
iterator would now point to end().  In other words, the advanced iterator
will "miss" the last element.  But that doesn't seem to be the
case
when I do an equality check with end().  It's pointing somewhere not
good because I try to dereference it and I get garbage.

Thanks for any help.

                                   -Dave

On Tuesday 04 December 2007 13:28, Chris Lattner wrote:
> > Specifically, the set is in small mode, I advance an iterator to the
last
> > element in the set (not end(), but one before) and then erase the
> > second-to-last element.  I understand that the last element will
replace
>
> Right, deleting an element will invalidate any iterators past it, just
> like a vector.  I don't know of a good solution to this that
doesn't break
> the efficiency properties of smallset.  Do you?
What I've done is code up a version of erase() that returns an iterator
to the next element.  There still seem to be some problems that I'm
looking into.  This interface has the side benefit of being standard-library
compatible and can be used with standard algorithms.

If I get something working I'll check it in if there's interest.

                                          -Dave

On Tue, 4 Dec 2007, David Greene wrote:
> What are the rules regarding iterator stability for SmallPtrSet?
> I'm running into a problem where erasing an element seems
> to invalidate iterators that are not pointing at the erased element.
Interesting question.
> Specifically, the set is in small mode, I advance an iterator to the last
> element in the set (not end(), but one before) and then erase the
> second-to-last element.  I understand that the last element will replace
Right, deleting an element will invalidate any iterators past it, just 
like a vector.  I don't know of a good solution to this that doesn't
break
the efficiency properties of smallset.  Do you?

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/