STL與泛型編程
一、STL是什么
STL（Standard TemplateLibrary），即標(biāo)準(zhǔn)模板庫(kù)，是一個(gè)具有工業(yè)強(qiáng)度的，高效的C++程序庫(kù)。它被容納于C++標(biāo)準(zhǔn)程序庫(kù)（C++ Standard Library）中，是ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫(kù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。
從邏輯層次來(lái)看，在STL中體現(xiàn)了泛型化程序設(shè)計(jì)的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)；
從實(shí)現(xiàn)層次看，整個(gè)STL是以一種類型參數(shù)化（type parameterized）的方式實(shí)現(xiàn)的，這種方式基于一個(gè)在早先C++標(biāo)準(zhǔn)中沒有出現(xiàn)的語(yǔ)言特性--模板（template）。如果查閱任何一個(gè)版本的STL源代碼，你就會(huì)發(fā)現(xiàn)，模板作為構(gòu)成整個(gè)STL的基石是一件千真萬(wàn)確的事情。除此之外，還有許多C++的新特性為STL的實(shí)現(xiàn)提供了方便；
二、STL的六大組件
STL：主要包含6個(gè)parts：
** 容器（****Container****），是一種數(shù)據(jù)結(jié)構(gòu)，如list，vector，和deque，以模板類的方法提供。為了訪問容器中的數(shù)據(jù)，可以使用由容器類輸出的迭代器（有的容器不含迭代器，如queue，stack）；
** 迭代器（****Iterator****），提供了訪問容器中對(duì)象的方法。例如，可以使用一對(duì)迭代器指定list或vector中的一定范圍的對(duì)象。迭代器就如同一個(gè)指針。事實(shí)上，C++的指針也是一種迭代器。但是，迭代器也可以是那些定義了operator()以及其他類似于指針的操作符地方法的類對(duì)象；
** 算法（****Algorithm****），是用來(lái)操作容器中的數(shù)據(jù)的模板函數(shù)。例如，STL用sort()來(lái)對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序，用find()來(lái)搜索一個(gè)list中的對(duì)象，函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無(wú)關(guān)，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用；
** 仿函數(shù)（Functionobject，仿函數(shù)(functor)又稱之為函數(shù)對(duì)象（function object），其實(shí)就是重載了()操作符的struct，沒有什么特別的地方
** 迭代適配器（Adaptor）
** 空間配制器、分配器（allocator*）其中主要工作包括兩部分1.對(duì)象的創(chuàng)建與銷毀2.內(nèi)存的獲取與釋放。
2.1 部件之間的關(guān)系

三、整個(gè)課程目錄：

