C和/或C++中的多维数组是否会引起任何问题?

4
我知道这个问题乍一看似乎有点滑稽。但是当我看到这个问题时,我发现了评论,来自C和C++高级用户@BasileStarynkevitch,他声称在C或C++中不应该使用多维数组:

不要在C++(或C)中使用多维数组。

为什么?为什么我不应该在C++或C中使用多维数组?

他的这个声明是什么意思?


随后,另一位用户回复了这条评论:

Basile是正确的。在C/C++中声明3D数组是可能的,但会引起太多问题。

哪些问题呢?
我经常使用多维数组,并没有发现使用它们有任何缺点。相反,我认为它只有优点。
  • 使用多维数组是否存在任何问题,我不知道吗?

  • 有人能解释一下他们的意思吗?


10
不用理会评论,多维数组没有问题。 - Eric Postpischil
1
由于任何动态的多维数据结构都需要单个分配以提高性能(而不是嵌套动态数据结构),因此我倾向于在静态情况下使用单维数组,这样我所编写的代码总是在相同的内存分配和指针传递假设下保持一致(手动进行索引)。如果您依赖于诸如 a[4][3][2] 这样的数组的多维索引,并希望稍后将其替换为动态内容,则会留下更多的重构工作。 - Lemon Drop
好的,尝试返回一个数组。 - Bob__
1
投票关闭,因为基于观点。任何此类问题都应该询问“为什么喜欢X而不是Y”,而不是“为什么X不好”。如果禁止多维数组(int x [6] [7] [8]),你应该问自己将使用什么代替; int x [6 * 7 * 8]int ***x;valarray<int> x?...许多替代方案将具有相同或更糟的问题。 - Yakov Galka
2
@ybungalobill 那么,你会将这些陈述归类为不正确和基于观点的吗?顺便说一句,我个人完全不禁止它们,也没有理由这样做。我的问题是特别想知道是否存在任何关于使用多维数组的问题,我之前并不知道。 - RobertS supports Monica Cellio
显示剩余7条评论
5个回答

5
这是一个非常广泛(也很有趣)的性能相关话题。我们可以讨论缓存未命中,多维数组初始化成本,矢量化,栈上分配多维 std::array,堆上分配多维std::vector,后两者的访问等等...。
话虽如此,如果您的程序使用多维数组运行良好,则保持原样,特别是如果多维数组可以提高可读性的话。
一个与性能相关的示例:
考虑一个保存了许多std::vector<double>std::vector
std::vector<std::vector<double>> v;

我们知道,v 中的每个 std::vector 对象都是连续分配的。此外,v 中的 std::vector<double> 中的所有元素都是连续分配的。然而,并非所有在 v 中存在的 double 都在连续的内存中。因此,根据您访问这些元素的方式(访问次数、访问顺序等),与包含所有 double 的连续内存中的单个 std::vector<double> 相比,一个 std::vectorstd::vector 可能会非常慢。
矩阵库通常会将5x5矩阵存储在大小为25的普通数组中。

2
话虽如此,如果您的程序在使用多维数组时运行良好,请保持原样,特别是如果您的多维数组可以提高可读性。这可能应该是本答案的第一句话。牺牲可读性几乎从来不是一个好主意。 - Andrew Henle
@mfnx 一个std::vector的std::vector与包含所有double的连续内存的单个std::vector<double>相比可能非常慢。 - 你更喜欢什么替代方案?你如何使它更有效率?你的首选替代方案是什么? - RobertS supports Monica Cellio
@RobertSupportsMonicaCellio 这要看情况。假设有一个由N个三元组双精度浮点数组成的向量,与一个由3*N个双精度浮点数组成的向量(在科学计算中典型的例子)。循环遍历三元组并使用它们。重复1M次并进行基准测试。 - mfnx
1
@RobertSupportsMonicaCellio 我更偏向于可读性。如果性能成为问题,那么您可以寻找优化的方法。但如何解决这个问题取决于您没有解释清楚的问题。因此,在我看来,这个问题太广泛了(尽管不是“基于意见”的,因为有许多方面不依赖于观点,在我看来;))。 - mfnx

4

你不能同时回答C和C++的这个问题,因为这两种语言以及它们处理多维数组的方式存在根本性的差异。所以这个回答包含了两个部分:


