為什么需要ＳＴＬ

容器、迭代器和通用算法是三位一體的概念，下面我們以向量類模板Vector為例[1]，具體闡述它們的必要性。

template＜class T＞

class Vector

{

private:

T *data;//數組指針

int theSize;//數據元素個數

int theMax;//數組長度，即容量

void Error(const char* cs)const {cout＜＜cs＜＜endl; exit(1);} //錯誤信息報告

public:

explicit Vector(int n=0):theSize(0)， theMax(n+SPARE_MAX)

{if(theMax＞0) data=new T[theMax];}

Vector(const Vector v):data(NULL)， theMax(0){operator=(v);}//拷貝構造函數

~Vector(void){delete[]data;}

Vector operator=(const Vector＜T＞ v);//復制賦值函數

T operator[](int id){return(data[id]);}//下標運算符函數

const T operator[](int index)const{return(data[id]);}//常量型下標運算符函數

bool Empty(void)const{return(theSize==0);} //判空

int Size(void)const{return(theSize);}//求數據個數

int Max(void)const{return(theMax);}//求數組容量

void Push_back(const T item);//尾插

void Pop_back(void); //尾刪

const T Back(void)const;//返回尾元素的引用

const T Front(void)const;//返回起始元素的引用

void Reserve(int newMax);//擴大數組容量為newtheMax，保留原來數據

void Resize(int newSize，const T item=T());//把數據個數擴大為newtheSize，原數據保留，

//其余的值初始化為item

enum{SPARE_MAX=16};//枚舉常量表示數組最小長度

};

1容器、迭代器和通用算法

向量類模板是一種容器類。容器類的對象包含一組元素，這組元素又同是一種類的對象。容器類的對象稱為容器。我們學過的數組、基本順序表都是容器類。一個整型數組和一個字符型數組，是數組容器類的兩個對象，即兩個容器，它們的元素類型分別是整型和字符型，因此也稱為整型數組容器和字符型數組容器。容器中的元素依然可以是容器，例如基本順序表數組，其中每一個數組元素都是基本順序表容器。以后我們主要討論類模板形式的容器類，例如向量類模板。

Vector＜char＞ charV;//字符型Vector容器charV

Vector＜Vector＜char＞ ＞ char_V;//Vector容器char_V的元素是字符型Vector容器

一般我們把非容器類型稱為數值類型。整型、實型、字符型、Date類型、String都是數值類型。String之所以不是容器類，是因為它的任何對象所包含的一組元素只能是字符型，不能是其他類型。

有一些算法對每一種容器都是需要的，稱為通用算法。例如，輸出容器中的每一個元素，增加容器中的每一個元素的值，查找容器中最大的元素。假定給出一組數值類型、一組容器類型和一組建立在容器上的通用算法，那么用目前傳統的C++方法開發，軟件的數量將有多少呢？舉例說明：

template＜class T＞

void Display(const Vector＜T＞ c);//輸出向量的元素

從現在看，容器類有多少，Display算法就有多少。可是問題還不只這樣簡單，如果算法是增加容器中的每一個元素的值，那么下面的通用函數就是錯誤的：

template＜class T＞

void Add(Vector＜T＞ c，const T val)//容器中每一個元素值增加val。非法！

為什么呢？一方面，假設給雙浮點型容器的元素增加一個整型值，這時，c是Vector＜double＞型對象，val是int型對象，模板參數T有二義性。而編譯器不會在實例化過程中進行自動類型轉換，因此每個模板參數都必須正確地匹配。另一個方面，容器類元素類型和容器類用戶即客戶端算法的元素類型，像容器和算法一樣，應該具有各自的獨立性。

根據現在的能力，我們解決的辦法只能是具體化一個元素類型：

template＜class T＞

void Add(Vector＜T＞ c，const int val);//具體化參數val的類型

template＜class T＞

void Add(Vector＜T＞ c，const String val); //具體化參數val的類型

或

template＜class T＞

void Add(Vector＜int＞ c，const T val); //具體化參數L的類型

