arrays - C++ 对象“堆”的二维数组的最佳数据结构是什么？

Question

网格的大小在开始时将是已知的（但每次程序启动时都会有所不同）。但是，每个单元格的 DEPTH 不仅仅是一个值，而是在运行时不断变化的一组对象。

问：最推荐的（高效且易于维护；不太容易出现用户错误）的实现方式是什么？

• 这是某种标准的二维向量指针数组吗？
• 它是 3D 矢量数组吗？
• 它是链表的二维数组还是二叉树（我认为二叉树会因为连续删除和插入节点体操而增加复杂性开销）
• 是其他一些自定义数据结构吗？

Answer 1

使用一维数组以获得最佳缓存位置。Avector会很好。

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

如果您需要快速索引行，请做一些事情来指向它：

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

现在您有一个存储在 1D 矢量中的 2D 直方图。您可以像这样访问它：

histogram[row][col]++;

如果您将所有这些都包装在一个简单的类中，您就不太可能用指针做一些愚蠢的事情。您还可以创建一个clear()函数将直方图数据设置为零（它只是撕开histdata向量并将其归零）。