c++中sort等算法中比较操作的规则是什么

对于c++中，标准库中提供的算法很多，这些算法（如sort等）都会有自己默认的对关键字的处理规则，这些都是适用于关键字符合要求的情况，而如果我们待处理的关键字是自己自定义的类的时候，这个时候就需要我们自己定义其中的处理规则，下面以sort为例：

对于sort这种排序的算法，c++中默认的比较操作是<运算符，用来处理非降序的排序要求。这些算法中提供的操作必须在关键字类型上定义一个严格弱序。可以将严格所需看做“小于等于”，虽然实际上定义的操作可能是一个复杂的函数，但是无论如何，这个比较函数必须具备如下的基本性质：

（1）两个关键字不能同时“小于等于”对方；如果k1“小于等于”k2，那么k2决不能“小于等于”k1。

（2）如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3.

（3）如果存在两个关键字，任何一个都不“小于等于”另一个，那我们称这两个关键字是“等价的”。如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。

在上面的规则中提到的“小于等于”是严格弱序的说法，千万不要和我们平时使用的“<=”符号混淆了，这是一个很大的误区，下面举个例子。

[cpp] view plain copy

1. #include

     

2. #include

     

3. #include

     

4. #include

     

5. using namespace std;  

7. class Node  

8. {  

9. public:  

10.     Node(int score,int age,string name):m_score(score),m_age(age),m_name(name){}  

11.     int getScore() { return m_score;  }  

12.     int getScore() const { return m_score; }  

13.     friend ostream &operator<<(ostream &out, const Node &node);  

14. private:  

15.     int m_score;  

16.     int m_age;  

17.     string m_name;  

18. };  

19. ostream &operator<<(ostream &out, const Node &node)  

20. {  

21.     out << "score:" << node.m_score << "  age:" << node.m_age << "        "   

22.         << node.m_name;  

23.     return out;  

24. }  

25. bool compare(const Node &node1, const Node &node2)  

26. {  

27.     return node1.getScore() < node2.getScore();  

28. }  

30. int main()  

31. {  

32.     Node node1 = { 32,30,"liu" };  

33.     Node node2 = { 90,23,"hu" };  

34.     Node node3 = { 67,32,"ki" };  

35.     Node node4 = { 78,45,"arr" };  

36.     vector

     vec;  

37.     vec.push_back(node1);  

38.     vec.push_back(node2);  

39.     vec.push_back(node3);  

40.     vec.push_back(node4);  

41.     sort(vec.begin(), vec.end(), compare);  

42.     for (auto itr = vec.begin(); itr != vec.end(); itr++)  

43.     {  

44.         cout << *itr << endl;  

45.     }  

46.     return 0;  

47. }  

在上面的程序示例中，我们定义了一个Node类，这个类中有三个数据，显然这在默认的sort函数中，是没办法进行排序的，这个时候我们就需要自己进行比较函数的重写。此示例中我们以分数m_score进行排序。这里需要注意的是compare函数中，我们使用的是“<”，这里面我们来看一下，这个小于号是不是符合我们要求。

检验如下：

（1）不存在数k1，k2，满足k1

（2）对于数k1，k2，k3而言，当k1

（3）对于条件3，显而易见任何对于数k1，k2而言，当k1和k2相等的时候，k1

如果我们将compare函数中的“<”符号改成“<=”号的时候，如下所示：

[cpp] view plain copy 

1. #include

     

2. #include

     

3. #include

     

4. #include

     

5. using namespace std;  

7. class Node  

8. {  

9. public:  

10.     Node(int score,int age,string name):m_score(score),m_age(age),m_name(name){}  

11.     int getScore() { return m_score;  }  

12.     int getScore() const { return m_score; }  

13.     friend ostream &operator<<(ostream &out, const Node &node);  

14. private:  

15.     int m_score;  

16.     int m_age;  

17.     string m_name;  

18. };  

19. ostream &operator<<(ostream &out, const Node &node)  

