1.1 STL的理念
那麼什麼是STL呢？到目前為止，它作為标準 C ++的一部分已經快十年了，是以你的确應該知道它，但是如果你不熟悉現代的C++，那麼我就有必要對它的想法和語言使用方式作一些簡單的介紹。
我們來考慮一個問題：把對象存儲在容器中，并編寫算法來操作這些對象。我們按照直接、獨立和概念的混合表現方式來考慮這個問題。自然地，我們希望能夠在多種容器（例如清單、向量、映射）中存儲多種類型（例如整型、Point、Shape）的對象，并在容器中的對象上 應用 大量的算法（例如排序、檢索、積聚）。此外，我們希望使用的這些對象、容器和算法都是靜态類型安全的、盡可能地快速、盡可能地簡潔、不冗長、易于閱讀。同時實作這些目标并不容易。實際上，為了解決這個難題，我差不多花費了十年還是沒有找到成功的方法。
STL解決方案是以帶元素類型的參數化容器以及與容器完全分離的算法為基礎的。容器的每種類型都提供一種疊代子（iterator）類型，隻使用這些疊代子就可以實作對容器中所有元素的通路。通過這種方式，我們可以編寫算法來使用疊代子而不用知道提供疊代子的容器的資訊。每種疊代子類型與其它類型都是完全獨立的，除非要為必要的操作（例如*和++）提供了相同語義（semantics）。我們可以用圖形來說明。
我們來看一個很恰當的例子，它在不同的容器中查找不同類型的元素。首先，下面是兩個容器：
| vector<int> vi; // 整型向量 list<double> vd; // 雙精度型清單 |
目前存在一些向量和清單概念的标準類庫，它們是作為模闆實作的。假如你已經用相應的元素類型值恰當地初始化過它們，那麼在vi中查找第一個值為7的元素和在vd中查找第一個值為3.14的元素的文法如下：
| vector<int>::iterator p = find(vi.begin(),vi.end(),7); list<double>::iterator q = find(vd.begin(),vd.end(),3.14); |
其基本的想法是，你能夠把任何容器的（所有）元素都作為一個元素序列（sequence）。容器"知道"第一個元素在哪兒，最後一個元素在哪兒。我們把指向一個元素的對象稱為"疊代子"。接着我們就可以使用一對疊代子（begin()和end()）來表示容器中的元素，其中begin()指向第一個元素，end()指向最後一個元素前面。
end()疊代子指向最後一個元素後面，而不是指向最後一個元素，這就使空序列不會成為一種特殊情況。
你能對疊代子做什麼樣的操作？你可以得到疊代子指向的元素的值（像指針一樣使用*），可以使疊代子指向下一個元素（像指針一樣使用++），可以比較兩個疊代子，看它們是否指向同一個元素（使用==或!=）。令人驚訝的是，這已經足以實作find()（查找功能）了：
| template<class Iter, class T> Iter find(Iter first, Iter last, const T& val) { while (first!=last && *first!=val) ++first; return first; } |
這是一個簡單的--真的非常簡單的--模闆函數。熟悉C和C++指針的人應該發現這些代碼很容易閱讀的：first!=last檢查我們是否到了序列末尾，*first!=val檢查我們是否找到了值val。如果沒有找到，我們增加first疊代子，使它指向下一個元素并重複。是以，當find()傳回的時候，它的值要麼指向值為val的第一個元素，要麼指向最後一個元素後面（end()）。于是我們可以編寫下面的代碼：
| vector<int>::iterator p = find(vi.begin(),vi.end(),7); if (p != vi.end()) { // 我們找到了 7 // … } else { // vi 中沒有 7 // … } |
這是非常非常簡單的。它簡單得像數學書的前面幾頁，速度也很快。但是，我知道自己不是唯一一個花時間來研究它到底是如何實作的、以及為什麼它是一個好的想法的人。與簡單的數學相似，最初的STL規則和原理的概括也是難以置信的。
考慮第一個實作：在調用find(vi.begin(),vi.end(),7)中，疊代子vi.begin()和vi.end()會相應地成first為last，在find()内部有些東西指向int（整型）、int*。在這樣的實作中，*成為了指針，++成為了指針增加操作符，!=成為了指針比較操作符。也就是說，find()的實作是明顯的、理想的。特别地，我們沒有使用函數調用來通路那些作為運算法則的有效參數的操作符（例如*和!=），因為它們依賴于模闆參數。在這種情況中，模闆與"泛型"的大多數機制從根本上都是不同的，它依賴于目前程式設計語言中的間接函數調用（類似虛拟函數）。如果有一個好的優化程式（optimizer），vector<int>::iterator可以成為一個把*和++作為内建函數（inline function）的、沒有資源花費（overhead）的類。這種優化程式現在很少，它通過捕捉無保證的假設（如下所示）來進行類改善類型檢查。
| int* p = find(vi.begin(),vi.end(),7); // 疊代子類型不能是 int* |
那麼為什麼我們不省去所有的"疊代子材料"和使用指針呢？其中一個原因是vector<int>::iterator可能已經成為了一個提供了範圍檢查通路的類。我們看看find()的其它調用：
| list<double>::iterator q= find(vd.begin(),vd.end(),3.14); if (q != vd.end()) { // 我們找到了3.14 // … } else { // vi 中沒有3.14 // … } |
此處list<double>::iterator不會成為double*。實際上，在最普通的連結清單實作方式中，應該是Link*類型的，其中是連結清單節點類型的，例如：
| template<class T> struct Link { T value; Link* suc; Link* pre; }; |
這意味着，*的意思是p->value（傳回值字段），++的意思是p->suc（使指針指向下一個連結），!=指針比較的意思是（比較Link*s）。同樣，這種實作也是明顯的、理想的。但是，它與我們前面看到的vector<int>::iterator完全不同了。
我們使用了模闆組合（combination）和重載解決方案為find()的單一 源代碼 定義和使用來挑選根本不同的、也是理想的代碼。請注意，這兒不存在運作時分派（dispatch）、沒有虛拟函數調用。實際上，它隻有瑣碎的内聯函數和指針的基本操作（例如*和++）的調用。在速度和代碼大小方面，我們都到取得了很大的成功。
為什麼沒有把"序列"或"容器"作為基本的概念，而使用了"一對疊代子"呢？部分原因在于"一對疊代子"隻不過比"容器"的概念更普通。例如，給定疊代子，我們可以隻對容器的前一半進行排序：sort(vi.begin(), vi.begin()+vi.size()/2)。另一個原因是STL遵循了 C ++的設計原則，我們必須一律地提供轉換（transition）路徑、支援内建的和使用者定義類型。如果某個人把資料儲存在普通的數組中會怎麼樣呢？我們仍然可以使用STL算法。例如：
| char buf[max]; // … 填充buf … int* p = find(buf,buf+max,7); if (p != buf+max) { // 我們找到了 7 // … } else { // buf 中沒有 7 // … } |
此處，find()中的*、++和!=都是指針操作符！與C++本身不同，STL與一些舊的概念（例如C數組）是相容的。我們始終提供轉換路徑，平等地對待使用者定義類型和内建類型（如數組）。
STL像ISO C++标準庫所采用的容器和算法架構一樣，包含一打容器（例如vector、list和 map ）和資料結構（例如數組），它們可以被當作序列使用。此外，還有大約60種算法（例如find、sort、accumulate和merge）。你可以查閱資料看到更詳細的資訊。
STL的優雅和性能的關鍵在于--與C++本身類似--它是基于直接的 記憶體 和計算硬體模型的。STL的序列的概念基本上是把記憶體作為一組對象序列的硬體視點。STL的基本文法直接映射到硬體指令，允許算法最佳地實作。接下來，模闆的編譯時解析和他們支援的完美内聯成為了把STL進階表達式高效率地映射到硬體層的關鍵因素。
1.2 函數對象
我将介紹STL使用的一些基本的技術，它會讓你了解：在普通C++機制上建立的STL是如何提供空前的靈活性和性能的。迄今為止，我們所描述的STL架構元件都有些嚴格。每種算法都嚴格地采用标準指定的方法來準确地實作某種功能。例如，我們需要查找一個與自己指定的值相等的元素。實際上，查找一個帶有某些（自己指定的）屬性的元素，例如小于某個給定的值、比對某個并非簡單相等的值（例如，比對大小寫無關的字元串或者在允許很小差别的情況下，比對雙精度數值），是一項很普通的事務。
下面的例子不是查找值7，我們将查找某些符合條件的值（也就是小于7的值）：
| vector<int>::iterator p = find_if(v.begin(),v.end(),Less_than<int>(7)); if (p != vi.end()) { // 我們找到了值小于7 的元素 // … } else { // vi 沒有值小于 7 的元素 // … } |
Less_than<int>(7)是什麼東西呢？它是一個函數對象，它是某個類的對象，該類帶有 應用 程式操作符（( )），被定義成執行某個函數：
| template<class T> struct Less_than { T value; Less_than(const T& v) :value(v) { } bool operator()(const T& v) const { return v<value; } }; |
例如：
| Less_than<double> f(3.14); // Less_than 儲存了雙精度值 3.14 bool b1 = f(3); // b1 為真（3<3.14 是真的） bool b2 = f(4); // b2 為假（4<3.14 是假的） |
從2004年的情況來看，在D&E中沒有提到函數對象是很奇怪的。我們應該使用一個章節來講述它們。甚至于使用者自定義的應用程式操作符（( )）的使用情況也沒有提到，盡管它已經存在很長時間，并且很卓著。例如，它是幾個最初的允許重載的操作符之一（在=之後），它還用于模仿Fortran下标（subscript notation）。
我們可以編寫一個find()版本，它使用了函數對象，而不是簡單的!=來檢測是否可以找到某個元素。它的名字是find_if()：
| template<class In, class Pred> In find_if(In first, In last, Pred pred) { while (first!=last && !pred(*first)) ++first; return first; } |
我們簡單地用!pred(*first)代替了*first!=val。函數模闆find_if()會接受任何能夠把元素值作為參數調用的對象。特别地，我們可以把普通的函數作為它的第三個參數來調用find_if()：
| bool less_than_7(int a) { return 7<a; } vector<int>::iterator p = find_if(v.begin(),v.end(),less_than_7); |
但是，這個例子顯示了，與函數相比我們為什麼更喜歡函數對象：我們可以使用一個（或多個）參數來初始化函數對象，同時函數對象可以保持這些資訊供以後使用。函數對象可以保持任何狀态。這樣就可以形成更 通用 、更優良的代碼。如果我們需要，我們以後可以檢查它的狀态。例如：
| template<class T> struct Accumulator { // 保持 n 個值的總和 T value; int count; Accumulator() :value(), count(0) { } Accumulator(const T& v) :value(v), count(0) { } void operator()(const T& v) { ++count; value+=v; } }; |
我們可以把Accumulator對象傳遞給一個重複調用它的算法。其部分結果保持在對象中。例如：
| int main() { vector<double> v; double d; while (cin>>d) v.push_back(d); Accumulator<double> ad; ad = for_each(v.begin(),v.end(), ad); cout << "sum==" << ad.value << ", mean==" << ad.value/ad.count << '\n'; } |
标準類庫算法for_each簡單地把它的第三個參數應用在自己序列中的每個元素上，并把這個參數作為傳回值。另一種使用函數對象的方法比較"雜亂"--就是使用全局變量來保持value和count。
有趣的是，簡單的函數對象比功能相同的函數的性能更好。其原因在于它們趨向于按值（by value）傳遞，是以它們更易于内聯（inline）。當我們傳遞那些執行很簡單操作（例如用于排序的比較條件）的對象或函數的時候，這一點是非常重要的。特别地，當對簡單類型（例如整型或雙精度型）的數組進行排序的時候，函數對象的内聯就是STL（C++标準類庫）的sort()在多方面超越了傳統的qsort()原因。
函數對象是用于更進階構造的一種C++機制。它并非進階理念的最好表達方式，但是它在用于普通目的的語言環境中，顯示出令人驚訝的表現能力和固有的高性能。作為表現能力的一個例子，Jaakko J?rvi示範了如何提供和使用一個Lambda類，使它的真正意義合法化：
| Lambda x; List<int>::iterator p = find_if(lst.begin(),lst.end(),x<=7); |
如果你希望 <= 能夠工作，那麼不用建立一個通用類庫，而是為Lambda和<=添加大約十餘行代碼定義。如果使用上面例子中的Less_than，那麼我們可以簡單地添加：
| class Lambda {}; template<class T> Less_than<T> operator<=(Lambda,const T& v) { return Less_than<T>(v); } |
是以，find_if調用中的x<=7參數變成了operator<=(Lambda,const int&)調用，它會生成一個Less_than<int>對象，它就是這一部分中第一個例子所使用的對象。它們之間的差别僅僅是--我們實作了更簡單和直覺的文法。這是C++表現能力的一個很好的例子，也是類庫的接口如何比其實作更加簡單的例子。自然地，與辛苦地編寫一個循環來查找值小于7的元素相比，它是沒有運作時開銷的。
1.3 STL的影響
STL對C++的思想的影響是極大的。在STL之前，我一般列舉C++支援的三種基本的程式設計樣式（"範例"）：
－面向過程程式設計
－資料抽象
－面向對象程式設計
我認為模闆是對資料抽象的支援。在試用了STL一段時間之後，我提出第四種樣式：
－泛型程式設計
以使用模闆為基礎的技術，以及從功能性程式設計中擷取大量靈感的技術與傳統的資料抽象有本質的不同。人們隻是認為類型、對象和資源不同。新的C++類庫是使用模闆技術編寫的，才獲得了靜态類型安全和高效率。模闆技術對于嵌入式系統程式設計和高性能數學運算也是很關鍵的，在這些環境中，資源的管理和正确性是關鍵。在這些領域中STL并非總是理想的。例如，它沒有直接地支援線性代數，而且在緊湊的實時系統中（在這種環境下一般會禁止自由地使用存儲）也很難使用它。但是，STL證明了在模闆的幫助下可以實作什麼樣的功能，并提出了一些有效的技術示例。例如，利用疊代子（和 配置設定器 ）把邏輯 記憶體 通路與實際記憶體通路分離開來，對于很多高性能數字運算就是很關鍵的；使用小型的、簡單的内聯、對象對于嵌入式系統程式設計中最佳地使用硬體也是很關鍵的。這類技術有一些記載在标準委員會關于性能的技術報告中了。這是對目前過度地使用過分依賴于類層次和虛拟函數的"面向對象"技術的這種趨勢的一種大範圍的反擊--也是一種有建設意義的替代方案。
很明顯，STL并不完美。相對來說沒有完美的東西。但是，它開辟了新天地，而且它擁有的影響力甚至于超過了巨大的C++群體。使用C++時，當人們試圖推動STL所倡導的技術來超越STL技術的時候，它們讨論"模闆中繼資料程式設計"。我們中有些人也會考慮STL疊代子的限制（使用generator和range是不是更好？），以及C++如何更好地支援這些使用（概念、初始化器）。
上一頁 1 2