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) ()

Where does the TimeUnlink function get called? Is this function or the list a static member? — mathematician1975, Jun 15 '12 at 21:34
As an aside, use smart pointers (or no pointers at all) in your container. Because you use pointers you need to manually deallocate each item (i.e., call `delete`), nullifying the container's ability to manage memory for you. — Ed S., Jun 15 '12 at 22:13
No need to worry about that in this case: these pointers only refer back to objects already instantiated elsewhere. — Shawn Buckley, Jun 15 '12 at 22:20

score 5 · Accepted Answer · answered Jun 15 '12 at 21:51

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.

I ended up going with something quite similar. Even though it is single threaded I redesigned it so that it could be multithreaded. — Shawn Buckley, Jun 15 '12 at 22:00

score 3 · Answer 2 · answered Jun 15 '12 at 21:43

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.

score 3 · Answer 3 · answered Jun 15 '12 at 21:43

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.

answered Jun 15 '12 at 21:43

Scott Langham

58,735
39
131
204

1

http://stackoverflow.com/questions/1016307/list-iterator-remove This answer explains the situation well and has a solution using the 'erase' method. – Scott Langham Jun 15 '12 at 21:45

score 1 · Answer 4 · answered Jun 15 '12 at 21:48

1

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.

answered Jun 15 '12 at 21:48

πάντα ῥεῖ

1
13
116
190

std::list of pointers becomes invalid on entry removal

4 Answers4