# Particle in Cell: efficient data structure handling

I am building a simulation where you have 'Agents' distributed over a rather large landscape. Because the number of Agents is small, compared to the size of the landscape, I use the PIC approach where the landscape is divided into rather large cells and every cell can contain multiple agents - in contrast to a classical grid based approach. This should speed up spatial analysis.

I am asking whether there is a way to improve the code I came up with:

Agents contain an iterator to the node in the cell and a ptr to the cell containing the node

class Agent;

typedef std::list <Agent*> CELL;

class Agent {
public:
//...stuff...
CELL::iterator cell_iter;
CELL*cell_ptr;
};

class Grid {
public:
Grid(int dimx,int dimy,int cellsize);
CELL *GetCell(double x,double y);
private:
std::vector <std::vector<CELL>> grid_;
int dimx_,dimy_,cellsize_,ncellx_,ncelly_;
};


std::list <Agent> population;
//..stuff...
Agent seed(pos_x,pos_y,seed_type,10.1); // create a local agent
population.push_back(std::move(seed));
Agent *agent=&population.back()
CELL *cell=GetCell(agent->x_,agent->y_); // get the cell for the agents pos
cell->push_back(agent); // add the agents ptr to the cell
agent->cell_ptr=cell; // save the agents cell to the agent
agent->cell_iter=--cell->end(); // save an iterator to the actual node


To delete an individual

auto iter=population.begin();
//...stuff...
(*iter).cell_ptr->erase((*iter).cell_iter); // erase the ptr to the agent from the cell
iter=population.erase(iter);


If you have move push_back then you should also have emplace_back.

population.emplace_back(pos_x,pos_y,seed_type,10.1);


Erasing the individual means moving everyone that comes after. If you don't care about order then do a swap with back:

auto iter=population.begin();
//...stuff...
(*iter).cell_ptr->erase((*iter).cell_iter); // erase the ptr to the agent from the cell
std::swap(*iter, population.back());
population.pop_back();
//doesn't invalidate iter

• thanks for the "emplace_back" trick. why is the swap faster? Apr 15, 2016 at 14:15
• @SebastianLehmann it only needs to copy 1 element over instead of half. The swap is a O(1) operation while the simple erase is O(n) Apr 15, 2016 at 14:38
• i thought erase is guarantied to be O(1) and remove is O(n) Apr 15, 2016 at 14:54
• Apr 15, 2016 at 14:55