C++ STL priority_queue自定义排序实现方法详解

2023-07-04 18:22:03 72

前面讲解priority_queue容器适配器时，还遗留一个问题，即当头文件提供的排序方式（std::less和std::greater）不再适用时，如何自定义一个满足需求的排序规则。

首先，无论priority_queue中存储的是基础数据类型（int、double等），还是string类对象或者自定义的类对象，都可以使用函数对象的方式自定义排序规则。例如：

#include
#include
usingnamespacestd;
//函数对象类
template
classcmp
{
public:
//重载()运算符
booloperator()(Ta,Tb)
{
returna>b;
}
};
intmain()
{
inta[]={4,2,3,5,6};
priority_queue,cmp>pq(a,a+5);
while(!pq.empty())
{
cout<

运行结果为：

23456

注意，C++中的struct和class非常类似，前者也可以包含成员变量和成员函数，因此上面程序中，函数对象类cmp也可以使用struct关键字创建：


structcmp
{
//重载()运算符
booloperator()(Ta,Tb)
{
returna>b;
}
};

可以看到，通过在cmp类（结构体）重载的()运算符中自定义排序规则，并将其实例化后作为priority_queue模板的第3个参数传入，即可实现为priority_queue容器适配器自定义比较函数。
除此之外，当priority_queue容器适配器中存储的数据类型为结构体或者类对象（包括string类对象）时，还可以通过重载其>或者<运算符，间接实现自定义排序规则的目的。


注意，此方式仅适用于priority_queue容器中存储的为类对象或者结构体变量，也就是说，当存储类型为类的指针对象或者结构体指针变量时，此方式将不再适用，而只能使用函数对象的方式。
要想彻底理解这种方式的实现原理，首先要搞清楚std::less和std::greater各自的底层实现。实际上，头文件中的std::less和std::greater，各自底层实现采用的都是函数对象的方式。比如，std::less的底层实现代码为：


template
structless{
//定义新的排序规则
booloperator()(constT&_lhs,constT&_rhs)const{
return_lhs<_rhs;
}
};

std::greater的底层实现代码为：


template
structgreater{
booloperator()(constT&_lhs,constT&_rhs)const{
return_lhs>_rhs;
}
};

可以看到，std::less和std::greater底层实现的唯一不同在于，前者使用<号实现从大到小排序，后者使用>号实现从小到大排序。
那么，是否可以通过重载<或者>运算符修改std::less和std::greater的排序规则，从而间接实现自定义排序呢？答案是肯定的，举个例子：


#include
#include
usingnamespacestd;
classnode{
public:
node(intx=0,inty=0):x(x),y(y){}
intx,y;
};
//新的排序规则为：先按照x值排序，如果x相等，则按y的值排序
booloperator<(constnode&a,constnode&b){
if(a.x>b.x)return1;
elseif(a.x==b.x)
if(a.y>=b.y)return1;
return0;
}
intmain(){
//创建一个priority_queue容器适配器，其使用默认的vector基础容器以及less排序规则。
priority_queuepq;
pq.push(node(1,2));
pq.push(node(2,2));
pq.push(node(3,4));
pq.push(node(3,3));
pq.push(node(2,3));
cout<<"xy"<

输出结果为：

xy

12

22

23

33

34

可以看到，通过重载<运算符，使得std::less变得适用了。

读者还可以自行尝试，通过重载>运算符，赋予std::greater和之前不同的排序方式。
当然，也可以以友元函数或者成员函数的方式重载>或者<运算符。需要注意的是，以成员函数的方式重载>或者<运算符时，该成员函数必须声明为const类型，且参数也必须为const类型，至于参数的传值方式是采用按引用传递还是按值传递，都可以（建议采用按引用传递，效率更高）。
例如，将上面程序改为以成员函数的方式重载<运算符：


classnode{
public:
node(intx=0,inty=0):x(x),y(y){}
intx,y;
booloperator<(constnode&b)const{
if((*this).x>b.x)return1;
elseif((*this).x==b.x)
if((*this).y>=b.y)return1;
return0;
}
};

同样，在以友元函数的方式重载<或者>运算符时，要求参数必须使用const修饰。例如，将上面程序改为以友元函数的方式重载<运算符。例如：


classnode{
public:
node(intx=0,inty=0):x(x),y(y){}
intx,y;
friendbooloperator<(constnode&a,constnode&b);
};
//新的排序规则为：先按照x值排序，如果x相等，则按y的值排序
booloperator<(constnode&a,constnode&b){
if(a.x>b.x)return1;
elseif(a.x==b.x)
if(a.y>=b.y)return1;
return0;
}

总的来说，以函数对象的方式自定义priority_queue的排序规则，适用于任何情况；而以重载>或者<运算符间接实现priority_queue自定义排序的方式，仅适用于priority_queue中存储的是结构体变量或者类对象（包括string类对象）。


到此这篇关于C++STLpriority_queue自定义排序实现方法详解的文章就介绍到这了,更多相关STLpriority_queue自定义排序内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！

C++ STL priority_queue自定义排序实现方法详解

热门推荐

随机推荐