Add and remove from a list in runtime

Question

I have a simulation program. In the main class of the simulation I am "creating + adding" and "removing + destroying" Agents.

The problem is that once in a while (once every 3-4 times I run the program) the program crashes because I am apparently calling a function of an invalid agent in the main loop. The program works just fine most of the time. There are normally thousands of agents in the list.

I don't know how is it possible that I have invalid Agents in my Loop.

It is very difficult to debug the code because I receive the memory exception inside the "Agent::Step function" (which is too late because I cannot understand how was the invalid Agent in the list and got called).

When I look into the Agent reference inside the Agent::Step function (exception point) no data in the agent makes sense, not even the initialized data. So it is definitely invalid.

void World::step()
{
    AddDemand();

    // run over all the agents and check whether they have remaining actions
    // Call their step function if they have, otherwise remove them from space and memory
    list<Agent*>::iterator it = agents_.begin();
    while (it != agents_.end())
    {
        if (!(*it)->AllIntentionsFinished())
        {
            (*it)->step();
            it++;
        }
        else
        {
            (*it)->removeYourselfFromSpace();  //removes its reference from the space
            delete (*it);
            agents_.erase(it++);
        }
    }
}

void World::AddDemand()
{
    int demand = demandIdentifier_.getDemandLevel(stepCounter_);
    for (int i = 0; i < demand; i++)
    {
        Agent*  tmp  = new Agent(*this);
        agents_.push_back(tmp);
    }
}

Agent:

bool Agent::AllIntentionsFinished()
{
    return this->allIntentionsFinished_;  //bool flag will be true if all work is done
}

1- Is it possible that VStudio 2012 optimization of Loops (i.e. running in multi-thread if possible) creates the problem?

2- Any suggestions on debugging the code?

Jerry Coffin · Answer 1 · 2013-07-20T21:07:57.300

If you're running the code multi-threaded, then you'll need to add code to protect things like adding items to and removing items from the list. You can create a wrapper that adds thread safety for a container fairly easily -- have a mutex that you lock any time you do a potentially modifying operation on the underlying container.

template <class Container>
thread_safe {
    Container c;
    std::mutex m;
public:
    void push_back(typename Container::value_type const &t) { 
         std::lock_guard l(m);
         c.push_back(t);
    }
    // ...
};

A few other points:

You can almost certainly clean your code up quite a bit by having the list hold Agents directly, instead of a pointer to an Agent that you have to allocate dynamically.
Your Agent::RemoveYourselfFromSpace looks/sounds a lot like something that should be handled by Agent's destructor.
You can almost certainly do quite a bit more to clean up the code by using some standard algorithms.

For example, it looks to me like your step could be written something like this:

agents.remove_if([](Agent const &a) { return a.AllIntentionsFinished(); });

std::for_each(agents.begin(), agents.end(),
              [](Agent &a) { a.step(); });

...or, you might prefer to continue using an explicit loop, but use something like:

for (Agent & a : agents)
    a.step();

Thanks for the comments. Agent::RemoveYourselfFromSpace only removes the agents references from an Array called Space (so that it does not appear in the space). It does not touch anything else. I have hundreds of classes and using pointers for agents would make it easier to avoid chain independence between classes. Thanks for other suggestions too. — wmac, Jul 20 '13 at 19:28
@Jerry Coffin Did you mean "std::lock" or "std::lock_guard"? I thought std::lock was [a function](http://en.cppreference.com/w/cpp/thread/lock). — kfsone, Jul 20 '13 at 19:33

score 0 · Answer 2 · edited May 23 '17 at 12:12

0

The problem is this:

agents_.erase(it++);

See Add and remove from a list in runtime

I don't see any thread-safe components in the code you showed, so if you are running multiple threads and sharing data between them, then absolutely you could have a threading issue. For instance, you do this:

(*it)->removeYourselfFromSpace();  //removes its reference from the space
delete (*it);
agents_.erase(it++);

This is the worst possible order for an unlocked list. You should: remove from the list, destruct object, delete object, in that order.

But if you are not specifically creating threads which share lists/agents, then threading is probably not your problem.

edited May 23 '17 at 12:12

Community

1
1

answered Jul 20 '13 at 19:15

kfsone

23,617
2
42
74

thanks. Does it apply to lists too (since I use a list and not a vector). I do not use threads but I think vstudio 2012 compiler tries to use threads if it thinks it is ok. – wmac Jul 20 '13 at 19:21
Heh, yes - sorry, that was the wrong link - it's actually where the page I was trying to link referenced, but linking to the list page will make more sense :) – kfsone Jul 20 '13 at 19:22
Changing the order did not fix the issue. Using "it = agents_erase(it);" does not fix the problem either. I guess I should take another serious look at all my code. Your link points too to this same question btw. – wmac Jul 21 '13 at 05:37
The perils of using a phone to answer s/o. http://stackoverflow.com/questions/596162/can-you-remove-elements-from-a-stdlist-while-iterating-through-it - is your code multi-threaded (are YOU specifically creating threads and assigning agents to them?) if not, then the ordering won't matter. – kfsone Jul 21 '13 at 09:01

Add and remove from a list in runtime

2 Answers2