? ? ? 學(xué)習(xí)過C++的朋友們應(yīng)該對(duì)STL和泛型編程這兩個(gè)名詞不會(huì)陌生。兩者之間的關(guān)系不言而喻，泛型編程的思想促使了STL的誕生，而STL則很好地體現(xiàn)了泛型編程這種思想。這次想簡(jiǎn)單說一下STL在ACM中的一些應(yīng)用。我們知道，在ACM競(jìng)賽中，經(jīng)常需要用到數(shù)組、字符串、隊(duì)列、堆棧、鏈表等數(shù)據(jù)結(jié)構(gòu)和排序、搜索等算法，以提高程序的時(shí)間、空間運(yùn)行效率。然而如果這些數(shù)據(jù)結(jié)構(gòu)總是需要手工來編寫，那無疑會(huì)是一件很麻煩的工作，而STL的出現(xiàn)很好地解決了這個(gè)問題。

? ? ? 我們簡(jiǎn)單來了解一下STL。STL提供了三種類型的組件：容器、迭代器和算法。容器主要有兩類：順序容器和關(guān)聯(lián)容器。順序容器（vector、list、deque和string等）是一系列元素的有序集合。關(guān)聯(lián)容器（set、multiset、map和multimap）包括查找元素的鍵值。迭代器的作用是遍歷容器。STL算法庫(kù)包含四類算法：排序算法、不可變序算法、變序性算法和數(shù)值算法。下面就簡(jiǎn)單介紹一下STL里常用的容器。

? ? ? 1. vector向量容器

? ? ? vector向量容器不但像數(shù)組一樣對(duì)元素進(jìn)行隨機(jī)訪問，還能在尾部插入元素，是一種簡(jiǎn)單、高效的容器，完全可以替代數(shù)組。由于vector具有內(nèi)存自動(dòng)管理的功能，對(duì)于元素的插入和刪除，可動(dòng)態(tài)調(diào)整所占的內(nèi)存空間，因此使用時(shí)不需要考慮釋放空間的問題。使用vector向量容器時(shí)，需要包含頭文件“vector”。(即#include <vector>)對(duì)于vector容器的容量定義，可以事先定義一個(gè)固定大小，事后可以隨時(shí)調(diào)整其大小；（例如vector<int> v(10); //定義一個(gè)用來存儲(chǔ)10個(gè)int類型元素的向量容器）也可以事先不用定義其大小，使用push_back()方法從尾部擴(kuò)張?jiān)?#xff0c;也可以使用insert()在某個(gè)元素位置前插入新元素。

? ? ? vector容器有兩個(gè)重要的方法，begin()和end()。begin()返回的是首元素位置的迭代器；end()返回的是最后一個(gè)元素的下一個(gè)元素位置的迭代器。通常在遍歷vector所有元素時(shí)會(huì)用到這兩個(gè)方法。例如：

vector<int> v(3); vector<int>::iterator it; for(it=v.begin(); it!=v.end(); it++){...}

　　至于vector元素的刪除，調(diào)用erase()方法可以刪除vector中迭代器所指的一個(gè)元素或一段區(qū)間中的所有元素，clear()方法則可以刪除vector中所有元素。

? ? ? 通過使用size()方法可以返回向量的大小，即元素個(gè)數(shù)，調(diào)用empty()方法返回向量是否為空。

? ? ? 再簡(jiǎn)單看一下在vector中常用到的算法。使用reverse()反向排列算法，需要定義頭文件“#include <algorithm>”，reverse()算法可將向量中某段迭代器區(qū)間元素反向排列；使用sort算法可以對(duì)向量排序，默認(rèn)情況下對(duì)元素進(jìn)行升序排列，也可以自己設(shè)計(jì)排序比較函數(shù)，具體使用細(xì)節(jié)就不贅述了。

? ? ? 2. string基本字符系列容器

? ? ? C語言中對(duì)于字符串只能使用字符數(shù)組來處理，顯得十分不方便。C++ STL提供了string基本字符序列容器來處理字符串，可以把string理解為字符串類，它提供了添加、刪除、替換、查找和比較等豐富方法。使用string容器需要包含頭文件聲明“#include <string>”。

? ? ? 3. set集合容器

? ? ? set集合容器實(shí)現(xiàn)了紅黑樹的平衡二叉檢索樹的數(shù)據(jù)結(jié)構(gòu)，在插入元素時(shí)，它會(huì)自動(dòng)調(diào)整二叉樹的排列，把該元素放到適當(dāng)?shù)奈恢?#xff0c;以確保每個(gè)子樹根節(jié)點(diǎn)的鍵值大于左子樹所有節(jié)點(diǎn)的鍵值，而小于右子樹所有節(jié)點(diǎn)的鍵值；另外，還得確保根節(jié)點(diǎn)左子樹的高度與右子樹的高度相等，因?yàn)槎鏄涓叨茸钚?#xff0c;檢索速度最快。這里要注意的是，set容器不會(huì)插入相同鍵值的元素。

