C++ 的標(biāo)準(zhǔn)模板庫(kù)（Standard Template Library，STL）是泛型程序設(shè)計(jì)最成功應(yīng)用的實(shí)例。STL 是一些常用數(shù)據(jù)結(jié)構(gòu)（如鏈表、可變長(zhǎng)數(shù)組、排序二叉樹）和算法（如排序袍辞、查找）的模板的集合。

容器用于存放數(shù)據(jù)的類模板常摧。
可變長(zhǎng)數(shù)組搅吁、鏈表、平衡二叉樹等數(shù)據(jù)結(jié)構(gòu)在 STL 中都被實(shí)現(xiàn)為容器落午。
程序員使用容器時(shí)谎懦，即將容器類模板實(shí)例化為容器類時(shí)，會(huì)指明容器中存放的元素是什么類型的溃斋。
容器中可以存放基本類型的變量界拦，也可以存放對(duì)象。對(duì)象或基本類型的變量被插入容器中時(shí)梗劫，實(shí)際插入的是對(duì)象或變量的一個(gè)復(fù)制品享甸。

STL 中的許多算法（即函數(shù)模板），如排序梳侨、查找等算法蛉威，在執(zhí)行過程中會(huì)對(duì)容器中的元素進(jìn)行比較。這些算法在比較元素是否相等時(shí)通常用運(yùn)算符進(jìn)行走哺，比較大小通常用<運(yùn)算符進(jìn)行蚯嫌，因此，被放入容器的對(duì)象所屬的類最好重載==和<運(yùn)算符丙躏，以使得兩個(gè)對(duì)象用==和<進(jìn)行比較是有定義的择示。

19.1 容器分為兩大類：

1、順序容器
順序容器有以下三種：可變長(zhǎng)動(dòng)態(tài)數(shù)組 vector晒旅、雙端隊(duì)列 deque栅盲、雙向鏈表 list。
之所以被稱為順序容器敢朱，是因?yàn)樵卦谌萜髦械奈恢猛氐闹禑o(wú)關(guān)剪菱，即容器不是排序的摩瞎。將元素插入容器時(shí)拴签，指定在什么位置（尾部孝常、頭部或中間某處）插入，元素就會(huì)位于什么位置蚓哩。
2构灸、關(guān)聯(lián)容器
關(guān)聯(lián)容器有以下四種：set、multiset岸梨、map喜颁、multimap。
關(guān)聯(lián)容器內(nèi)的元素是排序的曹阔。插入元素時(shí)半开，容器會(huì)按一定的排序規(guī)則將元素放到適當(dāng)?shù)奈恢蒙希虼瞬迦朐貢r(shí)不能指定位置赃份。默認(rèn)情況下寂拆，關(guān)聯(lián)容器中的元素是從小到大排序（或按關(guān)鍵字從小到大排序）的，而且用<運(yùn)算符比較元素或關(guān)鍵字大小抓韩。因?yàn)槭桥藕眯虻木烙溃躁P(guān)聯(lián)容器在查找時(shí)具有非常好的性能。

除了以上兩類容器外谒拴，STL 還在兩類容器的基礎(chǔ)上屏蔽一部分功能尝江，突出或增加另一部分功能，實(shí)現(xiàn)了三種容器適配器：棧 stack英上、隊(duì)列 queue炭序、優(yōu)先級(jí)隊(duì)列 priority_queue。

所有容器都有以下兩個(gè)成員函數(shù)：

int size()：返回容器對(duì)象中元素的個(gè)數(shù)苍日。
bool empty()：判斷容器對(duì)象是否為空少态。

順序容器和關(guān)聯(lián)容器還有以下成員函數(shù)：

begin()：返回指向容器中第一個(gè)元素的迭代器。
end()：返回指向容器中最后一個(gè)元素后面的位置的迭代器易遣。
rbegin()：返回指向容器中最后一個(gè)元素的反向迭代器彼妻。
rend()：返回指向容器中第一個(gè)元素前面的位置的反向迭代器。
erase(...)：從容器中刪除一個(gè)或幾個(gè)元素豆茫。該函數(shù)參數(shù)較復(fù)雜侨歉，此處省略。
clear()：從容器中刪除所有元素揩魂。

