[数据结构与算法]如何定义set的比较函数?

内置数据类型使用greater

//从大到小
set<int, greater<int>> s2;
//添加元素
for (int i = 0; i < 5; i++) {
    s2.insert(rand());
}
//遍历
cout<<"从大到小s2: "<<endl;
print_stl(s2);			
// 输出: 26500 19169 18467 6334 41

为什么上面的可以呢?因为greater<int>是一个仿函数,可以用于设置集合元素的排序规则。其伪代码如下:

// 去除模板定义的简化版本，int类型变量的比较函数定义
struct greater
{	
    //重载了括号操作符，用来比较大小
    bool operator()(const int &left, const int &right) const
    {
        //如果左值>右值，为真。从大到小的排列
        return left > right;
    }
};

定义struct

这是最简单直接的方法:

struct Node
{
   int l, r, v;
   Node(int l, int r, int v) : l(l), r(r), v(v) {}
   bool operator<(const Node &oth) const { return l < oth.l; }
};

set<Node> tree;

注意有两个const.这个代码练习来自老司机树(ODT),题目715. Range 模块.

自定义仿函数

如果嫌上面的有点臃肿,只用比较的,也可以自定义仿函数,注意除了参数,函数本身也要加一个const。

class Student {
public:
    char name[64]; 	// 变量定义为private将不能在外部访问
    int  age;
};
// 仿函数
struct Scomp{   	
    bool operator() (const Student &left, const Student &right)const{
    	return left.age < right.age; // 从小到大按照年龄排序
    }
};
set<Student, Scomp> ss;

指针比较仿函数

再来一个使用仿函数定义指针指向的值比较的,练习可以参考题[23. 合并K个升序链表].(https://leetcode.cn/problems/merge-k-sorted-lists/).

struct ListNode {
    int val;
    ListNode *next;
};
struct cmp{
    bool operator()(const ListNode* a,const ListNode * b)const{
    	return a->val < b->val;
    }
};
set<ListNode*,cmp>s;

定义类

定义类默认的比较函数，这个也比较直观。

class Student {
public:
    char name[64];
    int  age;
public:
    bool operator<(const Student &other)const{
        return this->age < other.age;
    }
};

set<Student> ss;

使用lambda函数

参考了用仿函数、lambda对set进行自定义排序。

typedef vector<int> V;
// 先定义一个lambda函数对象
auto cmp = [](const V& v,const V& v2){return v[0]<v2[0];};
// <>传入模板参数decltype(cmp),同时,需要为set对象传入比较函数对象cmp
set<V,decltype(cmp)>s(cmp);

这个题可以参考57. 插入区间，它是对一些区间的左端点进行排序，区间为长度为2的vector数组。
该代码也可以用自定义仿函数来写，如下：

typedef vector<int> V;
struct cmp{
    bool operator()(const V& v,const V& v2)const{return v[0]<v2[0];}
};
set<V,cmp>s;