What data structure to use for a multidimensional mesh grid? (C ++)

Question

I need to code a test platform to test a specific algorithm. It is assumed that the system will be determined by input and 3-dimensional - like a network on a chip, it has both node and link elements connecting them. Due to the sizes and connections between nodes, I had some difficulties in determining which data structures to use - a three-dimensional array, such as array [x] [y] [z], is difficult to treat as a pointer with flaws when adding links to connect nodes (leaves several holes with zero value in the structure). Binary search trees are difficult to implement since the type of grid. For this reason, I thought about creating a linked list where links are easier to implement. (the final testing platform should look something like below), where each link is also displayed on the map, 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 regarding what type of structure in C ++ is suitable for this kind of task. The finished program should be able to generate such a structure, taking into account the size parameters x, y and z.

currently, a 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 01/22/2013

and, first of all, as its test platform simulating a three-dimensional network on a multiprocessor system of microcircuits. The task that this system must complete is to enable testing of certain algorithms to help map tasks on these nodes (where each node is connected to the processor core). In light of this, memory consumption may not be a problem, since it is intended only for testing, as I said, therefore it is necessary that the system has both nodes and links, since none of them can be used by two events at the same time (link-by-link blocks all other messages, etc., which is why I wrote that the class type node / link will have a scheduler in it)

Answer 1

It largely depends on what operations you are going to perform in this structure. Will you need to perform a search? If so, which one: value-based or positional? Will you perform conversions on it? Do you need to access all of your elements several times and sequentially? Will you need to access elements based on their position in the grid? Is your structure sparse or dense?

Also, do you want to minimize creation time, search time, navigation time or conversion time? All this provides fundamental information for decision making.

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

• expensive in terms of memory consumption (due to additional link pointers);
• expensive in terms of complexity (to navigate through all nodes the following all links are required, therefore there is no random access) and;
• expensive in terms of data location (nodes will be distributed individually and distributed across all the heap at separate addresses, which will generate many misses in the cache and slow down your program);
• error prone (spoiling links is very easy, especially if you use raw pointers and don’t want to pay for the overhead of smart pointer memory).

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

If you want to do something on your own, then (again, not knowing too much about your requirements), I suggest you use vector<vector<vector<double>>> , which is relatively simple, has no fixed size and allows resizing the runtime guarantees you O (1) access through the subscription operator, as well as some data locality (here you have several vectors, so that while you access the data from one vector execution, it will be good).

A simple multidimensional C-style array is also an option, but it is inherently unsafe, which would make it the last choice if I were you (also allocating an adjacent block of memory may not be possible if your structure is huge).