对定义为向量<double>的矩阵进行排序

Question

假设我有一个A大小的方阵n,定义为a std::vector<double>.

std::vector<double> A(n*n);

矩阵的元素以通常的方式访问:

double a_ij = A[i*n + j];

我需要按照相对于第一列的升序对矩阵的行进行排序.

qsort函数允许我使用数组和函数指针来完成它,但我想找到一种方法来实现这一点,使用向量和std::sort.

另外,请注意,出于性能原因,我不希望将矩阵定义为向量矢量.

编辑:

我传递给qsort的函数:

static int comparisonFunction(const void* firstRow, const void* secondRow) 
{
    if (((double *)firstRow)[0] < ((double *)secondRow)[0]) return -1;
    else if (((double *)secondRow)[0] < ((double *)firstRow)[0]) return 1;
    return 0;
}

电话:

std::qsort(matrixArray, nbRows, sizeof(double)*nbRows, comparisonFunction);

Answer 1

可以替换qsort为std::sort对底层数组进行排序，但您必须定义：

• 直接访问向量底层存储的 Row 类型 - 此处不能使用向量，因为即使一个或多个数组仍然是一个数组，向量组成的向量也不是平方大小的向量。更糟糕的是，我不知道没有可移植的方法将现有存储分配给向量。该 Row 类型必须是可移动构造和可移动分配的，并且正确支持交换。
• 该 Row 类型上的 RandomAccessIterator，能够正确处理底层数组的末尾。

这取决于您，但标准 C++ 的所有版本都明确支持 C 库，因此qsort在此用例中使用没有任何害处，因为它更简单并且最终更不容易出错。该qsort方式仅需要7条线，易于控制和同行评审。好的C++ 方法将需要至少 2 个具有重要构造函数的类，因此行数更多，并且其中出错的可能性也更多。

如果您确实无法使用qsort，也许对于内部编码规则，那么我只需将数据复制到向量的向量中，对其进行排序并将数据复制回初始向量。它涉及矩阵的 2 个额外完整副本，但至少使用标准类并且需要少得多的编码。