如果一個(gè)容器是空的幽邓，則 begin() 和 end() 的返回值相等，rbegin() 和 rend() 的返回值也相等火脉。

順序容器還有以下常用成員函數(shù)：

front()：返回容器中第一個(gè)元素的引用牵舵。
back()：返回容器中最后一個(gè)元素的引用柒啤。
push_back()：在容器末尾增加新元素。
pop_back()：刪除容器末尾的元素畸颅。
insert(...)：插入一個(gè)或多個(gè)元素担巩。

19.2 STL迭代器(iterator)詳解

要訪問順序容器和關(guān)聯(lián)容器中的元素，需要通過iterator進(jìn)行没炒。iterator是一個(gè)變量涛癌，相當(dāng)于容器和操縱容器的算法之間的中介。迭代器可以指向容器中的某個(gè)元素送火，通過迭代器就可以讀寫它指向的元素拳话。從這一點(diǎn)上看，迭代器和指針類似种吸。

迭代器按照定義方式分成以下四種弃衍。

1) 正向迭代器，定義方法如下：
容器類名::iterator  迭代器名;

2) 常量正向迭代器坚俗，定義方法如下：
容器類名::const_iterator  迭代器名;

3) 反向迭代器镜盯，定義方法如下：
容器類名::reverse_iterator  迭代器名;

4) 常量反向迭代器，定義方法如下：
容器類名::const_reverse_iterator  迭代器名;

迭代器用法示例通過迭代器可以讀取它指向的元素坦冠，*迭代器名就表示迭代器指向的元素形耗。通過非常量迭代器還能修改其指向的元素。

迭代器都可以進(jìn)行++操作辙浑。反向迭代器和正向迭代器的區(qū)別在于：
1激涤、對(duì)正向迭代器進(jìn)行++操作時(shí)，迭代器會(huì)指向容器中的后一個(gè)元素判呕；
2倦踢、而對(duì)反向迭代器進(jìn)行++操作時(shí)，迭代器會(huì)指向容器中的前一個(gè)元素侠草。

實(shí)例：迭代器遍歷一個(gè) vector 容器

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v;  //v是存放int類型變量的可變長(zhǎng)數(shù)組辱挥，開始時(shí)沒有元素
    for (int n = 0; n<5; ++n)
        v.push_back(n);  //push_back成員函數(shù)在vector容器尾部添加一個(gè)元素
    vector<int>::iterator i;  //定義正向迭代器
    for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍歷容器
        cout << *i << " ";  //*i 就是迭代器i指向的元素
    }
    cout << endl;
    //用反向迭代器遍歷容器
    for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
        cout << *j << " ";
    return 0;
}

運(yùn)行結(jié)果.png

注意：
1、寫前置++相比于寫后置++边涕，程序的執(zhí)行速度更快晤碘。
2、后置++要多生成一個(gè)局部對(duì)象 tmp功蜓，因此執(zhí)行速度比前置的慢园爷。同理，迭代器是一個(gè)對(duì)象式撼，STL 在重載迭代器的++運(yùn)算符時(shí)童社，后置形式也比前置形式慢。在次數(shù)很多的循環(huán)中著隆，我們提倡使用前置++扰楼。
3呀癣、容器適配器 stack、queue 和 priority_queue 沒有迭代器弦赖。容器適配器有一些成員函數(shù)项栏，可以用來(lái)對(duì)元素進(jìn)行訪問。

19.3 迭代器的功能分類

不同容器的迭代器腾节，其功能強(qiáng)弱有所不同忘嫉。容器的迭代器的功能強(qiáng)弱荤牍，決定了該容器是否支持 STL 中的某種算法案腺。例如，排序算法需要通過隨機(jī)訪問迭代器來(lái)訪問容器中的元素康吵，因此有的容器就不支持排序算法劈榨。

常用的迭代器按功能強(qiáng)弱分為輸入、輸出晦嵌、正向同辣、雙向、隨機(jī)訪問五種惭载，我們介紹三種應(yīng)用度較高的旱函。

