文章目錄

二、STL三大組件

1、容器

容器，置物之所也。

研究數據的特定排列方式，以利于搜索或排序或其他特殊目的，這一門學科我們稱為數據結構。大學信息類相關專業里面，與編程最有直接關系的學科，首推數據結構與算法。幾乎可以說，任何特定的數據結構都是為了實現某種特定的算法。STL容器就是將運用最廣泛的一些數據結構實現出來。

常用的數據結構：數組（array），鏈表（list），tree（樹），棧（stack），隊列（queue），集合（set），映射表（map），根據數據在容器中的排列特性，這些數據分為序列式容器和關聯式容器兩種。

• 序列式容器強調值的排序，序列式容器中的每個元素均有固定的位置，除非用刪除或插入的操作改變這個位置。Vector容器、Deque容器、List容器等。
• 關聯式容器是非線性的樹結構，更準確的說是二叉樹結構。各元素之間沒有嚴格的物理上的順序關系，也就是說元素在容器中并沒有保存元素置入容器時的邏輯順序。關聯式容器另一個顯著特點是：在值中選擇一個值作為關鍵字key，這個關鍵字對值起到索引的作用，方便查找。Set/multiset容器Map/multimap容器

容器可以嵌套容器！

2、算法

算法，問題之解法也。

以有限的步驟，解決邏輯或數學上的問題，這一門學科我們叫做算法(Algorithms)。

廣義而言，我們所編寫的每個程序都是一個算法，其中的每個函數也都是一個算法，畢竟它們都是用來解決或大或小的邏輯問題或數學問題。STL收錄的算法經過了數學上的效能分析與證明，是極具復用價值的，包括常用的排序，查找等等。特定的算法往往搭配特定的數據結構，算法與數據結構相輔相成。

算法分為：質變算法 和 非質變算法。

• 質變算法：是指運算過程中會更改區間內的元素的內容。例如拷貝，替換，刪除等等
• 非質變算法：是指運算過程中不會更改區間內的元素內容，例如查找、計數、遍歷、尋找極值等等

3、迭代器

迭代器(iterator)是一種抽象的設計概念，現實程序語言中并沒有直接對應于這個概念的實物。iterator定義如下：提供一種方法，使之能夠依序尋訪某個容器所含的各個元素，而又無需暴露該容器的內部表示方式。

迭代器的設計思維–STL的關鍵所在，STL的中心思想在于將容器(container)和算法(algorithms)分開，彼此獨立設計，最后再一貼膠著劑將他們撮合在一起。從技術角度來看，容器和算法的泛型化并不困難，C++的class template和function template可分別達到目標，如何設計出兩這個之間的良好的膠著劑，才是大難題。

迭代器的種類：

迭代器類型	操作特性	操作支持
輸入迭代器	提供對數據的只讀訪問	只讀，支持++、==、！=
輸出迭代器	提供對數據的只寫訪問	只寫，支持++
前向迭代器	提供讀寫操作，并能向前推進迭代器	讀寫，支持++、==、！=
雙向迭代器	提供讀寫操作，并能向前和向后操作	讀寫，支持++、–
隨機訪問迭代器	提供讀寫操作，并能以跳躍的方式訪問容器的任意數據，是功能最強的迭代器	讀寫，支持++、–、[n]、-n、<、<=、>、>=