STL 六大元件概要

• • 資料結構與算法
  • STL
    • 容器（containers）
    • 算法（algorithms）
    • 疊代器（iterators）
    • 配置器（allocators）
    • 仿函數（functors）
    • 配接器或擴充卡（adapters）

資料結構與算法

相信大家都聽過一句話：程式 = 資料結構 + 算法。

我們在寫程式時，實際上就是在對給定的資料進行一系列的操作，然後将處理的結果傳回給需要接收的地方，這裡的地方可以指程式本身，也可以指傳回給使用者，你懂我意思的。

資料結構就是各種具有相似性質或屬性的資料的一種組織關系（邏輯的關系和實體的存儲方式），無非就那幾種，

集合

、

線性結構

、

樹狀結構

和

圖狀結構或網狀結構

。而我們現實生活中遇到的絕大部分問題，都可以将我們需要處理的資料抽象組織成上述幾種結構。

算法就是處理資料的各種操作步驟的集合，常見的操作有對具有某種結構的資料集中的資料進行

排序

，或者

查找

資料集中某個指定的資料等。

這些經典的資料結構和算法都是相當成熟的，而我們實際程式開發中又經常會用到相關的資料結構或算法，如果我們每個人都去實作自己的資料結構或者算法，先不考慮我們編寫的效率如何，單就實作這些功能來說就是一個浪費時間浪費人力的工作，這樣軟體開發就會出現在不同的地點不同的人在相同的時間做着重複而無效率保證的工作。

軟體設計的目标以及金科玉律就是：複用。

STL

對于使用 C++ 為語言工具做開發的人而言，幸運的是，有那麼一幫大神幫我們實作了一個叫 STL（Standard Template Library） 的東西，也就是标準模闆庫，是泛型程式設計的一個很好的執行個體或實踐。為什麼要用模闆？因為模闆可以通用，你想處理什麼類型的資料都可以，包括内置類型或者使用者自定義類型等，這麼一本萬利的東西，你說要不要用？

STL 為我們實作了一系列的資料結構以及一些典型的算法，而且效率肯定是有保證的，畢竟是大神設計的，是以我們大可肆無忌憚的使用 STL 為我們提供的東西，而不是重複造輪子（關鍵是造出來的沒别人的好）。

STL 就是一種高複用的軟體産品。

容器（containers）

當然，STL 并不是簡單的為我們實作各種資料結構提供給我們直接使用，而是将這些不同的資料結構設計為各種不同的容器，我們都知道容器是用來盛東西用的，比如碗用來盛飯、水杯用來盛水等，這裡的碗和水杯就是兩種不同的容器。而 STL 為我們提供的容器實際上就是用來存放我們需要處理的資料，具有不同結構的資料使用不同的容器，每一種容器就相當于是一種資料結構。

STL 中的容器是一種

class template

，常見的容器有

vector

、

list

、

deque

、

set

以及

map

等。

算法（algorithms）

有了資料，接下來就是對這些資料進行各種處理了，STL 為我們提供了各種常用的算法，如

sort

、

search

、

copy

、

erase

… 當然，某些容器也根據自身的特點實作了适應于本容器特性的算法或操作（比通用算法中更高效），成為其成員函數。是以，對于同一個算法，如果标準庫和容器本身都提供了，那麼我們優先使用容器本身提供的那個，這樣在效率上更有保證。

STL 算法是一種

function template

。

現在有個問題，對于容器本身實作的那些算法，由于其是容器的成員函數，是以自然而然的可以通路并操作容器内部的資料，那對于那些通用的算法呢？如何通路到容器内部的資料？資料可是容器私有的，外界不能直接通路。

為了解決這個問題，就需要一個中間橋梁，使算法能夠有辦法通路到給定容器中的資料。而 STL 所設計的這個橋梁就是疊代器。

疊代器（iterators）

疊代器所扮演的角色就是容器和算法之間的膠合劑，本質上是一個所謂的

泛型指針

。從實作的角度來看，疊代器就是一種将

operator*

、

operator->

、

operator++

以及

operator--

等指針相關操作進行重載的

class template

。

所有的 STL 容器都附帶有自己專屬的疊代器，隻有容器的設計者才知道如何周遊自己的元素。

