提供了類(lèi)型安全、高效而易用特性的STL無(wú)疑是最值得C++程序員驕傲的部分。每一個(gè)C＋＋程序員都應(yīng)該好好學(xué)習(xí)STL：).???
STL（Standard Template Library 標(biāo)準(zhǔn)模板庫(kù)）是C＋＋標(biāo)準(zhǔn)庫(kù)的一個(gè)重要組成部分，它由Stepanov and Lee等人最先開(kāi)發(fā)，它是與C＋＋幾乎同時(shí)開(kāi)始開(kāi)發(fā)的；一開(kāi)始STL選擇了Ada作為實(shí)現(xiàn)語(yǔ)言，但Ada有點(diǎn)不爭(zhēng)氣，最后他們選擇了C＋＋，一個(gè)原因了，C＋＋中已經(jīng)有了模板。在后來(lái)，STL又被添加進(jìn)了C＋＋庫(kù)。1996年，惠普公司又免費(fèi)公開(kāi)了STL，為STL的推廣做了很大的貢獻(xiàn)。
STL大體上包括container（容器）、algorithm（算法）和iterator（迭代器），容器和算法通過(guò)迭代器可以進(jìn)行無(wú)縫連接。??
STL體現(xiàn)了范型編程的思想，它具有高度的可重用性，高性能，高移植性。程序員不用思考具體實(shí)現(xiàn)過(guò)程，只要能夠熟練的應(yīng)用就OK了。（有興趣研究具體實(shí)現(xiàn)的，可以看侯捷老師編著的《STL源碼剖析》）這樣他們就可以把精力放在程序開(kāi)發(fā)的別的方面。
我非常佩服創(chuàng)造STL的那些計(jì)算機(jī)和數(shù)學(xué)精英。因?yàn)樗麄冏隽艘患浅Ｐ量嗟氖虑楱D――抽象概念。而STL就是通過(guò)把容器抽象為統(tǒng)一的接口，算法利用這個(gè)接口，通過(guò)迭代器來(lái)操縱容器。因?yàn)榻涌诓蛔儯瑢?shí)現(xiàn)的容器可以隨意更改。這樣，就為編程、調(diào)試和擴(kuò)展提供了便利。也許有一天，我們生產(chǎn)軟件的時(shí)候也可以想DIY一臺(tái)PC一樣簡(jiǎn)單，只要拿來(lái)相應(yīng)的實(shí)現(xiàn)模塊，通過(guò)簡(jiǎn)單的拼裝和調(diào)試就可以創(chuàng)造一個(gè)軟件。這是多么令人興奮的一件事^_^.不過(guò)，到時(shí)候，可能會(huì)有很多程序員失業(yè)了。呵呵，畢竟編寫(xiě)類(lèi)庫(kù)不需要很多的人員。
雖然STL不是面向?qū)ο蟮模蚁耄總€(gè)人都會(huì)為它的創(chuàng)造力和高性能而感到興奮和折服。
一、容器?
作為STL的最主要組成部分－－容器，分為向量（vector），雙端隊(duì)列(deque)，表(list)，隊(duì)列（queue），堆棧(stack)，集合(set)，多重集合(multiset)，映射(map)，多重映射(multimap)。
容器???? | 特性 | 所在頭文件 |
向量vector | 可以用常數(shù)時(shí)間訪問(wèn)和修改任意元素，在序列尾部進(jìn)行插入和刪除時(shí)，具有常數(shù)時(shí)間復(fù)雜度，對(duì)任意項(xiàng)的插入和刪除就有的時(shí)間復(fù)雜度與到末尾的距離成正比，尤其對(duì)向量頭的添加和刪除的代價(jià)是驚人的高的 | <vector> |
雙端隊(duì)列deque | 基本上與向量相同，唯一的不同是，其在序列頭部插入和刪除操作也具有常量時(shí)間復(fù)雜度 | <deque> |
表list | 對(duì)任意元素的訪問(wèn)與對(duì)兩端的距離成正比，但對(duì)某個(gè)位置上插入和刪除一個(gè)項(xiàng)的花費(fèi)為常數(shù)時(shí)間。 | <list> |
隊(duì)列queue | 插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許從頭部進(jìn)行。按照先進(jìn)先出的原則。 | <queue> |
堆棧stack | 堆棧是項(xiàng)的有限序列，并滿足序列中被刪除、檢索和修改的項(xiàng)只能是最近插入序列的項(xiàng)。即按照后進(jìn)先出的原則 | <stack> |
集合set | 由節(jié)點(diǎn)組成的紅黑樹(shù)，每個(gè)節(jié)點(diǎn)都包含著一個(gè)元素，節(jié)點(diǎn)之間以某種作用于元素對(duì)的謂詞排列，沒(méi)有兩個(gè)不同的元素能夠擁有相同的次序，具有快速查找的功能。但是它是以犧牲插入車(chē)刪除操作的效率為代價(jià)的 | <set> |
多重集合multiset | 和集合基本相同，但可以支持重復(fù)元素具有快速查找能力 | <set> |
映射map | 由{鍵，值}對(duì)組成的集合，以某種作用于鍵對(duì)上的謂詞排列。具有快速查找能力 | <map> |
多重集合multimap | 比起映射，一個(gè)鍵可以對(duì)應(yīng)多了值。具有快速查找能力 | <map> |
考慮到不同的實(shí)際需要，更主要的是效率的需要，我們可以選擇不同的容器來(lái)實(shí)現(xiàn)我們的程序，以此達(dá)到我們提高性能的目的。這也是用好STL的一個(gè)難點(diǎn)，但這也是關(guān)鍵。
二、算法
算法部分主要由頭文件<algorithm>，<numeric>和<functional>組成。<algorithm>是所有STL頭文件中最大的一個(gè)，它是由一大堆模版函數(shù)組成的，可以認(rèn)為每個(gè)函數(shù)在很大程度上都是獨(dú)立的，其中常用到的功能范圍涉及到比較、交換、查找、遍歷操作、復(fù)制、修改、移除、反轉(zhuǎn)、排序、合并等等。<numeric>體積很小，只包括幾個(gè)在序列上面進(jìn)行簡(jiǎn)單數(shù)學(xué)運(yùn)算的模板函數(shù)，包括加法和乘法在序列上的一些操作。<functional>中則定義了一些模板類(lèi)，用以聲明函數(shù)對(duì)象。
STL的算法也是非常優(yōu)秀的，它們大部分都是類(lèi)屬的，基本上都用到了C＋＋的模板來(lái)實(shí)現(xiàn)，這樣，很多相似的函數(shù)就不用自己寫(xiě)了，只要用函數(shù)模板就OK了。
我們使用算法的時(shí)候，要針對(duì)不同的容器，比如：對(duì)集合的查找，最好不要用通用函數(shù)find（），它對(duì)集合使用的時(shí)候，性能非常的差，最好用集合自帶的find（）函數(shù)，它針對(duì)了集合進(jìn)行了優(yōu)化，性能非常的高。
三、迭代器
它的具體實(shí)現(xiàn)在<itertator> 中，我們完全可以不管迭代器類(lèi)是怎么實(shí)現(xiàn)的，大多數(shù)的時(shí)候，把它理解為指針是沒(méi)有問(wèn)題的（指針是迭代器的一個(gè)特例，它也屬于迭代器），但是，決不能完全這么做。
迭代器功能（Abilities Of IteratorGategories） |
輸入迭代器 Input iterator | 向前讀 Reads forward | istream |
輸出迭代器 Output iterator | 向前寫(xiě) Writes forward | ostream,inserter |
前向迭代器 Forward iterator | 向前讀寫(xiě) Read and Writes forward | ? |
雙向迭代器 Bidirectional iterator | 向前向后讀寫(xiě) Read and Writes forward and backward | list,set,multiset,map,mul timap |
隨機(jī)迭代器 Random access iterator | 隨機(jī)讀寫(xiě) Read and Write with random access | vector,deque,array,string |
由此可見(jiàn)，指針和迭代器還是有很大差別的。和指針最接近的就是隨機(jī)訪問(wèn)迭代器。下面是一個(gè)我編寫(xiě)的小例子：功能是分別對(duì)數(shù)組，向量，表，多重集合進(jìn)行插入操作，對(duì)每個(gè)容器插入100萬(wàn)個(gè)隨機(jī)整數(shù)；
 #include<iostream>
