c++ - 我有一个存储在内存中的表。如何根据列对其进行排序？

Question

我有一个表存储在连续内存中。它需要在排序后保持该格式。

例如:

int table[5][3] = {
    { 60, 5, 10 },
    { 0, 200, 15 },
    { 55, 50, 365 },
    { 4, 7, 78 },
    { 555, 8, 11 },
};

除了更大(最大的大小，以字节为单位，大约为 27 KB)。每个单元格始终是一个 int32，并且所有行都具有相同数量的列。

假设我想根据第一列对其进行排序，那么结果必须等同于:

    { 0, 200, 15 },
    { 4, 7, 78 },
    { 55, 50, 365 },
    { 60, 5, 10 },
    { 555, 8, 11 },

执行此操作的最佳方法是什么？我想有比将其转换为 std::list，调用 sort()，然后再转换回来更好的方法。

此外，C++ 中内置的东西是最好的，我只需要调用一些函数。

Answer 1

std::sort 不会轻易做到，因为数组不可赋值。

但是，std::qsort 会这样做:

int cmp_first_column(const void *lhs_, const void *rhs_) {
    // optimize this to taste
    const int *lhs = static_cast<const int*>(lhs_);
    const int *rhs = static_cast<const int*>(rhs_);
    if (lhs[0] < rhs[0]) return -1;
    if (lhs[0] > rhs[0]) return 1;
    return 0;
}

std::qsort(table, 5, 3*sizeof(int), cmp_first_colum);

好的，所以 std::qsort 没有从模板内联优化中获益，但它完成了工作，至少你没有分配大量内存和进行不必要的复制。

您可以改为将 int[3] 数组替换为以 int[3] 作为数据成员的结构数组。那将是可分配的，您可以正常使用 std::sort 。取决于您编写了多少依赖于当前类型的其他代码，以及是否可以破坏代码使用的接口(interface)。