what data structure to use for multidimensional mesh grid? (c++)

Question

I need to code a test platform for testing a specific algorithm. The system is supposed to be definable by input and 3 dimensional - similar to network on chip it has both node and link elements connecting to connect them. Due to the dimensions and links between nodes i have had some hardships on figuring out what data structures to use - a 3 dimensional array like array[x][y][z] is hard to handle as the pointer with drawbacks when adding links to connect the nodes (leaves several null value holes in the structure). Binary search trees are hard to realize since its a grid type. For this reason i have thought about doing a linked list where links are easier to implement. (the final testing platform should look something like the presentation below) where every link is also mapped down as they contain communication schedules

01-------02-------03
| \      | \      | \
|  10----|--11----|--12
|  | \   |  | \   |  | \
|  |  19-|--|--20-|--|--21
04-------05-------06 |  |
| \   |  | \|  |  | \|  |
|  13----|--14----|--15 |
|  | \|  |  | \|  |  | \|
|  |  22-|--|--23-|--|--24
07-------08-------09 |  |
  \|  |    \|  |    \|  |
   16-------17-------18 |
     \|       \|       \|
      25-------26-------27

Can any of you offer some help as to what type of structure in c++ would suit this kind of task. The finished program should be able to generate such a structure, given the dimension parameters of x, y and z.

currently a the rough outline should look like this

>class Node{
>  public:
>   Link* north;
>   Link* east;
>   Link* south;
>   Link* west;
>   Link* up;
>   Link* down;
>   //will contain a node specific scheduler
>}
>
>class Link{
>
>   Node* A;
>   Node* B;
>   //will contain a link specific scheduler
>}

EDIT 22.01.2013

well first of all as its a testing platform simulating a three dimensional network on chip type multiprocessor system. The task this system has to fill is to enable testing certain algorithms to help map tasks onto these nodes (where each node is connected to a processor core). In the light of this, the memory consumption might not be a problem as it is only for testing as i stated, for this reason it is imperative that the system would have both nodes and links as neither of them can be used by two event at the same time (communication on a link will block all other communications etc, this is the reason why i wrote that the class type node/link will have a scheduler in it)

Answer 1

It depends very much on what kind of operations you are going to perform on that structure. Will you have to do searches? If so, what kind: value-based or position-based? Will you have to perform transformations on it? Will you have to access all of its elements repeatedly and in a sequence? Will you have to access elements based on their position in the grid? Is your structure sparse or dense?

Moreover, do you want to minimize creation time, search time, navigation time, or transformation time? This all gives fundamental information to make a decision.

I would not go for a solution based on nodes and links, because it is:

1. expensive in terms of memory consumption (due to the extra link pointers);
2. expensive in terms of complexity (navigating all the nodes require following all the links, so no random access), and;
3. expensive in terms of data locality (nodes will be allocated individually and spread all over the heap at separate addresses, which will generate many cache misses and slow down your program);
4. error-prone (messing up with links is easy, especially if you use raw pointers and don't want to pay for smart pointers' memory overhead)

Without knowing too much about your requirements, I would probably suggest you having a look at Boost.MultiArray.

If you want to do things on your own, then (again, without knowing too much about your requirements) I would suggest you using a vector<vector<vector<double>>>, which is relatively simple, does not have fixed size and allows you resizing at run-time, guarantees you O(1) access through the subscripting operator and also some locality of the data (you have several vectors here, so as long as you access data from one vector performance will be fine).

A plain C-style multi-dimensional array is also a possibility, but it's inherently unsafe, which would make it a last-resort choice if I were you (also, allocating a contiguous block of memory might be impossible if your structure is huge).