STL之父訪談錄????
??翻譯者 : myan
出處: http://www.sgi.com/technology/stl??
1995年3月，dr.dobb's journal特約記者, 著名技術(shù)書籍作家al stevens采訪了stl創(chuàng)始人alexander stepanov. 這份訪談紀(jì)錄是迄今為止對于stl發(fā)展歷史的最完備介紹, 侯捷先生在他的stl有關(guān)文章里推薦大家閱讀這篇文章. 因此我將該文全文翻譯如下:
q: 您對于generic programming進(jìn)行了長時(shí)間的研究, 請就此談?wù)?
a: 我開始考慮有關(guān)gp的問題是在7o年代末期, 當(dāng)時(shí)我注意到有些算法并不依賴于數(shù)據(jù)結(jié)構(gòu)的特定實(shí)現(xiàn)，而只是依賴于該結(jié)構(gòu)的幾個(gè)基本的語義屬性. 于是我開始研究大量不同的算法，結(jié)果發(fā)現(xiàn)大部分算法可以用這種方法從特定實(shí)現(xiàn)中抽象出來, 而且效率無損. 對我來說,效率是至關(guān)重要的, 要是一種算法抽象在實(shí)例化會導(dǎo)致性能的下降, 那可不夠棒.
??
?? 當(dāng)時(shí)我認(rèn)為這項(xiàng)研究的正確方向是創(chuàng)造一種編程語言. 我和我的兩個(gè)朋友一起開始干起來.一個(gè)是現(xiàn)在的紐約州立大學(xué)教授deepak kapur, 另一個(gè)是倫塞里爾技術(shù)學(xué)院教授david musser.當(dāng)時(shí)我們?nèi)齻€(gè)在通用電器公司研究中心工作. 我們開始設(shè)計(jì)一種叫tecton的語言. 該語言有一種我們稱為"通用結(jié)構(gòu)"的東西, 其實(shí)不過是一些形式類型和屬性的集合體, 人們可以用它來描述算法. 例如一些數(shù)學(xué)方面的結(jié)構(gòu)充許人們在其上定義一個(gè)代數(shù)操作, 精化之,擴(kuò)充之, 做各種各樣的事.
?? 雖然有很多有趣的創(chuàng)意, 最終該項(xiàng)研究沒有取得任何實(shí)用成果, 因?yàn)閠ecton語言是函數(shù)型語言. 我們信奉backus的理念，相信自己能把編程從von neumann風(fēng)格中解放出來. 我們不想使用副效應(yīng), 這一點(diǎn)限制了我們的能力, 因?yàn)榇嬖诖罅啃枰褂弥T如"狀態(tài)", "副效應(yīng)"等觀念的算法.??
?? 我在70年代末期在tecton上面所認(rèn)識到了一個(gè)有趣的問題: 被廣泛接受的adt觀念有著根本性的缺陷. 人們通常認(rèn)為adt的特點(diǎn)是只暴露對象行為特征, 而將實(shí)現(xiàn)隱藏起來. 一項(xiàng)操作的復(fù)雜度被認(rèn)為是與實(shí)現(xiàn)相關(guān)的屬性, 所以抽象的時(shí)候應(yīng)予忽略. 我則認(rèn)識到, 在考慮一個(gè)(抽象)操作時(shí), 復(fù)雜度(或者至少是一般觀念上的復(fù)雜度)必須被同時(shí)考慮在內(nèi). 這一點(diǎn)現(xiàn)在已經(jīng)成了gp的核心理念之一.
?? 例如一個(gè)抽象的棧stack類型,??僅僅保證你push進(jìn)去的東西可以隨后被pop出來是不夠的,同樣極端重要的是, 不管stack有多大, 你的push操作必須能在常數(shù)時(shí)間內(nèi)完成. 如果我寫了一個(gè)stack, 每push一次就慢一點(diǎn), 那誰都不會用這個(gè)爛玩藝.
?? 我們是要把實(shí)現(xiàn)和界面分開, 但不能完全忽略復(fù)雜度. 復(fù)雜度必須是, 而且也確實(shí)是橫陳于模塊的使用者與實(shí)現(xiàn)者之間的不成文契約. adt觀念的引入是為了允許軟件模塊相互可替換. 但除非另一個(gè)模塊的操作復(fù)雜度與這個(gè)模塊類似, 否則你肯定不愿意實(shí)現(xiàn)這種互換.如果我用另外一個(gè)模塊替換原來的模塊, 并提供完全相同的接口和行為, 但就是復(fù)雜度不同, 那么用戶肯定不高興. 就算我費(fèi)盡口舌介紹那些抽象實(shí)現(xiàn)的優(yōu)點(diǎn), 他肯定還是不樂意用. 復(fù)雜度必須被認(rèn)為是接口的一部分.
?? 1983年左右, 我轉(zhuǎn)往紐約布魯克林技術(shù)大學(xué)任教. 開始研究的是圖的算法, 主要的合作伙伴是現(xiàn)在ibm的aaron kershenbaum. 他在圖和網(wǎng)絡(luò)算法方面是個(gè)專家, 我使他相信高序(high order)的思想和gp能夠應(yīng)用在圖的算法中. 他支持我與他合作開始把這些想法用于實(shí)際的網(wǎng)絡(luò)算法. 某些圖的算法太復(fù)雜了, 只進(jìn)行過理論分析, 從來沒有實(shí)現(xiàn)過. 他企圖建立一個(gè)包含有高序的通用組件的工具箱, 這樣某些算法就可以實(shí)現(xiàn)了. 我決定使用lisp語言的一個(gè)變種scheme語言來建立這樣一個(gè)工具箱. 我們倆建立了一個(gè)巨大的庫, 展示了各種編程技術(shù).網(wǎng)絡(luò)算法是首要目標(biāo). 不久當(dāng)時(shí)還在通用電器的david musser加了進(jìn)來, 開發(fā)了更多的組件,一個(gè)非常大的庫. 這個(gè)庫供大學(xué)里的本科生使用, 但從未商業(yè)化. 在這項(xiàng)工作中, 我了解到副效應(yīng)是很重要的, 不利用副效應(yīng), 你根本沒法進(jìn)行圖操作. 你不能每次修改一個(gè)端點(diǎn)(vertex)時(shí)都在圖上兜圈子. 所以, 當(dāng)時(shí)得到的經(jīng)驗(yàn)是在實(shí)現(xiàn)通用算法時(shí)可以把高序技術(shù)和副效應(yīng)結(jié)合起來. 副效應(yīng)不總是壞的, 只有在被錯(cuò)誤使用時(shí)才是.
?? 1985年夏, 我回到通用電器講授有關(guān)高序程序設(shè)計(jì)的課程. 我展示了在構(gòu)件復(fù)雜算法時(shí)這項(xiàng)技術(shù)的應(yīng)用. 有一個(gè)聽課的人叫陳邇, 當(dāng)時(shí)是信息系統(tǒng)實(shí)驗(yàn)室的主任. 他問我是否能用ada語言實(shí)現(xiàn)這些技術(shù), 形成一個(gè)工業(yè)強(qiáng)度的庫, 并表示可以提供支持. 我是個(gè)窮助教, 所以盡管我當(dāng)時(shí)對于ada一無所知, 我還是回答"好的". 我跟dave musser一起建立這個(gè)ada庫. 這是很重要的一個(gè)時(shí)期, 從象scheme那樣的動態(tài)類型語言(dynamically typed language)轉(zhuǎn)向ada這樣的強(qiáng)類型語言, 使我認(rèn)識到了強(qiáng)類型的重要性. 誰都知道強(qiáng)類型有助于糾錯(cuò). 我則發(fā)現(xiàn)在ada的通用編程中, 強(qiáng)類型是獲取設(shè)計(jì)思想的有力工具. 它不僅是查錯(cuò)工具, 而且是思想工具.這項(xiàng)工作給了我對于組件空間進(jìn)行正交分解的觀念. 我認(rèn)識到, 軟件組件各自屬于不同的類別.oop的狂熱支持者認(rèn)為一切都是對象. 但我在ada通用庫的工作中認(rèn)識到, 這是不對的. 二分查找就不是個(gè)對象, 它是個(gè)算法. 此外, 我還認(rèn)識到, 通過將組件空間分解到幾個(gè)不同的方向上, 我們可以減少組件的數(shù)量, 更重要的是, 我們可以提供一個(gè)設(shè)計(jì)產(chǎn)品的概念框架.
?? 隨后, 我在貝爾實(shí)驗(yàn)室c++組中得到一份工作, 專事庫研究. 他們問我能不能用c++做類似的事.我那時(shí)還不懂c++, 但當(dāng)然, 我說我行. 可結(jié)果我不行, 因?yàn)?987年時(shí), c++中還沒有模板, 這玩意兒在通用編程中是個(gè)必需品. 結(jié)果只好用繼承來獲取通用性, 那顯然不理想.直到現(xiàn)在c++繼承機(jī)制也不大用在通用編程中, 我們來說說為什么. 很多人想用繼承實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和容器類, 結(jié)果幾乎全部一敗涂地. c++的繼承機(jī)制及與之相關(guān)的編程風(fēng)格有著戲劇性的局限. 用這種方式進(jìn)行通用編程, 連等于判斷這類的小問題都解決不了. 如果你以x類作為基類, 設(shè)計(jì)了一個(gè)虛函數(shù)operater==, 接受一個(gè)x類對象, 并由x派生類y, 那么y的operator==是在拿y類對象與x類對象做比較. 以動物為例, 定義animal類, 派生giraffe(長頸鹿)類. 定義一個(gè)成員函數(shù)mate(), 實(shí)現(xiàn)與另一個(gè)哺乳動物的交配操作, 返回一個(gè)animal對象. 現(xiàn)在看看你的派生類giraffe,它當(dāng)然也有一個(gè)mate()方法, 結(jié)果一個(gè)長頸鹿同一個(gè)動物交配, 返回一個(gè)動物對象. 這成何體統(tǒng)?當(dāng)然, 對于c++程序員來說, 交配函數(shù)沒那么重要, 可是operator==就很重要了.
?? 對付這種問題, 你得使用模板. 用模板機(jī)制, 一切如愿.
?? 盡管沒有模板, 我還是搞出來一個(gè)巨大的算法庫, 后來成了unix system laboratory standard component library的一部分. 在bell lab, 我從象andy koenig, bjarne stroustrup(andrew koenig, 前iso c++標(biāo)準(zhǔn)化委員會主席; bjarne stroustrup, c++之父 -- 譯者)這類專家身上學(xué)到很多東西. 我認(rèn)識到c/c++的重要, 它們的一些成功之處是不能被忽略的. 特別是我發(fā)現(xiàn)指針是個(gè)好東東. 我不是說空懸的指針, 或是指向棧的指針. 我是說指針這個(gè)一般觀念. 地址的觀念被廣泛使用著. 沒有指針我們就沒法描述并行算法.
?? 我們現(xiàn)在來探討一下為什么說c是一種偉大的語言. 通常人們認(rèn)為c是編程利器并且獲得如此成功,是因?yàn)閡nix是用c寫的. 我不同意. 計(jì)算機(jī)的體系結(jié)構(gòu)是長時(shí)間發(fā)展演變的結(jié)果, 不是哪一個(gè)聰明的人創(chuàng)造的. 事實(shí)上是廣大程序員在解決實(shí)際問題的過程中提出的要求推動了那些天才提出這些體系. 計(jì)算機(jī)經(jīng)過多次進(jìn)化, 現(xiàn)在只需要處理字節(jié)地址索引的內(nèi)存, 線性地址空間和指針. 這個(gè)進(jìn)化結(jié)果是對于人們要求解決問題的自然反映. dennis ritchie天才的作品c, 正反映了演化了30年的計(jì)算機(jī)的最小模型. c當(dāng)時(shí)并不是什么利器. 但是當(dāng)計(jì)算機(jī)被用來處理各種問題時(shí), 作為最小模型的c成了一種非常強(qiáng)大的語言, 在各個(gè)領(lǐng)域解決各種問題時(shí)都非常高效. 這就是c可移植性的奧秘, c是所有計(jì)算機(jī)的最佳抽象模型, 而且這種抽象確確實(shí)實(shí)是建立在實(shí)際的計(jì)算機(jī), 而不是假想的計(jì)算機(jī)上的. 人們可以比較容易的理解c背后的機(jī)器模型, 比理解ada和scheme語言背后的機(jī)器模型要容易的多. c的成功是因?yàn)閏做了正確的事, 不是因?yàn)閍t&t的極力鼓吹和unix.
?? c++的成功是因?yàn)閎jarne stroustrup以c為出發(fā)點(diǎn)來改進(jìn)c, 引入更多的編程技術(shù), 但始終保持在c所定義的機(jī)器模型框架之內(nèi), 而不是閉門造車地自己搞出一個(gè)新的機(jī)器模型來. c的機(jī)器模型非常簡單. 你擁有內(nèi)存, 對象保存在那里面, 你又有指向連續(xù)內(nèi)存空間的指針, 很好理解. c++保留了這個(gè)模型, 不過大大擴(kuò)展了內(nèi)存中對象的范疇, 畢竟c的數(shù)據(jù)類型太有限了, 它允許你建立新的類型結(jié)構(gòu), 但不允許你定義類型方法. 這限制了類型系統(tǒng)的能力. c++把c的機(jī)器模型擴(kuò)展為真正類型系統(tǒng).
?? 1988年我到惠普實(shí)驗(yàn)室從事通用庫開發(fā)工作. 但實(shí)際上好幾年我都是在作磁盤驅(qū)動器. 很有趣但跟
?? gp毫不相關(guān). 92年我終于回到了gp領(lǐng)域, 實(shí)驗(yàn)室主任bill worley建立了一個(gè)算法研究項(xiàng)目, 由我
?? 負(fù)責(zé). 那時(shí)候c++已經(jīng)有模板了. 我發(fā)現(xiàn)bjarne的模板設(shè)計(jì)方案是非常天才的. 在bell lab時(shí), 我參
?? 加過有關(guān)模班設(shè)計(jì)的幾個(gè)早期的討論, 跟bjarne吵得很兇, 我認(rèn)為c++的模板設(shè)計(jì)應(yīng)該盡可能向ada的
?? 通用方案看齊. 我想可能我吵得太兇了, 結(jié)果bjarne決定堅(jiān)決拒絕我的建議. 我當(dāng)時(shí)就認(rèn)識到在c++
?? 中設(shè)置模板函數(shù)的必要性了, 那時(shí)候好多人都覺得最好只有模板類. 不過我覺得一個(gè)模板函數(shù)在使用
?? 之前必須先顯式實(shí)例化, 跟ada似的. bjarne死活不聽我的, 他把模板函數(shù)設(shè)計(jì)成可以用重載機(jī)制來
?? 隱式實(shí)例化. 后來這個(gè)特別的技術(shù)在我的工作中變得至關(guān)重要, 我發(fā)現(xiàn)它容許我做很多在ada中不可能
?? 的任務(wù). 非常高興bjarne當(dāng)初沒聽我的.
q: 您是什么時(shí)候第一次構(gòu)思stl的, 最初的目的是什么?
a: 92年那個(gè)項(xiàng)目建立時(shí)由8個(gè)人, 漸漸地人越來越少, 最后剩下倆, 我和李夢, 而且李小姐是這個(gè)領(lǐng)域的新手. 在她的專業(yè)研究中編譯器是主要工作, 不過她接受了gp研究的想法, 并且堅(jiān)信此項(xiàng)研究將帶給軟件開發(fā)一個(gè)大變化, 要知道那時(shí)候有這個(gè)信念的認(rèn)可是寥寥無幾. 沒有她, 我可不敢想象我能搞定stl, 畢竟stl標(biāo)著兩個(gè)人的名字:stepanov和lee. 我們寫了一個(gè)龐大的庫, 龐大的代碼量, 龐大的數(shù)據(jù)結(jié)構(gòu)組件,函數(shù)對象, 適配器類, 等等. 可是雖然有很多代碼, 卻沒有文檔. 我們的工作被認(rèn)為是一個(gè)驗(yàn)證性項(xiàng)目,其目的是搞清楚到底能不能在使算法盡可能通用化的前提下仍然具有很高的效率. 我們化了很多時(shí)間來比較, 結(jié)果發(fā)現(xiàn), 我們算法不僅最通用, 而且要率與手寫代碼一樣高效, 這種程序設(shè)計(jì)風(fēng)格在性能上是不打折扣的! 這個(gè)庫在不斷成長, 但是很難說它是什么時(shí)候成為一個(gè)"項(xiàng)目"的. stl的誕生是好幾件事情的機(jī)緣巧合才促成的.
q: 什么時(shí)候, 什么原因促使您決定建議使stl成為ansi/iso標(biāo)準(zhǔn)c++一部分的?
a: 1993年夏, andy koenig跑到斯坦福來講c++課, 我把一些有關(guān)的材料給他看, 我想他當(dāng)時(shí)確實(shí)是很興奮.他安排我9月到圣何塞給c++標(biāo)準(zhǔn)委員會做一個(gè)演講. 我演講的題目是"c++程序設(shè)計(jì)的科學(xué)", 講得很理論化, 要點(diǎn)是存在一些c++的基本元素所必須遵循的, 有關(guān)基本操作的原則. 我舉了一些例子, 比如構(gòu)造函數(shù), 賦值操作, 相等操作. 作為一種語言,??c++沒有什么限制. 你可以用operator==()來做乘法. 但是相等操作就應(yīng)該是相等操作. 它要有自反性,??a == a; 它要有對稱性, a == b 則 b == a; 它還要有傳遞性. 作為一個(gè)數(shù)學(xué)公理, 相等操作對于其他操作是基本的要素. 構(gòu)造函數(shù)和相等操作之間的聯(lián)系就有公理性的東西在里邊. 你用拷貝構(gòu)造函數(shù)生成了一個(gè)新對象, 那么這個(gè)對象和原來那個(gè)就應(yīng)該是相等的. c++是沒有做強(qiáng)行要求, 但是這是我們都必須遵守這個(gè)規(guī)則. 同樣的, 賦值操作也必須產(chǎn)生相等的對象. 我展示了一些基本操作的"公理", 還講了一點(diǎn)迭代子(iterator), 以及一些通用算法怎樣利用迭代子來工作. 我覺得那是一個(gè)兩小時(shí)的枯燥演講, 但卻非常受歡迎. 不過我那時(shí)并沒有想把這個(gè)東西塞在標(biāo)準(zhǔn)里, 它畢竟是太過先進(jìn)的編程技術(shù), 大概還不適于出現(xiàn)在現(xiàn)實(shí)世界里, 恐怕那些做實(shí)際工作的人對它沒什么興趣.
?? 我是在9月做這個(gè)演講的, 直到次年(1994)月, 我都沒往ansi標(biāo)準(zhǔn)上動過什么腦筋. 1月6日, 我收到andy koenig的一封信(他那時(shí)是標(biāo)準(zhǔn)文檔項(xiàng)目編輯), 信中說如果我希望stl成為標(biāo)準(zhǔn)庫的一部分, 可以在1月25日之前提交一份建議到委員會. 我的答復(fù)是:"andy, 你發(fā)瘋了嗎?", 他答復(fù)道:"不錯(cuò), 是的我發(fā)瘋了, 為什么咱們不瘋一次試試看?"
?? 當(dāng)時(shí)我們有很多代碼, 但是沒有文檔, 更沒有正式的建議書. 李小姐和我每星期工作80小時(shí), 終于在期限之前寫出一份正式的建議書. 當(dāng)是時(shí)也, 只有andy一個(gè)人知道可能會發(fā)生些什么. 他是唯一的支持者, 在那段日子里他確實(shí)提供了很多幫助. 我們把建議寄出去了, 然后就是等待. 在寫建議的過程中我們做了很多事. 當(dāng)你把一個(gè)東西寫下來, 特別是想到你寫的可能會成為標(biāo)準(zhǔn), 你就會發(fā)現(xiàn)設(shè)計(jì)中的所有紕漏. 寄出標(biāo)準(zhǔn)后,我們不得不一段一段重寫了庫中間的代碼, 以及幾百個(gè)組件, 一直到3月份圣迭戈會議之前. 然后我們又重新修訂了建議書, 因?yàn)樵谥匦聦懘a的過程中, 我們又發(fā)現(xiàn)建議書中間的很多瑕疵.
q: 您能描述一下當(dāng)時(shí)委員會里的爭論嗎? 建議一開始是被支持呢, 還是反對?
a: 我當(dāng)時(shí)無法預(yù)料會發(fā)生些什么. 我做了一個(gè)報(bào)告, 反響很好. 但當(dāng)時(shí)有許多反對意見. 主要的意見是:這是一份龐大的建議, 而且來得太晚, 前一次會議上已經(jīng)做出決議, 不在接受任何大的建議. 而這個(gè)東西是有史以來最大的建議, 包括了一大堆新玩藝. 投票的結(jié)果很有趣, 壓倒多數(shù)的意見認(rèn)為應(yīng)對建議進(jìn)行再考慮, 并把投票推遲到下次會議, 就是后來眾所周知的滑鐵盧會議.
?? bjarne stroustrup成了stl的強(qiáng)有力支持者. 很多人都通過建議、更改和修訂的方式給予了幫助。bjarne干脆跑到這來跟我們一起工作了一個(gè)禮拜。andy更是無時(shí)無刻的幫助我們。c++是一種復(fù)雜的語言，不是總能搞得清楚確切的含義的。差不多每天我都要問andy和bjarne c++能不能干這干那。我得把特殊的榮譽(yù)歸于andy， 是他提出把stl作為c++標(biāo)準(zhǔn)庫的一部分；而bjarne也成了委員會中stl的主要鼓吹者。其他要感謝的人還有：mike vilot，標(biāo)準(zhǔn)庫小組的負(fù)責(zé)人； rogue wave公司的nathan myers(rogue wave是boland c++builder中stl方案的提供商 —— 譯者)，andersen咨詢公司的larry podmolik。確實(shí)有好多人要致謝。
?? 在圣迭戈提出的stl實(shí)際與當(dāng)時(shí)的c++，我們被要求用新的ansi/iso c++語言特性重寫stl，這些特性中有一些是尚未實(shí)現(xiàn)的。為了正確使用這些新的、未實(shí)現(xiàn)的c++特性，bjarne和andy花了無以計(jì)數(shù)的時(shí)間來幫助我們。
?? 人們希望容器獨(dú)立于內(nèi)存模式，這有點(diǎn)過分，因?yàn)檎Z言本身并沒有包括內(nèi)存模式。所以我們得要想出一些機(jī)制來抽象內(nèi)存模式。在stl的早期版本里，假定容器的容積可以用size_t類型來表示，迭代子之間的距離可以用ptrdiff_t來表示。現(xiàn)在我們被告知，你為什么不抽象的定義這些類型？這個(gè)要求比較高，連語言本身都沒有抽象定義這些類型，而且c/c++數(shù)組還不能被這些類型定義所限定。我們發(fā)明了一個(gè)機(jī)制稱作"allocator"，封裝了內(nèi)存模式的信息。這個(gè)機(jī)制深刻地影響了庫中間的每一個(gè)組件。你可能疑惑：內(nèi)存模式和算法或者容器類接口有什么關(guān)系？如果你使用size_t這樣的東西，你就無法使用 t* 對象，因?yàn)榇嬖诓煌闹羔橆愋?t*, t huge *, 等等)。這樣你就不能使用引用，因?yàn)閮?nèi)存模式不同的話，會產(chǎn)成不同的引用類型。這樣就會導(dǎo)致標(biāo)準(zhǔn)庫產(chǎn)生龐大的分支。
?? 另外一件重要的事情是我們原先的關(guān)聯(lián)類型數(shù)據(jù)結(jié)構(gòu)被擴(kuò)展了。這比較容易一些，但是最為標(biāo)準(zhǔn)的東西總是很困難的，因?yàn)槲覀冏龅臇|西人們要使用很多年。從容器的觀點(diǎn)看，stl做了十分清楚的二分法設(shè)計(jì)。所有的容器類被分成兩種：順序的和關(guān)聯(lián)的，就好像常規(guī)的內(nèi)存和按內(nèi)容尋址的內(nèi)存一般。這些容器的語義十分清楚。
?? 當(dāng)我到滑鐵盧以后，bjarne用了不少時(shí)間來安慰我不要太在意成敗與否，因?yàn)殡m然看上去似乎不會成功，但是我們畢竟做到了最好。我們試過了，所以應(yīng)該坦然面對。成功的期望很低。我們估計(jì)大部分的意見將是反對。但是事實(shí)上，確實(shí)有一些反對意見，但不占上風(fēng)。滑鐵盧投票的結(jié)果讓人大跌眼鏡，80%贊成，20%反對。所有人都預(yù)期會有一場惡戰(zhàn)，一場大論戰(zhàn)。結(jié)果是確實(shí)有爭論，但投票是壓倒性的。
q: stl對于1994年2月發(fā)行的ansi/iso c++工作文件中的類庫有何影響？
a: stl被放進(jìn)了滑鐵盧會議的工作文件里。stl文檔被分解成若干部分，放在了文件的不同部分中。mike
?? vilot負(fù)責(zé)此事。我并沒有過多地參與編輯工作，甚至也不是c++委員會的成員。不過每次有關(guān)stl的
?? 建議都由我來考慮。委員會考慮還是滿周到的。
q: 委員會后來又做了一些有關(guān)模板機(jī)制的改動，哪些影響到了stl？
a: 在stl被接受之前，有兩個(gè)變化影響到了我們修訂stl。其一是模板類增加了包含模板函數(shù)的能力。stl廣泛地使用了這個(gè)特性來允許你建立各種容納容器的容器。一個(gè)單獨(dú)的構(gòu)造函數(shù)就能讓你建立一個(gè)能容納list或其他容器的vector。還有一個(gè)模板構(gòu)造函數(shù)，從迭代子構(gòu)造容器對象，你可以用一對迭代子當(dāng)作參數(shù)傳給它，這對迭代子之間的元素都會被用來構(gòu)造新的容器類對象。另一個(gè)stl用到的新特性是把模板自身當(dāng)作模板參數(shù)傳給模板類。這項(xiàng)技術(shù)被用在剛剛提到的allocator中。
q: 那么stl影響了模板機(jī)制嗎？
a: 在弗基山谷的會議中，bjarne建議給模板增加一個(gè)“局部特殊化”(partial specialization)的特性。這個(gè)特性可以讓很多算法和類效率更高，但也會帶來代碼體積上的問題。我跟bjarne在這個(gè)建議上共同研究了一段時(shí)間，這個(gè)建議就是為了使stl更高效而提出的。我們來解釋一下什么是“局部特殊化”。你現(xiàn)在有一個(gè)模板函數(shù) swap( t&, t& )，用來交換兩個(gè)參數(shù)。但是當(dāng)t是某些特殊的類型參數(shù)時(shí)，你想做一些特殊的事情。例如對于swap( int&, int& )，你想用一種特別的操作來交換數(shù)據(jù)。這一點(diǎn)在沒有局部特殊化機(jī)制的情況下是不可能的。有了局部特殊化機(jī)制，你可以聲明一個(gè)模板函數(shù)如下：
??
?????? template <class t> void swap( vector<t>&, vector<t>& );
?? 這種形式給vector容器類的swap操作提供了一種特別的辦法。從性能的角度講，這是非常重要的。如果你用通用的形式去交換vector，會使用三個(gè)賦值操作，vector被復(fù)制三次，時(shí)間復(fù)雜度是線性的。然而，如果我們有一個(gè)局部特殊化的swap版本專門用來交換兩個(gè)vector，你可以得到一個(gè)時(shí)間復(fù)雜度為常數(shù)的，非常快的操作，只要移動vector頭部的兩個(gè)指針就ok。這能讓vector上的sort算法運(yùn)行得更快。沒有局部特殊化，讓某一種特殊的vector，例如vector<int>運(yùn)行得更快的唯一辦法是讓程序員自己定一個(gè)特殊的swap函數(shù)，這行得通，但是加重了程序員的負(fù)擔(dān)。在大部分情況下，局部特殊化機(jī)制能夠讓算法在某些通用類上表現(xiàn)得更高效。你有最通用的swap，不那么通用的swap，更不通用的swap，完全特殊的swap這么一系列重載的swap，然后你使用局部特殊化，編譯器會自動找到最接近的那個(gè)swap。另一個(gè)例子copy。現(xiàn)在我們的copy就是通過迭代子一個(gè)一個(gè)地拷貝。使用模板特殊化可以定義一個(gè)模板函數(shù)：
template <class t> t** copy( t**, t**, t** );
?? 這可以用memcpy高效地拷貝一系列指針來實(shí)現(xiàn)，因?yàn)槭侵羔樋截悾覀兛梢圆槐負(fù)?dān)心構(gòu)造對象和析構(gòu)對象的開銷。這個(gè)模板函數(shù)可以定義一次，然后供整個(gè)庫使用，而且用戶不必操心。我們使用局部特殊化處理了一些算法。這是個(gè)重要的改進(jìn)，據(jù)我所知在弗基山谷會議上得到了好評，將來會成為標(biāo)準(zhǔn)的一部分。(后來的確成了標(biāo)準(zhǔn)的一部分 —— 譯者）
q: 除了標(biāo)準(zhǔn)類庫外，stl對那一類的應(yīng)用程序來說最有用處？
a: 我希望stl能夠引導(dǎo)大家學(xué)習(xí)一種新的編程風(fēng)格：通用編程。我相信這種風(fēng)格適用于任何種類的應(yīng)用程序。這種風(fēng)格就是：用最通用的方式來寫算法和數(shù)據(jù)結(jié)構(gòu)。這些結(jié)構(gòu)所要求的語義特性應(yīng)該能夠被清楚地歸類和分類，而這些歸類分類的原則應(yīng)該是任何對象都能滿足的。理解和發(fā)展這種技術(shù)還要很長時(shí)間，stl不過是這個(gè)過程的起點(diǎn)。
?? 我們最終會對通用的組件有一個(gè)標(biāo)準(zhǔn)的分類，這些組件具有精心定義的接口和復(fù)雜度。程序員們將不必在微觀層次上編程。你再也不用去寫一個(gè)二分查找算法。就是在現(xiàn)在，stl也已經(jīng)提供了好幾個(gè)通用的二分查找算法，凡是能用二分查找算法的場合，都可以使用這些算法。算法所要求的前提條件很少：你只要在代碼里使用它。我希望所有的組件都能有這么一天。我們會有一個(gè)標(biāo)準(zhǔn)的分類，人們不用再重復(fù)這些工作。
?? 這就是douglas mcilroy的夢想，他在1969年關(guān)于“構(gòu)件工廠”的那篇著名文章中所提出來的東西。stl就是這種“構(gòu)件工廠”的一個(gè)范例。當(dāng)然，還需要有主流的力量介入這種技術(shù)的發(fā)展之中，光靠研究機(jī)構(gòu)不行，工業(yè)界應(yīng)該想程序員提供組件和工具，幫助他們找到所需的組件，把組件粘合到一起，然后確定復(fù)雜度是否達(dá)到預(yù)期。
q: stl沒有實(shí)現(xiàn)一個(gè)持久化(persistent)對象容器模型。map和multimap似乎是比較好的候選者，它們可以把對象按索引存入持久對象數(shù)據(jù)庫。您在此方向上做了什么工作嗎，或者對這類實(shí)現(xiàn)有何評論？
a：很多人都注意到這個(gè)問題。stl沒實(shí)現(xiàn)持久化是有理由的。stl在當(dāng)時(shí)已經(jīng)是能被接受的最巨大的庫了。再大一點(diǎn)的話，我認(rèn)為委員會肯定不會接受。當(dāng)然持久化是確實(shí)是一些人提出的問題。在設(shè)計(jì)stl，特別是設(shè)計(jì)allocator時(shí)，bjarne認(rèn)為這個(gè)封裝了內(nèi)存模式的組件可以用來封裝持久性內(nèi)存模式。bjarne的洞察秋毫非常的重要和有趣，好幾個(gè)對象數(shù)據(jù)庫公司正在盯著這項(xiàng)技術(shù)。1994年10月我參加了object database management group的一個(gè)會議，我做了一個(gè)關(guān)于演說。他們非常感興趣，想讓他們正在形成中的組件庫的接口與stl一致，但不包括allocator在內(nèi)。不過該集團(tuán)的某些成員仔細(xì)分析了allocator是否能夠被用來實(shí)現(xiàn)持久化。我希望與stl接口一致的組件對象持久化方案能在接下來的一年里出現(xiàn)。
q：set，multiset，map和multimap是用紅黑樹實(shí)現(xiàn)的，您試過用其他的結(jié)構(gòu)，比如b*樹來實(shí)現(xiàn)嗎？
a：我不認(rèn)為b*適用于內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，不過當(dāng)然這件事還是應(yīng)該去做的。應(yīng)該對許多其他的數(shù)據(jù)結(jié)構(gòu)，比如跳表(skip list)、伸展樹(splay tree)、半平衡樹(half-balanced tree)等，也實(shí)現(xiàn)stl容器的標(biāo)準(zhǔn)接口。應(yīng)該做這樣的研究工作，因?yàn)閟tl提供了一個(gè)很好的框架，可以用來比較這些結(jié)構(gòu)的性能。結(jié)口是固定的，基本的復(fù)雜度是固定的，現(xiàn)在我們就可一個(gè)對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行很有意義的比較了。在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域里有很多人用各種各樣的接口來實(shí)現(xiàn)不同的數(shù)據(jù)結(jié)構(gòu)，我希望他們能用stl框架來把這些數(shù)據(jù)結(jié)構(gòu)變成通用的。
?? （譯者注：上面所提到的各種數(shù)據(jù)結(jié)構(gòu)我以為大多并非急需，而一個(gè)stl沒有提供而又是真正重要的數(shù)據(jù)結(jié)構(gòu)是哈希結(jié)構(gòu)。后來在stepanov和matt austern等人的sgi*stl中增補(bǔ)了hashset，hashmap和hashtable三種容器，使得這個(gè)stl實(shí)現(xiàn)才比較完滿。眾所周知，紅黑樹的時(shí)間復(fù)雜度為o(logn), 而理想hash結(jié)構(gòu)為o(1)。當(dāng)然，如果實(shí)現(xiàn)了持久化，b+樹也是必須的。）
q：有沒有編譯器廠商跟您一起工作來把stl集成到他們的產(chǎn)品中去？
a：是的，我接到了很多廠家的電話。borland公司的peter becker出的力特別大。他幫助我實(shí)現(xiàn)了對應(yīng)borland編譯器的所有內(nèi)存模式的allocator組件。symantec打算為他們的macintosh編譯器提供一個(gè)stl實(shí)現(xiàn)。edison設(shè)計(jì)集團(tuán)也很有幫助。我們從大多數(shù)編譯器廠商都得到了幫助。
?? （譯者注：以目前的stl版本來看，最出色的無疑是sgi*stl和ibm stl for as/390，所有windows下的的stl實(shí)現(xiàn)都不令人滿意。根據(jù)測試數(shù)據(jù)，windows下最好的stl運(yùn)行在piii 500mhz上的速度遠(yuǎn)遠(yuǎn)落后與在250mhz sgi工作站（irix操作系統(tǒng)）上運(yùn)行的sgi*stl。以我個(gè)人經(jīng)驗(yàn)，linux也是運(yùn)行stl的極佳平臺。而在windows的stl實(shí)現(xiàn)中，又以borland c++builder的rogue wave stl為最差，其效率甚至低于jit執(zhí)行方式下的java2。visual c++中的stl是著名大師p. j. plauger的個(gè)人作品，性能較好，但其queue組件效率很差，慎用）
q：stl包括了對ms-dos的16位內(nèi)存模式編譯器的支持，不過當(dāng)前的重點(diǎn)顯然是在32位上線性內(nèi)存模式(flat model)的操作系統(tǒng)和編譯器上。您覺得這種面向內(nèi)存模式的方案以后還會有效嗎？
a：拋開intel的體系結(jié)構(gòu)不談，內(nèi)存模式是一個(gè)對象，封裝了有關(guān)指針的信息：這個(gè)指針的整型尺寸和距離類型是什么，相關(guān)的引用類型是什么，等等。如果我們想利用各種內(nèi)存，比如持久性內(nèi)存，共享內(nèi)存等等，抽象化的工作就非常重要了。stl的一個(gè)很漂亮的特性是整個(gè)庫中唯一與機(jī)器類型相關(guān)的部分——代表真實(shí)指針，真實(shí)引用的組件——被封裝到大約16行代碼里，其他的一切，容器、算法等等，都與機(jī)器無關(guān)（真是牛啊！）。從移植的觀點(diǎn)看，所有及其相關(guān)的東西，象是地址記法，指針等，都被封裝到一個(gè)微小的，很好理解的機(jī)制里面。這樣一來，allocator對于stl而言就不是那么重要了，至少不像對于基本數(shù)據(jù)結(jié)構(gòu)和算法的分解那么重要。
q：ansi/iso c標(biāo)準(zhǔn)委員會認(rèn)為像內(nèi)存模式這類問題是平臺相關(guān)的，沒有對此做出什么具體規(guī)定。c++委員會會不會采取不同的態(tài)度？為什么？
a：我認(rèn)為stl在內(nèi)存模式這一點(diǎn)上跟c++標(biāo)準(zhǔn)相比是超前的。但是在c和c++之間有著顯著的不同。c++有構(gòu)造函數(shù)和new操作符來對付內(nèi)存模式問題，而且它們是語言的一部分。現(xiàn)在看來似乎讓new操作符像stl容器使用allocater那樣來工作是很有意義的。不過現(xiàn)在對問題的重要性不像stl出現(xiàn)之前那么顯著了，因?yàn)樵诖蠖鄶?shù)場合，stl數(shù)據(jù)結(jié)構(gòu)將讓new失業(yè)。大部分人不再需要分配一個(gè)數(shù)組，因?yàn)閟tl在做這類事情上更為高效。要知道我對效率的迷信是無以復(fù)加的，可我在我的代碼里從不使用new，匯編代碼表明其效率比使用new時(shí)更高。隨著stl的廣泛使用，new會逐漸淡出江湖。而且stl永遠(yuǎn)都會記住回收內(nèi)存，因?yàn)楫?dāng)一個(gè)容器，比如vector退出作用域時(shí)，它的析構(gòu)函數(shù)被調(diào)用，會把容器里的所有東西都析構(gòu)。你也不必再擔(dān)心內(nèi)存泄漏了。stl可以戲劇性地降低對于垃圾收集機(jī)制的需求。使用stl容器，你可以為所欲為，不用關(guān)心內(nèi)存的管理，自有stl構(gòu)造函數(shù)和析構(gòu)函數(shù)來對付。
q：c++標(biāo)準(zhǔn)庫子委員會正在制訂標(biāo)準(zhǔn)名空間（namespace）和異常處理機(jī)制。stl類會有名空間嗎，會拋出異
常嗎？
a：是的。該委員會的幾個(gè)成員正在考慮這件事，他們的工作非常卓越。
q：現(xiàn)在的stl跟最終作為標(biāo)準(zhǔn)的stl會有多大不同？委員會會不會干預(yù)某些變化，新的設(shè)計(jì)會不會被嚴(yán)格地控
制起來？
a：多數(shù)人的意見看起來是不希望對stl做任何重要的改變。
q：在成為標(biāo)準(zhǔn)之前，程序員們怎樣的一些stl經(jīng)驗(yàn)？
a：他們可以從butler.hpl.hp.com/stl當(dāng)下stl頭文件，在borland和ibm或其他足夠強(qiáng)勁的的編譯器中使用它。學(xué)習(xí)這種編程技術(shù)的唯一途徑是編程，看看范例，試著用這種技術(shù)來編程。
q：您正在和p. j. plauger合作一本stl的書。那本書的重點(diǎn)是什么？什么時(shí)候面世？
a：計(jì)劃95年夏天面世，重點(diǎn)是對stl實(shí)現(xiàn)技術(shù)的詳解，跟他那本標(biāo)準(zhǔn)c庫實(shí)現(xiàn)和標(biāo)準(zhǔn)c++庫實(shí)現(xiàn)的書類似。他是
這本書的第一作者。該書可以作為stl的參考手冊。我希望跟bjarne合作另寫一本書，在c++/stl背景下介紹語言與庫的交互作用。
?? 好多工作都等著要做。為了stl的成功，人們需要對這種編程技術(shù)進(jìn)行更多的試驗(yàn)性研究，更多的文章和書籍應(yīng)該對此提供幫助。要準(zhǔn)備開設(shè)此類課程，寫一些入門指南，開發(fā)一些工具幫助人們漫游stl庫。stl是一個(gè)
框架，應(yīng)該有好的工具來幫助使用這個(gè)框架。
?? （譯者注：他說這番話時(shí)，并沒有預(yù)計(jì)到在接下來的幾年里會發(fā)生什么。由于internet的大爆炸和java、vb、delphi等語言的巨大成功，工業(yè)界的重心一下子從經(jīng)典的軟件工程領(lǐng)域轉(zhuǎn)移到internet上。再加上標(biāo)準(zhǔn)c++直到98年才制訂，完全符合要求的編譯器直到現(xiàn)在都還沒有出現(xiàn)，stl并沒有立刻成為人們心中的關(guān)注焦點(diǎn)。他提到的那本書也遲遲不能問世，直到前幾天（2001年元旦之后），這本眾人久已期盼的書終于問世，由p. j. plauger, alexander stepanov, meng lee, david musser四大高手聯(lián)手奉獻(xiàn)，prentice hall出版。不過該書主要關(guān)注的是stl的實(shí)現(xiàn)技術(shù)，不適用于普通程序員。
???? 另外就p. j. plauger做一個(gè)簡介：其人是標(biāo)準(zhǔn)c中stdio庫的早期實(shí)現(xiàn)者之一，91年的一本關(guān)于標(biāo)準(zhǔn)c庫的書使他名滿天下。他現(xiàn)在是c/c++ use's journal的主編，與microsoft保持著良好的，甚至是過分親密的關(guān)系，visual c++中的stl和其他的一些內(nèi)容就是出自他的那只生花妙筆。不過由于跟ms的關(guān)系已經(jīng)影響到了他的中立形象，現(xiàn)在有不少人對他有意見。
???? 至于stepanov想象中的那本與stroustrup的書，起碼目前是沒聽說。其實(shí)這兩位都是典型的編程圣手，跟ken thompson和dennis ritchie是一路的，懶得親自寫書，往往做個(gè)第二作者。如果作為第一作者，寫出來的書肯定是學(xué)院味十足，跟標(biāo)準(zhǔn)文件似的，不適合一般程序員閱讀。在計(jì)算機(jī)科學(xué)領(lǐng)域，編程圣手同時(shí)又是寫作高手的人是鳳毛麟角，最著名的可能是外星人d. e. knuth, c++領(lǐng)域里則首推前面提到的andrew koenig。可惜我們中國程序員無緣看到他的書。）
q：通用編程跟oop之間有什么關(guān)系？
a：一句話，通用編程是oop基本思想的自然延續(xù)。什么是oop的基本思想呢？把組件的實(shí)現(xiàn)和接口分開，并且讓組件具有多態(tài)性。不過，兩者還是有根本的不同。oop強(qiáng)調(diào)在程序構(gòu)造中語言要素的語法。你必須得繼承，使用類，使用對象，對象傳遞消息。gp不關(guān)心你繼承或是不繼承，它的開端是分析產(chǎn)品的分類，有些什么種類，他們的行為如何。就是說，兩件東西相等意味著什么？怎樣正確地定義相等操作？不單單是相等操作那么簡單，你往深處分析就會發(fā)現(xiàn)“相等”這個(gè)一般觀念意味著兩個(gè)對象部分，或者至少基本部分是相等的，據(jù)此我們就可以有一個(gè)通用的相等操作。再說對象的種類。假設(shè)存在一個(gè)順序序列和一組對于順序序列的操作。那么這些操作的語義是什么？從復(fù)雜度權(quán)衡的角度看，我們應(yīng)該向用戶提供什么樣的順序序列？該種序列上存在那些操作？那種排序是我們需要的？只有對這些組件的概念型分類搞清楚了，我們才能提到實(shí)現(xiàn)的問題：使用模板、繼承還是宏？使用什么語言和技術(shù)？gp的基本觀點(diǎn)是把抽象的軟件組件和它們的行為用標(biāo)準(zhǔn)的分類學(xué)分類，出發(fā)點(diǎn)就是要建造真實(shí)的、高效的和不取決于語言的算法和數(shù)據(jù)結(jié)構(gòu)。當(dāng)然最終的載體還是語言，沒有語言沒法編程。stl使用c++，你也可以用ada來實(shí)現(xiàn)，用其他的語言來實(shí)現(xiàn)也行，結(jié)果會有所不同，但基本的東西是一樣的。到處都要用到二分查找和排序，而這就是人們正在做的。對于容器的語義，不同的語言會帶來輕微的不同。但是基本的區(qū)別很清楚是gp所依存的語義，以及語義分解。例如，我們決定需要一個(gè)組件swap，然后指出這個(gè)組件在不同的語言中如果工作。顯然重點(diǎn)是語義以及語義分類。而oop所強(qiáng)調(diào)的（我認(rèn)為是過分強(qiáng)調(diào)的）是清楚的定義類之間的層次關(guān)系。oop告訴了你如何建立層次關(guān)系，卻沒有告訴你這些關(guān)系的實(shí)質(zhì)。
?? （這段不太好理解，有一些術(shù)語可能要過一段時(shí)間才會有合適的中文翻譯——譯者）
q：您對stl和gp的未來怎么看?
a：我剛才提到過，程序員們的夢想是擁有一個(gè)標(biāo)準(zhǔn)的組件倉庫，其中的組件都具有良好的、易于理解的和標(biāo)準(zhǔn)的接口。為了達(dá)成這一點(diǎn)，gp需要有一門專門的科學(xué)來作為基礎(chǔ)和支柱。stl在某種程度上開始了這項(xiàng)工作，它對于某些基本的組件進(jìn)行了語義上的分類。我們要在這上面下更多的功夫，目標(biāo)是要將軟件工程從一種手工藝技術(shù)轉(zhuǎn)化為工程學(xué)科。這需要一門對于基本概念的分類學(xué)，以及一些關(guān)于這些基本概念的定理，這些定理必須是容易理解和掌握的，每一個(gè)程序員即使不能很清楚的知道這些定理，也能正確地使用它。很多人根本不知道交換律，但只要上過學(xué)的人都知道2+5等于5+2。我希望所有的程序員都能學(xué)習(xí)一些基本的語義屬性和基本操作：賦值意味著什么？相等意味著什么？怎樣建立數(shù)據(jù)結(jié)構(gòu)，等等。
?? 當(dāng)前，c++是gp的最佳載體。我試過其他的語言，最后還是c++最理想地達(dá)成了抽象和高效的統(tǒng)一。但是我覺得可能設(shè)計(jì)出一種語言，基于c和很多c++的卓越思想，而又更適合于gp。它沒有c++的一些缺陷，特別是不會像c++一樣龐大。stl處理的東西是概念，什么是迭代子，不是類，不是類型，是概念。說得更正式一些，這是bourbaki所說的結(jié)構(gòu)類型（structure type），是邏輯學(xué)家所說的理念（theory），或是類型理論學(xué)派的人所說的種類（sort），這種東西在c++里沒有語言層面上的對應(yīng)物（原文是incarnation，直譯為肉身——譯者），但是可以有。你可以擁有一種語言，使用它你可以探討概念，精化概念，最終用一種非常“程序化”（programmatic，直譯為節(jié)目的，在這里是指符合程序員習(xí)慣的——譯者）的手段把它們轉(zhuǎn)化為類。當(dāng)然確實(shí)有一些語言能處理種類（sorts），但是當(dāng)你想排序（sort）時(shí)它們沒什么用處。我們能夠有一種語言，用它我們能定義叫做foward iterator（前向迭代子）的東西，在stl里這是個(gè)概念，沒有c++對應(yīng)物。然后我們可以從forword iterator中發(fā)展出bidirectional iterator（雙向迭代子），再發(fā)展出random iterator。可能設(shè)計(jì)一種語言大為簡化gp，我完全相信該語言足夠高效，其機(jī)器模型與c/c++充分接近。我完全相信能夠設(shè)計(jì)出一種語言，一方面盡可能地靠近機(jī)器層面以達(dá)成絕對的高效，另一方面能夠處理非常抽象化的實(shí)體。我認(rèn)為該語言的抽象性能夠超過c++，同時(shí)又與底層的機(jī)器之間契合得天衣無縫。我認(rèn)為gp會影響到語言的研究方向，我們會有適于gp的實(shí)用語言。從這些話中你應(yīng)該能猜出我下一步的計(jì)劃。
mengyan
譯于2001年1月