20. {  

21.     out << "score:" << node.m_score << "  age:" << node.m_age << "        "   

22.         << node.m_name;  

23.     return out;  

24. }  

25. bool compare(const Node &node1, const Node &node2)  

26. {  

27.     return node1.getScore() <= node2.getScore();  

28. }  

30. int main()  

31. {  

32.     Node node1 = { 32,30,"liu" };  

33.     Node node2 = { 90,23,"hu" };  

34.     Node node3 = { 67,32,"ki" };  

35.     Node node4 = { 78,45,"arr" };  

36.     vector

     vec;  

37.     vec.push_back(node1);  

38.     vec.push_back(node2);  

39.     vec.push_back(node3);  

40.     vec.push_back(node4);  

42.     sort(vec.begin(), vec.end(), compare);  

43.     for (auto itr = vec.begin(); itr != vec.end(); itr++)  

44.     {  

45.         cout << *itr << endl;  

46.     }  

47.     return 0;  

48. }  

这个时候如何你运行的话，会发现运行的结果和第一个程序的结果一样啊。这时候是不是就会感觉我是在忽悠人了，如果你是这么认为的，那我就真的好冤啊。我们仔细看一下，这个“<=”到底满不满足我们的要求。

检验如下：

（1）当k1<=k2的时候，k2<=k1是成立的，显然不符合我们的要求1。

（2）对于数k1，k2，k3而言，当k1<=k2，k2<=k3时，则必有k1<=k3，满足条件2

（3）对于条件3，显而易见任何对于数k1，k2而言，k1<=k2和k2<=k1都是成立的，显然条件3也不符合。

从上面的检验可以发现什么问题？是不是有种恍然大悟的感觉，一切的焦点都落在了“=”上，这也就可以解释为什么我们上面的程序对于“<=”同样没有出错，这不是说用“<=”没有错误，而是我们的测试数据没能检验出这个错误，这是因为在我们的数据中没有分数相等的数据，那就永远不会触发这个错误，现在让我们一起见证这个问题，很简单，我们插入一个分数相同的数据，代码如下：

[cpp] view plain copy 

1. #include

     

2. #include

     

3. #include

     

4. #include

     

5. using namespace std;  

7. class Node  

8. {  

9. public:  

10.     Node(int score,int age,string name):m_score(score),m_age(age),m_name(name){}  

11.     int getScore() { return m_score;  }  

12.     int getScore() const { return m_score; }  

13.     friend ostream &operator<<(ostream &out, const Node &node);  

14. private:  

15.     int m_score;  

16.     int m_age;  

17.     string m_name;  

18. };  

19. ostream &operator<<(ostream &out, const Node &node)  

20. {  

21.     out << "score:" << node.m_score << "  age:" << node.m_age << "        "   

22.         << node.m_name;  

23.     return out;  

24. }  

25. bool compare(const Node &node1, const Node &node2)  

26. {  

27.     return node1.getScore() <= node2.getScore();  

28. }  

30. int main()  

31. {  

32.     Node node1 = { 32,30,"liu" };  

33.     Node node2 = { 90,23,"hu" };  

34.     Node node3 = { 67,32,"ki" };  

35.     Node node4 = { 78,45,"arr" };  

36.     Node node5 = { 78,45,"dkk" };  

37.     vector

     vec;  

38.     vec.push_back(node1);  

39.     vec.push_back(node2);  

40.     vec.push_back(node3);  

41.     vec.push_back(node4);  

43.     sort(vec.begin(), vec.end(), compare);  

44.     for (auto itr = vec.begin(); itr != vec.end(); itr++)  

45.     {  

46.         cout << *itr << endl;  

47.     }  

48.     return 0;  

49. }  

当我们再次运行这个程序的时候，会出现什么呢？下面请看：

这里面提示的是invalid comparator，意思是不合法的比较符，说明我们的“<=”是不合法的，这也正是我们平时编程时比较容易忽略和犯错的地方，特此和大家分享一下。