[結(jié)貼]STL當(dāng)中弱序的概念，和偏序/全序有什么區(qū)別和聯(lián)系?

centos_71

STL里面的關(guān)聯(lián)容器，元素的存儲(chǔ)說是按照嚴(yán)格弱序來排列的。我查找了維基百科對(duì)于弱序這個(gè)概念本身并沒有給出特別清晰的解釋
我們學(xué)過的離散數(shù)學(xué)里面，只學(xué)過"偏序"和"全序"的概念。這個(gè)弱序到底是什么含義，和偏序的區(qū)別/聯(lián)系是什么?

求大俠的解釋。

windoze

回復(fù) 1# centos_71

A strict weak ordering is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently,[5] that is asymmetric) in which the relation "neither a < b nor b < a" is transitive.

也就是說“strict weak ordering”滿足以下幾個(gè)條件

1、對(duì)于給定集合S，其中任意兩個(gè)元素a和b都存在ordering，這一點(diǎn)和“partial ordering”不同，后者不能保證任意兩個(gè)元素之間都存在ordering，所以才叫“partial”
2、transitive指如果a<b且b<c，則a<c
3、irreflexive是指a<a一定為假
4、asymmetric指若a<b，則b<a為假
5、最后一句說的是“(not a<b) and (not b<a)”有傳遞性，也就是說，如果“(not a<b) and (not b<a)”且“(not b<c) and (not c<b)”，則“(not a<c) and (not c<a)”

STL里的less定義就需要滿足以上條件

centos_71

windoze 發(fā)表于 2015-01-17 13:35
回復(fù) 1# centos_71

謝謝，你的解釋很專業(yè)，就是第(5)點(diǎn)有點(diǎn)不太明白:

為什么要用兩個(gè)not之間加個(gè)and? 這個(gè)條件邏輯上等價(jià)于 ( a<b or b<a )------之前你在第(1)點(diǎn)和第(4)點(diǎn)不是說了嗎，必然有a<b成立，或者b<a成立(兩個(gè)不能同時(shí)成立)。如果是要說明這種關(guān)系可傳遞的，那么第(2)點(diǎn)也已經(jīng)說了啊。

我的理解是，第(5)點(diǎn)是不是想表達(dá)，(1)(2)(4)所構(gòu)成的等價(jià)關(guān)系(等價(jià)關(guān)系需要對(duì)稱，自反，可傳遞)，也是可傳遞的。這是更高一層的可傳遞，對(duì)嗎?

windoze

回復(fù) 3# centos_71

“(not a<b) and (not b<a)”咋能等價(jià)于“( a<b or b<a )”？明明是等價(jià)于“not ( a<b or b<a )”，話說你的數(shù)理邏輯要補(bǔ)課…………

(a<b)和(b<a)為啥一定要有一個(gè)成立？以自然數(shù)為例，難道a=b不行么？這不就是前面說的“(not a<b) and (not b<a)”的情況么？

weak ordering沒有定義“=”，所以用了一種比較麻煩的方式。

centos_71

windoze 發(fā)表于 2015-01-17 20:17
回復(fù) 3# centos_71

“(not a

因?yàn)闆]有定義相等，所以定義了一個(gè)比較麻煩的等價(jià)! 這回我理解清楚了!