#include<iterator>
#include<vector>
#include<list>
#include<set>
#include<time.h>
#include<conio.h>
#include<algorithm>
using?namespace?std;
template<typename?T>
void?arrayInsert(T*a,T*s,long?size)????//向數(shù)組插入數(shù)據(jù)
   {
 ???//for(long?i=0;i<10;i++)??//?//好像數(shù)組支持不到100萬(wàn)，我們就算10萬(wàn)的
?????????????????????????????????????????//最后在把把結(jié)果乘以10吧，
???//{
???????for(long?k=0;k<size;k++)
  ???????{
???????????a[k]=s[k];??
 ???????}
???//}
 }
template<typename?T>
void?vectorInsert(?vector<T>?*v,T*s,long?size)?????//向向量插入數(shù)據(jù)
{
???for(int?i=0;i<10;i++)
???{
???????for(long?k=0;k<size;k++)
???????{
???????????v->push_back(s[k]);?
??????}
???}
}
template<typename?T>
void?listInsert(list<T>*l,T*s,long?size)???//向表插入數(shù)據(jù)
{
???for(int?i=0;i<10;i++)
???{
???????for(long?k=0;k<size;k++)
???????{
???????????l->push_back(s[k]);
???????}???
???}
}
template<class?T>
void?multisetInsert(multiset<T>*s1,T*s,long?size)???//向多重集合插入數(shù)據(jù)
{
???for(int?i=0;i<10;i++)
???{
???????for(long?k=0;k<size;k++)
???????{
???????????s1->insert(s[k]);???
???????}
???}
}
int*?genIntData(long?size)??????????????????//生成隨機(jī)數(shù)
{
???int*?data=new?int[size];
???generate(&data[0],&data[size],rand);
???return?data;
}???
int?main(void)
{
???const?long?size=100000;
???int*?s_data,array1[size];
???double?begin,end;
???s_data=genIntData(size);
???vector<int>?vector1;
???list<int>?list1;
???multiset<int>?multiset1;
???clock();
???cout<<"?"<<endl;
???begin=(double)clock()/CLK_TCK;
???arrayInsert<int>(array1,s_data,size);
???end=(double)clock()/CLK_TCK;
???cout<<"??"<<(end-begin)<<endl;
???getch();
???begin=(double)clock()/CLK_TCK;
???vectorInsert<int>(&vector1,s_data,size);
???end=(double)clock()/CLK_TCK;
???cout<<"??"<<(end-begin)<<endl;
???getch();
???begin=(double)clock()/CLK_TCK;
???listInsert<int>(&list1,s_data,size);
???end=(double)clock()/CLK_TCK;
???cout<<"??"<<(end-begin)<<endl;
???getch();
???begin=(double)clock()/CLK_TCK;
???multisetInsert<int>(&multiset1,s_data,size);
???end=(double)clock()/CLK_TCK;
???cout<<"??"<<(end-begin)<<endl;
???getch();
???free(s_data);
???return?0;???????
}
|
?
這個(gè)程序清晰的表明這幾種容器在插入速度之間的差別，當(dāng)然，每種容器不是萬(wàn)能的，不能一好百好。比如說(shuō)，多集在查找方面的優(yōu)勢(shì)是其他序列容器不可比擬的。? 還有，最好不要試圖超越STL，因?yàn)椋?/span>
1、STL實(shí)現(xiàn)使用的是最佳算法。它是幾乎完美的。
2、STL實(shí)現(xiàn)的設(shè)計(jì)者通常是相應(yīng)領(lǐng)域的專家。
3、各領(lǐng)域的專家致力于提供靈活的、強(qiáng)大和高效的庫(kù)。這是他們的首要的任務(wù)。對(duì)于，我們這些其余的人，開(kāi)發(fā)可重用的容器和算法頂多只算第二個(gè)目標(biāo)。我們的首要任務(wù)是交付緊扣主題的應(yīng)用程序。大多數(shù)情況下，我們沒(méi)有時(shí)間和專門(mén)的技術(shù)去和那些專家相比。
但是，超越STL不是不可能的。但是一般情況下，你只能靠犧牲可移植性來(lái)提高性能，這對(duì)于很多情況來(lái)說(shuō)是很不好的。為了，超越STL，我們要付出非常大的努力。而且，最好我們知道一些STL專家們不知道的東西，爾后我們可以有針對(duì)性的進(jìn)行優(yōu)化，否則，我們的努力完全有可能白費(fèi)。
面對(duì)這樣一個(gè)優(yōu)秀的庫(kù)，并且它是免費(fèi)的。我們C++程序員沒(méi)有理由拒絕它，甚至去自己開(kāi)發(fā)一個(gè)庫(kù)。