STL演算法

**標準樣板函式庫**（英文：**Standard Template Library**，縮寫：**STL**），是一個 C++ 軟體庫，大量影響了 C++ 標準程式庫但並非是其的一部分。其中包含 4 個組件，分別為演算法、容器、函式、迭代器。

模板是 C++ 程式設計語言中的一個重要特徵，而標準樣板函式庫正是基於此特徵。標準樣板函式庫使得 C++ 程式語言在有了同 Java 一樣強大的類別館的同時，保有了更大的可延伸性。

## 歷史

標準樣板函式庫係由 Alexander Stepanov 創造於 1979 年前後，這也正是比雅尼・斯特勞斯特魯普創造 C++ 的年代。

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

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

1983 年，Stepanov 先生轉至紐約大學坦登工程學院擔任助理教授，繼續研究泛型程式設計，同時寫了許多 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++ 之父比雅尼討論模板的設計細節。如，Stepanov 認為 C++ 的函式模板（function template）應該像 Ada 一樣，在聲明其函式原型後，應該顯式的聲明一個函式模板之實例（instance）；比雅尼則不然，他認為可以透過 C++ 的重載（overloading）功能來表達。

Stepanov 想像中的函式模板：

比雅尼認為的函式模板：

幾經爭辯，Stepanov 發現比雅尼是對的（參考侯俊傑〈標準樣板函式庫講座・第三章〉）。事後 Stepanov 回想起來非常同意比雅尼的作法。

事實上，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 於是在次年夏天在滑鐵盧舉行的會議前完成其正式的提案，並以百分之八十壓倒性多數，一舉讓這個巨大的計劃成為 C++ Standard 的一部份。

標準樣板函式庫於 1994 年 2 月年正式成為 ANSI/ISO C++ 的一部份，它的出現，促使 C++ 程式設計師的思維方式更朝向泛型編程（generic program）發展。

## 內容

STL 將「在資料上執行的操作」與「要執行操作的資料分開」，分別以如下概念指代：

* 容器：包含、放置資料的地方。
* 迭代器：在容器中指出一個位置、或成對使用以劃定一個區域，用來限定操作所涉及到的資料範圍。
* 演算法：要執行的操作。

### 容器

標準樣板函式庫包含了序列容器（sequence containers）與關聯容器（associative containers）。

### 迭代器

迭代器是泛化的指標，通過使用迭代器，開發者可以運算元據結構而無需關心其內部實現。根據迭代器的操作方式的不同，迭代器分為五種：

* 輸入迭代器
* 輸出迭代器
* 前向迭代器
* 雙向迭代器
* 隨機存取迭代器

### 演算法

STL 提供了一些常見 的演算法，如排序和搜尋等。這些演算法與資料結構的實現進行了分離。因此，也可對自訂的資料結構使用這些演算法，只需讓這些自訂的資料結構擁有演算法所預期的迭代器。。

### 函式物件

狹義的函式物件即多載了運算子 () 的類別的實例，而廣義來講所有可用 x (...) 形式呼叫的 x 都可稱為函式物件、或曰可呼叫物件。。

### 配接器（Adaptor）

配接器為一個模板類，用於提供介面對映。。

## 與 C++ 標準程式庫的差異

一個常見的誤解是 STL 是 C++ 標準程式庫的一部分，但事實上並非如此。例如 hash table 的資料結構實作在 STL 中有 <hash\_map> 模板可供調用，但 C++ 標準程式庫一直到 C++11 才加入了 <unordered\_map>。參見無序關聯容器 \_(STL)。

## 參考文獻

## 參見

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