使用 std::sort 对具有特定标准的二维向量进行排序

Question

我遇到了一个关于使用库 algorithm

中的 std::sort 使用所需标准对 2D 向量（矩阵）进行排序的编码问题

例如，假设我有一个二维向量

1,8,3
1,9,1
1,4,2 
    ^

我想按第 3 列排序（例如增长标准）所以排序后我想要一个矩阵：

1,9,1
1,4,2
1,8,3
    ^

我知道要在std::sort中指定排序标准，需要在std::sort中发送第三个函数。如果它是 1D vector，那将不是问题。我会在 std::sort 内创建一个带有 2 个参数的 lambda，将它们与 return true/false.

进行比较

所以现在你可以看到我面临的问题，我如何访问矩阵中的特定元素，在我的例子中是第三列元素并将它们与 std::sort 进行比较？

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

void printMatrix(std::vector<std::vector<int>> m) {
    for(int i = 0; i < m.size(); i++) {
        for(int j = 0; j < m[i].size(); j++) {
            std::cout << m[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<std::vector<int>> m{
        {1,8,3},
        {1,9,1},
        {1,4,2}
    };

    std::sort(m.begin(), m.end(), [](int a, int b) { // error
                // ???
    });
    printMatrix(m);

    return 0;
}

我不想使用任何其他外部库来解决这个问题。

非常感谢任何帮助！ :)

Answer 1

std::sort(m.begin(), m.end(), [](int a, int b) { // error
                // ???
    });

m.begin()和m.end()返回的迭代器的value_type是std::vector<int>。因此，您的 lambda 需要为其两个参数采用 type。

std::sort(m.begin(), m.end(), 
        [](const std::vector<int>& a, const std::vector<int>& b) {
               return a.at(2) < b.at(2);
    });

注意：我在这里使用 at() 成员函数而不是运算符 [] 来防止 UB 如果您错误地尝试在无效索引中进行排序。

Demo

Answer 2

当您想要对 std::vector<std::vector<int>> 进行排序时，容器的项目是 std::vector<int> 类型，而不是 int。因此，您不能将 lambda 与声明

一起使用

[](int a, int b) { ... }

对这样的容器进行排序。您需要在声明

中使用 lambda

[](std::vector<int> a, std::vector<int> b) { ... }

或

[](std::vector<int> const& a, std::vector<int> const& b) { ... }

使用第一个版本的成本很高，因为它最终会为每次调用 lambda 制作 std::vector 的副本。因此，建议使用第二个版本。

std::sort(m.begin(), m.end(), [](std::vector<int> const& a,
                                 std::vector<int> const& b) {
   return a.back() < b.back();
});

Answer 3

虽然不是最有效的解决方案，但最简单的方法是转置 2D 向量（也称为矩阵），对每个向量进行排序，然后再次转置。这是一个经过测试的有效函数，可以为您执行此操作：

template<typename T>
void sortColumns(vector<vector<T> > &v){
    vector<vector<T> > rv(v[0].size(), vector<T>(v.size()));
    for(int i = 0; i < v.size(); i++){
        for(int j = 0; j < v[i].size(); j++){
            rv[j][i] = v[i][j];
        }
    }
    for(int i = 0; i < rv.size(); i++){
        sort(rv[i].begin(), rv[i].end());
        for(int j = 0; j < rv[i].size(); j++){
            v[j][i] = rv[i][j];
        }
    }
}

同样，这不是按列对矩阵进行排序的最有效或最现代的方法，但它有效且易于理解。

使用 std::sort 对具有特定标准的二维向量进行排序

Sorting a 2D vector with specific criteria using std::sort

c++

sorting

2d

vector