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?

Answer 1

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:

1. 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.

2. Your Agent::RemoveYourselfFromSpace looks/sounds a lot like something that should be handled by Agent's destructor.

3. 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();

Answer 2

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.