Comparator for vector>

Question

vector<pair<int,int> > v;
for(i=0;i<5;i++){
    cin>>b>>c;
    v.push_back(make_pair(b,c));
}
sort(v.begin(),v.end());

Is it possible to write a comparator for the sort function such that v[i].first is sorted in increasing order and for similar values of v[i].first, v[i].second is sorted in decreasing order?
like:-
i/p:

o/p:

Is this C++? Please add a tag specifying what language you're using. — Tom Zych, Jun 15 '14 at 11:43
Yes, it is possible and quite trivial. You just need to write a suitable comparison function and pass it to `std::sort`. — juanchopanza, Jun 15 '14 at 12:11
@juanchopanza: Having trouble in writing the comparator, can u help me about how can i write a comparator for this. — Shivam, Jun 15 '14 at 12:19

score 5 · Answer 1 · answered Jun 15 '14 at 12:30

5

Here is a compact comparison function object that does what you want: (uses C++11 features)

struct Shivam {
    typedef std::pair<int, int> const& param_type;
    bool operator()(param_type lhs, param_type rhs) const {
        return std::tie(lhs.first, rhs.second) < std::tie(rhs.first, lhs.second);
    };
};

And use it like this:

std::sort(std::begin(v), std::end(v), Shivam{});

answered Jun 15 '14 at 12:30

Blastfurnace

17,981
46
54
68

1

note that this needs C++11. – Csq Jun 15 '14 at 12:32

jalf · Accepted Answer · 2014-06-15T16:33:32.210

Sure, it's easy enough.

All you need to do is write a function with this signature:

bool f(std::pair<int, int> lhs, std::pair<int, int> rhs);

The function should return true if and only if lhs < rhs

So, by your criteria, lhs is smaller than rhs if:

lhs.first < rhs.first,
or lhs.first == rhs.first && lhs.second > rhs.second

So, basically just put those together, and you get:

bool mycomparer(std::pair<int, int> lhs, std::pair<int, int> rhs) {
    if (lhs.first < rhs.first) {
        return true;
    }
    else if (lhs.first == rhs.first && lhs.second > rhs.second) {
        return true;
    }
    else {
        return false;
    }
}

This could be written much more compactly, but I wanted to keep it simple and readable to get the point across. :)

you should encourage using functors. – Csq Jun 15 '14 at 12:28 — Csq, Jun 15 '14 at 12:28

Comparator for vector>

2 Answers2

Linked