1、正向迭代器描滔。假設(shè) p 是一個(gè)正向迭代器棒妨，則 p 支持以下操作：++p，p++含长，*p券腔。此外，兩個(gè)正向迭代器可以互相賦值拘泞，還可以用==和!=運(yùn)算符進(jìn)行比較纷纫。
2、雙向迭代器陪腌。雙向迭代器具有正向迭代器的全部功能辱魁。除此之外，若 p 是一個(gè)雙向迭代器诗鸭，則--p和p--都是有定義的染簇。--p使得 p 朝和++p相反的方向移動(dòng)。
3只泼、隨機(jī)訪問迭代器剖笙。隨機(jī)訪問迭代器具有雙向迭代器的全部功能。若 p 是一個(gè)隨機(jī)訪問迭代器请唱，i 是一個(gè)整型變量或常量弥咪，則 p 還支持以下操作：

p+=i：使得 p 往后移動(dòng) i 個(gè)元素过蹂。
p-=i：使得 p 往前移動(dòng) i 個(gè)元素。
p+i：返回 p 后面第 i 個(gè)元素的迭代器聚至。
p-i：返回 p 前面第 i 個(gè)元素的迭代器酷勺。
p[i]：返回 p 后面第 i 個(gè)元素的引用。

對(duì)于隨機(jī)訪問迭代器還要注意：
1扳躬、兩個(gè)隨機(jī)訪問迭代器 p1脆诉、p2 還可以用 <、>贷币、<=击胜、>= 運(yùn)算符進(jìn)行比較。p1<p2的含義是：p1 經(jīng)過若干次（至少一次）++操作后役纹，就會(huì)等于 p2偶摔。其他比較方式的含義與此類似。
2促脉、對(duì)于兩個(gè)隨機(jī)訪問迭代器 p1辰斋、p2，表達(dá)式p2-p1也是有定義的瘸味，其返回值是 p2 所指向元素和 p1 所指向元素的序號(hào)之差（也可以說(shuō)是 p2 和 p1 之間的元素個(gè)數(shù)減一）宫仗。

迭代器功能.png

vector 的迭代器是隨機(jī)迭代器例程：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v(5); //v被初始化成有5個(gè)元素
    for(int i = 0; i < v.size(); ++i) //size返回元素個(gè)數(shù)
    {
        cout << v[i]; //像普通數(shù)組一樣使用vector容器
    }
    cout << endl;

    vector<int>::iterator i;
    for(i = v.begin(); i != v.end(); ++i) //用 != 比較兩個(gè)迭代器
    {
        cout << *i;
    }
    cout << endl;

    for(i = v.begin(); i < v.end();++i) //用 < 比較兩個(gè)迭代器
    {
        cout << *i;
    }
    cout << endl;

    i = v.begin();
    while(i < v.end()) { //間隔一個(gè)輸出
        cout << *i;
        i += 2; // 隨機(jī)訪問迭代器支持 "+= 整數(shù)"  的操作
    }
}

運(yùn)行結(jié)果.png

list 容器的迭代器是雙向迭代器
如定義如下：

list<int> v;
list<int>::const_iterator i;

則以下代碼是合法的：

for(i=v.begin(); i!=v.end(); ++i)   cout << *i;

以下代碼則不合法：

for(i=v.begin(); i<v.end(); ++i)    cout << *i;

因?yàn)殡p向迭代器不支持用“<”進(jìn)行比較。以下代碼也不合法：

for(int i=0; i<v.size(); ++i)    cout << v[i];

因?yàn)?list 不支持隨機(jī)訪問迭代器的容器旁仿，也不支持用下標(biāo)隨機(jī)訪問其元素藕夫。

在 C++ 中，數(shù)組也是容器丁逝。數(shù)組的迭代器就是指針汁胆，而且是隨機(jī)訪問迭代器。
例如霜幼，對(duì)于數(shù)組 int a[10]嫩码，int * 類型的指針就是其迭代器。則 a罪既、a+1铸题、a+2 都是 a 的迭代器。

19.4 迭代器的輔助函數(shù)

STL 中有用于操作迭代器的三個(gè)函數(shù)模板琢感，涉及的頭文件 algorithm丢间，這三個(gè)函授木板是：

