标准模板库

维库，知识与思想的自由文库

标准模板库（STL）英文Standard Template Library的缩写。

模板是C++程序设计语言的一个比较新的重要特征，而标准模板库（STL）正是基于此特征。标准模板库（STL）使得C++编程语言在有了同Java一样强大的类库的同时，保有了更大的可扩展性。

目录 1 歷史 2 內容 2.1 Containers 2.2 Iterators 2.3 Algorithms 2.4 Functors 3 Criticisms 3.1 Quality of compiler 3.2 STL design 4 外部連結

[编辑] 歷史

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)發展.

[编辑] 內容

[编辑] Containers

STL 包含了序列容器（sequence containers）與關聯容器（associative containers）。 序列容器包含了 vector, deque 和 list。至於關聯容器則有 set, multiset, map 和 multimap。

資料容器	描述
Sequences / Lists - ordered collections
vector	C++提供了內建陣列的替代型態vector，vector 可以如同陣列一樣的存取方式，例如使用下標（Subscript）運算子，並記得自己的長度資訊（size），您也可以使用物件的方式來存取vector（push、pop）。使用vector可以輕易地定義二維可調整型陣列。要使用vector，必須含入vector表頭檔。
list	list容器是一個有序（Ordered）的資料結構（循序容器），其特性主要是實作串列資料結構。具有雙向鏈結作用。
deque (double ended queue)	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 - unordered collections
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 hash_map hash_multimap	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.

valarray - Another C-like array like vector, but is designed for high speed numerics at the expense of programming ease. It has many features that make it ideally suited for use with vector processors in traditional vector supercomputers.

[编辑] Iterators

STL 實現了五種迭代子（iterators）。These are input iterators (which can only be used to read a sequence of values), output iterators (which can only be used to write a sequence of values), forward iterators (which can be read, written to, and move forward), bidirectional iterators (which are like forward iterators but can also move backwards) and random access iterators (which can move freely any number of steps in one operation).

It is possible to have bidirectional iterators act like random access iterators, as moving forward ten steps could be done by simply moving forward a step at a time a total of ten times. However, having distinct random access iterators offers efficiency advantages. For example, a vector would have a random access iterator, but a list only a bidirectional iterator.

Iterators are the major feature which allow the generality of the STL. For example, an algorithm to reverse a sequence can be implemented using bidirectional iterators, and then the same implementation can be used on lists, vectors and deques. User-created containers only have to provide an iterator which implements one of the 5 standard iterator interfaces, and all the algorithms provided in the STL can be used on the container.

This generality also comes at a price at times. For example, performing a search on an associative container such as a map or set can be much slower using iterators than by calling member functions offered by the container itself. This is because an associative container's methods can take advantage of knowledge of the internal structure, which is opaque to algorithms using iterators.

[编辑] Algorithms

STL 提供大量的演算法，如排序演算法、搜尋演算法等，這些演算法以單一函數存在（跟物件導向的理念相反），每個演算法函數必須配合迭代器（Iterator）的實現，以期能跟容器（Container）連結在一起。

 std::vector<int> score;
 ...
 std::sort(score.begin(), score.end());

[编辑] Functors

The STL includes classes that overload the function operator (operator()). Classes that do this are called functors or function objects. They are useful for keeping and retrieving state information in functions passed into other functions. Regular function pointers can also be used as functors.

A particularly common type of functor is the predicate. For example, algorithms like find_if take a unary predicate that operates on the elements of a sequence. Algorithms like sort, partial_sort, nth_element and all sorted containers use a binary predicate which must provide a strict weak ordering, that is, it must behave like a membership test on a transitive, irreflexive and antisymmetric binary relation. If none is supplied, these algorithms and containers use less by default, which in turn calls the less-than-operator <.

[编辑] Criticisms

[编辑] Quality of compiler

The Quality of Implementation (QoI) of the C++ compiler has a large impact on usability of STL (and templated code in general):

• Error messages involving templates tend to be very long and difficult to decipher. This problem has been considered so severe that a number of tools have been written which simplify and indent STL-related error messages to make them more comprehensible. A proposal to the new C++ Standard (concept checking) tries to reduce this problem.
• Careless use of STL templates can lead to code bloat. This has been countered with special techniques within STL implementation (using void* containers internally) and by improving optimization techniques used by compilers.
• Template instantiation tends to increase compilation time and memory usage (even by an order of magnitude). Until the compiler technology improves enough this problem can be only partially eliminated by very careful coding and avoiding certain idioms.

[编辑] STL design

1. Design flaws due to limitations in the C++ language

• Initialization of STL containers with constants within the source code is not as easy as data structures inherited from C.

2. Perceived flaws due to the requirement to maximize speed and minimize space usage

• STL containers are not intended to be used as base classes (their destructors are deliberately non-virtual). Deriving from a container is a common mistake made by novices.^{[來源請求]}

3. Other flaws, caused either by trade-offs in design or which have become more visible over time

• The concept of iterators as implemented by STL can be difficult to understand at first: for example, if a value pointed to by the iterator is deleted, the iterator itself is then no longer valid. This is a common source of errors. Most implementations of the STL provide a debug mode which is slower but can locate such errors if used. However, at present no better replacement for iterators has been suggested and a similar problem exists in other languages, for example Java and C#.
• The design of STL allocator (used by the containers) is widely seen as flawed.^{[來源請求]}

• The set of algorithms is not complete — for example, the copy_if algorithm was left out by oversight (Stroustrup, p. 530).
• The interface of some containers (in particular string) is bloated (Sutter and Alexandrescu, p. 79); others are considered insufficient.
• Hashing containers were left out of the original standard, but have been added in Technical Report 1, a recent extension to C++.

[编辑] 外部連結

• 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.