原生指針（native pointer）也是一種疊代器。

配置器（allocators）

容器要放資料就得需要存儲空間，STL 容器中使用的記憶體空間配置設定不是直接使用我們熟知的

new

和

delete

， 而是對其進行了包裝，成為一個

class template

，負責空間配置、管理和釋放的工作。每個容器都有一個預設的配置器，當然也可以根據需要去更改預設的配置器，而使用 STL 提供的其他配置器。

空間配置設定器、容器和算法都有了，好像 STL 已經可以正常的工作了，擁有這3個元件的 STL 的确可以工作，但是你有沒有想過，對于一個算法而言，就拿最簡單的排序來說，

sort

算法内部通過對容器中的資料進行兩兩比較大小，進而進行排序；對于

int

、

float

以及其它的一些内置類型，可以簡單的直接使用

<

運算符來進行兩個資料的大小判斷，這沒什麼問題，但是對于使用者自定義的類型呢？

比如我定義了一個蘋果 class：

class Apple { ... };

，選擇

vector

這個容器來存放我的蘋果，現在我要對容器裡的蘋果進行排序，按重量（蘋果内部有一個表示重量的資料成員）的大小從小到大進行排，那麼對于

sort

算法來說，顯然直接将容器丢給它還不夠，因為容器裡的資料不是内置類型，它不知道如何來比較兩個蘋果的大小，我們必須顯示的告訴

sort

該如何比較我們的蘋果大小。

那麼現在問題來了，我們如何來告訴

sort

以及如何實作我們自己的比較大小（對于

sort

來說，比較大小是一個政策問題，我隻提供預設的比較方法，至于其他的比較政策，使用者可以自行定義）的方法？

STL 很貼心的為我們提供了仿函數這個東東。

仿函數（functors）

在 STL 中，仿函數其實就是一個

class

或

class template

，隻不過這些類重載了

operator()

這個運算符，使這個類所産生的對象的行為類似函數。仿函數的作用就是服務于算法，可以作為算法的某種政策（policy），比如對于

sort

來說比較大小的政策。

一般的函數指針也可以視為是狹義的仿函數。

對于 STL 提供的算法，除了内置預設的相關政策或準則，我們也可以通過函數或仿函數來實作我們自己的算法政策，然後将其通過參數的方法傳遞給算法使用。

通過上述描述，我們知道：

• 配置器服務于容器
• 仿函數服務于算法
• 疊代器和容器共同為算法服務

那麼我們可能會猜想：STL 有沒有提供什麼東西是用來服務配置器、容器、疊代器以及仿函數的嗎？

猜的沒錯，STL 還真提供了一個叫做 擴充卡或配接器 的東西來服務上述幾個元件，配置器元件除外。

配接器或擴充卡（adapters）

配接器就是一種用來修飾容器、疊代器或仿函數接口的東西。

有點類似于以前老式的變壓器，記得小時候家裡買了彩電（彩色電視機），除了彩電，還會買一個變壓器，将變壓器插在房間的插座中，然後将彩電的插頭插在變壓器上，在這裡，變壓器就是将房間的電壓與彩電需要的電壓進行轉換或者說進行适配，使房間提供的電壓通過變壓器能夠滿足彩電的需要，不管是因為房間的電壓不穩定還是彩電需要的電壓和房間提供的電壓不一緻，通過變壓器，就能正常的觀看彩電裡的節目了。

配接器就是這樣，通過小工程的改造 容器、疊代器或仿函數接口，使它們通過另一種形式（Adapters的形式）來服務于算法等。

改變 functor 接口者，稱為 function adapter。

改變 container 接口者，稱為 container adapter。

改變 iterator 接口者，稱為 iterator adapter。

通常 Adapters 的實作方式是在其内部含有（組合）一個 容器、疊代器或仿函數。

例如，STL 提供的

queue

和

stack

就是一種 container adapter，而不是一個容器，因為它們底部完全借助

deque

，所有的操作都由底層的

deque

供應。

最後放出一張 STL 六大元件的關系圖：

好了，STL 的六大元件基本概要已經講完了，以上内容基于查閱的資料以及自己的了解，有不對的地方還請各位看客指出，歡迎各位拍磚。

參考資料：

• [1] 《STL 源碼剖析》侯捷