一、泛型程序設計
1、泛型編程（generic programming）：相同的邏輯和算法，對不同類型的數據進行處理
2、將程序寫得盡可能通用
3、將算法從數據結構中抽象出來，成為通用的
4、C++的模板為泛型程序設計奠定了關鍵的基礎
二、什麼是STL
1、STL（Standard Template Library），即標准模板庫，是一個高效的C++程序庫。
2、包含了諸多在計算機科學領域裡常用的基本數據結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架，高度體現了軟件的可復用性
3、從邏輯層次來看，在STL中體現了泛型化程序設計的思想（generic programming）
（1）在這種思想裡，大部分基本算法被抽象，被泛化，獨立於與之對應的數據結構，用於以相同或相近的方式處理各種不同情形。
4、從實現層次看，整個STL是以一種類型參數化（type parameterized）的方式實現的
（1）基於模板(template)
（2）模板，泛型程序設計思想，STL的關系
模板為泛型程序設計奠定了基礎
STL是一套C++標准模板庫，體現了泛型程序設計思想，換句話說，STL是泛型程序設計思想比較成功的一套產品
三、STL六大組件及其關系
1、STL六大組件
————Container(容器) 各種基本數據結構
————Adapter(適配器) 可改變containers、Iterators或Function object接口的一種組件（之前通過deque是實現了新的容器Stack，Stack稱為容器適配器）
————Algorithm(算法) 各種基本算法如sort、search…等
————Iterator(迭代器) 連接containers和algorithms，迭代器是容器與算法的橋梁
————Function object(函數對象)
————Allocator(分配器)
2、容器算法迭代器關系
容器是數據結構，算法是邏輯，迭代器是遍歷接口
3、容器
（1）容器類是容納、包含一組元素或元素集合的對象
（2）七種基本容器：
————向量（vector）、雙端隊列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）
（3）標准容器的成員絕大部分都具有共同的名稱
（4）序列式容器
————序列式容器Sequence containers,其中每個元素均有固定位置——取決於插入時機和地點，和元素值無關。（vector、deque、list）
（5）關聯式容器
————關聯式容器Associative containers，元素位置取決於特定的排序准則以及元素值，和插入次序無關。（set、multiset、map、multimap）
（6）如何選擇序列式容器
【1】、需要頻繁在序列中間位置上進行插入和/或刪除操作且不需要過多地在序列內部進行長距離跳轉，應該選擇list。不支持下標操作
【2】、vector頭部與中間插入刪除效率較低，在尾部插入與刪除效率高。支持下標操作
【3】、deque是在頭部與尾部插入與刪除效率較高。支持下標操作
4、迭代器
（1）迭代器Iterators，用來在一個對象群集（collection of objects）的元素上進行遍歷。這個對象群集或許是個容器，或許是容器的一部分。迭代器的主要好處是，為所有容器提供了一組很小的公共接口。迭代器以++進行累進，以*進行提領，因而它類似於指針，我們可以把它視為一種smart pointer
（2）比如++操作可以遍歷至群集內的下一個元素。至於如何做到，取決於容器內部的數據組織形式。
（3）每種容器都提供了自己的迭代器，而這些迭代器能夠了解容器內部的數據結構。
5、算法
算法Algorithms，用來處理群集內的元素。它們可以出於不同的目的而搜尋、排序、修改、使用那些元素。通過迭代器的協助，我們可以只需編寫一次算法，就可以將它應用於任意容器，這是因為所有的容器迭代器都提供一致的接口。
6、適配器
（1）、適配器是一種接口類（構造出新的類）
【1】為已有的類提供新的接口stack、queue
【2】目的是簡化、約束、使之安全、隱藏或者改變被修改類提供的服務集合
（2）、三種類型的適配器：
【1】容器適配器：用來擴展7種基本容器，它們和順序容器相結合構成棧、隊列和優先隊列容器
【2】迭代器適配器（反向迭代器、插入迭代器、IO流迭代器）
【3】函數適配器（函數對象適配器、成員函數適配器、普通函數適配器）
7、函數對象
（1）、函數對象（function object）也稱為仿函數（functor）
（2）、一個行為類似函數的對象，它可以沒有參數，也可以帶有若干參數。
（3）、任何重載了調用運算符operator()的類的對象都滿足函數對象的特征
（4）、函數對象可以把它稱之為smart function。
（5）、STL中也定義了一些標准的函數對象，如果以功能劃分，可以分為算術運算、關系運算、邏輯運算三大類。為了調用這些標准函數對象，需要包含頭文件
8、分配器
負責空間配置與管理。從實現的角度來看，配置器是一個實現了動態空間配置、空間管理、空間釋放的class template。
隱藏在這些容器後的內存管理工作是通過STL提供的一個默認的allocator實現的。當然，用戶也可以定制自己的allocator，只要實現allocator模板所定義的接口方法即可，然後通過將自定義的allocator作為模板參數傳遞給STL容器，創建一個使用自定義allocator的STL容器對象，如：
stl::vector
大多數情況下，STL默認的allocator就已經足夠了。這個allocator是一個由兩級分配器構成的內存管理器，當申請的內存大小大於128byte時，就啟動第一級分配器通過malloc直接向系統的堆空間分配，如果申請的內存大小小於128byte時，就啟動第二級分配器，從一個預先分配好的內存池中取一塊內存交付給用戶，這個內存池由16個不同大小（8的倍數，8~128byte）的空閒列表組成，allocator會根據申請內存的大小（將這個大小round up成8的倍數）從對應的空閒塊列表取表頭塊給用戶。
這種做法有兩個優點：
（1)小對象的快速分配。小對象是從內存池分配的，這個內存池是系統調用一次malloc分配一塊足夠大的區域給程序備用，當內存池耗盡時再向系統申請一塊新的區域，整個過程類似於批發和零售，起先是由allocator向總經商批發一定量的貨物，然後零售給用戶，與每次都總經商要一個貨物再零售給用戶的過程相比，顯然是快捷了。當然，這裡的一個問題時，內存池會帶來一些內存的浪費，比如當只需分配一個小對象時，為了這個小對象可能要申請一大塊的內存池，但這個浪費還是值得的，況且這種情況在實際應用中也並不多見。
(2)避免了內存碎片的生成。程序中的小對象的分配極易造成內存碎片，給操作系統的內存管理帶來了很大壓力，系統中碎片的增多不但會影響內存分配的速度，而且會極大地降低內存的利用率。以內存池組織小對象的內存，從系統的角度看，只是一大塊內存池，看不到小對象內存的分配和釋放。
參考：
C++ primer 第四版
Effective C++ 3rd
C++編程規范
