STL與泛型編程
一咒林、STL是什么
STL（Standard TemplateLibrary），即標準模板庫，是一個具有工業(yè)強度的锤岸，高效的C++程序庫集漾。它被容納于C++標準程序庫（C++ Standard Library）中切黔，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法具篇。為廣大C++程序員們提供了一個可擴展的應用框架纬霞，高度體現(xiàn)了軟件的可復用性。
從邏輯層次來看驱显，在STL中體現(xiàn)了泛型化程序設計的思想（generic programming）诗芜，引入了諸多新的名詞，比如像需求（requirements）埃疫，概念（concept）伏恐，模型（model），容器（container）栓霜，算法（algorithmn）翠桦，迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣胳蛮，泛型也是一種軟件的復用技術销凑；
從實現(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)和類型無關罪佳，因此他們可以在從簡單數(shù)組到高度復雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用；
** 仿函數(shù)（Functionobject娃兽，仿函數(shù)(functor)又稱之為函數(shù)對象（function object）菇民，其實就是重載了()操作符的struct，沒有什么特別的地方
** 迭代適配器（Adaptor）
** 空間配制器、分配器（allocator*）其中主要工作包括兩部分1.對象的創(chuàng)建與銷毀2.內(nèi)存的獲取與釋放第练。
2.1 部件之間的關系
三阔馋、整個課程目錄：
（***完***）* 第一課：體系結(jié)構(gòu)與內(nèi)核分析 在C++標準中，STL被組織為下面的17個頭文件：<[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++標準庫頭文件header不包含副檔名 如：#include不包含.h后綴 新式C庫也不包含副檔名暇屋。#include
幾個重要的C++網(wǎng)站：
* ** cplusplus.com***
*** cppReference.com***
*** gcc.gnu.org***
程序復雜度O(n)：n需要很大，工業(yè)級的洞辣，比如幾十萬幾百萬數(shù)據(jù)量咐刨，才能體現(xiàn)線性復雜度。
標準庫容器迭代器采用前閉后開區(qū)間[ a,b)屋彪。
不能對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ù)組的類實現(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ù)元素不能重復
multiSet和multiMap中數(shù)據(jù)元素可以重復
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不夠用時，在另外一個地方重新開辟一個大小為2space的空間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)比較復雜，內(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的使用（關聯(lián)式容器）：
紅黑樹和哈希表。作為數(shù)據(jù)結(jié)構(gòu)我抠，非常適用于需要大量查找的場合苇本。
元素就是key，key就是元素菜拓。
set和multiset會根據(jù)特定的排序準則瓣窄，自動將元素進行排序。不同的是multiset****允許元素重復而set****不允許纳鼎。只要是可復賦值俺夕、可拷貝、可以根據(jù)某個排序準則進行比較的型別都可以成為它們的元素喷橙。第二個參數(shù)用來定義排序準則啥么。缺省準則less是一個仿函數(shù)登舞。
和所有關聯(lián)式容器類似贰逾，通常使用平衡二叉樹完成。事實上菠秒，set和multiset通常以紅黑樹實作而成疙剑。
自動排序的優(yōu)點是使得搜尋元素時具有良好的性能****氯迂，具有對數(shù)時間復雜度。但是造成的一個缺點就是：
不能直接改變元素值言缤。因為這樣會打亂原有的順序嚼蚀。
改變元素值的方法是：先刪除舊元素，再插入新元素管挟。
存取元素只能通過迭代器轿曙，從迭代器的角度看，元素值是常數(shù)僻孝。
用STL的算法：：find()查找元素和用MultiSet自身的find（）成員函數(shù)查找速度對比：
1.7容器map和multimap的使用（關聯(lián)式容器）：
每一個元素包含一個key导帝，通過key來查找元素。
1.8容器unordered_multiset的使用（關聯(lián)式容器）：
Hash table.
Hash
table籃子一定比元素多穿铆，大概是元素的2倍 您单。
新版本STL中用unordered_XXX代替了舊版本的hash_XXX
2 分配器
容器內(nèi)部需要分配器來管理內(nèi)存。
