🔒 Locked 🎯 Unreal

std::vector erase + iteration question

Started by MikeJM Jan 23, 2007 at 1:26 AM 5 replies 1.1k views

Original Post

Jan 23, 2007 at 1:26 AM

Hi, I don't have a copy of the standard so I mostly rely on things like sgi's stl site. I have a bunch of legacy code to deal with that is pretty ugly and I cannot make wholesale changes to it. I'm trying to convert a tick loop that was obviously wrong before into a tick loop that works. It's now storing a vector of objects that have a virtual tick function that can remove the object from the list that it is stored in but often won't. The order of iteration doesn't matter but each item should be ticked exactly once per frame. I cannot change the interface of the Tick call or the fact that things can remove themselves from the vector during the call. After reading notes on vector at the bottom of the sgi site, particularly number 5, I came to the conclusion that if I make sure I have an iterator before the one whose value is being Tick'ed I will be safe. So I tried:

ObjectList::reverse_iterator it = m_objects.rbegin();
while( it != m_objects.rend() )
{
    Object* o = *it++;
    o->Tick();
}

(note there is a post increment after "*it" that is not showing up in the preview pane of my firefox) However, Microsoft's VC8 STL assert that the ( it != m_objects.rend() ) uses incompatible iterators after a Tick is reached that removes itself. Is there a problem with my understanding of vector::erase or are Microsoft's checked iterators overly cautious?

Vorpy

Jan 23, 2007 at 3:11 AM

You can ensure that it is definitely correct by making a copy of the vector and iterating on the copy.

The Microsoft STL is surprisingly not being overly cautious! The problem is not in your understanding of erase, but in the reverse iterators. A reverse iterator wraps a base iterator that comes after the element the reverse iterator is currently on. For example, rbegin() returns an iterator to the last element of the sequence, but internally it wraps the end() iterator. The way your code is written actually guarantees that your iterator will be invalidated! While the result of this is undefined I'm inclined to believe that it would probably work in practice since you never dereference the invalidated base iterator.

Try rewriting your code using normal iterators, keeping a copy of the iterator before the one you're calling Tick() on. If it's possible for a Tick() to add elements to the vector, then use my suggestion above.

MikeJM

Author

MikeJM

Jan 23, 2007 at 9:28 AM

OIC reverse_iterator *it internally does essentially a return *(it-1);

I'm not sure how to implement the required behavior using iterators then. The best I could come up with was:

std::size_t sz = m_objects.size();for( std::size_t i = 0; i < sz; ){	m_objects->Tick();	i += 1 - (sz - m_objects.size());	sz = m_objects.size();}

Which feels like a hack.

Vorpy

Jan 24, 2007 at 4:27 PM

Hmm I see, yeah it is kind of tough to do this with iterators. The solution feels like a hack because having elements remove themselves from a list is a poor design. I guess you could disable microsoft's iterator checking, or use your solution, or use my solution of creating a copy of the pointers and iterating over the copies.

The problem with iterating over such a collection is that you have no way to determine if an element removed itself from the list after calling tick(). A better design would have been to have the elements simply return true or false to indicate if they should be removed after calling tick, or at least to indicate if they removed themselves.

Zipster

511

Zipster

Jan 24, 2007 at 8:01 PM

You could always check the size of the vector both before and after the Tick call to see if there are less elements, but... ick. You definitely wouldn't want to do this with iterators.

Zahlman

257

Zahlman

Jan 24, 2007 at 11:05 PM

Quote:
Original post by MikeJM
I cannot change the interface of the Tick call or the fact that things can remove themselves from the vector during the call.

!!!
Extreme danger!

This code is effectively broken. Objects, generally speaking, have no business removing themselves from containers because they have no business knowing whether or not they *are in* containers.

Also, storing raw pointers to objects in a container is just begging for trouble, unless they are weak (i.e. the responsibility for deallocating the pointed-at objects lies somewhere else entirely).

Go yell at the person responsible.

With properly written code (an Object class that doesn't store any kind of container reference, and with a Tick function that returns a bool to indicate "death", and a container of elements or smart pointers to elements rather than raw pointers to elements - or something like this), you can do this simply and idiomatically, and know that it will work, using the erase-remove idiom.

jeroenb

Jan 25, 2007 at 6:43 AM

I agree with Zahlman. An object should generally not know its container (although I know of implementations which do know their container).

But if you insist of using a hack version than I would really recommend the following lines:

for ( int i = m_object.size()-1; i >= 0; --i ){  Object* o = m_objects;  o->Tick();}

This code iterates over your vector from the end till the beginning. For these lines of code is does not matter whether or not the object removes itself or not.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.