【转】自定义排序函数实现时需要注意的问题

huangyhg

http://www.blog.edu.cn/user2/60478/archives/2006/1218973.shtml



stl范型算法中的sort可以根据自定义的函数进行排序，也可以用函数对象。我今天碰到一个关于错误地定义此函数的问题，运行时出现assert异常，检查了好久以后，才发现是什么原因。

我要比较两个CPoint *类型的对象，定义的函数如下：

bool compair_points(CPoint const* p1, CPoint const* p2)
{
return p1->x-p2- >x;
}
我是要用这个函数按照每个点的x坐标的大小来排序，所以直接用减法，看起来没什么问题，于是就对一个数组排序了，但是运行时老是在sort那句出现错误，反正是说小于符号的问题。就像下面这样的信息：
Debug Assertion Failed!
Program: f:"My Cpp"mfc projects"FindCenter"debug"FindCenter.exe
File: d:"microsoft visual studio 8"vc"include"algorithm
Line: 2764

Expression: invalid operator<

For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.
(Press Retry to debug the application)

看样子是说小于符号定义得不对。我跟踪到出现异常的stl的源代码的一个函数中，就是下面这个函数：
template<class _Pr, class _Ty1, class _Ty2> inline
bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, _Ty1& _Left, _Ty2& _Right,
const wchar_t *_Where, unsigned int _Line)
{ // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
if (!_Pred (_Left, _Right))
return (false);
else if (_Pred(_Right, _Left))
_DEBUG_ERROR2("invalid operator<", _Where, _Line);
return (true);
}
看 了这个函数，我就知道错误了。这个函数要求对于调用的两个参数交换位置时不能得到相同的结果，其实理论上也是这样，如果a比b小，则b肯定不会比a小。如 果定义的函数既得出a比b小，又得出b比a小，那这个函数定义得肯定有问题。所以我定义的那个比较函数有问题，里面只有一句return p1->x-p2->x;显然，不管p1和p2的x为何值，只要他们的x不同，那么这个函数都回返回true，所以这样定义是错误的。应该 为：return (p1->x-p2->x)<0;

看来以后要严禁，该用逻辑类型的时候就严格地使用逻辑类型，而不要使用算数类型，否则容易出逻辑错误，这样的错误很难检查。stl的代码中对于这样的愚蠢错误进行了检查，感觉还是很人性化的，虽然提示不太明确，但是对找错很有帮助。

显然，对于比较函数，sort方法要求的只是小于符号，当然如果要降序排列也可以定义成别的，只要不出现像上面那样的冲突。定义返回值不要比 较<=或者>=，因为中间有了等于，同样会出现逻辑错误，如果a>=b,则当b==a时，b>=a也是成立的，所以同样会出错。 两个元素相等不能考虑在这个里面。实际上当两个元素相等时谁排在前面或者后面根本就不重要。如果一定要排除个顺序来，就还要根据别的条件来排，比如说，我 的这个根据x坐标来排序的函数，假设数组中没有重复的点，则当x相等时，再根据y来排序，可以这样：
bool compair_points(CPoint const* p1, CPoint const* p2)
{
if(p1->x!=p2->x)
return (p1->x-p2->x)<0;
else
return (p1->y-p2->y)<0;
}

huangyhg

C语言中用qsort()快速排序
C语言中排序的算法有很多种，系统也提供了一个函数qsort()可以实现快速排序。原型如下：
void qsort(void *base, size_t nmem, size_t size, int (*comp)(const void *, const void *));
它根据comp所指向的函数所提供的顺序对base所指向的数组进行排序，nmem为参加排序的元素个数，size为每个元素所占的字节数。例如要对元素进行升序排列，则定义comp所指向的函数为：如果其第一个参数比第二个参数小，则返回一个小于0的值，反之则返回一个大于0的值，如果相等，则返回0。

例：
#include <stdio.h>
#include <stdlib.h>

int comp(const void *, const void *);

int main(int argc, char *argv[])
{
int i;
int array[] = {6, 8, 2, 9, 1, 0};

qsort(array, 6, sizeof(int), comp);

for (i = 0; i < 6; i ++) {
printf("%d\t", array[i]);
}
printf("\n");

return 0;
}

int comp(const void *p, const void *q)
{
return (*(int *)p - *(int *)q);
}
运行结果如下：
0 1 2 6 8 9

huangyhg

#include <vector>
#include <algorithm> // Include algorithms
#include <iostream>

using namespace std;

bool pr(int s1, int s2)
{
return s1>s2;
}

int main(int argc, char* argv[])
{
vector<int> vec;
vector<int>::iterator i;

vec.push_back (10);
vec.push_back (3);
vec.push_back (7);
sort(vec.begin(), vec.end(),pr); // Sort the vector

for (i = vec.begin(); i != vec.end(); i++)
{
cout<<*i<<endl;
}
system("pause");
return 0;
}

sort模板有两种:
---------------------------------------------------------------------
template<class RanIt>
void sort(RanIt fist, RanIt last);
template<class RanIt, class Pred>
void sort(RanIt fist, RanIt last, Pred pr);
---------------------------------------------------------------------
第一种模板，sort重排[first,last)之间的元素，产生一个按operate<排列的序列。sort将序列中的元素以升序方式排列。
第二种模板和前一个的行为相似，不过它用pr(X,Y)代替了operate<(x,y)。