CODEWITHSUNDEEP
c++sortingvector2d
galaxyworks
galaxyworks

Reputation: 331

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

I have encountered one coding problem regarding sorting a 2D vector (matrix) using a desired criteria using std::sort from library algorithm

For example let's say I have a 2D vector

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

and I want to sort it by 3rd column (for example growth criteria) So after sorting I want to have a matrix: 

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

I know that in order to specify sorting criteria in std::sort, third function needs to be sent in std::sort. If it were a 1D vector it would not be a problem. I would make a lambda inside std::sort with 2 parameters, compare them and return true/false.

So now you can see the problem I am facing, how can I access specific elements inside a matrix, in my case third column elements and compare them with 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;
}

I would not like to use any other external libraries to solve this problem.

Any help is very appreciated! :)

Upvotes: 4

Views: 1457

Answers (3)

Panos
Panos

Reputation: 1834

Although not the most efficient solution, the simplest thing to do would be to transpose your 2D vector (aka matrix) sort each vector and then transpose again. Here is a tested, working function that will do this for you:

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

Again this isn't the most efficient or the most modern way to sort a matrix by columns but it works and is simple to understand.

Upvotes: 0

WhiZTiM
WhiZTiM

Reputation: 21576

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

The value_type of the iterators returned by m.begin() and m.end() is a std::vector<int>. Hence, your lambda needs to take that type for both of its parameters.

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

Note: I am using the at() member function here rather than operator [] to prevent UB should you ever mistakenly attempt to sort by in invalid index.

Demo

Upvotes: 3

R Sahu
R Sahu

Reputation: 206567

When you want to sort a std::vector<std::vector<int>>, the items of the container are of type std::vector<int>, not int. Hence, you cannot use a lambda with the declaration

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

to sort such a container. You need to use a lambda with the declaration

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

or

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

Using the first version is expensive since it will end up making copies of std::vector for each call to the lambda. Hence, it is recommended to use the second version.

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

Upvotes: 2

Related Questions