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