C++

在C++中,多维数组几乎没什么用处,因为你不能使用动态大小来分配它们。除最外层外的所有维度大小都必须是编译时常量。在我遇到的几乎所有多维数组用例中,尺寸参数都不是在编译时知道的,因为它们来自于图像文件或一些仿真参数等。

在某些特殊情况下,实际上可能会在编译时就知道这些维度的大小,在这些情况下,在C++中使用多维数组就没有问题。在所有其他情况下,你需要使用指针数组(设置繁琐)、嵌套的std :: vector<std :: vector<std :: vector<...>>>,或者使用1D数组并手动计算索引(容易出错)。


C

C允许使用真正的动态大小的多维数组,自C99以来就成为可能。这被称为VLA,并且它允许你在堆栈和堆上创建完全动态大小的多维数组。

然而,有两个注意点:

  • You can pass a multidimensional VLA to a function, but you can't return it. If you want to pass multidimensional data out of a function, you must return it by reference.

    void foo(int width, int height, int (*data)[width]);  //works
    //int (*bar(int width, int height))[width];  //does not work
    
  • You can have pointers to multidimensional arrays in variables, and you can pass them to functions, but you cannot store them in structs.

    struct foo {
        int width, height;
        //int (*data)[width];  //does not work
    };
    
两个问题都可以通过解决(通过引用传递返回多维数组,并将指针存储为结构体中的void*),但这并不容易。由于它不是一个经常使用的功能,只有很少的人知道如何正确地使用它。

编译时数组大小

C和C ++都允许您在编译时使用具有已知尺寸的多维数组,这些数组没有上述缺点。

但是它们的效用大大减少:只有在有许多情况下需要使用多维数组且无法在编译时得知涉及的大小的幽灵时,您才能使用它们。例如,图像处理:在打开图像文件之前,您不知道图像的尺寸。同样,任何物理模拟:直到程序加载其配置文件之前,您都不知道工作域的大小。等等。

因此,为了有用,多维数组必须支持动态大小。


4
你不能使用多维数组是因为你无法使用动态大小分配它们。在C++中,多维数组确实存在,但由于无法进行动态大小分配,因此不能使用它们。也许可以将原文改为“你不应该使用多维数组”? - alteredinstance
2
@RobertSsupportsMonicaCellio 这是毫无意义的,因为在几乎所有相关情况下,所需的尺寸根本不会在编译时知道。想象一下进行图像处理:您真的知道在编译时要处理的图像的大小吗?对我来说,这就是“动态尺寸!”我可以数出我可以使用编译时大小缓冲区的情况,而且肯定没有一个情况是二维的编译时大小缓冲区。 - cmaster - reinstate monica
2
@RobertSsupportsMonicaCellio 我更喜欢“不能”这个词:如果用“不得”,听起来就像我在命令别人不要使用多维数组。而这绝对不是我的本意。“不能”则意味着存在一些根本性、无法解决的问题。这个问题就是编译时常量数组大小的限制。你可以说我应该更清楚地表明,在某些边角情况下,这个问题并没有完全破坏这种结构的使用,但这已经隐含在“因为你不能用动态大小分配它们”的语句中了。 - cmaster - reinstate monica
1
@RobertSsupportsMonicaCellio 关于我会使用什么替代:在 C 中,我确实会使用多维数组并解决我概述的两个问题。在 C++ 中,我会使用 1D 数组,并手动计算索引,例如 data[(z*depth + y)*height + x] 的方式。这将编译成与 C 中 data[z][y][x] 表达式相同的代码,只是有点难以阅读和正确理解。我通常不会使用指针数组,因为它们设置和拆除非常繁琐,而且性能也不如索引计算方法。 - cmaster - reinstate monica
3
好的,我已经重新表达了C++部分。希望现在对所有人都可以接受了。(很抱歉我之前太固执了。) - cmaster - reinstate monica
显示剩余12条评论

2

所指的“问题”是没有正确使用结构,走出了数组的某个维度的末尾。如果您知道自己在做什么并且小心编码,它将完美地工作。

