c++ - 如何将单独的数组排序在一起(类似于按一列对表格进行排序)？

Question

给定两个或多个数组，我如何选择对一个数组进行排序并相应地对其他数组进行排序？这类似于按一列对表格进行排序。

int main()
{
    int values1[] = {5, 4, 3, 2, 1};
    double values2[] = {1.0, 2.0, 3.0, 4.0, 5.0};
    std::string values3[] = {"h", "e", "l", "l", "o"};

    // sort by values1

    // values1 = {1, 2, 3, 4, 5};
    // values2 = {5.0, 4.0, 3.0, 2.0, 1.0};
    // values3 = {"o", "l", "l", "e", "h"};

    // sort by values3

    // values1 = {4, 5, 3, 2, 1};
    // values2 = {2.0, 1.0, 3.0, 4.0, 5.0};
    // values3 = {"e", "h", "l", "l", "o"};
}

以下是我想出的一些策略。我希望你能给我一些正确方向的提示。谢谢!

策略一:

1. 制作一个结构struct sortstruct{int i;双d; std::string s};
2. 创建 vector 并在其中复制值
3. 编写谓词函数并使用std::sort
4. 将值复制回原始结构。

这似乎很容易，但也涉及将所有数据复制两次，如果数组很大，还会创建很多小对象。此外，如果数组数量不同，这也不灵活。

策略 2:

1. 制作数组的拷贝以用于排序。
2. 使用 std::sort 对拷贝进行排序。
3. 遍历已排序的拷贝并针对每个值，在原始数组中找到该值，然后交换所有值数组中的索引位置。

也很容易实现，但是在未排序的数组中找到值需要二次方时间(每个值的线性时间)。

策略三:

1. 实现自定义排序算法，该算法采用“键”数组并将所有交换应用于其他数组。

我不喜欢我必须自己进行排序。但如果这是最好的策略，这当然没有问题。

Answer 1

最好的解决方案可能是创建一个包含值的结构或使用 std::tuple，将它的实例放在一个 vector 中并对后者进行排序，从而摆脱所有的其他数组。

如果你不能这样做，你可以引入一个间接层，它是一个索引数组(实际上是一个查找数组)。
根据您的政策对其进行排序，并且永远不要更改其他数组中项目的位置。每当您想获取元素的第 i 个元组时，从索引数组中获取第 i 个元素，并使用它从所有其他数组中获取正确的值。
如果您将来添加越来越多的数组，您将不会有问题，只要您创建它们以某种方式相对于另一个隐式排序即可。
当你添加一个新元组时，只需将其他数组的 size 推到索引数组的末尾(我假设它们都具有相同的大小):这将是新元组的索引元素。然后根据需要再次对索引数组进行排序。
排序函数可能需要您传递一个可以访问外部数组的比较函数，但这对于使用 lambda 和通过引用捕获非常简单。