•                                        （***完***）*
         第一課：體系結(jié)構(gòu)與內(nèi)核分析
   在C++標(biāo)準(zhǔn)中，STL被組織為下面的17個(gè)頭文件：<[algorithm](http://baike.baidu.com/item/algorithm)>、<[deque](http://baike.baidu.com/item/deque)>、<[functional](http://baike.baidu.com/item/functional)>、<[iterator](http://baike.baidu.com/item/iterator)>、<[array](http://baike.baidu.com/item/array)>、<[vector](http://baike.baidu.com/item/vector)>、<[list](http://baike.baidu.com/item/list)>、、、、、<[numeric](http://baike.baidu.com/item/numeric)>、<[queue](http://baike.baidu.com/item/queue)>、<[set](http://baike.baidu.com/item/set)>、、<[stack](http://baike.baidu.com/item/stack)>和<[utility](http://baike.baidu.com/item/utility)>。
   C++標(biāo)準(zhǔn)庫(kù)頭文件header不包含副檔名
  如：#include不包含.h后綴
   新式C庫(kù)也不包含副檔名。#include
  

幾個(gè)重要的C++網(wǎng)站：
* ** cplusplus.com***
*** cppReference.com***
*** gcc.gnu.org***
程序復(fù)雜度O(n)：n需要很大，工業(yè)級(jí)的，比如幾十萬(wàn)幾百萬(wàn)數(shù)據(jù)量，才能體現(xiàn)線性復(fù)雜度。
標(biāo)準(zhǔn)庫(kù)容器迭代器采用前閉后開區(qū)間[ a,b)。
不能對(duì)c.end()取內(nèi)容。*c.end() //(X)
容器在內(nèi)存中不一定連續(xù)。

新版本（since C++11）容器遍歷：

1容器的分類和內(nèi)存結(jié)構(gòu)

1容器的分類和內(nèi)存結(jié)構(gòu)
1.1容器的分類
[圖片上傳中。。。（5）]

容器大致可以分為兩種；Sequence containers****和****associative containers兩大類
一、****Sequence
containers:**有序的容器；******

1、如數(shù)組的類實(shí)現(xiàn)array（在內(nèi)存中順序排放，并且長(zhǎng)度不能動(dòng)態(tài)改變。）、
2、Vector：當(dāng)空間不夠時(shí)，分配器會(huì)自動(dòng)向后擴(kuò)充空間
3、deque（讀daike）：雙頭隊(duì)列。
**1,2,3****這些容器在內(nèi)存中連續(xù)******
4、list：雙向鏈表，空間在內(nèi)存中不連續(xù)

二、****associative containers****：查找效率高。******
在STL內(nèi)部，set用紅黑樹**實(shí)現(xiàn)
Set/multiSet: Map/multiMap
Set和Map中數(shù)據(jù)元素不能重復(fù)
multiSet和multiMap中數(shù)據(jù)元素可以重復(fù)

1.2 容器Array的使用：
使用,很方便,用起來(lái)和STL一樣;執(zhí)行效率比高,幾乎和
int myarray[5]效率一樣。當(dāng)你想要一個(gè)執(zhí)行時(shí)效率高,而用不想自己管理內(nèi)存的時(shí)候,就用它。Array在內(nèi)存中是連續(xù)排列的?？梢允褂肹]操作符或c.at(i)索引數(shù)組元素。包含頭文件：#include
實(shí)測(cè)：類型和大小相同的Array對(duì)象可以相互賦值，且拷貝賦值之后彼此不影響。屬于深拷貝。
arrayc;
array a,b;
a[0] = 1
b = a;
1.3容器Vector的使用：

Vector是一端開口的數(shù)組，每次擴(kuò)充以2倍增長(zhǎng)。
擴(kuò)充：即成長(zhǎng)，這個(gè)過程是非常緩慢的，存在內(nèi)存拷貝。當(dāng)當(dāng)前空間Aspace不夠用時(shí)，在另外一個(gè)地方重新開辟一個(gè)大小為2space的空間B，將A中元素拷貝到B，然后清理掉A。
定義自動(dòng)變量pItem；
同時(shí)調(diào)用全局函數(shù)：：find()順序查找值為target的元素地址。
通過pItem就可獲得值。
在c++中，vector是一個(gè)十分有用的容器。
*1****基本操作******
(1)頭文件#include.
(2)創(chuàng)建vector對(duì)象，vectorvec;
(3)尾部插入數(shù)字：vec.push_back(a);
(4)使用下標(biāo)訪問元素，cout<
(5)使用迭代器訪問元素.
vector::iteratorit;
for(it=vec.begin();it!=vec.end();it++)
cout<<it<
(6)插入元素：vec.insert(vec.begin()+i,a);在第i+1個(gè)元素前面插入a;
(7)刪除元素：vec.erase(vec.begin()+2);刪除第3個(gè)元素
vec.erase(vec.begin()+i,vec.end()+j);刪除區(qū)間[i,j-1];區(qū)間從0開始
(8)向量大小:vec.size();
(9)清空:vec.clear();
1.4容器List的使用：
STL中的list就是一雙向鏈表，可高效地進(jìn)行插入、刪除元素操作。
list不支持隨機(jī)訪問。所以沒有at(pos)和operator[]。
List本身提供sort函數(shù)。這是排序算法最好采用內(nèi)部sort成員函數(shù)。
有些容器沒有提供sort成員函數(shù)，如vector、array。

標(biāo)準(zhǔn)庫(kù)提供的：：find()函數(shù)是
順序查找。
1.5容器deque的使用：
deque雙向隊(duì)列是一種雙向開口的連續(xù)線性空間，可以高效的在頭尾兩端插入和刪除元素，deque在接口上和vector非常相似。
deque的實(shí)現(xiàn)比較復(fù)雜，內(nèi)部會(huì)維護(hù)一個(gè)map（注意！不是STL中的map容器）即一小塊連續(xù)的空間，該空間中每個(gè)元素都是指針，指向另一段（較大的）區(qū)域，這個(gè)區(qū)域稱為緩沖區(qū)，緩沖區(qū)用來(lái)保存deque中的數(shù)據(jù)。因此deque在隨機(jī)訪問和遍歷數(shù)據(jù)會(huì)比vector慢。具體的deque實(shí)現(xiàn)可以參考《STL源碼剖析》。
Deque在內(nèi)存中是分段連續(xù)的，但在使用者用起來(lái)是沒有這種“分段連續(xù)”的感受，
我們?cè)谑褂?+操作符作用在deque對(duì)象。

