标准模板库
维基百科，自由的百科全书
标准模板库（STL，即Standard Template Library），是一个C++软件库，也是C++標準程式庫的一部分。
模板是C++程序设计语言的一个比较新的重要特征，而标准模板库（STL）正是基于此特征。标准模板库（STL）使得C++编程语言在有了同Java一样强大的类库的同时，保有了更大的可扩展性。
目录 |
[编辑] 歷史
STL 係由 Alexander Stepanov 創造於 1979 年前後，這也正是Bjarne Stroustrup創造 C++ 的年代。
雖然David R. Musser 於 1971 開始即在計算機幾何領域發展並倡導某些泛型程式設計觀念，但早期並沒有任何程式語言支援泛型程式設計。第一個支援泛型概念的語言是Ada Alex 和 Musser 曾於 1987 開發出一套相關的 Ada library.
STL之設計人——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 語言中指標的威力，他表示一個程式師只要有些許硬體概念，就很容易接受C語言中指標的觀念，同時也瞭解到C語言的所有資料結構均可以指標間接表示，這點是C與Ada、Scheme的最大不同.
Steepanov 並認為，雖然C++ 中的繼承功能可以表示通用型設計，但終究有個限制。雖然可以在基礎類別(superclass)定義演算法和介面，但不可能要求所有物件皆是繼承這些，而且龐大的繼承體系將減低虛擬(virtual) 函數的執行效率，這便違反的前面所說的「效率」原則.
到了C++樣版觀念，Stepanov參加了許多有關的研討會，與C++之父Bjarne討論樣版的製作細節。如，Stepanov認為C++ 的函數樣版(function template) 應該像Ada一樣，在宣告其函數原型後，應該明顯產生一個函數例元(instance)；Bjarne則不然，他認為可以透過C++的多載(overloading)功能來表達。
Stepanov想像中的函數樣版
in *.hpp
template<class T>
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<class T>
T square(T x) { return x*x; }
in *.cpp
cout << square(3.3);
cout << square(3);
幾經爭辯，Stepanov發現Bjarne是對的（參考侯俊傑〈STL講座·第三章〉）。事後Stepanov回想起來非常同意Bjarne的作法。
| “ | template 引數推導機制（arguments deduction ，在 STL中佔非常重要的角色。Alexander Stepanov（STL 的創造者）在與 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 一樣，也就是說它們應該 是 explicit instantiatedBjarne沒有聽進我的話，他設計了一個 template function 機制，其中的 template 是以一個多載化機制 （overloading mechanism 來進行implicitly instantiated這項特殊的技術對我的工作具有關鍵性的影響，因為我發現它使我得以完成Ada不可能完成的許多動作。我非常高 興 Bjarne當初沒有聽我的意見。』（DDJ 1995 年三月號） |
” |
事實上，C++的樣版，本身即是一套複雜的巨集語言(macro language)，巨集語言最大的特色為：所有工作在編譯時期就已完成。明顯的宣告函數樣版之例元，與直接透過C++的多載功能隱含宣告，結果一樣，並無很大區別，只是前者加重程式師的負擔，使得程式變得累贅。
1992年 Meng Lee 加入 Alex 的專案，成為另一位主要貢獻者。
1992年，HP通用型程式庫計畫結束，小組解散，只剩下Stepanov先生與Meng Lee小姐（她是東方人，STL的名稱其實是取STepanov與Lee而來），Lee 先前研究的是編譯器的製作，對C++的樣版很熟，第一版的STL中許多程式都是Lee的傑作。
1993年，Andy Koenig到史丹福演講，Stepanov便向他介紹STL，Koenig聽後，隨即邀請Stepanov參加1993年11月的ANSI/ISO C++標準化會議，並發表演講。
Bell 實驗室的 Andrew Koenig 於1993年知道STL 研究計劃後，邀請 Alex 於是年11月的ANSI/ISO C++標準委員會會議上展示其觀念。並獲得與會者熱烈的迴應。
1994年1月6日，Koenig寄封電子郵件給Stepanov，表示如果Stepanov願意將STL的說明文件撰寫齊全，在1月25日前提出，便可能成為標準C++的一部份。Stepanov回信道："Andy, are you crazy?" 。 Koenig便說："Well, yes I am crazy,but why not try it?"。
Alex 於是在次年夏天在Waterloo 舉行的會議前完成其正式的提案，並以百分之八十壓倒性多數，一舉讓這個巨大的計劃成為 C++ Standard的一部份。
STL 於1994年2月年正式成為ANSI/ISO C++的一部份，它的出現，促使C++程式師的思維方式更朝向通用型程式(generic program)發展.
[编辑] 內容
[编辑] 容器
STL 包含了序列容器（sequence containers）與關聯容器（associative containers）。 序列容器包含了 vector, deque 和 list。至於關聯容器則有 set, multiset, map 和 multimap。
| 資料容器 | 描述 | |
|---|---|---|
| 有序 / Lists - 有序集 | ||
| vector | C++提供了內建陣列的替代型態vector，vector 可以如同陣列一樣的存取方式，例如使用下標（Subscript）運算子，並記得自己的長度資訊（size），您也可以使用物件的方式來存取vector（push、pop）。使用vector可以輕易地定義二維可調整型陣列。要使用vector，必須含入vector表頭檔。 | |
| list | list容器是一個有序（Ordered）的資料結構（循序容器），其特性主要是實作串列資料結構。具有雙向鏈結作用。 | |
| deque (双端队列) | a vector with insertion/erase at the beginning or end in amortized constant time, however lacking some guarantees on iterator validity after altering the deque. | |
| Associative containers - 无序集 | ||
| set | a sorted set; inserting/erasing elements in a set does not invalidate iterators pointing in the set. Provides set operations union, intersection, difference, symmetric difference and test of inclusion. Type of data must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree. |
|
| multiset | 跟set具有相同功能，但允許重複的元素。 | |
| map | a sorted associative array; allows mapping from one data item (a key) to another (a value). Type of key must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree. |
|
| multimap | 跟map具有相同功能，但允許重複的鍵值。 | |
| hash_set hash_multiset |
similar as a set, multiset, map, or multimap, respectively, but implemented using a hash table; keys are not sorted, but a hash function must exist for key type. These containers are not part of the C++ Standard Library, but are included in SGI's STL extensions, and are included in common libraries such as the GNU C++ Library in the __gnu_cxx namespace. They may be included in future extensions of the C++ standard.
|
|
| 其他类型的容器 | ||
| bitset | stores series of bits similar to a fixed-sized vector of bools. Also optimizes for space | |
| valarray | another C-like array like vector, but is designed for high speed numerics at the expense of some programming ease and general purpose use. It has many features that make it ideally suited for use with vector processors in traditional vector supercomputers and SIMD units in consumer-level scalar processors, and also ease vector mathematics programming even in scalar computers. | |
[编辑] 参见
[编辑] 外部連結
- C/C++ reference includes a section on the STL
- STL programmer's guide official guide from SGI
- Bjarne Stroustrup on The emergence of the STL (Page 5, Section 3.1)
- Apache stdcxx portable Open Source implementation based on Rogue Wave STL
- STLport multiplatform STL implementation
- Dinkumware commercial STL implementation (ships with Visual C++ and several other compilers)
- Rogue Wave STL Class Reference
- MPTL shared-memory parallel extension of the STL using the Native POSIX Thread Library.
- STXXL: an STL implementation for external memory.
- STLSoft libraries: open-source, 100% header-only, C/C++ libraries of technology-specific facades and STL extensions.
