C++ `std::sort` 在不复制的情况下指向二维数据的指针

Question

我在二维数据的 C 样式数组中有大量数据(GiB 到 TiB)。它不是数组的数组，而是指向被解释为二维数据的数据的指针。它非常大，所以我不想将它复制到 std::vector s 或类似的。我无法控制数据的来源，它来自外部库。

我需要std::sort基于列中数据的数据行(不完全是词法排序，但类似的概念)。

我已经弄清楚如何使用编译时已知的列数来完成此操作。例如:

#define COLUMNS 4
struct Row {
    double values[COLUMNS];
};

double* data = ...;
size_t n_rows = ...;
size_t n_cols = COLUMNS;

std::sort((Row*)data, ((Row*)data)+n_rows, comp);

我知道我可以为 COLUMNS 的结构模板而不是使用宏而不是使用 comp可以定义 operator<比Row结构，但这不会改变列数*的编译时性质。

我能想到的唯一解决方案是使用知道每一行步幅的自定义随机访问迭代器。但在我制作自己的迭代器(这对我来说总是有点令人生畏)之前，我想确保没有其他方法。

*做出这些设计选择是因为我实际上是用 Cython 而不是 C++ 编写的，但这无关紧要，我不知道如何在没有自定义迭代器的情况下使用 C++ 执行此操作。我愿意用 C++ 编写解决方案，但更喜欢可以用 Cython 编写的选项(我可以转换)。

Answer 1

示例代码显示在下面的 O(n) 时间内重新排序。您需要更改 pa[i]-a，它将指针转换为索引以处理 a[] 的实际结构。

#include <algorithm>
#include <iostream>

bool compare(const double *p0, const double *p1)
{
    return *p0 < *p1;
}

int main()
{
double a[8] = {8.0,6.0,1.0,7.0,5.0,3.0,4.0,2.0};
double *pa[8];
size_t i, j, k;
double ta;
    // create array of pointers to a[]
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];
    // sort array of pointers to a[]
    std::sort(pa, pa+sizeof(a)/sizeof(a[0]), compare);
    // reorder a[] and pa[] according to pa[] in O(n) time
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            pa[k] = &a[k];
        }
    }
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        std::cout << a[i] << ' ';
    std::cout << std::endl;
    return 0;
}

---

就地重新排序通过撤销根据 a[] 排序的 pa[] 中的“循环”来实现。对于此示例代码，索引列表 0 到 7 后跟 pa[i]-a 列表(i = 0 到 7)导致:

0 1 2 3 4 5 6 7    (i)
2 7 5 6 4 1 3 0    (pa[i] - a)

这显示了根据 a[] 排序的 pa[] 中的“循环”。从第(i)行的0开始，它下面的索引是2。看第i行的2，它下面的数字是5。5下面是1。1下面是7。7下面是a 0，完成那个循环。使用 -> 标记下一个索引，本例中有 3 个循环:

{0->2->5->1->7->0} {3->6->3} {4->4}

就地重新排序的作用是撤销 a[] 和 pa[] 的循环。它在 pa[0] (i != pa[i]-a) 找到第一个循环。查看 a[]，您有 ta=a[0]、a[0]=a[2]、a[2] = a[5]、a[5]=a[1]、a[1]= a[7]，此时 i == 0 == pa[7]-a，循环的最后一部分，它设置 a[7] = ta。 pa[] 以相同的方式更新。下一个循环是ta=a[3]，a[3]=a[6]，a[6] = ta。最后一个循环，4->4 指向它自己，所以被跳过 (i == pa[i]-a)。时间复杂度为 O(n)。

YouTube 上有一个关于排列和循环表示法的视频(在本例中为 (0,2,5,1,7)(3,6)((4) 被忽略，因为它就位了)。您可以在网络上搜索“排列循环”以获取其他文章。

https://www.youtube.com/watch?v=MpKG6FmcIHk