将定义为vector<double>的矩阵排序

Question

假设我有一个大小为n的方阵A，定义为std::vector。

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);

- Dooggy

---

你能详细说明一下"性能原因"吗？ - SingerOfTheFall

我需要对已排序的矩阵进行重型计算，因此内存连续性更好。 - Dooggy

你需要一个包装器来允许 begin 和 end 迭代行。 - bolov

@doctorlove：我补充了一些关于如何让qsort工作的精确信息。 - Dooggy

我会采取两步操作。首先，对一个包含每行第一个元素和原始索引的 pair 的向量进行排序，然后使用排序结果重新排列矩阵。向量排序速度快，并且在排序过程中可以避免移动整个行。 - 463035818_is_not_a_number

Answer 1

std::sort适用于迭代器，并且不关心迭代器的实现。因此，如果您定义了一个struct RowIter，它包装了一个std::vector<double>& matrix，并带有一个成员size_t RowSize用于operator+(size_t)(以及operator-、operator++等)，以及一个Row operator*() const，那么std::sort可以通过该迭代器进行排序。

不幸的是，这比qsort要复杂得多，但它可以推广到非POD类型。

- MSalters

---

RowIter 应该继承自 RandomAccessIterator 吗？ - Dooggy

@Dooggy：不是继承，但确实应该实现整个RandomAccessIterator概念。已修复。 - MSalters

@Dooggy：由于您是新手，可能会将StackOverflow误认为是论坛，我们正在努力将其保持为一个问答网站。当您贡献出最终解决方案时，我们非常感激，但您可以将其作为答案发布。 （故意没有规定不允许回答自己的问题） - MSalters

Answer 2

可以用std::sort替换qsort来对底层数组进行排序，但您需要定义：

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

这取决于您自己去完成，但所有版本的标准C ++都明确支持C库，因此在这种情况下使用qsort没有任何害处，因为它更简单，最终更少出错。 qsort的方法只需要7行，易于控制和同行评审。漂亮的C ++方法至少需要2个具有非平凡构造函数的类，因此需要更多的行以及其中的错误可能性更大。 如果您真的无法使用qsort，也许是因为内部编码规则，则我将简单地将数据复制到向量的向量中，对其进行排序，然后将数据复制回初始向量。它涉及2个附加的完整矩阵副本，但至少使用标准类，并且需要编写更少的代码。

- Serge Ballesta

Answer 3

最简单的解决方案是保留qsort()，并使用std::vector::data()，它返回指向第一个元素的指针，从而允许您像使用C数组一样使用std::vector：

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

正确使用std::sort()是可能的，但冗长，因为您不仅需要一个随机访问迭代器类来按行迭代，还需要一个抽象出一行的类，以便std::sort()可以交换它们。

绕过这个问题，但仍然使用std::sort的方法是将要排序的元素提取到它们自己的std::vector中，并附带一个索引。然后对该向量进行排序，最后通过该向量中的索引重新排序原始矩阵中的行。

#include <vector>
#include <tuple>
#include <algorithm>

const int n = 10;

std::vector<double>
row_sort(std::vector<double> const& A)
{
  std::vector<std::tuple<int, double> > first_element(n);
  for(int i = 0; i < n; ++i)
  {
    first_element[i] = std::make_tuple(i, A[i*n]);
  }

  std::sort(std::begin(first_element), std::end(first_element),
            [](std::tuple<int, double> const& lhs,
               std::tuple<int, double> const& rhs)
            {
              return std::get<1>(lhs) < std::get<1>(rhs);
            });

  std::vector<double> result(n*n);
  for(int i = 0; i < n; ++i)
  {
    std::copy_n(&A[std::get<0>(first_element[i])*n], n, &result[i*n]);
  }

  return result;
}

- Grumbel