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

网格的大小在开始时是已知的（但每次程序启动时都会有所不同）。然而，每个单元的深度并不仅仅是一个值，而是一个在运行时期间会不断变化的对象群体。C++什么是对象“桩”的二维数组的最佳数据结构？

问：什么是最推荐的（高效且易于维护;不易发生用户错误）的方式来实现这一点？

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

enter image description here

2013-05-20 Thomas An

也许你可以描述你的实际应用。你需要迭代这些桩，还是只需要计算每个桩的高度？如果您有一组固定的节点，您可以将网格位置存储在节点中并更新深度直方图。移动节点时，只需执行两个直方图更新并更改网格位置。不知道这是否有用。正如我所说，取决于你想达到的目标。 – paddy

这是一个碰撞网格表。每个单元格都包含对可变数量对象的引用。所以我们每毫秒处理数以千计的搜索，删除和添加。但是，每个单元不应该有超过5或10个对象（我们宁愿使网格更精细以减少每个单元的对象数量）。 –

好吧，试着在每个单元中存储一个向量。在大多数情况下，矢量比列表好。听起来有点像[这个答案]（http://stackoverflow.com/a/14615449/1553090）我回了一段时间。如果你需要更快，更肮脏，你可以记忆载体。也许甚至使用矢量作为第二手段。您可能想试验将小型本地数组以内联方式存储，然后将数据溢出到某个矢量上，以便将大部分内存访问保留在本地。在这方面，将网格屏蔽成页面也可能有助于改善局部性。 – paddy

使用最好缓存局部性一维数组。 A vector会很好。

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

现在，你必须存储在一维向量2D直方图。你可以像这样访问：

histogram[row][col]++;

如果你包装这一切在一个简单的类，你就不太可能做一些愚蠢的用指针。您也可以使用clear()函数来将直方图数据设置为零（它只是穿过histdata矢量并将其零）。

来源

2013-05-20 00:51:43 paddy

每个单元格的深度不仅仅是一个值。这是一个在运行时会不断变化的对象群体。 –

在这种情况下，我很难将其称为直方图。无论如何，没关系。在上面的例子中，只需'typedef std :: vector Objects'并用'Objects'代替'int'。然后，每个单元格都有一个可以填充项目的矢量。 – paddy

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

回答

相关问题