STL介紹
C++ STL (Standard Template Library標準模板庫) 是通用類模板和算法的集合，它提供給程序員一些標準的數據結構的實現如 queues(隊列), lists(鏈表), 和 stacks(棧)等. 該庫包含了諸多在計算機科學領域里所常用的基本數據結構和基本算法。提供了一個可擴展的應用框架，高度體現了軟件的可復用性。從邏輯層次來看，在STL中體現了泛型化程序設計的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態（polymorphism）一樣，泛型也是一種軟件的復用技術。
從實現層次看，整個STL是以一種類型參數化（type parameterized）的方式實現的，這種方式基于一個在早先C++標準中沒有出現的語言特性--模板（template）。
C++ STL 提供給程序員以下三類數據結構的實現：
標準容器類
順序性容器
vector 從后面快速的插入與刪除，直接訪問任何元素
deque 從前面或后面快速的插入與刪除，直接訪問任何元素
list 雙鏈表，從任何地方快速插入與刪除
三者比較：
vector 是一段連續的內存塊，而deque 是多個連續的內存塊， list 是所有數據元素分開保存，可以是任何兩個元素沒有連續。vector 的查詢性能最好，并且在末端增加數據也很好，除非它重新申請內存段；適合高效地隨機存儲。list 是一個鏈表，任何一個元素都可以是不連續的，但它都有兩個指向上一元素和下一元素的指針。所以它對插入、刪除元素性能是最好的，而查詢性能非常差；適合大量地插入和刪除操作而不關心隨機存取的需求。deque 是介于兩者之間，它兼顧了數組和鏈表的優點，它是分塊的鏈表和多個數組的聯合。所以它有被list好的查詢性能，有被vector好的插入、刪除性能。 如果你需要隨即存取又關心兩端數據的插入和刪除，那么deque是最佳之選。
關聯容器
set 快速查找，不允許重復值
multiset 快速查找，允許重復值
map 一對多映射，基于關鍵字快速查找，不允許重復值
multimap 一對多映射，基于關鍵字快速查找，允許重復值
關聯容器(Associative Container)提供了快速檢索基于關鍵詞(Key)的數據的能力。和序列容器(vector、list、deque)一樣，關聯容器用來存儲數據，而且設計關聯容器時考慮到了優化數據檢索的意圖 --- 通過關鍵詞(Key)作為標識把單一的數據記錄組織到特定的結構中(如tree)。STL 提供了不同的關聯容器：集合(set)、多元集合(multiset)、映射(map)、多元映射(multimap)。set 和map 支持唯一關鍵詞(unique key)，就是對每個KEY，最多只保存一個元素(數據
記錄)。multiset 和multimap 則支持相同關鍵詞(equal key)，這樣可有很多個元素可以用同一個KEY 進行存儲。set(multiset)和map(multimap)之間的區別在于set(multiset)中的存儲數據內含了KEY 表達式；而map(multimap)則將Key 表達式和對應的數據分開存放。
容器適配器
stack 后進先出
queue 先進先出
priority_queue 最高優先級元素總是第一個出列
STL 中包含三種適配器：棧stack 、隊列queue 和優先級priority_queue 。適配器是容器的接口，它本身不能直接保存元素，它保存元素的機制是調用另一種順序容器去實現，即可以把適配器看作“它保存一個容器，這個容器再保存所有元素”。
STL 中提供的三種適配器可以由某一種順序容器去實現。默認下stack 和queue 基于deque 容器實現，priority_queue 則基于vector 容器實現。當然在創建一個適配器時也可以指定具體的實現容器，創建適配器時在第二個參數上指定具體的順序容器可以覆蓋適配器的默認實現。由于適配器的特點，一個適配器不是可以由任一個順序容器都可以實現的。
棧stack 的特點是后進先出，所以它關聯的基本容器可以是任意一種順序容器，因為這些容器類型結構都可以提供棧的操作有求，它們都提供了push_back 、pop_back 和back 操作。
隊列queue 的特點是先進先出，適配器要求其關聯的基礎容器必須提供pop_front 操作，因此其不能建立在vector 容器上。
posted on 2012-06-04 08:52
王海光 閱讀(900)
評論(0) 編輯 收藏 引用 所屬分類:
STL