标準模闆庫

标準模闆庫

惠普實驗室所開發軟件統稱
标準模闆庫(Standard Template Library,STL)是惠普實驗室開發的一系列軟件的統稱。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普實驗室工作時所開發出來的。雖說它主要表出現到C++中,但在被引入C++之前該技術就已經存在了很長時間。STL的代碼從廣義上講分為三類:algorithm(算法)、container(容器)和iterator(叠代器),幾乎所有的代碼都采用了模闆類和模闆函數的方式,這相比于傳統的由函數和類組成的庫來說提供了更好的代碼重用機會。[1]
  • 中文名:标準模闆庫
  • 外文名:Standard Template Library
  • 别名:
  • 解釋:開發的一系列軟件的統稱
  • 惠普實驗室:惠普實驗室
  • 縮寫:STL

簡介

标準模闆庫是一個C++軟件庫,大量影響了C++标準程序庫但并非是其的一部分。其中包含4個組件,分别為算法、容器、函數、叠代器。

模闆是C++程序設計語言中的一個重要特征,而标準模闆庫正是基于此特征。标準模闆庫使得C++編程語言在有了同Java一樣強大的類庫的同時,保有了更大的可擴展性。

在C++标準中,STL被組織為下面的13個頭文件:

曆史

标準模闆庫系由Alexander Stepanov創造于1979年前後,這也正是比雅尼·斯特勞斯特魯普創造C++的年代。

雖然David R. Musser于1971年開始即在計算機幾何領域發展并倡導某些泛型程序設計觀念,但早期并沒有任何編程語言支持泛型程序設計。第一個支持泛型概念的語言是Ada。Alex和Musser曾于1987開發出一套相關的Ada library.

标準模闆庫設計人Stepanov早期從事教育工作,1970年代研究泛型程序設計,那時他與其同事一起在GE公司開發出一個新的程序語言——Tecton。

1983年,Stepanov先生轉至Polytechnic大學教書,繼續研究泛型程序設計,同時寫了許多Scheme的程序,應用在graph與network的算法上,1985年又轉至GE公司專門教授高階程序設計,并将graph與network的Scheme程序,改用Ada寫,用了Ada以後,他發現到一個動态(dynamically)類型的程序(如Scheme)與強制(strongly)類型的程序(如Ada)有多麼的不同。

在動态類型的程序中,所有類型都可以自由的轉換成别的類型,而強制類型的程序卻不能。但是,強制類型在出錯時較容易發現程序錯誤。

1988年Stepanov先生轉至HP公司運行開發泛型程序庫的工作。此時,他已經認識C語言中指針(pointer)的威力,他表示一個程序員隻要有些許硬件知識,就很容易接受C語言中指針的觀念,同時也了解到C語言的所有數據結構均可以指針間接表示,這點是C與Ada、Scheme的最大不同。

Stepanov并認為,雖然C++中的繼承功能可以表示泛型設計,但終究有個限制。雖然可以在基礎類型(superclass)定義算法和接口,但不可能要求所有對象皆是繼承這些,而且龐大的繼承體系将減低虛拟(virtual)函數的運行效率,這便違反的前面所說的“效率”原則。

到了C++模闆觀念,Stepanov參加了許多有關的研讨會,與C++之父Bjarne讨論模闆的設計細節。如,Stepanov認為C++的函數模闆(function template)應該像Ada一樣,在聲明其函數原型後,應該顯式的聲明一個函數模闆之實例(instance);Bjarne則不然,他認為可以通過C++的重載(overloading)功能來表達。

Stepanov想像中的函數模闆:

 in *.hpp

   template

   T square(T x) { return x*x; }

   in *.cpp

   double square(double);

   cout << square(3.3);

   int square(int);

   cout << square(3);

Bjarne認為的函數模闆:

  in *.hpp

   template

   T square(T x) { return x*x; }

   in *.cpp

   cout << square(3.3);

   cout << square(3);

幾經争辯,Stepanov發現Bjarne是對的(引用侯俊傑《标準模闆庫講座·第三章》)。事後Stepanov回想起來非常同意Bjarne的作法。

