【C++】STL容器中的比较函数对象

目录

set、map容器

priority_queue容器

在STL中涉及到以某种规则排序的容器都需要比较函数对象，比如：set、map、priority_queue这些容器内部都是依赖比较函数对象以某种规则存储数据的。STL容器中的比较函数对象可以是：函数指针、仿函数(函数对象)。当然，比较函数对象的应用肯定是不限于STL容器的，比如某些排序函数，如：std::sort，对于sort而言其比较函数对象可以是：函数指针、仿函数、lambda表达式。

set、map容器

set类模板参数如下：

可以看到set和map的默认比较函数对象是std::less<T>，默认存储的数据是按照pair<const Key,T>中的键值升序排序的。如果要降序呢？std::greater<T>是降序的，我们也可以自己实现一个比较函数对象，如下是set的构造函数种类：

set的构造函数只有空构造和范围构造是可以对比较函数对象进行设置，至于拷贝构造中的比较函数对象则是与源对象x的相同。

比较函数对象的一个重要作用就是我们可以根据实际情况灵活设置容器的数据按照某种规则排序。

比如，现在要实现一个排序需求：set容器中存储的数据类型是结构体，里面存储学生的基本信息(年龄，身高，性别)，将这些结构体数据按照学生的年龄升序排序：

#include <iostream>
#include <set>
#include <string>
using namespace std;
struct StuData
{
	StuData(int age, int height, const string&  sex)
	{
		_age = age;
		_height = height;
		_sex = sex;
	}
	int _age;
	int _height;
	string _sex;
};

//仿函数
class Comp
{
public:
	bool operator()(const StuData& stu1, const StuData& stu2) const
	{
		return stu1._age < stu2._age;
	}
};

//函数指针
bool comp(const StuData& stu1, const StuData& stu2)
{
	return stu1._age < stu2._age;
}
typedef bool(*func_t)(const StuData&, const StuData&);
int main()
{
	//比较函数对象为仿函数：
	//set<StuData, Comp> myset({ StuData(23,170,"male"),StuData(21,165,"female"),StuData(25,160,"female") });
	//比较函数为函数指针：
	func_t f = comp;
	set<StuData, func_t> myset({ StuData(23,170,"male"),StuData(21,165,"female"),StuData(25,160,"female") }, f);
	cout<<"年龄排序：";
	for (const auto& e : myset)
	cout << e._age << " ";
	return 0;
}

需要注意的是：当比较函数对象是我们自己实现的仿函数，其operator()重载运算符函数必须后应该加上const，否则会报错，我们可以观察到set容器构造函数参数中设置比较函数是以传const引用传参的,如下：

也就是说，我们实现的仿函数在传入到set对象中，此时这个仿函数是具有const属性的，然而调用被const属性修饰的对象中的某成员函数时(调用该成员函数时也不会修改对象中的成员变量时)，此时就应该在该成员函数后加上const，那么这个成员函数参数列表中的this指针类型就从Comp*变成了const Comp*。这个对于比较函数对象按传const引用传参的设置应该是考虑到传入的仿函数是匿名对象的情况。

priority_queue容器

对于priority_queue的构造函数参数列表中，设置比较函数对象也是传const引用传参，优先级队列默认是大堆，对应的默认的比较函数对象是std::less<T>，我们也可以根据实际情况来实现新的比较函数对象。

一个应用：

合并K个升序链表

class Solution {
public:
    //仿函数
    class Compare
    {
    public:
        bool operator()(const ListNode* node_1, const ListNode* node_2)const
        {
            return node_1->val > node_2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (0 == lists.size())
            return nullptr;
        int size = lists.size();
        priority_queue<ListNode*, vector<ListNode*>, Compare> q;
        for (int i = 0;i < size;++i)
        {
            if (lists[i] != nullptr)
                q.push(lists[i]);
        }
        ListNode* head = new ListNode();
        ListNode* cur = head;
        while (!q.empty())
        {
            ListNode* tmp = q.top();
            q.pop();
            cur->next = tmp;
            cur = cur->next;
            if (tmp->next != nullptr)
                q.push(tmp->next);
        }
        cur = head->next;
        delete head;
        return cur;
    }
};