STL與泛型編程
一、STL是什么
? ? ? ? ?STL（Standard TemplateLibrary），即標準模板庫，是一個具有工業(yè)強度的，高效的C++程序庫。它被容納于C++標準程序庫（C++ Standard Library）中，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域里所常用的基本數據結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架，高度體現了軟件的可復用性。
? ? ? ? 從邏輯層次來看，在STL中體現了泛型化程序設計的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復用技術；
? ? ? ? 從實現層次看，整個STL是以一種類型參數化（type parameterized）的方式實現的，這種方式基于一個在早先C++標準中沒有出現的語言特性--模板（template）。如果查閱任何一個版本的STL源代碼，你就會發(fā)現，模板作為構成整個STL的基石是一件千真萬確的事情。除此之外，還有許多C++的新特性為STL的實現提供了方便；
二、STL的六大組件
STL：主要包含6個parts：
? ? ? ?容器（Container），是一種數據結構，如list，vector，和deque，以模板類的方法提供。為了訪問容器中的數據，可以使用由容器類輸出的迭代器（有的容器不含迭代器，如queue，stack）；
? ? ? ? 迭代器（Iterator），提供了訪問容器中對象的方法。例如，可以使用一對迭代器指定list或vector中的一定范圍的對象。迭代器就如同一個指針。事實上，C++的指針也是一種迭代器。但是，迭代器也可以是那些定義了operator*()以及其他類似于指針的操作符地方法的類對象；
? ? ? ? 算法（Algorithm），是用來操作容器中的數據的模板函數。例如，STL用sort()來對一個vector中的數據進行排序，用find()來搜索一個list中的對象，函數本身與他們操作的數據的結構和類型無關，因此他們可以在從簡單數組到高度復雜容器的任何數據結構上使用；
? ? ? ? 仿函數（Functionobject，仿函數(functor)又稱之為函數對象（function object），其實就是重載了()操作符的struct，沒有什么特別的地方
? ? ? ?迭代適配器（Adaptor）
? ? ? 空間配制器、分配器（allocator）其中主要工作包括兩部分1.對象的創(chuàng)建與銷毀2.內存的獲取與釋放。
2.1 ?部件之間的關系
三、整個課程目錄：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （完）
? ? ? ? ? ? ?第一課：體系結構與內核分析
? ? ? ?在C++標準中，STL被組織為下面的17個頭文件：<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、、、、、<numeric>、<queue>、<set>、、<stack>和<utility>。
? ? ? ?C++標準庫頭文件header不包含副檔名
? ? ? 如：#include不包含.h后綴
? ? ? ?新式C庫也不包含副檔名。#include
幾個重要的C++網站：
? ? ? ? cplusplus.com
? ? ? ? cppReference.com
? ? ? ? gcc.gnu.org
程序復雜度O(n)：n需要很大，工業(yè)級的，比如幾十萬幾百萬數據量，才能體現線性復雜度。
標準庫容器迭代器采用前閉后開區(qū)間[ a,b)。
不能對c.end()取內容。*c.end() //(X)
容器在內存中不一定連續(xù)。
新版本（since C++11）容器遍歷：
1容器的分類和內存結構
1.1容器的分類
容器大致可以分為兩種；Sequence containers和associative containers兩大類
一、Sequence
containers:有序的容器；
----------------------------------------------------------------------------------------------------------------------
1、如數組的類實現array（在內存中順序排放，并且長度不能動態(tài)改變。）、
2、Vector：當空間不夠時，分配器會自動向后擴充空間
3、deque（讀daike）：雙頭隊列。
1,2,3這些容器在內存中連續(xù)
4、list：雙向鏈表，空間在內存中不連續(xù)
----------------------------------------------------------------------------------------------------------------------
二、associative containers：查找效率高。
在STL內部，set用紅黑樹實現
Set/multiSet: ? Map/multiMap
Set和Map中數據元素不能重復
multiSet和multiMap中數據元素可以重復
1.2 ?容器Array的使用：
使用,很方便,用起來和STL一樣;執(zhí)行效率比高,幾乎和
int myarray[5]效率一樣。當你想要一個執(zhí)行時效率高,而用不想自己管理內存的時候,就用它。Array在內存中是連續(xù)排列的?？梢允褂肹]操作符或c.at(i)索引數組元素。包含頭文件：#include
實測：類型和大小相同的Array對象可以相互賦值，且拷貝賦值之后彼此不影響。屬于深拷貝。
arrayc;
array a,b;
a[0] = 1
b = a;?
1.3容器Vector的使用：
Vector是一端開口的數組，每次擴充以2倍增長。
? ? ? ?擴充：即成長，這個過程是非常緩慢的，存在內存拷貝。當當前空間Aspace不夠用時，在另外一個地方重新開辟一個大小為2*space的空間B，將A中元素拷貝到B，然后清理掉A。
定義自動變量pItem；
? ? ?同時調用全局函數：：find()順序查找值為target的元素地址。
通過*pItem就可獲得值。
在c++中，vector是一個十分有用的容器。
1基本操作
(1)頭文件#include.
(2)創(chuàng)建vector對象，vectorvec;
(3)尾部插入數字：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函數。這是排序算法最好采用內部sort成員函數。
有些容器沒有提供sort成員函數，如vector、array。
標準庫提供的：：find()函數是
順序查找。
1.5容器deque的使用：
deque雙向隊列是一種雙向開口的連續(xù)線性空間，可以高效的在頭尾兩端插入和刪除元素，deque在接口上和vector非常相似。
deque的實現比較復雜，內部會維護一個map（注意！不是STL中的map容器）即一小塊連續(xù)的空間，該空間中每個元素都是指針，指向另一段（較大的）區(qū)域，這個區(qū)域稱為緩沖區(qū)，緩沖區(qū)用來保存deque中的數據。因此deque在隨機訪問和遍歷數據會比vector慢。具體的deque實現可以參考《STL源碼剖析》。
Deque在內存中是分段連續(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中數據:\n");
for (i = 0; i < 20; ++i)
printf("%d ", ideq[i]);
putchar('\n');
//在頭尾加入新數據
printf("\n在頭尾加入新數據...\n");
ideq.push_back(100);
ideq.push_front(i);
//輸出deque
printf("\n輸出deque中數據:\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");
//在頭尾刪除數據
printf("\n在頭尾刪除數據...\n");
ideq.pop_back();
ideq.pop_front();
//輸出deque
printf("\n輸出deque中數據:\n");
for (pos = ideq.begin(); pos != ideq.end(); pos++)
printf("%d ", *pos);
putchar('\n');
return 0;
}
```
Queue和stack的內部實現都包含一個deque。因此，queue和stack都可以看做是特殊的deque。
1.6容器set和multiset的使用（關聯式容器）：
紅黑樹和哈希表。作為數據結構，非常適用于需要大量查找的場合。
元素就是key，key就是元素。
set和multiset會根據特定的排序準則，自動將元素進行排序。不同的是multiset允許元素重復而set不允許。只要是可復賦值、可拷貝、可以根據某個排序準則進行比較的型別都可以成為它們的元素。第二個參數用來定義排序準則。缺省準則less是一個仿函數。
和所有關聯式容器類似，通常使用平衡二叉樹完成。事實上，set和multiset通常以紅黑樹實作而成。
自動排序的優(yōu)點是使得搜尋元素時具有良好的性能，具有對數時間復雜度。但是造成的一個缺點就是：
不能直接改變元素值。因為這樣會打亂原有的順序。
改變元素值的方法是：先刪除舊元素，再插入新元素。
存取元素只能通過迭代器，從迭代器的角度看，元素值是常數。
用STL的算法：：find()查找元素和用MultiSet自身的find（）成員函數查找速度對比：
1.7容器map和multimap的使用（關聯式容器）：
每一個元素包含一個key，通過key來查找元素。
1.8容器unordered_multiset的使用（關聯式容器）：
Hash table.
Hash
table籃子一定比元素多，大概是元素的2倍 。
新版本STL中用unordered_XXX代替了舊版本的hash_XXX
2 ?分配器
? ? ? 容器內部需要分配器來管理內存。