template 引數推導機制(arguments deduction ,在标準模闆庫中占非常重要的角色。Alexander Stepanov(标準模闆庫創造者)在與Dr. Dobb's Journal進行的訪談中說道‘1992 我重回generic-library的開發工作。這時候C++有了template

“我發現Bjarne完成了一個非常美妙的設計。之前我在Bell Lab曾參與數次template的相關設計讨論,并且非常粗暴地要求Bjarne應該将C++ template設計得盡可能像Ada generics那樣。我想由于我的争辯是如此地粗暴,他決定反對。我了解到在C++中除了擁有template classes之外還擁有template functions的重要性。然而我認為template function應該像Ada generics一樣,也就是說它們應該是顯式實例,Bjarne沒有聽進我的話,他設計了一個template function機制,其中的template是以一個重載化機制 (overloading mechanism來進行隐式實例這項特殊的技術對我的工作具有關鍵性的影響,因為我發現它使我得以完成Ada不可能完成的許多動作。我非常高興Bjarne當初沒有聽我的意見。’(DDJ 1995 年三月号)”

事實上,C++的模闆,本身即是一套複雜的宏語言(macro language),宏語言最大的特色為:所有工作在編譯時期就已完成。顯式的聲明函數模闆之實例,與直接通過C++的重載功能隐式聲明,結果一樣,并無很大區别,隻是前者加重程序員的負擔,使得程序變得累贅。

1992年Meng Lee加入Alex的項目,成為另一位主要貢獻者。

1992年,HP泛型程序庫項目結束,小組解散,隻剩下Stepanov先生與Meng Lee小姐(她是東方人,标準模闆庫的英文名稱其實是取STepanov與Lee而來),Lee先前研究的是編譯器的制作,對C++的模闆很熟,第一版的标準模闆庫中許多程序都是Lee的傑作。

1993年,Andy Koenig到史丹佛演講,Stepanov便向他介紹标準模闆庫,Koenig聽後,随即邀請Stepanov參加1993年11月的ANSI/ISO C++标準化會議,并發表演講。

Bell實驗室的Andrew Koenig于1993年知道标準模闆庫研究計劃後,邀請Alex于是年11月的ANSI/ISO C++标準委員會會議上展示其觀念。并獲得與會者熱烈的回應。

1994年1月6日,Koenig寄封電子郵件給Stepanov,表示如果Stepanov願意将标準模闆庫的幫助文檔撰寫齊全,在1月25日前提出,便可能成為标準C++的一部分。Stepanov回信道:"Andy, are you crazy?" 。 Koenig便說:"Well, yes I am crazy,but why not try it?"。

Alex于是在次年夏天在Waterloo舉行的會議前完成其正式的提案,并以百分之八十壓倒性多數,一舉讓這個巨大的計劃成為C++ Standard的一部分。

标準模闆庫于1994年2月年正式成為ANSI/ISO C++的一部分,它的出現,促使C++程序員的思維方式更朝向泛型編程(generic program)發展。

内容

STL 将“在數據上執行的操作”與“要執行操作的數據分開”,分别以如下概念指代:

容器:包含、放置數據的地方。

叠代器:在容器中指出一個位置、或成對使用以劃定一個區域,用來限定操作所涉及到的數據範圍。

算法:要執行的操作。

标準模闆庫包含了序列容器(sequence containers)與關系容器(associative containers)。

序列容器包括vector,list,forward_list,deque和array等。

關聯容器包括set,multiset,map,multimap,unordered_set,bitset和valarray等。

叠代器

STL 将“在數據上執行的操作”與“要執行操作的數據分開”,分别以如下概念指代:

容器:包含、放置數據的地方。

叠代器:在容器中指出一個位置、或成對使用以劃定一個區域,用來限定操作所涉及到的數據範圍。

算法:要執行的操作。

标準模闆庫包含了序列容器(sequence containers)與關系容器(associative containers)。

序列容器包括vector,list,forward_list,deque和array等。

關聯容器包括set,multiset,map,multimap,unordered_set,bitset和valarray等。

算法

STL提供了一些常見 的算法,如排序和搜索等。這些算法與數據結構的實現進行了分離。因此,用于也可對自定義的數據結構使用這些算法,隻需讓這些自定義的數據結構擁有算法所預期的叠代器。

函數對象

狹義的函數對象即重載了操作符()的類的實例,而廣義來講所有可用 x(...) 形式調用的 x 都可稱為函數對象、或曰可調用對象。

适配器

适配器(Adaptor)為一個模闆類,用于提供接口映射。

與C++标準程序庫的差異

一個常見的誤解是STL是C++标準程序庫的一部分,但事實上并非如此。例如hash table的數據結構實當前STL中有模闆可供調用,但C++标準程序庫一直到C++11才加入了

上一篇:SSL安全協議

下一篇:多模光纖收發器

相關詞條

相關搜索

其它詞條