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 replaceRight, 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/