STL標(biāo)著兩個人的名字:Stepanov和Lee. 我們寫了一個龐大的庫, 龐大的代碼量, 龐大的數(shù)據(jù)結(jié)構(gòu)組件,
   函數(shù)對象, 適配器類, 等等. 可是雖然有很多代碼, 卻沒有文檔. 我們的工作被認(rèn)為是一個驗(yàn)證性項目,
   其目的是搞清楚到底能不能在使算法盡可能通用化的前提下仍然具有很高的效率. 我們化了很多時間來
   比較, 結(jié)果發(fā)現(xiàn), 我們算法不僅最通用, 而且要率與手寫代碼一樣高效, 這種程序設(shè)計風(fēng)格在性能上是
   不打折扣的! 這個庫在不斷成長, 但是很難說它是什么時候成為一個"項目"的. STL的誕生是好幾件事情
   的機(jī)緣巧合才促成的.
Q: 什么時候, 什么原因促使您決定建議使STL成為ANSI/ISO標(biāo)準(zhǔn)C++一部分的?
A: 1993年夏, Andy Koenig跑到斯坦福來講C++課, 我把一些有關(guān)的材料給他看, 我想他當(dāng)時確實(shí)是很興奮.
   他安排我9月到圣何塞給C++標(biāo)準(zhǔn)委員會做一個演講. 我演講的題目是"C++程序設(shè)計的科學(xué)", 講得很理
   論化, 要點(diǎn)是存在一些C++的基本元素所必須遵循的, 有關(guān)基本操作的原則. 我舉了一些例子, 比如構(gòu)
   造函數(shù), 賦值操作, 相等操作. 作為一種語言,  C++沒有什么限制. 你可以用operator==()來做乘法. 
   但是相等操作就應(yīng)該是相等操作. 它要有自反性,  A == A; 它要有對稱性, A == B 則 B == A; 它還
   要有傳遞性. 作為一個數(shù)學(xué)公理, 相等操作對于其他操作是基本的要素. 構(gòu)造函數(shù)和相等操作之間的聯(lián)
   系就有公理性的東西在里邊. 你用拷貝構(gòu)造函數(shù)生成了一個新對象, 那么這個對象和原來那個就應(yīng)該是
   相等的. C++是沒有做強(qiáng)行要求, 但是這是我們都必須遵守這個規(guī)則. 同樣的, 賦值操作也必須產(chǎn)生相等
   的對象. 我展示了一些基本操作的"公理", 還講了一點(diǎn)迭代子(iterator), 以及一些通用算法怎樣利用迭
   代子來工作. 我覺得那是一個兩小時的枯燥演講, 但卻非常受歡迎. 不過我那時并沒有想把這個東西塞在
   標(biāo)準(zhǔn)里, 它畢竟是太過先進(jìn)的編程技術(shù), 大概還不適于出現(xiàn)在現(xiàn)實(shí)世界里, 恐怕那些做實(shí)際工作的人對它
   沒什么興趣.
   我是在9月做這個演講的, 直到次年(1994)月, 我都沒往ANSI標(biāo)準(zhǔn)上動過什么腦筋. 1月6日, 我收到
   Andy Koenig的一封信(他那時是標(biāo)準(zhǔn)文檔項目編輯), 信中說如果我希望STL成為標(biāo)準(zhǔn)庫的一部分, 可以
   在1月25日之前提交一份建議到委員會. 我的答復(fù)是:"Andy, 你發(fā)瘋了嗎?", 他答復(fù)道:"不錯, 是的我
   發(fā)瘋了, 為什么咱們不瘋一次試試看?"
   當(dāng)時我們有很多代碼, 但是沒有文檔, 更沒有正式的建議書. 李小姐和我每星期工作80小時, 終于在
   期限之前寫出一份正式的建議書. 當(dāng)是時也, 只有Andy一個人知道可能會發(fā)生些什么. 他是唯一的支
   持者, 在那段日子里他確實(shí)提供了很多幫助. 我們把建議寄出去了, 然后就是等待. 在寫建議的過程
   中我們做了很多事. 當(dāng)你把一個東西寫下來, 特別是想到你寫的可能會成為標(biāo)準(zhǔn), 你就會發(fā)現(xiàn)設(shè)計中
   的所有紕漏. 寄出標(biāo)準(zhǔn)后,我們不得不一段一段重寫了庫中間的代碼, 以及幾百個組件, 一直到3月份
   圣迭戈會議之前. 然后我們又重新修訂了建議書, 因?yàn)樵谥匦聦懘a的過程中, 我們又發(fā)現(xiàn)建議書中
   間的很多瑕疵.
