c++ - 多维网格使用什么数据结构？ (c++)

Question

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

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

这在很大程度上取决于您要对该结构执行的何种操作。您需要搜索吗？如果是，是哪种类型:基于值(value)还是基于位置？您需要对其执行转换吗？您是否必须按顺序重复访问其所有元素？您是否必须根据元素在网格中的位置 访问元素？你的结构是稀疏还是密集？

此外，您是否希望最大限度地减少创建时间、搜索时间、导航时间或转换时间？这一切都为做出决定提供了基本信息。

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

1. 在内存消耗方面很昂贵(由于额外的链接指针)；
2. 在复杂性方面很昂贵(导航所有节点需要遵循 所有链接，所以没有随机访问)；
3. 在数据局部性方面昂贵(节点将单独分配并遍布 堆在不同的地址，这将产生许多缓存未命中并减慢您的程序)；
4. 容易出错(弄乱链接很容易，尤其是当您使用原始指针并且不想为智能指针的内存开销付出代价时)

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

如果您想自己做事，那么(同样，在不太了解您的要求的情况下)我建议您使用 vector<vector<vector<double>>> ，它相对简单，没有固定大小，允许您在运行时调整大小，保证您通过下标运算符进行 O(1) 访问，并且一些数据的局部性(您有几个 vector 在这里，只要您从一个 vector 访问数据，性能就可以了。

普通的 C 风格多维数组也是一种可能性，但它本质上是不安全的，如果我是你，这将成为最后的选择(另外，如果你的结构分配一个连续的内存块可能是不可能的很大)。