共计 2402 个字符,预计需要花费 7 分钟才能阅读完成。
- 数学中 关系的定义:https://baike.baidu.com/item/%E5%85%B3%E7%B3%BB/3785874?fr=aladdin
关系是有序对的汇合
- 关系可能具备的性质定义
以下均假如 R 是汇合 A 上的二元关系:
- 自反性,如果对于 A 中的每个元素 x,都有 <x, x> 属于 R,则称 R 具备自反性。
- 反自反性(irreflexivity),如果对于 A 中每个元素 x,都有 <x, x> 不属于 R,则称 R 具备反自反性。
- 对称性,如果对于 R 中的每个有序对 <x, y> 都有对应的有序对 <y, x> 也属于关系 R,则称 R 具备对称性。
- 反对称性,如果对于 R 中的每个有序对 <x, y>,且 <y, x> 也属于关系 R,那么 x == y 肯定成立,则称 R 具备反对称性。留神:有些关系既是对称的,又是拥护称的,如相等关系;有些关系是对称的,但不是拥护称的,如 Z 中的“绝对值相等”;有些关系是拥护称的,但不是对称的,如 Z 中的≤和 <;还有的关系既不是对称的,又不是拥护称的。
- 传递性 对于 A 中的元素 x, y, z, 如果 <x, y> 属于 R 并且 <y, z> 属于 R,那么 <x, z> 就属于 R,则称 R 具备传递性。
- 偏序集(partical order)
设 R 是汇合 A 上的一个关系,如果 R 是自反的、拥护称的和可传递的,则称 R 是汇合 A 的偏序关系,简称偏序,记作“≤”。这里的符号不仅仅指咱们之前学过的具体符号,而是偏序的符号,当然小于等于号(对应的关系)自身是典型的偏序关系。
个别将一个汇合 A 和定义在其上的偏序关系 R 一起称为偏序集。
wiki 定义:https://en.wikipedia.org/wiki/Partially_ordered_set#Strict_and_non-strict_partial_orders
对于汇合 A 中的元素 x 和 y 而言,如果有序对 <x, y> 或者 <y, x> 属于偏序关系 R,则称 x 和 y 是可比拟的(comparable),否则称 x 和 y 是不可比拟的(incomparable)。如果汇合 A 中的任意两个元素之间是可比拟的,则称偏序关系 R 为全序关系(total order)。
- 全序集(total order)
对于一个偏序集 A,R,如果对于 A 中的任意两个元素 x 和 y,有序对 <x, y> 和 <y, x> 至多有一个属于关系 R,则称 R 为序关系,A 和 R 一起称为全序集合 / 有序集。和下面的定义实质上是一样的。
举例:一个偏序集而不是全序集的例子,汇合的蕴含关系,两个汇合间可能是不可比拟的。
- 严格和非严格偏序关系(strict and non-strict partial orders)
上述定义的偏序集能够认为是非严格的,次要是为了与上面的严格偏序集做比照:
一个严格偏序关系须要具备如下性质:
反自反性,传递性和反对称性。记作小于号符号,和下面的定义相似,这里仅作为一个符号应用,当然咱们相熟的小于号对应的关系是典型的严格偏序关系。
- 严格的弱序关系(strict weak orderings)
如果一个严格偏序集(汇合 A 与定义在汇合 A 上的严格偏序关系 R)的关系 R 满足:如果 A 上的元素 x,y,z,x 和 y 是不可比拟的,y 和 z 是不可比拟的,则 x 和 z 是不可比拟的。那么称这样的关系为严格弱序关系,也就是说具备可传递的不可比拟性。
- 等价关系(equivalence relation)
一个等价关系应该具备如下性质:
自反性,传递性,对称性。
留神到,严格弱序集上的不可比拟的关系(incomparability relation)是一种等价关系。 // 集体猜想,官网说法很含糊。
证实:
// 留神了解,不可比拟关系是依附于某个关系定义的,即是关系的关系。
// 自反性:x 和 x 是不可比拟的,因为严格弱序是反自反的,所以!(xRx) && !(xRx)为真。
// 传递性:!(xRy) && !(yRx)为真,!(yRz) && !(zRy)为真,则因为严格弱序关系的额定性质,即可传递的不可比拟性,因而!(xRz) && !(zRx)为真,不可比拟关系是传递的
// 对称性:!(xRy) && !(yRx) 为真,则因为逻辑运算左右两侧替换不影响后果,因而不可比拟关系是对称的。
所以说严格弱序关系的定义保障了定义在其上的不可比拟关系是等价关系。
wiki:https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings
以上是前导常识,当初看下明天要说的 c ++ 中的一个 concept:Compare。这个 concept 在 c ++ 的规范库中宽泛波及并应用,例如关联容器 set 和 map 中,算法 sort 中等等,url:https://en.cppreference.com/w/cpp/named_req/Compare
具体的 requirements 见上链接即可,总的来说就是满足 Compare 的类的对象是一个函数对象,等同于关系,其两个参数等同于元素,这个关系应该是一个严格弱序关系。
留神规范中的这句话:Note: comp
induces a strict total ordering on the equivalence classes determined by equiv
这个严格弱序关系在 equiv 定义的等价类上是一个严格全序关系
//equiv 就是上文中的不可比拟关系(也是等价关系),原汇合能够被划分为不同的等价类,每个等价类是一个子集合,该汇合中的元素两两等价。
这其实很好了解,只有 x 和 y 来自不同的等价类,那么 <x, y> 或者 <y, x> 至多有一个属于严格弱序关系的汇合 – 因为依据定义都不属于的话 x 和 y 必定在一个等价类中。
因而,当你为 map 和 set 以及可反复版本提供自定义类型的 key 时,以及对自定义类型的对象进行 sort 排序时(无论应用默认版本还是提供比拟函数,因为默认版本最终还是要调用 operator<)都要留神,你定义的关系须要满足严格弱序关系。
之后会举一个例子阐明,这种状况并不少见,而且有时候比较复杂和费解。