在 C++ 中使用一维索引数组访问 n 维数组元素的更好方法？
A better way to access n-d array element with a 1-d index array in C++?
最近在做一些关于C++指针的事情，当我想用一个包含索引的一维数组来访问多维数组中的元素时，我遇到了这个问题。
假设我有一个数组 arr，它是一个 4 维数组，所有元素都设置为 0 除了 arr[1][2][3][4] 是 1，还有一个数组idx 包含 arr 每个维度的索引，我可以使用 arr[idx[0]][idx[1]][idx[2]][idx[3]] 或 *(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3]).
访问此元素
问题来了，当n很大时，这样就不太好了，所以我想知道是否有更好的方法来处理多维访问？
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
cout<<"Got with ****: ";
cout<<*(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3])<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff54c61f28
Got with ****: 1
我自己想出了解决这个问题的方法。
思路是使用void *指针，我们知道每个内存单元都保存一个值或者一个内存单元的地址，所以我们可以直接计算目标到基地址的偏移量。
本例中，我们使用void *p = arr获取第n维数组的基地址，然后循环idx数组，计算偏移量。
对于arr[10][10][10][10]，arr[0]和arr[1]之间的偏移量是10 * 10 * 10 * sizeof(int)，因为arr是4-d，arr[0]和arr[1]是3维的，所以arr[0]和arr[1]之间有10 * 10 * 10 = 1000个元素，之后我们应该知道两个void *相邻地址的偏移量是1 byte，所以我们应该乘sizeof(int)得到正确的偏移量，据此，我们最终得到我们要访问的内存单元的确切地址。
最后，我们必须将void *指针转换为int *指针并访问地址以获得正确的int值，就是这样！
和void *(不太好)
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
cout<<"Got with ****: ";
cout<<*(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3])<<endl;
void *p = arr;
for(int i = 0; i < 4; i++)
p += idx[i] * int(pow(10, 3-i)) * sizeof(int);
cout<<"Got with void *:";
cout<<*((int*)p)<<" at "<<p<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff5e3a3f18
Got with ****: 1
Got with void *:1 at 0x7fff5e3a3f18
注意事项：
编译的时候有警告，我选择忽略
test.cpp: In function 'int main()':
test.cpp:23:53: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
p += idx[i] * int(pow(10, 3-i)) * sizeof(int);
使用char *代替void *（更好）
既然我们要逐字节操作指针，那么用char *代替void *会更好。
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
char *p = (char *)arr;
for(int i = 0; i < 4; i++)
p += idx[i] * int(pow(10, 3-i)) * sizeof(int);
cout<<"Got with char *:";
cout<<*((int*)p)<<" at "<<(void *)p<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff4ffd7f18
Got with char *:1 at 0x7fff4ffd7f18
和int *（在这种情况下）
我被告知在算术中使用 void * 不是一个好的做法，使用 int * 会更好，所以我将 arr 转换为 int *指针并替换 pow.
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
cout<<"Got with ****: ";
cout<<*(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3])<<endl;
int *p = (int *)arr;
int offset = 1e3;
for(int i = 0; i < 4; i++)
{
p += idx[i] * offset;
offset /= 10;
}
cout<<"Got with int *:";
cout<<*p<<" at "<<p<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff5eaf9f08
Got with ****: 1
Got with int *:1 at 0x7fff5eaf9f08
构造索引多维数组的算法的方式会因选择的语言而异；你已经用 C 和 C++ 标记了这个问题。我会坚持使用后者，因为我的回答与 C++ 有关。一段时间以来，我一直在研究类似但不同的东西，所以当我构建一个多用途多维矩阵 class 模板时，这成为一个有趣的问题。
关于更高层次的多维向量和矩阵，我发现 3 的阶数在理解更高维度的本质方面反复创造奇迹。在考虑它的算法软件实现方面之前，先从几何角度考虑这一点。
从数学上讲，让我们考虑第一个形状为 0 维对象的最低维 0。这恰好是任意点，该点可以具有无限量的坐标位置属性。诸如 p0(0)、p1(1)、p2(2,2)、p3(3,3,3),... pn(n,n,...n) 之类的点，其中每个对象都指向具有定义数量的维度属性的特定语言环境。这意味着没有线性距离，例如长度、宽度或高度，相反，没有任何方向或维度的大小，其中没有大小边界的形状或对象不定义任何面积、体积或更高维度的体积。同样对于这些 0 维点，没有方向意识，这也意味着没有定义大小的旋转角度。另一件需要考虑的事情是任意点也是零向量。另一件有助于理解这一点的事情是通过使用代数多项式，使得线性的 f(x) = mx+b 是一维方程、形状（在这种情况下是一条线）或图形，f(x) = x^2 是二维的， f(x) = x^3 是三维的，f(x) = x^4 是四维的，依此类推直到 f(x) = x^n 是 N 维的。长度或大小、旋转方向或角度、面积、体积等无法定义，除非您将两个不同的点相关联以给出至少 1 个具有指定方向的线段或矢量。一旦你有了一个隐含的方向，你就会有坡度。
在看数学运算时，最简单的是加法，它只不过是线性平移，一旦你介绍了加法，你就同时介绍了所有其他运算，例如减法、乘法、除法、幂和根；一旦你有了乘法和除法，你就可以定义旋转、旋转角度、面积、体积、变化率、斜率（也就是正切函数），从而定义几何和三角学，然后它们也会导致积分和导数。是的，我们都上过数学课，但我认为这对于理解如何构建一个数量级与另一个数量级的关系很重要，一旦你知道如何构建，这将帮助我们轻松处理更高维度的订单构建它。一旦你明白即使你的高阶运算也不过是加法和减法的展开，你就会开始了解到它们的连续运算在本质上仍然是线性的，只是它们扩展到多个维度。
前面我说过 3 的顺序重复创造奇迹所以让我解释一下我的意思。由于我们每天都以 3D 的视角感知事物；我们只能可视化 3 个不同的向量，它们彼此正交，给你我们自然的 Space 的 3 个维度，例如左和右，向前和向后给你水平轴和平面，向上和向下给你垂直轴和飞机。我们无法想象更高的东西，所以 x^4, x^5, x^6 etc... 的维度我们无法想象，但它们确实存在。如果我们开始查看数学多项式的图形，我们可以开始看到奇函数和偶函数之间的模式，其中 x^4, x^6, x^8 相似，它们只不过是 x^2 的展开和 [= 的函数19=] 只不过是 x^3 的扩展。所以我认为前几个维度是正常的：零点，第一个 - 线性，第二个 - 面积和第三个 - 体积，至于第四个和更高的维度，我称之为体积。
因此，如果您看到我使用 Volume，那么它直接与第 3 维相关，而如果我提到 Volumetric，则它与高于第 3 维的任何维度相关。现在让我们考虑一个矩阵，就像您在常规代数中看到的那样，其中公共矩阵由 MxN 定义。好吧，这是一个具有 M * N 个元素的二维平面矩阵，并且该矩阵的面积也为 M * N。让我们扩展到更高维的矩阵，例如 MxNxO 这是一个具有 M * N * O 个元素的 3D 矩阵，现在具有 M * N * O 个体积。因此，当您将此可视化时，将 MxN 2D 部分视为一本书的一页，而 O 组件代表一本书的每一页或盒子的每一片。这些矩阵的元素可以是任何东西，从简单值到应用运算，再到方程、方程组、集合或存储容器中的任意对象。所以现在当我们有一个 4 阶矩阵时，例如 MxNxOxP，它现在有一个 4 维的方面，但最简单的可视化方法是，这将是一个一维数组或向量，其中它的所有P 个元素将是 MxNxO 个体积的 3D 矩阵。当你有一个 MxNxOxPxQ 的矩阵时，你现在有一个 PxQ 的二维区域矩阵，其中每个元素都是一个 MxNxO 体积矩阵。然后如果你有一个 MxNxOxPxQxR 你现在有一个 6 维矩阵，这次你有一个 3D 体积矩阵，其中每个 PxQxR 元素实际上是 MxNxO 的 3D 矩阵。一旦你走得越来越高，这种模式就会重复并再次融合。所以任意矩阵的行为顺序是这些维度重复：1D 是线性向量或矩阵，2D 是面积或平面矩阵，3D 是体积矩阵，任何更高的东西重复这个过程压缩体积的前一步因此术语体积矩阵。看看这个 table:
// Order of Magnitude And groupings
-----------------------------------
Linear Area Volume
x^1 x^2 x^3
x^4 x^5 x^6
x^7 x^8 x^9
x^10 x^11 x^12
... ... ...
----------------------------------
现在只需使用一点微积分就可以知道将哪个数量级索引到哪个更高维度级别。一旦你知道了一个特定的维度，就可以很容易地求出多个导数来得到一个线性表达式；然后遍历space，然后对多个导数的同阶积分得到结果。这应该通过首先忽略高维顺序中最不重要的较低维度来消除大量的中间工作。如果您正在处理具有 12 个维度的东西，您可以假设定义第一组体积的前 3 个维度被紧密打包为另一个 3D 体积矩阵的元素，然后再一次，体积矩阵的 2d 阶本身就是一个元素另一个 3D 体积矩阵。因此我们有一个重复模式，现在只需应用它来构建一个算法，一旦你有了一个算法；用任何可编程语言实现这些方法应该很容易。因此，您可能必须进行 3 种情况切换以确定使用哪种算法方法，了解矩阵或 n-d 数组的整体维度，其中一个处理线性顺序，另一个处理面积，最后一个处理体积，如果它们是 4th+那么整个过程本质上就变成了递归。
最近在做一些关于C++指针的事情，当我想用一个包含索引的一维数组来访问多维数组中的元素时，我遇到了这个问题。
假设我有一个数组 arr，它是一个 4 维数组，所有元素都设置为 0 除了 arr[1][2][3][4] 是 1，还有一个数组idx 包含 arr 每个维度的索引，我可以使用 arr[idx[0]][idx[1]][idx[2]][idx[3]] 或 *(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3]).
问题来了，当n很大时，这样就不太好了，所以我想知道是否有更好的方法来处理多维访问？
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
cout<<"Got with ****: ";
cout<<*(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3])<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff54c61f28
Got with ****: 1
我自己想出了解决这个问题的方法。
思路是使用void *指针，我们知道每个内存单元都保存一个值或者一个内存单元的地址，所以我们可以直接计算目标到基地址的偏移量。
本例中，我们使用void *p = arr获取第n维数组的基地址，然后循环idx数组，计算偏移量。
对于arr[10][10][10][10]，arr[0]和arr[1]之间的偏移量是10 * 10 * 10 * sizeof(int)，因为arr是4-d，arr[0]和arr[1]是3维的，所以arr[0]和arr[1]之间有10 * 10 * 10 = 1000个元素，之后我们应该知道两个void *相邻地址的偏移量是1 byte，所以我们应该乘sizeof(int)得到正确的偏移量，据此，我们最终得到我们要访问的内存单元的确切地址。
最后，我们必须将void *指针转换为int *指针并访问地址以获得正确的int值，就是这样！
和void *(不太好)
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
cout<<"Got with ****: ";
cout<<*(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3])<<endl;
void *p = arr;
for(int i = 0; i < 4; i++)
p += idx[i] * int(pow(10, 3-i)) * sizeof(int);
cout<<"Got with void *:";
cout<<*((int*)p)<<" at "<<p<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff5e3a3f18
Got with ****: 1
Got with void *:1 at 0x7fff5e3a3f18
注意事项： 编译的时候有警告，我选择忽略
test.cpp: In function 'int main()':
test.cpp:23:53: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
p += idx[i] * int(pow(10, 3-i)) * sizeof(int);
使用char *代替void *（更好）
既然我们要逐字节操作指针，那么用char *代替void *会更好。
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
char *p = (char *)arr;
for(int i = 0; i < 4; i++)
p += idx[i] * int(pow(10, 3-i)) * sizeof(int);
cout<<"Got with char *:";
cout<<*((int*)p)<<" at "<<(void *)p<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff4ffd7f18
Got with char *:1 at 0x7fff4ffd7f18
和int *（在这种情况下）
我被告知在算术中使用 void * 不是一个好的做法，使用 int * 会更好，所以我将 arr 转换为 int *指针并替换 pow.
#include <bits/stdc++.h>
using namespace std;
#define N 10
int main()
{
int arr[N][N][N][N] = {0};
int idx[4] = {1, 2, 3, 4};
arr[1][2][3][4] = 1;
cout<<"Expected: "<<arr[1][2][3][4]<<" at "<<&arr[1][2][3][4]<<endl;
cout<<"Got with ****: ";
cout<<*(*(*(*(arr + idx[0]) + idx[1]) + idx[2]) + idx[3])<<endl;
int *p = (int *)arr;
int offset = 1e3;
for(int i = 0; i < 4; i++)
{
p += idx[i] * offset;
offset /= 10;
}
cout<<"Got with int *:";
cout<<*p<<" at "<<p<<endl;
return 0;
}
输出
Expected: 1 at 0x7fff5eaf9f08
Got with ****: 1
Got with int *:1 at 0x7fff5eaf9f08
构造索引多维数组的算法的方式会因选择的语言而异；你已经用 C 和 C++ 标记了这个问题。我会坚持使用后者，因为我的回答与 C++ 有关。一段时间以来，我一直在研究类似但不同的东西，所以当我构建一个多用途多维矩阵 class 模板时，这成为一个有趣的问题。
关于更高层次的多维向量和矩阵，我发现 3 的阶数在理解更高维度的本质方面反复创造奇迹。在考虑它的算法软件实现方面之前，先从几何角度考虑这一点。
从数学上讲，让我们考虑第一个形状为 0 维对象的最低维 0。这恰好是任意点，该点可以具有无限量的坐标位置属性。诸如 p0(0)、p1(1)、p2(2,2)、p3(3,3,3),... pn(n,n,...n) 之类的点，其中每个对象都指向具有定义数量的维度属性的特定语言环境。这意味着没有线性距离，例如长度、宽度或高度，相反，没有任何方向或维度的大小，其中没有大小边界的形状或对象不定义任何面积、体积或更高维度的体积。同样对于这些 0 维点，没有方向意识，这也意味着没有定义大小的旋转角度。另一件需要考虑的事情是任意点也是零向量。另一件有助于理解这一点的事情是通过使用代数多项式，使得线性的 f(x) = mx+b 是一维方程、形状（在这种情况下是一条线）或图形，f(x) = x^2 是二维的， f(x) = x^3 是三维的，f(x) = x^4 是四维的，依此类推直到 f(x) = x^n 是 N 维的。长度或大小、旋转方向或角度、面积、体积等无法定义，除非您将两个不同的点相关联以给出至少 1 个具有指定方向的线段或矢量。一旦你有了一个隐含的方向，你就会有坡度。
在看数学运算时，最简单的是加法，它只不过是线性平移，一旦你介绍了加法，你就同时介绍了所有其他运算，例如减法、乘法、除法、幂和根；一旦你有了乘法和除法，你就可以定义旋转、旋转角度、面积、体积、变化率、斜率（也就是正切函数），从而定义几何和三角学，然后它们也会导致积分和导数。是的，我们都上过数学课，但我认为这对于理解如何构建一个数量级与另一个数量级的关系很重要，一旦你知道如何构建，这将帮助我们轻松处理更高维度的订单构建它。一旦你明白即使你的高阶运算也不过是加法和减法的展开，你就会开始了解到它们的连续运算在本质上仍然是线性的，只是它们扩展到多个维度。
前面我说过 3 的顺序重复创造奇迹所以让我解释一下我的意思。由于我们每天都以 3D 的视角感知事物；我们只能可视化 3 个不同的向量，它们彼此正交，给你我们自然的 Space 的 3 个维度，例如左和右，向前和向后给你水平轴和平面，向上和向下给你垂直轴和飞机。我们无法想象更高的东西，所以 x^4, x^5, x^6 etc... 的维度我们无法想象，但它们确实存在。如果我们开始查看数学多项式的图形，我们可以开始看到奇函数和偶函数之间的模式，其中 x^4, x^6, x^8 相似，它们只不过是 x^2 的展开和 [= 的函数19=] 只不过是 x^3 的扩展。所以我认为前几个维度是正常的：零点，第一个 - 线性，第二个 - 面积和第三个 - 体积，至于第四个和更高的维度，我称之为体积。
因此，如果您看到我使用 Volume，那么它直接与第 3 维相关，而如果我提到 Volumetric，则它与高于第 3 维的任何维度相关。现在让我们考虑一个矩阵，就像您在常规代数中看到的那样，其中公共矩阵由 MxN 定义。好吧，这是一个具有 M * N 个元素的二维平面矩阵，并且该矩阵的面积也为 M * N。让我们扩展到更高维的矩阵，例如 MxNxO 这是一个具有 M * N * O 个元素的 3D 矩阵，现在具有 M * N * O 个体积。因此，当您将此可视化时，将 MxN 2D 部分视为一本书的一页，而 O 组件代表一本书的每一页或盒子的每一片。这些矩阵的元素可以是任何东西，从简单值到应用运算，再到方程、方程组、集合或存储容器中的任意对象。所以现在当我们有一个 4 阶矩阵时，例如 MxNxOxP，它现在有一个 4 维的方面，但最简单的可视化方法是，这将是一个一维数组或向量，其中它的所有P 个元素将是 MxNxO 个体积的 3D 矩阵。当你有一个 MxNxOxPxQ 的矩阵时，你现在有一个 PxQ 的二维区域矩阵，其中每个元素都是一个 MxNxO 体积矩阵。然后如果你有一个 MxNxOxPxQxR 你现在有一个 6 维矩阵，这次你有一个 3D 体积矩阵，其中每个 PxQxR 元素实际上是 MxNxO 的 3D 矩阵。一旦你走得越来越高，这种模式就会重复并再次融合。所以任意矩阵的行为顺序是这些维度重复：1D 是线性向量或矩阵，2D 是面积或平面矩阵，3D 是体积矩阵，任何更高的东西重复这个过程压缩体积的前一步因此术语体积矩阵。看看这个 table:
// Order of Magnitude And groupings
-----------------------------------
Linear Area Volume
x^1 x^2 x^3
x^4 x^5 x^6
x^7 x^8 x^9
x^10 x^11 x^12
... ... ...
----------------------------------
现在只需使用一点微积分就可以知道将哪个数量级索引到哪个更高维度级别。一旦你知道了一个特定的维度，就可以很容易地求出多个导数来得到一个线性表达式；然后遍历space，然后对多个导数的同阶积分得到结果。这应该通过首先忽略高维顺序中最不重要的较低维度来消除大量的中间工作。如果您正在处理具有 12 个维度的东西，您可以假设定义第一组体积的前 3 个维度被紧密打包为另一个 3D 体积矩阵的元素，然后再一次，体积矩阵的 2d 阶本身就是一个元素另一个 3D 体积矩阵。因此我们有一个重复模式，现在只需应用它来构建一个算法，一旦你有了一个算法；用任何可编程语言实现这些方法应该很容易。因此，您可能必须进行 3 种情况切换以确定使用哪种算法方法，了解矩阵或 n-d 数组的整体维度，其中一个处理线性顺序，另一个处理面积，最后一个处理体积，如果它们是 4th+那么整个过程本质上就变成了递归。