对sort函数(需要algorithm头文件),它的cmp可以是“函数”,也可以是“对象”
bool myfunction (int i,int j) { return (i<j); } struct myclass { bool operator() (int i,int j) { return (i<j);} } myobject; int main () { int myints[] = {32,71,12,45,26,80,53,33}; vector<int> myvector (myints, myints+8);//放进容器vector sort(myfunction); //参数cmp是个函数 sort(myobject);//参数cmp是个结构体对象 return 0; }
▲注意:这里的函数myfunction返回类型为bool,返回真时认为i<j,假时认为i>=j,排序默认从小到大,因此反向排序只需把return (i<j)改成return (i>j)。
另外值得一提,结构体的bool operator() (int i,int j)函数,实际上是操作符的重载函数,对括号进行了重载,相当于平时用的operator +(…)这种,因此对于结构体对象myobject,可以这样操作bool re = myobject(1,2);,结果将会返回false,书写的形式跟函数一样(方便理解记忆,实际上参数并不能从“函数”类型转换成“对象”类型,是重载)
---------------------------------------------------------------------------------------------------------------------
对qsort函数,cmp是函数名
int values[] = { 40, 10, 100, 90, 20, 25 }; int cmp(const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int main () { int n; qsort (values, 6, sizeof(int), cmp);//qsort() 函数的声明: //C 库函数 void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) 对数组进行排序。 //base -- 指向要排序的数组的第一个元素的指针。 //nitems -- 由 base 指向的数组中元素的个数。 //size -- 数组中每个元素的大小,以字节为单位。 //compar -- 用来比较两个元素的函数。 return 0; }
▲注意:这里的函数cmp必须对上原型 int (__cdecl* _PtFuncCompare)(void const, void const),说白了就是返回值为 int,函数名字随意,函数参数类型要为 void const*(const顺序可调)。里面 (int)a 实际就是:先把 void* 型的指针a强制转成 int* 指针,在 * ((int*)a),把指向对象拿出来比较,如果是其他float/double,不用多说,改成 *(double *)之类的。
顺带一题,此处为升序排列,返回值小于0(一般写成返回-1),认为a比b小,等于0认为相等,大于0(一般写成返回1)认为a比b大,想要从大到小的降序排序,改下即可
cmp( (void *) & a, (void *) & b ); | |
cmp 函数的返回值 | 描述 |
<0 | a将被排在b前面 |
>0 | a将被排在b后面 |
=0 | a=b |
-----------------------------------------------------------------------------------------------------------------------------------
对STL容器,如优先队列(最大/最小堆,默认为最大堆)priority_queue类来说,其模板参数只能类/结构体名,因此它的"cmp"要为结构体名(注意不是上面说的myobject了,是结构体的名字),里面需有操作符()重载函数。
struct cmp //名字自定 { bool operator ()(int a, int b) { return a.val < b.val; } } int main() { /*需要头文件queue,第一个模板参数为数据类型,第二个为容器类型,第三个为结构体*/ priority_queue<int, vector<int>, cmp> t; return 0; }
▲注意:这里的cmp返回值为bool型,函数为对括号的重载函数。
值得一提的是,这个花样还挺多的:
class A { int val; bool operator <(int a, int b) const {return a<b;} //这里const不能省,参数你可写成const int &a等,加const说明函数是不能改变类中的成员变量的。 //如果想最小堆优先,则将return a<b;改为return a>b;后者根据题目需求自己定义。 //friend bool operator <(const int &a, const int &b) //友元函数也可以 } int main() { priority_queue< A , vector<A> > t; return 0; }
如果类中重载了“ < ” (注意:重载 “>” 会编译错误,从数学上来讲只重载 < 就够了),就不用指定队列使用哪个cmp。若指定为最大堆可以第三参数( cmp 的位置)可写成 less,最小堆可以写成 greater,一步到位。
简单来说,STL 中模板参数需要填类名,要么类里重载 '< '、要么类外写个结构体重载 ‘()’ 后作模板参数填进去。