STL與泛型編程
一盖喷、STL是什么
? ? ? ? ?STL（Standard TemplateLibrary）爆办，即標準模板庫，是一個具有工業(yè)強度的课梳，高效的C++程序庫距辆。它被容納于C++標準程序庫（C++ Standard Library）中，是ANSI/ISO C++標準中最新的也是極具革命性的一部分暮刃。該庫包含了諸多在計算機科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法跨算。為廣大C++程序員們提供了一個可擴展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性椭懊。
? ? ? ? 從邏輯層次來看诸蚕，在STL中體現(xiàn)了泛型化程序設(shè)計的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements）背犯，概念（concept）坏瘩，模型（model），容器（container）漠魏，算法（algorithmn）倔矾，迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣柱锹，泛型也是一種軟件的復(fù)用技術(shù)哪自；
? ? ? ? 從實現(xiàn)層次看，整個STL是以一種類型參數(shù)化（type parameterized）的方式實現(xiàn)的禁熏，這種方式基于一個在早先C++標準中沒有出現(xiàn)的語言特性--模板（template）壤巷。如果查閱任何一個版本的STL源代碼，你就會發(fā)現(xiàn)瞧毙，模板作為構(gòu)成整個STL的基石是一件千真萬確的事情隙笆。除此之外，還有許多C++的新特性為STL的實現(xiàn)提供了方便升筏；
二、STL的六大組件
STL：主要包含6個parts：
? ? ? ?容器（Container）瘸爽，是一種數(shù)據(jù)結(jié)構(gòu)您访，如list，vector剪决，和deque灵汪，以模板類的方法提供。為了訪問容器中的數(shù)據(jù)柑潦，可以使用由容器類輸出的迭代器（有的容器不含迭代器享言，如queue，stack）渗鬼；
? ? ? ? 迭代器（Iterator）览露，提供了訪問容器中對象的方法。例如譬胎，可以使用一對迭代器指定list或vector中的一定范圍的對象差牛。迭代器就如同一個指針。事實上堰乔，C++的指針也是一種迭代器偏化。但是，迭代器也可以是那些定義了operator*()以及其他類似于指針的操作符地方法的類對象镐侯；
? ? ? ? 算法（Algorithm）侦讨，是用來操作容器中的數(shù)據(jù)的模板函數(shù)。例如，STL用sort()來對一個vector中的數(shù)據(jù)進行排序韵卤，用find()來搜索一個list中的對象骗污，函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無關(guān)，因此他們可以在從簡單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用怜俐；
? ? ? ? 仿函數(shù)（Functionobject身堡，仿函數(shù)(functor)又稱之為函數(shù)對象（function object），其實就是重載了()操作符的struct拍鲤，沒有什么特別的地方
? ? ? ?迭代適配器（Adaptor）
? ? ? 空間配制器贴谎、分配器（allocator）其中主要工作包括兩部分1.對象的創(chuàng)建與銷毀2.內(nèi)存的獲取與釋放。
2.1 ?部件之間的關(guān)系
三季稳、整個課程目錄：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （完）
? ? ? ? ? ? ?第一課：體系結(jié)構(gòu)與內(nèi)核分析
? ? ? ?在C++標準中擅这，STL被組織為下面的17個頭文件：<algorithm>、<deque>景鼠、<functional>仲翎、<iterator>、<array>铛漓、<vector>溯香、<list>、浓恶、玫坛、、包晰、<numeric>湿镀、<queue>、<set>伐憾、勉痴、<stack>和<utility>。
? ? ? ?C++標準庫頭文件header不包含副檔名
? ? ? 如：#include不包含.h后綴
? ? ? ?新式C庫也不包含副檔名树肃。#include
幾個重要的C++網(wǎng)站：
? ? ? ? cplusplus.com
? ? ? ? cppReference.com
? ? ? ? gcc.gnu.org
程序復(fù)雜度O(n)：n需要很大蒸矛，工業(yè)級的，比如幾十萬幾百萬數(shù)據(jù)量胸嘴，才能體現(xiàn)線性復(fù)雜度莉钙。
標準庫容器迭代器采用前閉后開區(qū)間[ a,b)。
不能對c.end()取內(nèi)容筛谚。*c.end() //(X)
容器在內(nèi)存中不一定連續(xù)磁玉。
新版本（since C++11）容器遍歷：
1容器的分類和內(nèi)存結(jié)構(gòu)
1.1容器的分類
容器大致可以分為兩種；Sequence containers和associative containers兩大類
一驾讲、Sequence
containers:有序的容器蚊伞；
----------------------------------------------------------------------------------------------------------------------
1席赂、如數(shù)組的類實現(xiàn)array（在內(nèi)存中順序排放，并且長度不能動態(tài)改變时迫。）颅停、
2、Vector：當空間不夠時掠拳，分配器會自動向后擴充空間
3癞揉、deque（讀daike）：雙頭隊列。
1,2,3這些容器在內(nèi)存中連續(xù)
4溺欧、list：雙向鏈表喊熟，空間在內(nèi)存中不連續(xù)
----------------------------------------------------------------------------------------------------------------------
二、associative containers：查找效率高姐刁。
在STL內(nèi)部芥牌，set用紅黑樹實現(xiàn)
Set/multiSet: ? Map/multiMap
Set和Map中數(shù)據(jù)元素不能重復(fù)
multiSet和multiMap中數(shù)據(jù)元素可以重復(fù)
1.2 ?容器Array的使用：
使用,很方便,用起來和STL一樣;執(zhí)行效率比高,幾乎和
int myarray[5]效率一樣。當你想要一個執(zhí)行時效率高,而用不想自己管理內(nèi)存的時候,就用它聂使。Array在內(nèi)存中是連續(xù)排列的壁拉。可以使用[]操作符或c.at(i)索引數(shù)組元素柏靶。包含頭文件：#include
實測：類型和大小相同的Array對象可以相互賦值弃理，且拷貝賦值之后彼此不影響。屬于深拷貝屎蜓。
arrayc;
array a,b;
a[0] = 1
b = a;?
1.3容器Vector的使用：
Vector是一端開口的數(shù)組痘昌，每次擴充以2倍增長。
? ? ? ?擴充：即成長梆靖，這個過程是非常緩慢的，存在內(nèi)存拷貝笔诵。當當前空間Aspace不夠用時返吻，在另外一個地方重新開辟一個大小為2*space的空間B，將A中元素拷貝到B乎婿，然后清理掉A测僵。
定義自動變量pItem；
? ? ?同時調(diào)用全局函數(shù)：：find()順序查找值為target的元素地址谢翎。
通過*pItem就可獲得值捍靠。
在c++中，vector是一個十分有用的容器森逮。
1基本操作
(1)頭文件#include.
(2)創(chuàng)建vector對象榨婆，vectorvec;
(3)尾部插入數(shù)字：vec.push_back(a);
(4)使用下標訪問元素，cout<
(5)使用迭代器訪問元素.
vector::iteratorit;
for(it=vec.begin();it!=vec.end();it++)
cout<<*it<
(6)插入元素：vec.insert(vec.begin()+i,a);在第i+1個元素前面插入a;
(7)刪除元素：vec.erase(vec.begin()+2);刪除第3個元素
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就是一雙向鏈表褒侧，可高效地進行插入良风、刪除元素操作谊迄。
list不支持隨機訪問。所以沒有at(pos)和operator[]烟央。
List本身提供sort函數(shù)统诺。這是排序算法最好采用內(nèi)部sort成員函數(shù)。
有些容器沒有提供sort成員函數(shù)疑俭，如vector粮呢、array。
標準庫提供的：：find()函數(shù)是
順序查找钞艇。
1.5容器deque的使用：
deque雙向隊列是一種雙向開口的連續(xù)線性空間啄寡，可以高效的在頭尾兩端插入和刪除元素，deque在接口上和vector非常相似香璃。
deque的實現(xiàn)比較復(fù)雜这难，內(nèi)部會維護一個map（注意！不是STL中的map容器）即一小塊連續(xù)的空間葡秒，該空間中每個元素都是指針姻乓，指向另一段（較大的）區(qū)域，這個區(qū)域稱為緩沖區(qū)眯牧，緩沖區(qū)用來保存deque中的數(shù)據(jù)蹋岩。因此deque在隨機訪問和遍歷數(shù)據(jù)會比vector慢。具體的deque實現(xiàn)可以參考《STL源碼剖析》学少。
Deque在內(nèi)存中是分段連續(xù)的剪个，但在使用者用起來是沒有這種“分段連續(xù)”的感受，
我們在使用++操作符作用在deque對象版确。
下面給出deque的使用范例：
```
//雙向隊列 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在計算機中就是賦值的意思
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)部實現(xiàn)都包含一個deque扣囊。因此，queue和stack都可以看做是特殊的deque绒疗。
1.6容器set和multiset的使用（關(guān)聯(lián)式容器）：
紅黑樹和哈希表侵歇。作為數(shù)據(jù)結(jié)構(gòu)，非常適用于需要大量查找的場合吓蘑。
元素就是key惕虑，key就是元素。
set和multiset會根據(jù)特定的排序準則磨镶，自動將元素進行排序溃蔫。不同的是multiset允許元素重復(fù)而set不允許。只要是可復(fù)賦值琳猫、可拷貝伟叛、可以根據(jù)某個排序準則進行比較的型別都可以成為它們的元素。第二個參數(shù)用來定義排序準則脐嫂。缺省準則less是一個仿函數(shù)痪伦。
和所有關(guān)聯(lián)式容器類似侄榴，通常使用平衡二叉樹完成。事實上网沾，set和multiset通常以紅黑樹實作而成癞蚕。
自動排序的優(yōu)點是使得搜尋元素時具有良好的性能，具有對數(shù)時間復(fù)雜度辉哥。但是造成的一個缺點就是：
不能直接改變元素值桦山。因為這樣會打亂原有的順序。
改變元素值的方法是：先刪除舊元素醋旦，再插入新元素恒水。
存取元素只能通過迭代器，從迭代器的角度看饲齐，元素值是常數(shù)钉凌。
用STL的算法：：find()查找元素和用MultiSet自身的find（）成員函數(shù)查找速度對比：
1.7容器map和multimap的使用（關(guān)聯(lián)式容器）：
每一個元素包含一個key，通過key來查找元素捂人。
1.8容器unordered_multiset的使用（關(guān)聯(lián)式容器）：
Hash table.
Hash
table籃子一定比元素多御雕，大概是元素的2倍 。
新版本STL中用unordered_XXX代替了舊版本的hash_XXX
2 ?分配器
? ? ? 容器內(nèi)部需要分配器來管理內(nèi)存滥搭。