Q: 您能描述一下當(dāng)時委員會里的爭論嗎? 建議一開始是被支持呢, 還是反對?
A: 我當(dāng)時無法預(yù)料會發(fā)生些什么. 我做了一個報告, 反響很好. 但當(dāng)時有許多反對意見. 主要的意見是:
   這是一份龐大的建議, 而且來得太晚, 前一次會議上已經(jīng)做出決議, 不在接受任何大的建議. 而這個
   東西是有史以來最大的建議, 包括了一大堆新玩藝. 投票的結(jié)果很有趣, 壓倒多數(shù)的意見認(rèn)為應(yīng)對
   建議進(jìn)行再考慮, 并把投票推遲到下次會議, 就是后來眾所周知的滑鐵盧會議.
   Bjarne Stroustrup成了STL的強(qiáng)有力支持者. 很多人都通過建議、更改和修訂的方式給予了幫助。
   Bjarne干脆跑到這來跟我們一起工作了一個禮拜。Andy更是無時無刻的幫助我們。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)時的C++，我們被要求用新的ANSI/ISO C++語言特性重寫STL，這些特性
   中有一些是尚未實(shí)現(xiàn)的。為了正確使用這些新的、未實(shí)現(xiàn)的C++特性，Bjarne和Andy花了無以計數(shù)的
   時間   來幫助我們。
   人們希望容器獨(dú)立于內(nèi)存模式，這有點(diǎn)過分，因?yàn)檎Z言本身并沒有包括內(nèi)存模式。所以我們得要想出
   一些機(jī)制來抽象內(nèi)存模式。在STL的早期版本里，假定容器的容積可以用size_t類型來表示，迭代子
   之間的距離可以用ptrdiff_t來表示。現(xiàn)在我們被告知，你為什么不抽象的定義這些類型？這個要求
   比較高，連語言本身都沒有抽象定義這些類型，而且C/C++數(shù)組還不能被這些類型定義所限定。我們
   發(fā)明了一個機(jī)制稱作"allocator"，封裝了內(nèi)存模式的信息。這各機(jī)制深刻地影響了庫中間的每一個
   組件。你可能疑惑：內(nèi)存模式和算法或者容器類接口有什么關(guān)系？如果你使用size_t這樣的東西，你
   就無法使用 T* 對象，因?yàn)榇嬖诓煌闹羔橆愋?T*, T huge *, 等等)。這樣你就不能使用引用，因
   為內(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è)計。所有的容器類被分成兩種：順序的和關(guān)聯(lián)的，就好像常規(guī)的內(nèi)存和按內(nèi)容尋址的內(nèi)存一般。
   這些容器的語義十分清楚。
   當(dāng)我到滑鐵盧以后，Bjarne用了不少時間來安慰我不要太在意成敗與否，因?yàn)殡m然看上去似乎不會成功，
   但是我們畢竟做到了最好。我們試過了，所以應(yīng)該坦然面對。成功的期望很低。我們估計大部分的意見
   將是反對。但是事實(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被接受之前，有兩個變化影響到了我們修訂STL。其一是模板類增加了包含模板函數(shù)的能力。STL
   廣泛地使用了這個特性來允許你建立各種容納容器的容器。一個單獨(dú)的構(gòu)造函數(shù)就能讓你建立一個能容
   納list或其他容器的的vector。還有一個模板構(gòu)造函數(shù)，從迭代子構(gòu)造容器對象，你可以用一對迭代子
   當(dāng)作參數(shù)傳給它，這對迭代子之間的元素都會被用來構(gòu)造新的容器類對象。另一個STL用到的新特性是
   把模板自身當(dāng)作模板參數(shù)傳給模板類。這項技術(shù)被用在剛剛提到的allocator中。
Q: 那么STL影響了模板機(jī)制嗎？
A: 在弗基山谷的會議中，Bjarne建議給模板增加一個“局部特殊化”(partial specialization)的特性。
   這個特性可以讓很多算法和類效率更高，但也會帶來代碼體積上的問題。我跟Bjarne在這個建議上共同
   研究了一段時間，這個建議就是為了使STL更高效而提出的。我們來解釋一下什么是“局部特殊化”。
   你現(xiàn)在有一個模板函數(shù) swap( T&, T& )，用來交換兩個參數(shù)。但是當(dāng)T是某些特殊的類型參數(shù)時，你想
   做一些特殊的事情。例如對于swap( int&, int& )，你想用一種特別的操作來交換數(shù)據(jù)。這一點(diǎn)在沒有
   局部特殊化機(jī)制的情況下是不可能的。有了局部特殊化機(jī)制，你可以聲明一個模板函數(shù)如下：
   
       template <class T> void swap( vector<T>&, vector<T>& );
   這種形式給vector容器類的swap操作提供了一種特別的辦法。從性能的角度講，這是非常重要的。如果
   你用通用的形式去交換vector，會使用三個賦值操作，vector被復(fù)制三次，時間復(fù)雜度是線性的。然而，
   如果我們有一個局部特殊化的swap版本專門用來交換兩個vector，你可以得到一個時間復(fù)雜度為常數(shù)的，
   非常快的操作，只要移動vector頭部的兩個指針就OK。這能讓vector上的sort算法運(yùn)行得更快。沒有局
   部特殊化，讓某一種特殊的vector，例如vector<int>運(yùn)行得更快的唯一辦法是讓程序員自己定一個特殊
   的swap函數(shù)，這行得通，但是加重了程序員的負(fù)擔(dān)。在大部分情況下，局部特殊化機(jī)制能夠讓算法在某
   些通用類上表現(xiàn)得更高效。你有最通用的swap，不那么通用的swap，更不通用的swap，完全特殊的swap
   這么一系列重載的swap，然后你使用局部特殊化，編譯器會自動找到最接近的那個swap。另一個例子是
   copy。現(xiàn)在我們的copy就是通過迭代子一個一個地拷貝。使用模板特殊化可以定義一個模板函數(shù)：
 template <class T> T** copy( T**, T**, T** );
   這可以用memcpy高效地拷貝一系列指針來實(shí)現(xiàn)，因?yàn)槭侵羔樋截悾覀兛梢圆槐負(fù)?dān)心構(gòu)造對象和析構(gòu)
   對象的開銷。這個模板函數(shù)可以定義一次，然后供整個庫使用，而且用戶不必操心。我們使用局部特殊
   化處理了一些算法。這是個重要的改進(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ù)還要很長時間，
   STL不過是這個過程的起點(diǎn)。
 
   我們最終會對通用的組件有一個標(biāo)準(zhǔn)的分類，這些組件具有精心定義的接口和復(fù)雜度。程序員們將不必
   在微觀層次上編程。你再也不用去寫一個二分查找算法。就是在現(xiàn)在，STL也已經(jīng)提供了好幾個通用的
   二分查找算法，凡是能用二分查找算法的場合，都可以使用這些算法。算法所要求的前提條件很少：你
   只要在代碼里使用它。我希望所有的組件都能有這么一天。我們會有一個標(biāo)準(zhǔn)的分類，人們不用再重復(fù)
   這些工作。
   這就是Douglas McIlroy的夢想，他在1969年關(guān)于“構(gòu)件工廠”的那篇著名文章中所提出來的東西。STL
   就是這種“構(gòu)件工廠”的一個范例。當(dāng)然，還需要有主流的力量介入這種技術(shù)的發(fā)展之中，光靠研究機(jī)
   構(gòu)不行，工業(yè)界應(yīng)該想程序員提供組件和工具，幫助他們找到所需的組件，把組件粘合到一起，然后
   確定復(fù)雜度是否達(dá)到預(yù)期。
