C++——以安静的顺序交换数组行

Question

我想通过另一个数组的索引按一定顺序更改二维数组的行。例如：

5 1 1 1 4 1 4 2 3 1 -- 0
2 1 2 3 4 3 5 2 5 3 -- 1
1 1 3 4 5 4 2 1 4 1 -- 2
5 5 5 5 1 1 5 3 4 3 -- 3
4 2 2 4 4 1 5 2 3 4 -- 4
5 2 4 2 1 2 2 1 4 4 -- 5
4 2 2 4 5 3 2 4 5 3 -- 6
3 4 2 2 5 3 5 4 1 5 -- 7
4 2 5 1 1 2 3 4 2 3 -- 8
5 2 3 2 3 1 5 1 4 3 -- 9

这是带有索引的数组：

0.575 0
0.65 2
0.675 5
0.675 8
0.725 9
0.75 1
0.775 4
0.85 6
0.85 7
0.925 3

我想按数组中的索引更改行，以便它们的顺序与第二个数组中的数字相同。它应该是这样的：

5 1 1 1 4 1 4 2 3 1 -- 0
1 1 3 4 5 4 2 1 4 1 -- 2
5 2 4 2 1 2 2 1 4 4 -- 5
4 2 5 1 1 2 3 4 2 3 -- 8
5 2 3 2 3 1 5 1 4 3 -- 9
2 1 2 3 4 3 5 2 5 3 -- 1
4 2 2 4 4 1 5 2 3 4 -- 4
4 2 2 4 5 3 2 4 5 3 -- 6
3 4 2 2 5 3 5 4 1 5 -- 7
5 5 5 5 1 1 5 3 4 3 -- 3

不太了解行替换算法，我想知道如何做到这一点

Answer 1

根据数组有多大，以及重新映射行后需要对其进行多少操作，您也许可以使用间接寻址——从您希望行看起来像的逻辑地址开始的映射，到实际存储的物理地址。

所以就你而言，是这样的：

std::vector<size_t> rows = {
    0,
    5,
    1,
    9,
    6,
    2,
    7,
    8,
    4
};

然后要按重新排列的顺序使用第 N 行，您可以使用

array[rows[N]]

。

关于大小和使用频率：出现的问题是，如果您按索引顺序遍历数组，则不会按地址顺序访问它。特别是如果您大量使用足够大的数组，但它不能全部放入缓存中，这可能会降低引用的局部性，从而损害访问速度。但除非您的数组比您显示的大得多（例如兆字节），否则这可能不是主要问题。