第六章 ADT
ADT和RI的目的是將設計與使用分離
ADT通過封裝避免表示暴露
ADT的特性:表示泄漏、抽象函數AF、表示不變量RI
一.用戶自定義類型
1.抽象類型:強調“作用于數據上的操作”,程序員和client無需關心數據如何具體存儲的,只需設計/使用操作即可
2.ADT完全由操作定義,與數據結構、內存存儲或實現等無關
例如:List不是由具體的ArrayList,LinkedList等定義,而是定義為滿足get()、size()…一系列操作的類
二.區(qū)分類型和操作
1.可變類型的對象:提供了可改變其內部數據的值的操作
2.不變數據類型: 其操作不改變內部值,而是構造新的對象
3.區(qū)分抽象類型的操作
(1)Creator(構造器) t*->T,構造一個之前沒有的
(2)Producer(生產器) T+,t*->T 在已有的基礎上構造一個新的,比如concat()連接兩個字符串為一個新的字符串
(3)Observer(觀察器) 接受抽象類型對象并返回一個不同類型的對象,比如size():看List中有幾個元素,返回的是一個int型
(4)Mutator(變值器) 改變對象屬性的方法,例如List中調用.add()方法,增加一個元素
4.Signature of Creator
實現為構造函數或靜態(tài)方法(靜態(tài)方法不需要用new來構造,通過一個靜態(tài)的方法直接調用即可),例如Arrays.asList()
實現為靜態(tài)方法的構造器通常稱為工廠方法
5.Signature of a mutator
變值器通常返回void
如果返回值為void,則必然意味著它改變了對象的某些內部狀態(tài)
變值器也可能返回非空類型,例如Set.add()返回一個布爾值,表示Set是否真的發(fā)生了改變
注:如果一個類型是immutable的,它就沒有mutator
三.設計一個好的ADT
1.設計好的ADT,靠“經驗法則”,提供一組操作,設計其行為規(guī)約 spec
2.設計一組簡單操作,通過簡單操作的組合實現復雜的操作,操作的行為內聚
3.要足以支持client對數據所做的所有操作需要,且用操作滿足client需要的難度要低(必須有的操作或者不必須但是如果提供了會為客戶提供便利的都加上)
4.要么抽象、要么具體,不要混合 — 要么針對抽象設計,要么針對具體應用的設計
例:數組,圖,集合等通用的ADT里面包含的操作就應該是通用的,不包含特性;一些針對特定領域特定問題的操作就可以有特性 通用和特定的方法不應混在一起
四.表示獨立性
1.表示獨立性:client使用ADT時無需考慮其內部如何實現,ADT內部表示的變化不應影響外部spec和客戶端
2.通過前置條件和后置條件明確了ADT的操作,調用者知道可以安全更改的內容
Specification:規(guī)約(注意類和方法聲明的標簽也是規(guī)約)
Representation:表示(內部數據結構)
Implementation:內部實現
五.測試ADT
1.測試creators, producers, and mutators:調用observers來觀察這些
operations的結果是否滿足spec
2.測試observers:調用creators, producers, and mutators等方法產生或
改變對象,來看結果是否正確
3.風險:如果被依賴的其他方法有錯誤,可能導致被測試方法的測試結
果失效
六.不變性(Invariants)
1.由ADT來負責其不變量,與client端的任何行為無關
2.不變量:在任何時候總是true
3.為什么需要不變量:保持程序的“正確性”,容易發(fā)現錯誤,可以利用不變性去進行一些推斷,解決相應問題;如果沒有這個不變性,那么在所有使用該變量的地方,都要檢查其是否改變了(總是要假設客戶會破壞不變量)
4.表示泄露:內部數據結構泄露出去,被用戶看到,用戶可以直接操作,無法在不影響客戶端的情況下改變其內部表示
5.保證不變性
(1)用private:外部方法無法修改變量
(2)用final:內部方法無法修改變量,指向同一個內存空間
該程序中:Date是mutable類型,這條return語句將內部變量返回給外部,還會聯系到表示泄露問題;this.timestamp=timestamp這一句將內部和外部的變量關聯了起來,一旦外部變量改變,也會對內部造成影響
defensive copying(防御式拷貝)(P54)
注:可變類型通常有一個復制構造函數,允許您創(chuàng)建一個新實例來復制現有實例的值。
總結:(1)檢查所有ADT的參數類型和返回類型
(2)如果是mutable就不要返回直接的引用(要返回副本)->表示泄露
最好的辦法就是用immutable類型,徹底避免表示泄露
七.RI和AF
1.R空間:表示值構成的空間:實現者看到和使用的值
A空間:抽象值構成的空間:客戶看到和使用的值
2.R->A的映射:一定是滿射,未必是單射,未必是雙射
3.AF就是抽象函數,描述R->A的映射
4.RI的定義是描述一個真假值,描述哪些映射是合法的,只有為真的才有映射;RI描述了所有“合法”表示值的集合(AF這個映射中有定義的表示值集合)
注:判斷是否可能是一個RI的判斷方法是看是否會產生一個布爾值
5.總結:選擇某種特定的表示方式R,進而指定某個子集是“合法”的(RI),并為該子集中的每個值做出“解釋”(AF)——即如何映射到抽象空間中的值
6.同樣的表示空間R,可以有不同的RI
7.即使是同樣的R、同樣的RI,也可能有不同的AF(解釋不同)
8.設計ADT:(1) 選擇R和A;(2) RI — 合法的表示值;(3) 如何解釋合法的表示值 —映射AF 要將R空間映射到A空間中的方式解釋好,并且明確地寫在代碼中
9.
客戶只需要知道1,3,4(Creator,Observer需要客戶去調用);開發(fā)者需要知道所有的
10.操作支持RI的意思就是在執(zhí)行完這些操作以后,RI還能繼續(xù)保持(P76)
11.注:在所有可能改變rep的方法內都要檢查(observer可以不檢查,但最好也檢查),保證在改變rep的時候保持RI checkRep()
assert相當于if…else…,成功則通過,否則拋出異常
八.有益的可變性
1.對immutable的ADT來說,它在A空間的abstract value應是不變的。但其內部表示的R空間中的取值則可以是變化的
2.只要保證A空間的值不變,R空間的值是允許變化的(非單射)
九.記錄AF,RI和表示暴露的安全性
1.ADT的規(guī)約里只能使用client可見的內容來撰寫,包括參數、返回值、異常等
2.如果規(guī)約里需要提及“值”,只能使用A空間中的“值”,不能使用R空間
3.AF和RI應寫普通注釋,不能像規(guī)約那樣,否則Javadoc文檔會將其暴露
十.總結
1.如何建立不變性
(1)構造器和生產器在創(chuàng)建對象時要確保不變量為true
(2)變值器和觀察器在執(zhí)行時必須保持不變性(每一步執(zhí)行完用checkRep()來檢查)
(3)在每個方法return之前,用checkRep()檢查不變量是否得以保持
2.三個標準來檢查ADT是否保持不變
(1)established by creators and producers
(2)preserved by mutators, and observers
(3)no representation exposure occurs
十一.用ADT不變性取代前置條件
利用SortedSet這個ADT的操作來取代了perconditions中的前兩句,排序和不重復在SortedSet中得以實現->Set集合類,本身就有不重復這一要求
這樣做的好處就是一旦需求變了的話,只需要改變SortedSet操作的實現即可
可以降低對客戶的要求,將這些要求全都放在ADT中去解決
總結
- 上一篇: autocad连接mysql_AutoC
- 下一篇: 【渗透cs-成功上线的第一个cs】