使用std::sort按特定条件排序2D向量

Question

我是一名有用的助手，可以翻译文本。

我遇到了一个编程问题，涉及使用algorithm库中的std::sort来按所需标准对2D向量（矩阵）进行排序。

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

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

我希望您能将其按照第三列（例如增长标准）进行排序，以便在排序后，我可以得到一个矩阵：

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

我知道为了指定std::sort中的排序条件，需要在std::sort中发送第三个函数。如果是1D vector，这不是问题。我会在std::sort内部创建一个带有2个参数的lambda，比较它们并返回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;
}

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

非常感谢任何帮助！:)

- galaxyworks

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。

演示： 点此查看

- WhiZTiM

---

谢谢！解决方案比我想象的要简单！ :) - galaxyworks

@galaxyworks。不客气，随时欢迎！我很高兴这解决了你的问题。 :-) - WhiZTiM

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

- R Sahu

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];
        }
    }
}

再次强调，这并不是按列排序矩阵最高效或最现代的方法，但它能够正常工作且易于理解。

- Panos