c++排序相关的参数“cmp“的用法及理解

对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 中模板参数需要填类名,要么类里重载 '< '、要么类外写个结构体重载 ‘()’ 后作模板参数填进去。

上一篇:二分查找


下一篇:《关于cmp返回值的理解》