下面給出deque的使用范例：

//雙向隊(duì)列 deque  //by MoreWindows http://blog.csdn.net/morewindows  #include#include#includeusing namespace std;  int main()  {      dequeideq(20); //Create a deque ideq with 20 elements of default value 0      deque::iterator pos;
int i;
//使用assign()賦值  assign在計(jì)算機(jī)中就是賦值的意思
for (i = 0; i < 20; ++i)
ideq[i] = i;
//輸出deque
printf("輸出deque中數(shù)據(jù):\n");
for (i = 0; i < 20; ++i)
printf("%d ", ideq[i]);
putchar('\n');
//在頭尾加入新數(shù)據(jù)
printf("\n在頭尾加入新數(shù)據(jù)...\n");
ideq.push_back(100);
ideq.push_front(i);
//輸出deque
printf("\n輸出deque中數(shù)據(jù):\n");
for (pos = ideq.begin(); pos != ideq.end(); pos++)
printf("%d ", *pos);
putchar('\n');
//查找
const int FINDNUMBER = 19;
printf("\n查找%d\n", FINDNUMBER);
pos = find(ideq.begin(), ideq.end(), FINDNUMBER);
if (pos != ideq.end())
printf("find %d success\n", *pos);
else
printf("find failed\n");
//在頭尾刪除數(shù)據(jù)
printf("\n在頭尾刪除數(shù)據(jù)...\n");
ideq.pop_back();
ideq.pop_front();
//輸出deque
printf("\n輸出deque中數(shù)據(jù):\n");
for (pos = ideq.begin(); pos != ideq.end(); pos++)
printf("%d ", *pos);
putchar('\n');
return 0;
}

Queue和stack的內(nèi)部實(shí)現(xiàn)都包含一個(gè)deque。因此，queue和stack都可以看做是特殊的deque。
1.6容器set和multiset的使用（關(guān)聯(lián)式容器）：
紅黑樹和哈希表。作為數(shù)據(jù)結(jié)構(gòu)，非常適用于需要大量查找的場(chǎng)合。
元素就是key，key就是元素。
set和multiset會(huì)根據(jù)特定的排序準(zhǔn)則，自動(dòng)將元素進(jìn)行排序。不同的是multiset****允許元素重復(fù)而set****不允許。只要是可復(fù)賦值、可拷貝、可以根據(jù)某個(gè)排序準(zhǔn)則進(jìn)行比較的型別都可以成為它們的元素。第二個(gè)參數(shù)用來(lái)定義排序準(zhǔn)則。缺省準(zhǔn)則less是一個(gè)仿函數(shù)。
和所有關(guān)聯(lián)式容器類似，通常使用平衡二叉樹完成。事實(shí)上，set和multiset通常以紅黑樹實(shí)作而成。
自動(dòng)排序的優(yōu)點(diǎn)是使得搜尋元素時(shí)具有良好的性能****，具有對(duì)數(shù)時(shí)間復(fù)雜度。但是造成的一個(gè)缺點(diǎn)就是：
不能直接改變?cè)刂?。因?yàn)檫@樣會(huì)打亂原有的順序。
改變?cè)刂档姆椒ㄊ牵合葎h除舊元素，再插入新元素。
存取元素只能通過迭代器，從迭代器的角度看，元素值是常數(shù)。
用STL的算法：：find()查找元素和用MultiSet自身的find（）成員函數(shù)查找速度對(duì)比：

1.7容器map和multimap的使用（關(guān)聯(lián)式容器）：
每一個(gè)元素包含一個(gè)key，通過key來(lái)查找元素。
1.8容器unordered_multiset的使用（關(guān)聯(lián)式容器）：
Hash table.
Hash
table籃子一定比元素多，大概是元素的2倍 。

新版本STL中用unordered_XXX代替了舊版本的hash_XXX

2 分配器
容器內(nèi)部需要分配器來(lái)管理內(nèi)存。