I needed to write a function which will sort the rows of a matrix (vector<vector<int>>
) by a specified criterion. The criterion is that a row is said to come first if its biggest element is bigger than the biggest element of the row it is being compared to. If the elements are equal, then the row that comes first is the one that is "bigger" lexicographically. Next, I need to find if a sequence appears in any row of that matrix. Here's what I tried:
#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;
}
Now, as a reference, I know that my matrix is being sorted as it should. The expected sorted matrix is {{3,2,1}, {1,2,3}, {2,2,2}, {1,1,1}}
, which is what my program outputs if I print it after sorting the rows. However, if you copy and paste this snippet of code, it will tell you that the sequence is not found! But of course, it should be found at index 2 (if we count from 1). Note that the YouTube tutorial I'm following challenged us to do this using lower_bound
so I am wondering why this does not work.
Since std::lower_bounds
requires the range to be sorted according to the supplied comparator, you need to use the same comparator for std::lower_bound
as you did for std::sort
. Currently, you are using compareRows<int>
which is not how the range is sorted.
auto it = lower_bound(matrix.begin(), matrix.end(), sequence, Criterion<int>);
// ^^^^^^^^^^^^^^
I also suggest that you take the parameters to Criterion
by const&
instead of copying the vector<int>
s every time you call the function:
template <typename Type>
bool Criterion(const std::vector<Type>& vec1, const std::vector<Type>& vec2) {
//...
}