template＜class T＞

void Add(Vector＜String＞ c，const T val);//具體化參數L的類型

現在我們可以計算：假定給出n組數值類型、n組容器類型和n組建立在容器上的通用算法，那么軟件數量將是n×n×n。把這個數量減少至n，是軟件必須發展的基本理由。

新的解決方案是，設立兩個獨立的模板參數。例如：

template＜class Container，class T＞ //用模板參數名稱Container代表容器類

void Add(Container c，const T val);//容器中每一個元素值增加val

下面要解決的問題是，通用算法的實現代碼如何具有通用性。基于容器類的算法，一般都是在遍歷容器元素的過程中實現的，而遍歷的方法一般有兩種，一種是基于下標運算，另一種是基于指針運算。以數組為例：

for(int i=0;i!=size; ++i)//基于下標。size表示數組中的數據元素個數

p[i]=p[i]+val;

或

for(int *p=a[0];p!=a[size];++p)//基于指針。a[size]是最后一個數據元素的后繼指針

*p=*p+val;

下標運算沒有普遍性，因為有的容器類(例如鏈表容器類)可以不支持這種操作。這使得指針成了唯一的選擇。于是問題轉化為，如何使容器的用戶即客戶端的算法具有一個可以指向容器元素的通用指針？引入一個新的語法：

typename Container::iterator itr;

一般來說，這是通用算法中的一條語句，指定itr(用戶自選的標識符)是一個通用類型iterator的指針，指向容器類Container的對象中的元素，通常稱為迭代器或指示器。關鍵字typename不能由class替代。如果Container實例化為一個整型Vector容器，那么itr就是指向該容器的整型元素的指針。如果Container實例化為String型Vector容器，那么itr就是指向該容器的String型元素的指針。這條語句使容器類具有了對通用類型指針iterator的解釋權。為什么必須要由容器類來解釋呢？因為不同的容器類，其元素存儲結構不同(連續存儲或鏈式存儲，線性存儲或非線性存儲)，指向元素的指針運算也不同，例如自增(++)和自減(--)運算，如果是鏈式存儲結構，就需要重載。

一個容器如何具有這種解釋能力呢？一般是通過在容器類內部的聲明來取得這種能力。這個聲明可以是typedef聲明，也可以是類型聲明。以向量類模板Vector為例：

template＜class T＞

class Vector

{

private:

T *data;//數組指針

int theSize;//數組中的數據元素個數

int theMax;//數組容量

void Error(const char* cs)const{cout＜＜cs ＜＜endl;exit(1);}//錯誤信息報告

public:

┄┄

typedef T* iterator;//迭代器類型

typedef const T* const_iterator;//指向const常量的迭代器類型

iterator begin(){return data[0];}//使迭代器指向容器的數據元素起始位置

const_iterator begin()const{return data[0];}

iterator end(){return(data[theSize]);}//使迭代器指向容器結束位置

const_iterator end()const{ return(data[theSize]);}

iterator Insert(iterator itr，const T item); //將元素item插入到指示器itr指向的位置

iterator Erase(iterator itr); //刪除指示器itr指向的元素

};

const_iterator是指向const常量的形式化的迭代器類型，一般供常量型通用算法使用。

每個容器類都必須提供一些起碼的成員函數，以服務于自己的迭代器類型：begin使迭代器指向容器中的第一個數據元素；end使迭代器指向容器的結束位置，一般是最后一個數據元素的下一個位置；++和--運算，解引用運算等。不過，向量類模板Vector沒有提供++、--和解引用運算，因為它是順序存儲結構，編譯器提供的默認的運算與它需要的正好相符。

現在我們可以寫出不依賴容器類型和數值類型的通用算法：

template＜class Container，class T＞

void Add(Container c，const T val)

{

typename Container::iterator itr;

for(itr=c.begin();itr!=c.end();++itr)

*itr=*itr+val;

}

template＜class Container＞

void Display(const Container c)

{

typename Container::const_iterator itr;

for(itr=c.begin();itr!=c.end();++itr)

cout＜＜*itr＜＜'\';

}

