0

The size of the grid will be known at the start (but will be different each time the program starts). However, the DEPTH of each cell is not a mere value, but rather a population of objects that will vary constantly during runtime.

Q: What is the most recommended (efficient and easy to maintain; less prone to user error) way of implementing this ?

  • Is this some kind of a standard 2D array of vector pointers ?
  • Is it a 3D Vector array ?
  • Is it a 2D array of linked lists, or binary trees (I am thinking binary trees will add complexity overhead because of continuous deletion and insertion node-gymnastics)
  • Is it some other custom data structure ?

enter image description here

Thomas An
  • 503
  • 2
  • 7
  • 17
  • Maybe you could describe your actual application. Do you need to iterate through these piles, or do you just need to count the height of each pile? If you have a fixed set of nodes, you could simply store the grid position in the node and update a depth histogram. When you move a node, you just do two histogram updates and change the grid position. Not sure if that's useful. As I say, depends on what you're trying to achieve. – paddy May 20 '13 at 03:47
  • It's a collision grid table. Each cell contains references to a variable number of objects. So we are dealing with thousands of searches, deletions and additions per millisecond. However, there should be no more than about 5 or 10 objects per cell (we would rather make the grid finer to reduce the number of objects per cell) – Thomas An May 20 '13 at 03:55
  • Well, try it out with storing a vector in each cell. In most cases, a vector is better than a list. Sounds a bit like [this answer](http://stackoverflow.com/a/14615449/1553090) I gave a while back. If you need to get quicker and dirtier, you can memory-pool the vectors. Maybe even use vectors as a second-resort. You might want to experiment with storing small local arrays inline and then spilling over to a vector, so you keep most of your memory accesses local. In that respect, blocking your grid into pages might also help to improve locality. – paddy May 20 '13 at 04:11

1 Answers1

2

Use a 1D array for best cache locality. A vector would be fine for this.

std::vector<int> histdata( width * height );

If you need to index the rows quickly, then make something to point into it:

std::vector<int*> histogram( height );
histogram[0] = &histdata[0];
for( int i = 1; i < height; i++ ) {
    histogram[i] = histogram[i-1] + width;
}

Now you have a 2D histogram stored in a 1D vector. You can access it like this:

histogram[row][col]++;

If you wrap all this up in a simple class, you're less likely to do something silly with the pointers. You can also make a clear() function to set the histogram data to zero (which just rips through the histdata vector and zeros it).

paddy
  • 60,864
  • 6
  • 61
  • 103
  • the depth of each cell is not a mere value. It's a population of objects that will vary constantly during runtime. – Thomas An May 20 '13 at 03:09
  • I'd hardly call it a histogram in that case. Anyway, that's fine. Just `typedef std::vector Objects` and replace `int` with `Objects` in the example above. Then every cell has a vector that you can populate with your items. – paddy May 20 '13 at 03:34