Q: STL沒有實(shí)現(xiàn)一個持久化(persistent)對象容器模型。map和multimap似乎是比較好的候選者，它們可以
   把對象按索引存入持久對象數(shù)據(jù)庫。您在此方向上做了什么工作嗎，或者對這類實(shí)現(xiàn)有何評論？
A：很多人都注意到這個問題。STL沒實(shí)現(xiàn)持久化是有理由的。STL在當(dāng)時已經(jīng)是能被接受的最巨大的庫了。
   再大一點(diǎn)的話，我認(rèn)為委員會肯定不會接受。當(dāng)然持久化是確實(shí)是一些人提出的問題。在設(shè)計STL，特別
   是設(shè)計allocator時，Bjarne認(rèn)為這個封裝了內(nèi)存模式的組件可以用來封裝持久性內(nèi)存模式。Bjarne的
   洞察秋毫非常的重要和有趣，好幾個對象數(shù)據(jù)庫公司正在盯著這項技術(shù)。1994年10月我參加了Object
   Database Management Group的一個會議，我做了一個關(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提供了一個很好的框架，可以用來比較這些結(jié)構(gòu)的性能。結(jié)口
   是固定的，基本的復(fù)雜度是固定的，現(xiàn)在我們就可一個對各種數(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)我以為大多并非急需，而一個STL沒有提供而又是真正重要的數(shù)據(jù)
     結(jié)構(gòu)是哈希結(jié)構(gòu)。后來在Stepanov和Matt Austern等人的SGI*STL中增補(bǔ)了hashset，hashmap和
     hashtable三種容器，使得這個STL實(shí)現(xiàn)才比較完滿。眾所周知，紅黑樹的時間復(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編譯器提供一個STL
   實(shí)現(xiàn)。Edison設(shè)計集團(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。以我個人經(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的個人作品，性能較
     好，但其queue組件效率很差，慎用）
Q：STL包括了對MS-DOS的16位內(nèi)存模式編譯器的支持，不過當(dāng)前的重點(diǎn)顯然是在32位上線性內(nèi)存模式
   (flat model)的操作系統(tǒng)和編譯器上。您覺得這種面向內(nèi)存模式的方案以后還會有效嗎？