什么数据结构用于多维网格？(C++)

Question

我需要编写一个测试平台来测试特定的算法.该系统应该可以通过输入和三维来定义 - 类似于片上网络,它具有连接它们的节点和链接元件.由于节点之间的维度和链接,我在确定要使用的数据结构时遇到了一些困难 - 像数组[x] [y] [z]这样的三维数组很难处理,因为指针在添加链接时有缺点连接节点(在结构中留下几个空值孔).二进制搜索树很难实现,因为它是网格类型.出于这个原因,我考虑过做一个链接更容易实现的链表.(最终的测试平台应该类似于下面的演示文稿),其中每个链接也会映射下来,因为它们包含通信计划

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

你们中的任何人都可以提供一些帮助,了解c ++中哪种类型的结构适合这种任务.在给定x,y和z的尺寸参数的情况下,完成的程序应该能够生成这样的结构.

目前粗略的轮廓应该是这样的

>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
>}

编辑22.01.2013

首先,它是一个模拟三维网络片上多处理器系统的测试平台.该系统必须完成的任务是启用测试某些算法以帮助将任务映射到这些节点(每个节点连接到处理器核心).鉴于此,内存消耗可能不是问题,因为它仅用于我所说的测试,因此系统必须同时具有节点和链接,因为它们都不能被两个事件用于同时(链接上的通信将阻止所有其他通信等,这就是为什么我写的类型节点/链接将有一个调度程序)

Answer 1

这在很大程度上取决于您将在该结构上执行哪种操作.你需要做搜索吗？如果是这样,那么:基于价值还是基于头寸？你需要对它进行转换吗？您是否必须按顺序重复访问其所有元素？您是否必须根据其在网格中的位置来访问元素？你的结构稀疏还是密集？

此外,您想最小化创建时间,搜索时间,导航时间或转换时间吗？这一切都为做出决定提供了基本信息.

我不会寻求基于节点和链接的解决方案,因为它是:

1. 在内存消耗方面很昂贵(由于额外的链接指针);
2. 昂贵的复杂性(导航所有节点需要跟随所有链接,因此没有随机访问),和;
3. 在数据局部性方面是昂贵的(节点将被单独分配并在整个堆中分布在不同的地址,这将产生许多缓存未命中并减慢程序速度);
4. 容易出错(搞乱链接很容易,特别是如果你使用原始指针并且不想支付智能指针的内存开销)

在不了解您的要求的情况下,我可能会建议您查看Boost.MultiArray.

如果你想自己做事,那么(同样,不太了解你的要求)我会建议你使用一个vector<vector<vector<double>>>相对简单的,没有固定大小,允许你在运行时调整大小,保证你O(1)通过下标运算符和数据的某些位置进行访问(这里有几个向量,因此只要从一个向量性能访问数据就可以了).

一个简单的C风格的多维数组也是一种可能性,但它本身就是不安全的,如果我是你的话,这将使它成为最后的选择(如果你的结构很大,也可能无法分配连续的内存块) .