STL使用sort注意的问题

2024-04-17 19:56:02

结构体使用sort算法时，重载operator<(..)。如果我们按下面这样写

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

#include <iostream>

#include <vector>

#include <stdint.h>

#include <algorithm>

#include <string.h>

using namespace std;

typedef struct SidInterface {

SidInterface() {

memset(this, 0, sizeof(SidInterface));

}

SidInterface(uint64_t s, uint32_t i) {

sid = s;

interface = i;

}

uint64_t sid;

uint32_t interface;

bool operator<(const SidInterface& tmp) const {

if (sid > tmp.sid) {

return false;

} else if (sid <= tmp.sid) {

return true;

} else {

return interface < tmp.interface;

}

}

bool operator==(const SidInterface& tmp) const {

return (sid == tmp.sid && interface == tmp.interface);

}

} SidInterface_T;

int main()

{

vector<SidInterface_T> vec {

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

SidInterface(4504699140857627, 4001),

SidInterface(4511296210624283, 4001),

};

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

auto uni = unique(vec.begin(), vec.end());

vec.erase(uni, vec.end());

}

我们在运行的时候，就会产生一个core dump；仔细去看也没有发现哪里不对，是不是很郁闷？
其实问题就在这里：

else if (sid <= tmp.sid) {

这种写法是错误的，应该是

else if (sid < tmp.sid) {

这里为什么会出错呢？这里牵扯到“Strict Weak Ordering"，什么是Strict Weak Ordering？

1.必须是”反对称的(antisymmetric)" : 如果x < y 为真，则y < x为假

2.必须是“可传递(transitive)" ：如果x<y为真且y<z为真，则x < z为真

3.必须是“非自反的(irreflexive)： x < x永远为假

基于"Strict Weak Ordering"，也就是所如果 x < y 为假且y < x为假，那么x == y.用程序表示即是：

!(x<y) && !(y<x)

...

而sort算法恰恰就必须遵循"Strict Weak Ordering".

于是 else if (sid <= tmp.sid) 这样写就会出现一件特别cool的事情：

sort在比较的时候，我们简单一些，假如10出现两次，为了好区分，第一次叫10A，第二次叫10B，

于是在比较两个10是否相等的时候，就会出现!(10A <= 10B) && !(10B <= 10A)，这样结果就是false，也就是说10A！=10B，这是多么的COOL

所以不能这样写。

我们参见Effective STL 21条款，永远让比较函数对相等的值返回false

请参见：

www.sgi.com/tech/stl/StrictWeakOrdering.html

Effictive STL 条款21：永远让比较函数对相等的值返回false

Effictive STL 条款31:了解你的排序选择

最新文章

热门文章