排序比较函数std::set<std::pair<int,std::pair<int,int>>>

Question

我有这些结构：

typedef std::pair<unsigned int, std::pair<int, int> > myPair;
typedef std::set< myPair> Graph;

Graph g;

排序图形的正确比较函数是什么？

std::sort(g.begin(), g.end(), Cmp());

我试过这样做：

struct Cmp{
    bool operator()(const myPair& l, const myPair& r)const{
        return l.second.second < r.second.second;
    }
};

我希望集合按照最内对的第二个元素排序。可能吗？

a = (std::make_pair(0,std::make_pair(1,1)));
b = (std::make_pair(0,std::make_pair(1,2)));
c = (std::make_pair(0,std::make_pair(1,0)));
d = (std::make_pair(1,std::make_pair(2,0)));

结果将是：

订购前

c = (0,(1,0)), a = (0,(1,1)), b = (0,(1,2)), d = (1,(2,0)

下单后

c = (0,(1,0)), d = (1,(2,0), a = (0,(1,1)), b = (0,(1,2))

问：是否可以按照这种排序方式创建集合？

Answer 1

您不能在 std::set 上调用 std::sort，但您可以使用谓词构造 set。

typedef std::set<myPair, Cmp> Graph;

Answer 2

您需要另一个具有不同谓词的 set。您无法更改现有 set.

的排序算法

Answer 3

您的比较功能是一个好的开始。缺少的是 "tie resolution"。您需要指定 l.second.second == r.second.second 时发生的情况，以及 l.second.first == r.second.first:

时发生的情况

bool operator()(const myPair& l, const myPair& r)const{
    return (l.second.second < r.second.second) ||
           ((l.second.second == r.second.second) && (l.second.first < r.second.first)) ||
           ((l.second.second == r.second.second) && (l.second.first == r.second.first) && (l.first < r.first)).
}

第一个条件来自您的实施。
第二个条件告诉当第一优先级项目彼此相等时做什么
第三个条件告诉当第一优先级和第二优先级项目彼此相等时做什么。

为了使用此功能对您的集合进行排序，您需要将其作为第二个模板参数传递给 std::set。 Here is a Q&A explaining how to do it.

排序比较函数std::set<std::pair<int,std::pair<int,int>>>

Comparison function for sorting std::set<std::pair<int,std::pair<int,int>>>

c++

stl

std-pair