How to sort a vector or deque KeyPair

Question

I have a deque <pair<int, int> > r;. I need to sort all by second parameter, and return a deque<int> of first all parameters. For example:

deque<pair<int, int> > r;
r.push_back(make_pair(1, 5));
r.push_back(make_pair(0, 8));
r.push_back(make_pair(7, 3));
r.push_back(make_pair(2, 1));

I need this result

{2, 7, 1, 0}

I have a working method that "brute force" all value to N², but it's very bad. Maybe there exists something this std::? I hope you help me.

Answer 1

You just need to define a comparison operator to work with the second item in your pair:

std::sort(r.begin(), r.end(), 
    [](std::pair<int, int> const &a, std::pair<int, int> const &b) {
         return a.second < b.second;
    }
);

...or, if you can't use a lambda (e.g., using too old of a compiler) you can define your functor explicitly instead:

template <class T>
struct by_second { 
    bool operator()(T const &a, T const &b) { 
        return a.second < b.second;
    }
};

std::sort(r.begin(), r.end(), by_second());

From there, it's a matter of getting the first item in each pair and putting it into your result:

std::transform(r.begin(), r.end(), std::back_inserter(result),
    [](std::pair<int, int> const &p) { return p.first; });