一、前言

STL：Standard Template Library(標(biāo)準(zhǔn)模板庫(kù)或泛型庫(kù))，是C++標(biāo)準(zhǔn)庫(kù)的組成部分。STL借助模板把常用的數(shù)據(jù)結(jié)構(gòu)及其算法實(shí)現(xiàn)了一次，并且做到了數(shù)據(jù)結(jié)構(gòu)和算法的分離。STL已完全被內(nèi)置到支持 C++ 的編譯器中，無(wú)需額外安裝，這可能也是STL被廣泛使用的原因之一。STL是以源代碼的形式提供的。根本上來(lái)說(shuō)，STL是一些容器（封裝有數(shù)據(jù)結(jié)構(gòu)的模板類(lèi)）、算法和其他的一些組件的集合，基本達(dá)到了各種存儲(chǔ)方法和相關(guān)算法的高度優(yōu)化。

STL的版本

HP STL

Alexandar Stepanov（STL 標(biāo)準(zhǔn)模板庫(kù)之父）與 Meng Lee 合作完成。是開(kāi)放源碼的。

SGI STL

HP STL的一個(gè)繼承版本，開(kāi)源、可讀性好

STLport

為了使 SGI STL 的基本代碼都適用于 VC++ 和 C++ Builder 等多種編譯器而提出的，開(kāi)源

PL STL

參照 HP STL 實(shí)現(xiàn)出來(lái)的，也是 HP STL 的一個(gè)繼承版本，因此該頭文件中不僅含有 HP STL 的相關(guān)授權(quán)信息，同時(shí)還有 P.J.Plauger 本人的版權(quán)信息。非開(kāi)源。

Rouge Wave STL

由 Rouge Wave 公司開(kāi)發(fā)的，也是繼承 HP STL 的一個(gè)版本，它也不是開(kāi)源的。

二、STL的基本組成

STL是由容器、算法、迭代器、函數(shù)對(duì)象、適配器、內(nèi)存分配器6部分構(gòu)成，其中迭代器、函數(shù)對(duì)象、適配器、內(nèi)存分配器是為容器、算法服務(wù)。

在 C++ 標(biāo)準(zhǔn)中，STL被重新組織為13個(gè)頭文件，如下：

注意：
或許是為了向下兼容，或許是為了內(nèi)部組織規(guī)劃，某些 STL 版本同時(shí)存儲(chǔ)具備擴(kuò)展名和無(wú)擴(kuò)展名的兩份文件，建議最好遵照C++規(guī)范，使用無(wú)擴(kuò)展名的頭文件。

三、容器是什么

在實(shí)際的開(kāi)發(fā)過(guò)程中，存取數(shù)據(jù)的方式會(huì)直接影響到對(duì)它們進(jìn)行增刪改查操作的復(fù)雜程度和時(shí)間消耗。
簡(jiǎn)單的理解容器，就是一些模板類(lèi)的集合，但和普通模板類(lèi)不同的是，容器中封裝的是組織數(shù)據(jù)的方法（也就是數(shù)據(jù)結(jié)構(gòu)）。STL 提供有3類(lèi)標(biāo)準(zhǔn)容器，分別是序列容器、排序容器和哈希容器，其中后兩類(lèi)容器有時(shí)也統(tǒng)稱(chēng)為關(guān)聯(lián)容器，如下表：

以上3類(lèi)容器的存儲(chǔ)方式完全不同，因此使用不同容器完成相同操作的效率也大不相同。因此在實(shí)際使用中，要根據(jù)具體的功能選擇最適合的容器。

四、迭代器

無(wú)論是序列容器還是關(guān)聯(lián)容器，最常做的操作無(wú)疑是遍歷容器中存儲(chǔ)的元素，而實(shí)現(xiàn)此操作，多數(shù)情況會(huì)選用“迭代器（iterator）”來(lái)實(shí)現(xiàn)。
雖然不同容器的內(nèi)部結(jié)構(gòu)各異，但它們本質(zhì)上都是用來(lái)存儲(chǔ)大量數(shù)據(jù)的，所以容器有一些操作方法是類(lèi)似的，因此完全可以利用泛型的技術(shù)，將其設(shè)計(jì)成適用所有容器的通用算法，從未將容器和算法分離。

1、迭代器類(lèi)別

STL標(biāo)準(zhǔn)庫(kù)為每一種標(biāo)準(zhǔn)容器定義了一種迭代器類(lèi)型，即不同容器的迭代器不同，因此容器的迭代器功能的強(qiáng)弱也不同，進(jìn)而決定了容器是否哦支持STL中的某些算法。
常用的迭代器按功能強(qiáng)弱分為輸入迭代器、輸出迭代器、前向迭代器、雙向迭代器、隨機(jī)訪問(wèn)迭代器 5 種。輸入迭代器和輸出迭代器比較特殊，它們不是把數(shù)組或容器當(dāng)做操作對(duì)象，而是把輸入流/輸出流作為操作對(duì)象。關(guān)于輸入迭代器和輸出迭代器在這里暫時(shí)不多講。

假設(shè)存在一個(gè)迭代器Iter

1）前向迭代器（forward iterator）

Iter支持++Iter、Iter++、*Iter操作、被復(fù)制或賦值、可使用==和!=運(yùn)算符進(jìn)行比較

2）雙向迭代器（bidirectional iterator）

雙向迭代器具有正向迭代器的全部功能，除此之外，還可以進(jìn)行 --Iter 或者 Iter-- 操作（即一次向后移動(dòng)一個(gè)位置）。

3）隨機(jī)訪問(wèn)迭代器（random access iterator）

隨機(jī)訪問(wèn)迭代器具有雙向迭代器的全部功能。除此之外，假設(shè) i 是一個(gè)整型變量或常量，則 Iter 還支持以下操作：

兩個(gè)隨機(jī)訪問(wèn)迭代器 p1、p2 還可以用 <、>、<=、>= 運(yùn)算符進(jìn)行比較。另外，表達(dá)式 p2-p1 也是有定義的，其返回值表示 p2 所指向元素和 p1 所指向元素的序號(hào)之差。

五、容器對(duì)應(yīng)的迭代器

1、對(duì)應(yīng)關(guān)系

注意：
容器適配器 stack 和 queue 沒(méi)有迭代器，它們包含有一些成員函數(shù)，可以用來(lái)對(duì)元素進(jìn)行訪問(wèn)。

2、迭代器的定義方式

說(shuō)明：
*迭代器名：迭代器指向的元素
常量迭代器和非常量迭代器的分別在于：通過(guò)非常量迭代器還能修改其指向的元素
反向迭代器和正向迭代器的區(qū)別在于：對(duì)正向迭代器進(jìn)行 ++ 操作時(shí)，迭代器會(huì)指向容器中的后一個(gè)元素；而對(duì)反向迭代器進(jìn)行 ++ 操作時(shí)，迭代器會(huì)指向容器中的前一個(gè)元素。
以上 4 種定義迭代器的方式，并不是每個(gè)容器都適用。

六、總結(jié)

序列式容器.png

關(guān)聯(lián)式容器.png

無(wú)序關(guān)聯(lián)式容器.png

適配器.png

迭代器適配器.png