std::list of pointers becomes invalid on entry removal

Question

I have a list of pointers that reference time objects that need a turn to go in my game. This example has two TimeObject* in the list. This code works until an item is removed from the list: when that happens the other one points to becomes an invalid address. Neither TimeObject is deleted when this happens; only the pointer is removed from the list. What is causing this?

TimeUnlink() is called in TimeObject::Tick(). It is not a static, but the list is.

I'm using GCC 4.6.2 on Linux. The program is not threaded.

void TimeObject::TimeUnlink()
{
    printf("Time unlink\n");

    TimeObject::list_.remove(this);

    timeobject_flags_.linked_ = 0;
}

void GameTime::GameTurn(uint16_t _time)
{
    tick_ += _time;

    for(std::list<TimeObject*>::iterator it = TimeObject::list_.begin(); it != TimeObject::list_.end(); ++it)
    {
        TimeObject *timeobject = *it;

        printf("GameTurn %p\n", timeobject);

        if(timeobject == NULL) { printf("continue\n"); continue; }

        timeobject->time_ += _time;

        if(timeobject->speed_ && timeobject->time_ >= timeobject->speed_)
        {
            while(timeobject->timeobject_flags_.linked_ && timeobject->time_ - timeobject->speed_ > 0)
            {
                timeobject->time_ -= timeobject->speed_;

                if(timeobject->mapobject_)
                {
                    timeobject->mapobject_->Tick();
                }
            }
        }
    }
}

Error output:

GameTurn 0xc1e048
GameTurn 0x696828
GameTurn 0xc1e048
GameTurn 0x696828
GameTurn 0xc1e048
GameTurn 0x696828
GameTurn 0xc1e048
Time unlink
GameTurn (nil)
continue
GameTurn 0xc1e030

Program received signal SIGSEGV, Segmentation fault.
0x00000000004059a1 in GameTime::GameTurn(unsigned short) ()

Answer 1

In your output sequence, the pointers are alternating between 0xc1e048 and 0x696828, implying that 0xc1e048 is the first item in the list and 0x696828 is the second. Based on that, it looks like the object at 0xc1e048 is getting unlinked while GameTurn::GameTurn is in the middle of the loop, most likely in the call to timeobject->mapobject_->Tick(), or by another thread as mentioned by @hmjd. Removing an object from the list makes the iterator pointing to the object invalid.

Assuming the code is single threaded and the call to Tick is causing the problem, then something like this might work:

void GameTime::GameTurn(uint16_t _time)
{
    tick_ += _time;

    for(std::list<TimeObject*>::iterator it = TimeObject::list_.begin(); it != TimeObject::list_.end(); )
    {
        TimeObject *timeobject = *it;
        ++it;

        printf("GameTurn %p\n", timeobject);

        if(timeobject == NULL) { printf("continue\n"); continue; }

        timeobject->time_ += _time;

        if(timeobject->speed_ && timeobject->time_ >= timeobject->speed_)
        {
            while(timeobject->timeobject_flags_.linked_ && timeobject->time_ - timeobject->speed_ > 0)
            {
                timeobject->time_ -= timeobject->speed_;

                if(timeobject->mapobject_)
                {
                    timeobject->mapobject_->Tick();
                }
            }
        }
    }
}

(The only difference is the the increment of it is moved from the for statement to the loop body after assigning it to timeobject. Advancing it before it can be invalidated should fix the problem.

If your code is multithreaded, you will need a mutex.

Answer 2

When you remove the object from the list_ you need to take care of the iterator because it becomes invalid after you have removed the list entry

One way is to before removing the item, remember the next entry in the list and continue with that after you removed the object.

Answer 3

Does the call:

timeobject->mapobject_->Tick();

result in TimeUnlink() being called and then remove being called?

When you remove from a list, the iterator for the element being removed will become invalid, but your code may continue trying to use it by doing a ++it.

Answer 4

It looks like you're deleting s.th. from the list during the iteration loop in the GameTurn method. That makes the iterator invalid. You have to remember the items to delete from the list and delete these from the list after the loop ended.