用C++按列排序表格，同时保留行内容

Question

给定一个行主序表，类型为 std::vector<std::vector<T>> （其中 T 是一种不可比较的类型，例如 int 或 std::string），我想按照特定列对表进行排序，同时保留行内容（即行只能作为一个整体移动，而不能移动其单个单元格）。

例如，给定以下表格：

2 8 1 4
3 7 6 7
3 3 4 9
8 6 3 4
7 1 5 7

按照第三列（索引为2）排序，所期望的结果应该是：

2 8 1 4
8 6 3 4
3 3 4 9
7 1 5 7
3 7 6 7

如何使用STL实现这个功能？

我能想到一种解决方法，即将应该排序的列复制到一个关联容器中（例如 std::unordered_map<T, std::size_t>，其中键是单元格值，值是行索引），然后按键（使用std::sort()）对映射进行排序，提取结果行索引的顺序，并将其用于重新排序原始表中的行。

但是，当将其编写为实际代码时，此解决方案似乎不够优雅且过于冗长。

有哪些可能的“好”解决方案来实现这个功能？

注意：给定表类型为 std::vector<std::vector<T>>，不能更改/修改它。

- Joel Bodenmann

---

你有什么？这应该很简单，只需要两行代码。 - Marek R

Answer 1

使用比较器来比较元素。

std::vector<std::vector<T>> vec;
// add elements to vec
int idx = 2;
std::sort(vec.begin(), vec.end(), [idx](const std::vector<T>& a, const std::vector<T>& b) {
    return a.at(idx) < b.at(idx);
});

完整的可工作示例：

点击此处查看。

#include <iostream>
#include <vector>
#include <algorithm>

typedef int T;

int main() {
    std::vector<std::vector<T>> vec = {
        {2, 8, 1, 4},
        {3, 7, 6, 7},
        {3, 3, 4, 9},
        {8, 6, 3, 4},
        {7, 1, 5, 7}
    };
    int idx = 2;
    std::sort(vec.begin(), vec.end(), [idx](const std::vector<T>& a, const std::vector<T>& b) {
        return a.at(idx) < b.at(idx);
    });
    for (size_t i = 0; i < vec.size(); i++) {
        for (size_t j = 0; j < vec[i].size(); j++) {
            std::cout << vec[i][j] << (j + 1 < vec[i].size() ? ' ' : '\n');
        }
    }
    return 0;
}

- MikeCAT

Answer 2

你可以通过使用自定义的投影函数来实现 std::ranges::sort。

#include <algorithm>
#include <vector>

int main() {
  std::vector<std::vector<int>> v{
    {2, 8, 1, 4},
    {3, 7, 6, 7},
    {3, 3, 4, 9},
    {8, 6, 3, 4},
    {7, 1, 5, 7}
  };
  
  int col = 2;
  std::ranges::sort(
    v, {}, [&col](auto& x) { return x[col]; }
  );
}

演示

- 康桓瑋

---

排序 + 转换视图？你尝试编译它了吗？ - Marek R

@MarekR 这是完全符合规范的。 - 康桓瑋

好的，你是对的。上次我尝试过这种方法，但失败了（无法将视图上的交换传播回向量）。所以在我看来，你应该保留原始版本。 - Marek R

但是我发现我误解了OP的意图，没有必要使用transform_view。 - 康桓瑋

Answer 3

std::sort 可以选择性地接受一个比较器参数。

comparison function object ... which returns ​true if the first argument is less than (i.e. is ordered before) the second.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b); 

如果你有一个名为 vec 的 std::vector<std::vector<T>>（假设类型 T 可以使用 < 操作符进行比较），并且我们想要按照第三列进行排序，那么可以编写如下代码：

std::sort(
  std::begin(vec),
  std::end(vec),
  [](const std::vector<T>& a, const std::vector<T>& b) { return a[2] < b[2]; }
);

如果要更改列，只需更改数字“2”。它也可以是一个变量，只要你在lambda函数中捕获该变量即可。

- Silvio Mayolo

Answer 4

C++20的方法：

std::ranges::sort(v, std::less<> {}, [](const auto& vv) { return vv[2]; });

实时演示

- Marek R

Answer 5

有另一种方法可以对数组进行排序，那就是不要对数组进行排序。

相反，对指向数据项的索引数组进行排序：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<std::vector<int>> vec = {
        {2, 8, 1, 4},
        {3, 7, 6, 7},
        {3, 3, 4, 9},
        {8, 6, 3, 4},
        {7, 1, 5, 7}
    };

    // index starts out as 0,1,2,3,4 
    std::vector<int> index(5);
    std::iota(index.begin(), index.end(), 0);

    // desired column
    int idx = 2;
    
    // sort index array based on vec's column value
    std::sort(index.begin(), index.end(), [&](int n1, int n2) 
              { return vec[n1][idx] < vec[n2][idx]; });

    // Output results using the index array
    for (size_t i = 0; i < vec.size(); ++i)
    {
        for (size_t j = 0; j < vec[index[i]].size(); ++j)
              std::cout << vec[index[i]][j] << " ";
       std::cout << "\n";
   }
}

输出：

2 8 1 4 
8 6 3 4 
3 3 4 9 
7 1 5 7 
3 7 6 7 

这样做的一个优点是，在排序期间不需要交换整个向量，而只需要交换一个简单的 int。

- PaulMcKenzie