Как отсортировать std::set по второму элементу?

Question

Дано n точки в двумерном пространстве, отсортировать все точки в порядке возрастания.

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

Входная спецификация:

Первая строка состоит из целого числа tколичество тестовых случаев. Затем для каждого теста первая строка состоит из целого числа n, количество баллов. Тогда следующий n строки содержат два целых числа xi, yi который представляет собой точку.

Спецификация выхода:

Для каждого теста выведите отсортированный порядок точек. Входные ограничения:

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

ПРИМЕЧАНИЕ: строгий лимит времени. предпочитать scanf/printf/BufferedReader вместо cin/cout/Scanner,

Пример ввода:

1
5
3 4
-1 2
5 -3
3 3
-1 -2

Пример вывода:

-1 2
-1 -2
3 4
3 3
5 -3

Я объявил setТеперь я хочу отсортировать по убыванию (значения), если ключи равны. Вот мой код:

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

мой вывод

-1 -2
-1 2
3 3
3 4
5 -3

Я хочу, чтобы значения ключей сортировались по убыванию, если ключи одинаковые.

Answer 1

По умолчанию Set не сортирует так, как вы хотите, поэтому вам нужно предоставить собственную функцию сравнения.

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;

Answer 2

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

В вашем случае у вас есть std::pair<int,int> as your element type hence, the std::set uses the default operator< из 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;
}

Выход:

-1 2
-1 -2
3 4
3 3
5 -3

Answer 3

Как ответили Jejo и другие, вы можете создать собственный компаратор, чтобы указать, как вы хотите, чтобы ваши баллы были отсортированы:

// 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);

Однако, если производительность вас беспокоит, вы, вероятно, обнаружите, что использование std:: vector и вызов std:: sort намного быстрее, чем альтернатива std:: set / insert:

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

Несколько причин, по которым вставка в набор происходит медленнее, чем вставка в вектор, а затем сортировка:

1. Реализации std:: set включают двоичные деревья, обычно красно-черные деревья. Смотрите здесь для деталей.
2. Итерации по диапазону элементов в std:: set намного медленнее

Обратите внимание, что оба метода требуют n выделений и требуют порядка операций nlog(n) для вставки + сортировки.