//使迭代器 p 向前或向后移動(dòng) n 個(gè)元素。
advance(p, n);
//計(jì)算兩個(gè)迭代器之間的距離驹针，即迭代器 p 經(jīng)過多少次 + + 操作后和迭代器 q 相等烘挫。
//如果調(diào)用時(shí) p 已經(jīng)指向 q 的后面，則這個(gè)函數(shù)會(huì)陷入死循環(huán)。
distance(p, q);
//用于交換兩個(gè)迭代器 p饮六、q 指向的值其垄。
iter_swap(p, q);

三個(gè)函數(shù)模板例程：

#include <list>
#include <iostream>
#include <algorithm> //要使用操作迭代器的函數(shù)模板，需要包含此文件
using namespace std;
int main()
{
    int a[5] = { 1, 2, 3, 4, 5 };
    list <int> lst(a, a+5);
    list <int>::iterator p = lst.begin();
    advance(p, 2);  //p向后移動(dòng)兩個(gè)元素卤橄，指向3
    cout << "1:" << *p << endl;  //輸出 1:3

    advance(p, -1);  //p向前移動(dòng)一個(gè)元素绿满，指向2
    cout << "2:" << *p << endl;  //輸出 2:2

    list<int>::iterator q = lst.end();
    q--;  //q 指向 5
    cout << "3:" << distance(p, q) << endl;  //輸出 3:3
    iter_swap(p, q); //交換 2 和 5

    cout << "4:";
    for (p = lst.begin(); p != lst.end(); ++p){
        cout << *p << " ";
    }
    return 0;
}

運(yùn)行結(jié)果.png

19.5 STL算法詳解

STL 提供能在各種容器中通用的算法（大約有70種），如插入窟扑、刪除喇颁、查找、排序等嚎货。算法就是函數(shù)模板橘霎。算法通過迭代器來(lái)操縱容器中的元素。

許多算法操作的是容器上的一個(gè)區(qū)間（也可以是整個(gè)容器）厂抖，因此需要兩個(gè)參數(shù)茎毁，一個(gè)是區(qū)間起點(diǎn)元素的迭代器克懊，另一個(gè)是區(qū)間終點(diǎn)元素的后面一個(gè)元素的迭代器忱辅。例如，排序和查找算法都需要這兩個(gè)參數(shù)來(lái)指明待排序或待查找的區(qū)間谭溉。有的算法返回一個(gè)迭代器墙懂。例如，find 算法在容器中查找一個(gè)元素扮念，并返回一個(gè)指向該元素的迭代器损搬。

算法可以處理容器，也可以處理普通的數(shù)組柜与。

有的算法會(huì)改變其所作用的容器巧勤。如：

copy：將一個(gè)容器的內(nèi)容復(fù)制到另一個(gè)容器。
remove：在容器中刪除一個(gè)元素弄匕。
random_shuffle：隨機(jī)打亂容器中的元素颅悉。
fill：用某個(gè)值填充容器。

有的算法不會(huì)改變其所作用的容器迁匠。例如：

find：在容器中查找元素剩瓶。
count_if：統(tǒng)計(jì)容器中符合某種條件的元素的個(gè)數(shù)。

STL 中的大部分常用算法都在頭文件 algorithm 中定義城丧。此外延曙，頭文件 numeric 中也有一些算法。
因?yàn)榉N類繁多亡哄，需要自行查看API文檔
這里我們就一個(gè)例子：

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()  {
    int a[10] = {5, 6, 7, 8};
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4); //此后v里放著4個(gè)元素：1,2,3,4

    vector<int>::iterator p;
    p = find(v.begin(),v.end(),3); //在v中查找3
    if(p != v.end()){ //若找不到,find返回 v.end()
        cout << "1: " <<  * p << endl; //找到了
    }

    p = find(v.begin(),v.end(),9);
    if(p == v.end()){
        cout << "沒找到 " << endl;
    }
    p = find(v.begin()+1,v.end()-1,4); //在,3 這兩個(gè)元素中查找4
    cout << "2: " << * p << endl;

    int * pp = find(a,a+4,20);

    if(pp == a + 4){
        cout << "沒找到" << endl;
    }
    else{
        cout << "3: " <<* pp << endl;
    }
}

運(yùn)行結(jié)果.png