Sorting a Vector of Vector in Cpp

Question

Say I have this vector of vector [[5,10],[2,5],[4,7],[3,9]] and I want to sort it using the sort() method of cpp, such that it becomes this [[5,10],[3,9],[4,7],[2,5]] after sorting. That is I want to sort based on the second index.

Now I have written this code to sort this vector of vector, but it is not working correctly.

static bool compareInterval( vector<vector<int>> &v1, vector<vector<int>> &v2)
    {
        return (v1[0][1]>v2[0][1]);
    }
    

sort(boxTypes.begin(), boxTypes.end(), compareInterval);

Can anyone tell me where I am going wrong and hwo can I correct it. Thanks in advance.

I'd guess the compare function should take a (reference to) vector-of-int, not a vector-of-vectors. — chi
– chi, Commented Sep 7, 2021 at 14:35

Cory Kramer · Accepted Answer · 2021-09-07 14:07:07Z

6

Your sort could look like

std::sort(boxTypes.begin(), boxTypes.end(), [](auto const& lhs, auto const& rhs) {
    return lhs[1] > rhs[1];
});

in other words sorting by the [1] element of each vector and using > to sort in descending order. Note that in the lambda function lhs and rhs are of type const std::vector<int>&.

answered Sep 7, 2021 at 14:07

Cory Kramer

119k19 gold badges176 silver badges233 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Aniket Sharma · Accepted Answer · 2021-09-07 15:10:44Z

When your code is sorting vector of vectors then to the boolean function it passes two vectors (not vector of vectors), and compares them to determine if they need to be interchanged, or are they in correct positions relative to each other.

Hence, here you only need to compare 2 vectors (you have tried to compare vector of vectors).

The change you need to make in compareInterval is:

static bool compareInterval( vector<int> &v1, vector<int> &v2)
{
    return (v1[1]>v2[1]);
}

Find my testing code below:

#include <bits/stdc++.h>

using namespace std;

static bool compareInterval( vector<int> &v1, vector<int> &v2)
{
    return (v1[1]>v2[1]);
}

int main() {
    vector<vector<int>> boxTypes = {{5,10},{2,5},{4,7},{3,9}};
        
    sort(boxTypes.begin(), boxTypes.end(), compareInterval);
    
    for(int i=0;i<4;i++)
        cout<<boxTypes[i][0]<<" "<<boxTypes[i][1]<<"\n";
}

rturrado · Accepted Answer · 2021-09-07 15:03:05Z

1

Range projections will come somewhat handy for this.

ranges::sort algorithm would receive:

just the vector to sort; no iterators to the begin and end.
(optionally) the function you want to use for sorting, greater in this case.
(optionally) the projection: for every element t of the original vector, which happens to be another vector of two elements, get its second element, i.e. t[1], and sort on that.

std::ranges::sort(boxTypes, std::ranges::greater{}, [](auto&& bt) { return bt[1]; });

Note I have only been able to have this compiling on msvc, not on gcc or clang (and with /std:c++latest, not even with /std:c++20; https://godbolt.org/z/9Kqfa9vhx).

edited Sep 7, 2021 at 15:03

answered Sep 7, 2021 at 14:53

rturrado

8,2097 gold badges44 silver badges65 bronze badges

Collectives™ on Stack Overflow

Sorting a Vector of Vector in Cpp

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related