? ? ? 平衡二叉檢索樹的檢索使用中序遍歷算法，檢索效率高于vector、deque和list等容器。另外，采用中序遍歷算法可將鍵值由小到大遍歷出來，所以，可以理解為平衡二叉檢索樹在插入元素時(shí)，就會(huì)自動(dòng)將元素按鍵值由小到大的順序排列。由于構(gòu)造set集合的主要目的就是為了快速檢索，對(duì)于set容器中的鍵值，不可直接去修改。multiset、map和multimap的內(nèi)部結(jié)構(gòu)也是平衡二叉檢索樹。

? ? ? 4. multiset多重集合容器

? ? ? multiset與set一樣，也是使用紅黑樹來組織元素?cái)?shù)據(jù)的，唯一不同的是，multiset允許重復(fù)的元素鍵值插入，而set則不允許。multiset也需要聲明頭文件包含“#include <set>”，由于它包含重復(fù)元素，所以在插入元素、刪除元素、查找元素上較set有差別。

? ? ? 5. map映照容器

? ? ? map映照容器的元素?cái)?shù)據(jù)是由一個(gè)鍵值和一個(gè)映照數(shù)據(jù)組成的，鍵值與映照數(shù)據(jù)之間具有一一映照的關(guān)系。map映照容器的數(shù)據(jù)結(jié)構(gòu)也是采用紅黑樹來實(shí)現(xiàn)的，插入元素的鍵值不允許重復(fù)，比較函數(shù)只對(duì)元素的鍵值進(jìn)行比較，元素的各項(xiàng)數(shù)據(jù)可通過鍵值檢索出來。由于map與set采用的都是紅黑樹的數(shù)據(jù)結(jié)構(gòu)，所以它們的用法基本類似。使用map容器需要頭文件包含語句“#include <map>”。

? ? ? 6. multiset多重映照容器

? ? ? multiset與map基本相同，唯獨(dú)不同的是，mulitiset允許插入重復(fù)鍵值的元素。由于允許重復(fù)鍵值存在，所以multiset的元素插入、刪除、查找都與map不相同。

? ? ? 7. deque雙端隊(duì)列容器

? ? ? deque雙端隊(duì)列容器與vector一樣，采用線性表順序存儲(chǔ)結(jié)構(gòu)。但與vector唯一不同的是，deque采用分塊的線性存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)，每塊的大小一般為512字節(jié)，稱為一個(gè)deque塊，所有的deque塊使用一個(gè)Map塊進(jìn)行管理，每個(gè)Map數(shù)據(jù)項(xiàng)紀(jì)錄每個(gè)deque塊的首地址。這樣，deque塊在頭部和尾部都可插入和刪除元素，而不需移動(dòng)其他元素。一般來說，當(dāng)考慮到容器元素的內(nèi)存分配策略和操作的性能時(shí)，deque相對(duì)于vector會(huì)更有優(yōu)勢(shì)。使用deque需要聲明頭文件包含“#include <deque>”。

? ? ? 8. list雙向鏈表容器

? ? ? list容器實(shí)現(xiàn)了雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素是通過鏈表指針串連成邏輯意義上的線性表，這樣，對(duì)鏈表的任一位置的元素進(jìn)行插入、刪除和查找都是極快速的。由于list對(duì)象的節(jié)點(diǎn)并不要求在一段連續(xù)的內(nèi)存中，所以對(duì)于迭代器，只能通過“++”或“--”的操作將迭代器移動(dòng)到后繼/前驅(qū)節(jié)點(diǎn)元素處。而不能對(duì)迭代器進(jìn)行+n或-n的操作，這點(diǎn)是與vector等不同的地方。使用list需要聲明頭文件包含“#include <list>”。

? ? ?9. stack堆棧容器

? ? ?stack堆棧是一個(gè)后進(jìn)先出的線性表，插入和刪除元素都只能在表的一端進(jìn)行。插入元素的一端稱為棧頂，另一端稱為棧底。插入元素叫入棧，元素的刪除稱為出棧。要使用stack必須聲明頭文件包含語句“#include <stack>”。

? ? ?10. queue隊(duì)列容器

? ? ?queue隊(duì)列容器是一個(gè)先進(jìn)先出的線性存儲(chǔ)表，元素的插入只能在隊(duì)尾，元素的刪除只能在隊(duì)首。使用queue需要聲明頭文件包含語句“#include <queue>” 。

總結(jié)

以上是生活随笔為你收集整理的C++ STL泛型编程——在ACM中的运用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。