std ::矢量尺寸，“俄罗斯方块”形状允许？

Question

您好我有一个关于在C++中使用矢量的问题，我正在研究通过随机运动模拟通过容器的粒子运动的问题。我需要添加和去除粒子，因为它们符合或不符合某些标准，为此我发现矢量类非常方便，但是我对C++很陌生，并且存在我需要考虑的效率问题。

我定义的二维数组是限定为矩形还是正方形？我只需要在每个容器中存储粒子的位置。我害怕的是我的矩阵看起来像这样：

| | | | |

| | | | |

| | | | |

| | | | |

为4x4的情况。随着柱的进入是每个箱/容器中的粒子的位置和不同于箱的粒子的数量，我不知道这样的事情是否可能：

| | | | |第一个垃圾箱中有4个粒子

| | |在第二个仓中有2个粒子，占用的内存比上面的少2倍

| | | | | | | | | | | | | | | | |这个很多在第三个斌等等。

我还需要删除行中的元素（减小行大小）或添加行中的元素（增加行大小）或列中，这取决于我实现算法的方式，如果您可以事先提醒我如果有多个维度的向量处理时，有常见的错误，因为我相信做一个，是新的编程语言:)

Answer 1

您可以使用向量的向量：vector<vector<Particle> >

Answer 2

起初，当你询问“2D数组......限于...矩形或正方形”，这听起来像是在问如何表示“锯齿状”数组（数组不是矩形，而是具有固定的“高度t“，每行有一个可变的”宽度“）。

但"tetris" shapes（tetraminos）不适合锯齿阵列。这让我觉得你实际上想要a sparse array。也就是说，你只想存储粒子的位置，而不是存储非粒子的位置。

最简单的方法是简单地跳过网格，直接维护占用空间/粒子位置列表。

struct Position 
{ 
    float X; 
    float Y; 
}; 

// ... 

std::vector<Position> particles; // std::list works too... 

但是，对于某些目的，普通列表效率不高。如果您需要对这些数据进行空间索引访问（例如，查找模拟中给定体积/区域中有多少个粒子），那么应该使用a space partitioning data structure，这仍然允许稀疏人群。

人们通常按照您描述的方式使用矩形网格，然后在内存储列表，该网格单元中包含的粒子的每个网格位置。但是那个“浪费空间”的网格单元没有被使用。它不能解决人口稀少问题。

支持空间索引和稀疏填充的流行数据结构是a quadtree。