如何根据第二个元素对std::set进行排序？

Question

给定 n 个二维 space 点，按升序顺序对所有点进行排序。

(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.

样本输入:

示例输出:

我声明了一个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;
}

我的输出

如果键相同，我希望键值降序排列。

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 作为默认比较器，用于比较插入其中的元素。

在您的情况下，您将 std::pair<int,int> 作为您的元素类型，因此，std::set 使用标准中定义的 std::pair 的 default operator<，因此您不是得到你想要的结果。

为了实现你的自定义样式比较，你需要提供一个自定义比较器

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

应该满足compare的要求。从 C++11 开始，您还可以为此使用 lambda 函数：

以下是示例代码：(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;
}

输出:

Answer 3

正如和其他人的回答，您可以创建一个自定义比较器来指定您希望如何对您的点进行排序：

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

插入集合比插入向量然后排序慢的几个原因：

std::set 实现涉及二叉树，通常是 red-black 树。 See here for details.
迭代 std::set 中的元素范围是 much slower

请注意，这两种方法都需要 n 次分配，并且需要按 nlog(n) 次操作顺序进行插入 + 排序。

如何根据第二个元素对std::set进行排序？

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

c++

sorting

custom-compare

stdset