C++標準模板庫STL中的標準通用算法，一般稱泛型算法，它們的前兩個參數通常都是一對迭代器(iterator)，first和last，用以標示算法的操作區間。而且習慣采用前閉后開區間(或稱左涵蓋區間)表示法，寫成[first，last)表示區間涵蓋first至last(不含last)之間的所有元素。下面我們按這個標準，重寫上述兩個通用算法：

template＜class Iterator，class T＞//Iterator是迭代器類型模板參數

void Add(Iterator first，Iterator last，const T val)

{

for(;first!=last;++first)

*first=*first+val;

}

template＜class Iterator＞//Iterator是迭代器類型模板參數

void Display(Iterator first，Iterator last)

{

for(;first!=last;++first)

cout＜＜*first＜＜'\';

}

調用例句：

Vector＜int＞ intV;//整型Vector容器

for(int i=1;i＜=10;i++)//后插0~19間10個隨機數

intV.Push_back(rand()%20);

Add(intV.begin()，intV.end()，5);//每個元素加5

Display(intV.begin()，intV.end());//輸出

2函數對象

下面是一個模板函數，其功能是在指示器規定的范圍內，返回第一個最大元素的指示器：

template＜class Iterator＞//在指示器規定的范圍內，返回第一個最大元素的指示器

Iterator findMax(Iterator first，Iterator last)

{

Iterator max=first;//令指示器max指向第一個元素(作為當前最大元素)

for(++first;first!=last;++first)//從第二個元素開始掃描

if(*max＜*first)//如果當前元素大于最大元素

max=first;//令指示器max指向該元素

return(max);//返回指向最大元素的指示器

}

這個模板函數有一個限制：指示器指向的對象必須定義了operator＜函數。可是有的時候，這個要求行不通。例如，一個類的數據成員是工號、工資、年齡和工作年限，這時要定義operator＜函數就很牽強。即使定義了，假設比較的是工資，而實際所需要的可能是比較工作年限。

解決這類問題的一個方法是：定義一個只含一個成員函數的類，通過傳遞這個類的實例即對象來傳遞函數，由這個函數實現比較操作。這樣的對象通常稱為函數對象(function object)。

struct Employee

{

String name;//姓名

int age;//年齡

int years;//工齡

double sal;//工資

};

class MyCriterion //只含一個成員函數的類

{

public:

bool isLessThan(const Employee e1，const Employee e2)const//成員函數

{return(e1.years＜e2.years);}

};

template＜class Iterator，class C＞//在指示器規定的范圍內，返回第一個最大元素的指示器

Iterator findMax(Iterator first，Iterator last，C cmp)//通過對象cmp傳遞函數

{

Iterator max=first;

for(++first;first!=last;++first)

if(cmp.isLessThan(*max，*first))//調用對象的成員函數

max=first;

return(max);

}

函數對象的另一種形式是，函數調用操作符(operator())重載：

class MyCriterion

{

public:

bool operator()(const Employee e1，const Employee e2)const //函數調用操作符重載

{return(e1.years＜e2.years);}

};

這時，findMax函數中的cmp.isLessThan(x，y)轉為cmp.operator()(x，y)，而后者可以縮寫為cmp(x，y)。進一步，為了便于理解，可以把findMax函數的參數名稱cmp改為isLessThan，使cmp(x，y)轉為isLessThan(x，y)。對象名像函數名一樣使用。

template＜class Iterator，class C＞//在指示器規定的范圍內，返回第一個最大元素的指示器

Iterator findMax(Iterator first，Iteratorlast， C isLessThan)//把參數名稱cmp改為isLessThan

{

Iterator max=first;

for(++first;first!=last;++first)

if(isLessThan(*max，*first)) //對象名稱像函數名稱一樣使用

max=first;

return(max);

}

3結束語

任何概念，即使像通用算法、迭代器和函數對象這樣的復雜概念，都應該用具體的程序嚴格地描述其產生的必要性，這是辯證法為我們確定的方法準則。