使用 lower_bound 在矩阵的一行中查找序列

Question

我需要编写一个函数，根据指定的标准对矩阵 (

vector<vector<int>>

) 的行进行排序。标准是，如果某行的最大元素大于与其比较的行的最大元素，则该行被认为是第一位的。如果元素相等，则第一个行是字典顺序“更大”的行。接下来，我需要查找序列是否出现在该矩阵的任何行中。这是我尝试过的：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

template <typename Type>
bool compareRows(vector<Type> row1, vector<Type> row2) {
    return row1 > row2;
}


// This is the criterion specified for sorting the rows
template <typename Type>
bool Criterion(vector<Type> vec1, vector<Type> vec2) {
    Type el1 = *max_element(vec1.begin(), vec1.end());
    Type el2 = *max_element(vec2.begin(), vec2.end());

    if(el1 != el2) {
        return el1>el2;
    }
    return vec1>vec2;
}


// This function sorts the rows based on the criterion
template <typename Type>
void sortRows(vector<vector<Type>>& matrix) {
    sort(matrix.begin(), matrix.end(), Criterion<Type>);
}

int main()
{

   vector<vector<int>> matrix = {{1,2,3}, {3,2,1}, {2,2,2}, {1,1,1}};
   vector<int> sequence = {1,2,3};

   sortRows(matrix);
    auto it = lower_bound(matrix.begin(), matrix.end(), sequence, compareRows<int>);
    if (it != matrix.end() && *it == sequence) {
        int index = it - matrix.begin()+1;
        cout << "Found at index " << index;
    } else {
        cout << "Not found!" << endl;
    }

return 0;
}

现在，作为参考，我知道我的矩阵正在按应有的方式排序。预期的排序矩阵是

{{3,2,1}, {1,2,3}, {2,2,2}, {1,1,1}}

，如果我在对行进行排序后打印它，这就是我的程序输出的结果。但是，如果您复制并粘贴这段代码，它会告诉您找不到该序列！当然，它应该在索引 2 处找到（如果我们从 1 开始计数）。请注意，我正在关注的 YouTube 教程要求我们使用

lower_bound

来完成此操作，所以我想知道为什么这不起作用。

Answer 1

由于

std::lower_bounds

要求根据提供的比较器对范围进行排序，因此您需要对

std::lower_bound

使用与对

std::sort

相同的比较器。目前，您正在使用

compareRows<int>

，它不如何对范围进行排序。

auto it = lower_bound(matrix.begin(), matrix.end(), sequence, Criterion<int>);
//                                                            ^^^^^^^^^^^^^^