我经常在C和C ++中使用多维数组进行复杂矩阵操作。这在信号分析和信号检测以及用于模拟中分析几何体的高性能库中非常频繁。我甚至没有考虑动态数组分配作为问题的一部分。即使对于某些有界问题来说,具有重置功能的定型数组也可以节省内存并提高复杂分析的性能。对于较小的矩阵操作,可以在库中使用缓存,而对于每个问题基础上的更大的动态分配,则可以使用更复杂的C ++ OO处理。


“更难出错”是选择某个东西而不是多维数组的一个明智理由。 - Caleth
过度复杂和内存占用也是问题。学习精确编码和仔细编写代码也是值得追求的目标,并且根据应用程序的需求可能是必要的。对于像数组操作这样简单的事情,毫无头绪地说“不要这样做”似乎不太合适,我作为新程序员的导师和教师认为如此。 - ggb667

2
大多数数据结构都有适合使用和不适合使用的时候。这在很大程度上是主观的,但为了回答这个问题,让我们假设您正在使用2D数组,而这并不合适。
话虽如此,我认为有两个值得注意的原因需要避免在C++中使用多维数组,它们主要基于数组的用例。即:
1. 较慢的内存遍历
例如i[j][k]这样的2维数组可以被连续访问,但计算机必须花费额外的时间来计算每个元素的地址,比1D数组更耗时。更重要的是,迭代器在多维数组中失去了可用性,迫使您使用[j][k]符号,这会更慢。简单数组的一个主要优点是它们能够顺序访问所有成员。这在2+D数组中部分丢失。
2. 不灵活的大小
这只是一般情况下的一个问题,但是对于2、3或更多维的数组,调整大小变得更加复杂。如果某个维度需要改变大小,则整个结构必须被复制。如果您的应用程序需要调整大小,最好使用除多维数组之外的某种结构。
再次强调,这些都是基于用例的,但这两种情况都是可能出现的使用多维数组的重要问题。在上述两种情况中,有其他解决方案可用,这些解决方案将比多维数组更好的选择。

4
启用优化功能后,据我所知编译器足够聪明,可以编译嵌套的for循环而无需进行任何每项乘法计算;因此,我怀疑[j][k]表示法的速度不会比一维数组的[j]表示法慢。但是,您需要小心地按正确顺序嵌套for循环,以便后续内存访问在RAM中相邻,否则可能会引入大量不必要的缓存未命中。 - Jeremy Friesner
@JeremyFriesner 对于完整的数组遍历,你可能是正确的。我认为真正的问题出现在程序想要进行随机访问时,例如当[j][k]不是编译时常量时。如果j和k在编译时未知,我会假设程序将不得不即时执行地址计算。 - alteredinstance
同意,但是使用1D数组时也是如此(您只需要明确地进行计算:float val = the1DArray[rowIdx*rowSize+colIdx];)。 - Jeremy Friesner
@JeremyFriesner 我完全同意,这就是为什么使用迭代器与数组(而不是i[j][k])被认为是最佳实践的原因。然而,对于多维数组来说,使用迭代器变得不切实际甚至是不可能的,这就是我认为它是“较慢”的数据结构的主要原因。 - alteredinstance
@alteredinstance 在上述两种情况中,有其他更好的解决方案可用,而不是使用多维数组。您如何更好地处理它?您推荐使用什么替代多维数组的方法? - RobertS supports Monica Cellio

1
这些语句具有广泛适用性,但不是普遍适用的。如果您有静态边界,那就没问题。
在C++中,如果您想要动态边界,则不能有单个连续分配,因为维度是类型的一部分。即使您不关心连续分配,您也必须格外小心,特别是如果您希望调整维度。
更简单的方法是在某些容器中具有单个维度来管理分配,并具有多维视图。
给定:
std::size_t N, M, L;
std::cin >> N >> M >> L;

比较:
int *** arr = new int**[N];
std::generate_n(arr, N, [M, L]()
{ 
    int ** sub = new int*[M];
    std::generate_n(sub, M, [L](){ return new int[L]; });
    return sub;
});

// use arr

std::for_each_n(arr, N, [M](int** sub)
{ 
    std::for_each_n(sub, M, [](int* subsub){ delete[] subsub; });
    delete[] sub;
});
delete[] arr;

With:

std::vector<int> vec(N * M * L);
gsl::multi_span arr(vec.data(), gsl::strided_bounds<3>({ N, M, L }));

// use arr

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接