How to sort std::set according to the second element?

Question

Given n points in a two-dimensional space, sort all the points in ascending order.

(x1,y1) > (x2,y2) if and only if (x1>x2) or (x1==x2 && y1<y2)

Input specification:

The first line consists of an integer t, the number of test cases. Then for each test case, the first line consists of an integer n, the number of points. Then the next n lines contain two integers xi, yi which represents the point.

Output Specification:

For each test case print the sorted order of the points. Input constraints:

1 <= t <= 10
1 <= n <= 100000
- 10 ^ 9 <= co - ordinates <= 10 ^ 9

NOTE: Strict time limit. Prefer scanf/printf/BufferedReader instead of cin/cout/Scanner.

Sample Input:

Sample Output:

I declared a set, now I want to sort descendingly(values) if the keys are equal. Here is my code:

int main() 
{
    int n, i, hold = 0;
    set<pair<int, int>>s;
    int x, y, t;
    set<pair<int, int>>::iterator it;

    SF(t)
        while (t--)
        {

            SF(n) while (n--) {
                SF(x) SF(y)
                    s.insert({ x,y });
            }

            for (it = s.begin(); it != s.end(); it++) {
                PF(it->first) printf(" "); PF(it->second); printf("\n");
            }
            s.clear();
        }
    return 0;
}

my output

I want the key values to be sorted descendingly if the keys are same.

What is `SF` and `PF`? Do you want the `set` itself to sort the values descending? — AndyG, Jul 15 '19 at 11:54

score 2 · Answer 1 · answered Jul 15 '19 at 12:23

The std::set uses by default std::less as default comparator for comparing the elements inserting to it.

In your case, you have std::pair<int,int> as your element type hence, the std::set uses the default operator< of std::pair defined in the standard and hence you are not getting the result you want.

In order to achieve your custom style comparison, you need to provide a custom comparator

template<
    class Key,
    class Compare = std::less<Key>,
 //                 ^^^^^^^^^^^^^^^ --> instead of this
    class Allocator = std::allocator<Key>
> class set;

which should meet the requirements of compare. Since C++11 you could also use a lambda function for this:

Following is a sample example code: (See Online)

#include <iostream>
#include <set>
using  pairs = std::pair<int, int>;

int main()
{
    // custom compare
    const auto compare = [](const pairs &lhs, const pairs &rhs) 
    {
        return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second);
    };

    std::set<pairs, decltype(compare)> mySet(compare);

    mySet.emplace(3, 4);
    mySet.emplace(-1, 2);
    mySet.emplace(5, -3);
    mySet.emplace(3, 3);
    mySet.emplace(-1, -2);

    for (const auto& it : mySet)
        std::cout << it.first << " " << it.second << std::endl;
}

Output:

score 0 · Accepted Answer · answered Jul 15 '19 at 12:03

Set doesn't sort the way you want by default, so you have to supply your own comparison function.

struct MyComp
{
    bool operator()(const pair<int,int>& x, const pair<int,int>& y) const
    {
        return x.first < y.first || (x.first == y.first && x.second > y.second);
    }
};

set<pair<int,int>, MyComp> s;

Graham Palmer · Answer 3 · 2019-07-15T15:00:10.397

As Jejo and others have answered, you can create a custom comparitor to specify how you want your points sorted:

// custom compare
const auto compare = [](const pairs &lhs, const pairs &rhs) 
{
    return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second);
};

set<pair<int, int>, decltype(compare)> mySet(compare);

However, if performance is your concern, you will probably find that using a std::vector and calling std::sort is much faster than the std::set/insert alternative:

#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
    int n, i, hold = 0;
    vector<pair<int, int>> v;
    int x, y, t;

    SF(t)
        while (t--)
        {

            SF(n) 
            v.reserve(n);
            while (n--) {
                SF(x) SF(y)
                    v.emplace_back( x,y );
            }

            // custom comparitor
            const auto comp = [](const pairs &lhs, const pairs &rhs) 
            {
                return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second > rhs.second);
            };

            sort(v.begin(), v.end(), comp);

            for (const auto &p : v) {
                PF(p.first) printf(" "); PF(p.second); printf("\n");
            }
            v.clear();
        }
    return 0;
}

A couple reasons why inserting into a set is slower than inserting into a vector and then sorting:

std::set implementations involve binary trees, usually red-black trees. See here for details.
Iterating over the range of elements in a std::set is much slower

Note that both methods require n allocations and require on the order of nlog(n) operations for insertion + sorting.

How to sort std::set according to the second element?

3 Answers3