嵌套向量的缺点是什么？

Question

我仍然是C++的新手,还有很多需要学习的东西,但我最近变得非常依旧的是使用嵌套(多维)向量.所以我通常会得到这样的东西:

std::vector<std::vector<std::string> > table;

然后,我可以轻松访问这样的元素:

std::string data = table[3][5];

然而,最近我得到的印象是(在性能方面)更好地拥有一维向量,然后只使用"索引算术"来相应地访问元素.我认为这种性能影响对于更大或更高维度的向量来说是重要的,但我真的不知道,到目前为止还没有找到关于它的大量信息.

虽然直觉上,单个矢量比一个更高维的矢量具有更好的性能是有道理的,但老实说,我不明白其实际原因.此外,如果我只是使用单维向量,我将失去用于访问多维元素的直观语法.所以这是我的问题:

为什么多维向量效率低下？如果我只使用一维向量(表示更高维度的数据),那么访问其元素的最佳,最直观的方法是什么？

Answer 1

这取决于具体条件.当嵌套版本是真正的2D表格时(即所有行的长度相等),我将讨论这种情况.

一维矢量通常在每种使用模式上都会更快.或者,至少,它不会比嵌套版本慢.

嵌套版本可以被认为更糟,因为:

• 它需要分配行数,而不是一行.
• 访问一个元素需要额外的间接,因此它更慢(额外的间接通常比1D情况下所需的乘法更慢)
• 如果您按顺序处理数据,那么如果2D数据散布在内存中,则可能会慢得多.这是因为可能存在大量缓存未命中,这取决于内存分配器如何返回不同行的内存区域.

所以,如果你追求性能,我建议你为1D向量创建一个2D包装类.这样,您可以获得与嵌套版本一样简单的API,并且您也将获得最佳性能.甚至,如果由于某种原因,您决定使用嵌套版本,您只需更改此包装类的内部实现.

访问1D元素最直观的方法是y*width+x.但是,如果您知道自己的访问模式,则可以选择其他模式.例如,在绘画程序中,基于图块的索引可以更好地存储和操纵图像.在这里,数据可以像这样索引:

int tileMask = (1<<tileSizeL)-1; // tileSizeL is log of tileSize
int tileX = x>>tileSizeL;
int tileY = y>>tileSizeL;
int tileIndex = tileY*numberOfTilesInARow + tileX;
int index = (tileIndex<<(tileSizeL*2)) + ((y&tileMask)<<tileSizeL) + (x&tileMask);

该方法在存储器中具有更好的空间局部性(彼此接近的像素倾向于具有接近的存储器地址).索引计算比简单慢y*width+x,但这种方法可能会有更少的缓存未命中,所以最后它可能更快.