stl严格弱序(stick weak ordering)

STL有序容器对元素关键字的类型有要求，元素关键字的类型必须定义了严格弱序（stick weak ordering）

什么是严格弱序

STL严格弱序条件

如果类型T满足以下Compare
类型 T 满足二元谓词 (BinaryPredicate) 且提供以下两个对象

  1. T类型的对象 comp 函数
  2. 一个等价于 !comp(a, b) && !comp(b, a) 的表达式 equiv(a, b)

以下表达式必须合法有效。

表达式 返回类型 要求
comp(a, b) 可隐式转换为 bool 建立具有下列性质的严格弱序关系
a. 对于所有 a，comp(a,a)==false
b. 若 comp(a,b)==true 则 comp(b,a)==false
c. 若 comp(a,b)==true 且 comp(b,c)==true 则 comp(a,c)==true
equiv(a, b) bool 建立具有下列性质的等价关系
a. 对于所有 a，equiv(a,a)==true
b. 若 equiv(a,b)==true 则 equiv(b,a)==true
c. 若 equiv(a,b)==true 且 equiv(b,c)==true 则 equiv(a,c)==true

STL严格弱序实现方式

对于STL中的容器实现<操作符，这就是一个严格弱序;而<=不是一个严格弱序

在自定义比较函数(self_compare )的时候需要注意在相等时要返回false， 不能返回true.

严格若序应用

  • 标准库中的 map set multiset multiset 等都是严格弱序。
  • map 的 key 为自定义对象时需要重载 < 操作符, 需注意相等时返回false。

参考

1
2
3
https://zh.cppreference.com/w/cpp/named_req/Compare
https://blog.csdn.net/River_Lethe/article/details/78618788