1.什么是STL？
標準模板庫(Standard Template Library)。虛函數(shù)和模板（包括函數(shù)模板和類模板）是C++語言的兩個重要特性，MFC利用大量地運用了虛函數(shù)，而STL則是利用模板實現(xiàn)的。
2.為什么要使用類屬算法？
軟件模塊的可重用性考慮，使得不必為每一種數(shù)據(jù)類型編寫算法，在抽象數(shù)據(jù)類型上定義算法，當算法作用于具體數(shù)據(jù)類型時，只要用特定的數(shù)據(jù)類型具體化便可。
例如：
template <typename T>
T max(T x,T y)
{
if(x<y) ruturn y;
else return x;
}
調(diào)用如下：
int u=3,v=4;
double d=4.7;
cout<<max(u,v)<<endl;
cout<<max(d,9.3)<<endl;
函數(shù)模板在使用時不必告訴編譯器所使用的實際類型，編譯器可以從參數(shù)中直接判斷出來，如上例。
注意：編譯器不會進行自動類型轉(zhuǎn)換。所以如下調(diào)用時不正確的：
cout<<max(u,d)<<endl; //incorrect
這里使用的是內(nèi)置數(shù)據(jù)類型，也可以傳遞用戶定義數(shù)據(jù)類型，但必須定義<比較運算符 。
另一方面，STL使用的類屬算法，與容器（STL的重要基本概念之一，通俗地理解，就是封裝過的數(shù)組，隊列，集合等
放置數(shù)據(jù)的一種結(jié)構(gòu)，從字面意思即可理解，也可以理解為一種模板類）是相對獨立的，即一種類屬算法可以應(yīng)用于多種容器之上，甚至有些類屬算法可以應(yīng)用于所
有的容器。OOP編程一般把作用于類的操作，即使算法實現(xiàn)為特定類的成員函數(shù)，使得數(shù)據(jù)和算法緊密的聯(lián)系在一起，但是STL把各種容器的公共操作提取出
來，作為一個獨立的組件（算法集合），而把某些特殊的算法實現(xiàn)為容器的成員函數(shù)（出于容器的特殊性考慮，有些類屬算法雖然可以實現(xiàn)同樣的功能，但適當考慮
某些容器的特殊性之后，可以有不同的實現(xiàn)方式，使得這種操作作用于特殊的類時效率更高，于是一部分某些容器也提供實現(xiàn)相同功能的成員函數(shù)），例如對于類屬
算法find，其時間復(fù)雜度是線性的，而有序關(guān)聯(lián)容器（set,multiset,map,multiset）就提供了成員函數(shù)，其實見復(fù)雜度為log
(N)。
總的來說，使用類屬算法，提高了通用性，降低了程序員工作的復(fù)雜度，可以通過標準的統(tǒng)一接口來編程，也易于維護。
3.類屬算法如何工作？
容器(container)<——>迭代器(iterator)<——>類屬算法(algorithm)
迭代器是類似于指針的一種STL組件，在STL中，迭代器的用法跟指針類似，目前就暫且把它理解為指針。
可以這樣理解，類屬算法不是對容器直接操作，而是通過對指向容器某個位置的迭代器（類似指針）來實現(xiàn)對該地址的數(shù)據(jù)的操作。
4.基本概念
類模板
template<typename T1,typename T2>
class pair{
public:
T1 first;
T2 second;
pair():first(T1()),sencond(T2()){} //默認構(gòu)造函數(shù)
pair(const T1& x,const T2&
y):first(x),second(y){} //自定義構(gòu)造函數(shù)
} ;
實際調(diào)用時:
pair<int,char> pair1(13,'a');
pair<bool,double> pair2(true,0.1);
函數(shù)模板：上面的max（）函數(shù)就是一個簡單的函數(shù)模板。
成員函數(shù)模板
不管類屬否使用模板定義，其成員函數(shù)都可以有模板參數(shù)，例如：
template <typename T>
class vector{
//.....
public:
template <typename InputIterator>
void insert(iterator position,InputIterator first,InputIterator last);
//.....
};
容器
在STL中，容器指存儲其他對象的集合的對象，主要有兩種類型的STL容器：序列容器和順序關(guān)聯(lián)容器。
序列容器
序列容器將一組具有相同類型的對象以嚴格線性的形式組織在一起。包括如下幾種：
vector<T> 提供對變長序列的隨機訪問，對序列末尾的插入和刪除操作時間是分攤常量的，對序列開頭的插入和刪除是線性的。可以理解為封裝后的數(shù)組。
depue<T>提供對變長序列的隨機訪問，對序列開頭和末尾的插入和刪除操作是分攤常量的。存儲空間是連續(xù)的（這一點尚未在書上說明，只是個人推測）。
list<T>提供對變長序列的線性時間訪問，但是對序列中任意位置的插入和刪除操作均為常量時間的。可以理解為封裝后的鏈表。
對向量使用STL類屬算法reverse:
#include<iostream>
#include<vector>
#include<cassert>
#include<string>
#include<algorithm> //for reverse
using namespace std;
template<typename Container>
Container make(const char s[])
{
return Container(&s[0],&s[strlen(s)]);
}
int main()
{
cout<<"Using reverse algorithm with a vector"<<endl;
string string1="mark twain";
vector<char> vector1(string1.begin(),string1.end()); //begin()和end()是訪問器，返回迭代器
reverse(vector1.begin(),vector1.end());
assert(vector1==make< vector<char> >("niawt kram"));
cout<<" --OK."<<endl;
return 0;
}
有序關(guān)聯(lián)容器
有序關(guān)聯(lián)容器具有從基于鍵的集合種快速提取對象的能力。集合的大小可以在運行時改變。STL中有4種類型的有序關(guān)聯(lián)容器：
set<Key>支持唯一的鍵（每個鍵值只能有一個）并提供對見本身的快速檢索。
multiset<Key>支持客重復(fù)的鍵（同一個鍵值可以有多個副本）并提供對鍵本身的快速檢索。
map<Key,T>支持唯一的（Key類型的）鍵并提供對另一個基于鍵的類型T的快速檢索 。
multimap<Key,T>支持可重復(fù)的（Key類型的）鍵并提供對另一個基于鍵的類型T的快速檢索。
演示STL映射（map）:
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string,long> directory;
directory["Bogart"]=123;
directory["Bacall"]=456;
directory["Cagney"]=789;
string name;
while(cin>>name)
{
if(directory.find(name)!=directory.end())
cout<<"The phone number for "<<name
<<" is "<<directory[name]<<"\n";
else
cout<<"Sorry,no listing for "<<name<<endl;
}
return 0;
}
上例中，find()為所有有序關(guān)聯(lián)容器的成員函數(shù)，查找時間復(fù)雜度為logN，該函數(shù)首先檢查name是否為保存在directory中的一個鍵，假如directory確實存在以name作為鍵值的數(shù)據(jù)項，則其返回該數(shù)據(jù)項的迭代器，否則find函數(shù)返回“序列末尾最后一個元素之后的一個位置”迭代器，該迭代器與end成員函數(shù)返回的迭代器相同。
STL容器和其他C++容器類庫中的容器的一個重要區(qū)別：STL容易并沒有為其所包含的容器提供過多的操作（成員函數(shù)），相反，STL提供的是類屬算法。
類屬算法
最簡單的類屬算法：find和merge
類屬查找算法find
用表演示find類屬算法
#include<iostream>
#include<cassert>
#include<list>
#include<algorithm>
using namespace std;
template<typename Container>
Container make(const char s[])
{
return Container(&s[0],&s[strlen(s)]);
}
int main()
{
list<char> list1=make< list<char> >("C++ is a better C.");
list<char>::iterator
where=find(list1.begin(),list1.end(),'e');
list<char>::iterator next=where;
++next;
assert(*where=='e' && *next=='t');
cout<<" ---OK."<<endl;
return 0;
}
注意：與表對應(yīng)的迭代器不支持表達式*(where+1)中的+運算符，而向量(vector)和雙端隊列支持這樣的表達式。但所有的STL迭代器都要求支持++。
類屬合并算法merge
merge算法的功能是將兩個序列的元素合并到一個序列中，調(diào)用形式為
merge(first1,last1,first2,last2,result);
則包含如下假定：
*迭代器first1和last1表示一個輸入序列的起始和終止位置，其元素類型為T;
*迭代器first2和last2表示另一個輸入序列的起始和終止位置，其元素類型也為T;
*按照類型T上的<運算符的定義，兩個輸入序列均為升序排列。
*result表示合并后序列存放的起始位置。
merge函數(shù)返回的結(jié)果是合并兩個序列后的一個升序序列。
示例：merge類屬算法合并數(shù)組和向量，把結(jié)果保存在表中
#include<iostream>
#include<string>
#include<cassert>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
template<typename Container>
Container make(const char s[])
{
return Container(&s[0],&s[strlen(s)]);
}
int main()
{
char s[]="acegikm";
vector<char> vector1(
make< vector<char> >("bdfhjlnopqrstuvwxyz"));
list<char> list1(26,'x'); //將list1初始化為26個'x'
//merge first 5 letters in array s with first 10 in
//vector1,putting result in list1
merge(&s[0],&s[5],vector1.begin(),vector1.begin()+10,list1.begin());
assert(list1==
make< list<char> >("abcdefghijlnopqxxxxxxxxxxx"));
cout<<" --OK."<<endl;
return 0;
}
疑問：vc6.0下如果把上述程序中的vector換作deque，則無法通過編譯，不知道是否是編譯器不支持
deque<char> deque1(
make< deque<char> >("bdfhjlnopqrstuvwxyz"));
這種初始化方式？
迭代器
普通的C++指針就是一種迭代器，但除了指針以外，還有其他種類的迭代器。STL要求這些迭代器具有和指針類似的特性，既可以對迭代器做++和*等操作，而且這些操作與定義在指針上的相同操作具有相同的功能。
各個迭代器（不包括分配器）之間的層次關(guān)系及其要求定義的運算：
1. == != *
2. ++
3. --
4.+= -= + - < > <= >=
前向（輸入，輸出）：1，2
雙向：1，2，3
隨機：所有
前向也是雙向迭代器，雙向也是隨機迭代器。
對于輸入迭代器，只能讀取數(shù)據(jù)，不能寫入；對于輸出迭代器，只能寫入數(shù)據(jù)，不能讀取。
演示類屬算法accumulate,該算法在初始值基礎(chǔ)上累加指定容器區(qū)間的值。
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
int main()
{
int x[5]={2,3,5,7,11};
vector<int> vector1(&x[0],&x[5]);
int sum=accumulate(vector1.begin(),vector1.end(),0); //最后一個參數(shù)是累加的初始值
assert(sum==28);
cout<<"--OK."<<endl;
return 0;
}
向量和雙端隊列迭代器是隨機迭代器，而表迭代器僅僅是雙向的，并非隨機，固有些要求隨機迭代器的類屬算法不能用于表容器，例如sort算法，一次表容器有排序成員函數(shù)。
函數(shù)對象
先看一例。STL提供了accumulate函數(shù)的一個更為通用的版本。其定義如下：
template <typename InputIterator,typename T,typename BinaryOperation>
T accumulate(InputIterator first,InputIterator last,
T init,BinaryOperation binary_op)
{
while (first!=last)
{
init=binary_op(init,*first);
++first;
}
return init;
}
上面的定義沒有定義+運算符，而是引入了另一個參數(shù)binary_op，作為定義在序列質(zhì)類型上的二元操作符。
示例：使用增強版的accumulate計算連乘積
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
int mult(int x,int y){return x*y;}
int main()
{
int x[5]={2,3,5,7,11};
vector<int> vector1(&x[0],&x[5]);
int product=
accumulate(vector1.begin(),vector1.end(),1,mult);
assert(product==2310);
cout<<"--OK."<<endl;
return 0;
}
這里傳遞給accumulate函數(shù)的是一個普通函數(shù)的mult,實際上傳遞的是該函數(shù)的地址。
函數(shù)對象是一種實體，可以不帶參數(shù)，也可以帶有一個以上的參數(shù)，不能夠從中獲得一個值或者改變程序的狀態(tài)。除了上面所示的普通函數(shù)，另一類函數(shù)對象是類或者結(jié)構(gòu)的對象，且在其定義中重載了()運算符，而且這種方式在STL中更為常用。
請看下例：
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
class multiply
{
public:
int operator()(int x,int y) const{return x*y;}
};
int main()
{
int x[5]={2,3,5,7,11};
vector<int> vector1(&x[0],&x[5]);
int product=
accumulate(vector1.begin(),vector1.end(),1,multiply());
assert(product==2310);
cout<<"--OK."<<endl;
return 0;
}
通過在類multiply中定義運算符operator()，就定義了一種可以作為函數(shù)參數(shù)的對象，可以像使用函數(shù)一樣使用這種對象。這里傳遞給accumulate的對象是通過調(diào)用multiply類的默認構(gòu)造函數(shù)multiply()獲得的。
使用以類的形式定義的函數(shù)對象比普通函數(shù)優(yōu)越，它可以攜帶更多額外的信息（可以靜態(tài)數(shù)據(jù)成員的形式），以后再舉例子。
適配器
用來改變其他組件接口的組件稱為適配器。包括迭代器適配器、容器適配器和函數(shù)適配器。
迭代器適配器
reverse_iterator將某種類型的迭代器變成一種新的迭代器，但保持其功能不變，而僅將其便利的順序倒轉(zhuǎn)過來。
容器適配器
棧適配器可以將序列容器變換到后進先出的棧接口中。
隊列適配器可以將序列容器變換到先進先出的隊列中。
優(yōu)先級隊列可以將序列容器變換到優(yōu)先級隊列中，由一個比較參數(shù)來控制對其元素的訪問順序。
函數(shù)適配器
取反器(negator)用于對判定函數(shù)對象（判定函數(shù)對象指那些返回值為bool類型的函數(shù)對象）的結(jié)果進行取反。
邦定器(binder)通過將二元函數(shù)的一個參數(shù)與某個特定的值邦定，可以將二元函數(shù)變成一元函數(shù)。
函數(shù)指針適配器從函數(shù)指針得到函數(shù)對象，與使用標準函數(shù)相比，這將使編譯后的代碼具有更大的靈活性。
下面一例使用反向迭代器。
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
int main()
{
float small=(float)1.0/(1<<26);
float x[5]={1.0,3*small,2*small,small,small};
vector<float> vector1(&x[0],&x[5]);
cout<<"Values to be added: "<<endl;
vector<float>::iterator i;
for(i=vector1.begin(); i != vector1.end(); ++i)
cout<<*i<<endl;
cout<<endl;
float sum=accumulate(vector1.begin(),vector1.end(),(float)0.0);
cout<<"Sum accumulated from left = "<<sum<<endl;
float sum1=accumulate(vector1.rbegin(),vector1.rend(),(float)0.0);
cout<<"sum accumulated from right = "<<(double)sum1<<endl;
return 0;
}
vector<float>::reverse_iterator類型是用迭代器適配器定義的。也可以在程序中直接使用適配器：
reverse_iterator<vector<float>::iterator> start(vector1.end()),finish(vector1.begin());
float sum1=accumulate(start,finish,(float)0.0);
reverse_iterator類型也提供了++和--運算符，但互換了這兩個運算符的含義。上例中的vector1.rbegin()和vector1.rend()成員函數(shù)返回的即是reverse_iterator類型。
分配器
每種STL容器都是用了一種分配器類，用來封裝程序所用的內(nèi)存分配模式的信息。不同的內(nèi)存分配模式采用不同的方法從
操作系統(tǒng)中檢索內(nèi)存。分配器類可以封裝許多方面的信息，包括指針、常量指針、引用、常量引用、對象大小、不同類型指針之間的差別、分配函數(shù)與釋放函數(shù)、以
及一些函數(shù)的信息。分配器上的所有操作都具有分攤常量的運行時間。
由于內(nèi)存分配模式方面的信息可以封裝在分配器中，所以提供不同的分配器，就可以使STL容易能夠用于不同的內(nèi)存分配模式。
對多數(shù)程序員來說，STL提供的默認分配器類已經(jīng)可以滿足編程的需要了。