set,map和vector講解課件

1、衡陽師范學(xué)院計(jì)算機(jī)系1STL在C+中稱為標(biāo)準(zhǔn)模板庫。STL定義了一系列用途廣泛的模板類和模板函數(shù)，它們可以用來實(shí)現(xiàn)許多通用的算法和數(shù)據(jù)結(jié)構(gòu)。衡陽師范學(xué)院計(jì)算機(jī)系2標(biāo)準(zhǔn)模板庫STL的核心內(nèi)容是3個(gè)基本組件：容器、算法和迭代器。STL將這些組件結(jié)合在一起為許多程序設(shè)計(jì)難題提供實(shí)際可行的解決辦法。衡陽師范學(xué)院計(jì)算機(jī)系3Set集合容器衡陽師范學(xué)院計(jì)算機(jī)系4set集合容器實(shí)現(xiàn)了紅黑樹(Red-Black Tree)的平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)，在插入元素時(shí)，它會(huì)自動(dòng)調(diào)整二叉樹的排列，把該元素放到適當(dāng)?shù)奈恢?。以確保每個(gè)子樹根節(jié)點(diǎn)的鍵值大于左子樹所有節(jié)點(diǎn)的鍵值，而小于右子樹的鍵值；另外，還得確保左子樹的高度與右子

2、樹的高度相等，這樣，二叉樹的高度最小，從而檢索速度最快。注意：set集合不會(huì)重復(fù)插入相同鍵值的元素，采取忽略處理。衡陽師范學(xué)院計(jì)算機(jī)系52612376162932215203080上圖是一個(gè)典型的平衡檢索二叉樹衡陽師范學(xué)院計(jì)算機(jī)系6平衡二叉檢索樹的檢索使用中序遍歷算法，檢索效率高于vector、deque和list等容器。Set 的特點(diǎn) set容器中，插入元素時(shí)，就會(huì)自動(dòng)將元素按鍵值由小到大的順序排列，并沒有重復(fù)的鍵值。對(duì)于set容器中的鍵值，不可直接去修改。所以，構(gòu)造set集合的主要目的就是為了快速檢索。衡陽師范學(xué)院計(jì)算機(jī)系8創(chuàng)建一個(gè)創(chuàng)建一個(gè)set集合對(duì)象集合對(duì)象#includeusing

3、namespace std; set v1; set v2; 衡陽師范學(xué)院計(jì)算機(jī)系9采用采用insert()方法插入元素方法插入元素采用insert()方法把元素插入集合中去，插入的具體規(guī)則在默認(rèn)的比較規(guī)則下，是按元素值從小到大插入。set1-1.cpp 衡陽師范學(xué)院計(jì)算機(jī)系10采用采用insert()方法插入元素方法插入元素采用insert()方法把元素插入集合中去，如果自己指定了比較規(guī)則的函數(shù)，則按自定義比較規(guī)則函數(shù)插入。set1-2.cpp 衡陽師范學(xué)院計(jì)算機(jī)系11采用采用insert()方法插入元素方法插入元素如果元素是結(jié)構(gòu)體，可以直接把比較函數(shù)寫在結(jié)構(gòu)體內(nèi)。set1-3.cpp 衡陽

4、師范學(xué)院計(jì)算機(jī)系12元素的反向遍歷元素的反向遍歷使用反向迭代器reverse_iterator可以反向遍歷元素，輸出的結(jié)果正好是集合元素的反向排序結(jié)果。它需要用到rbegin()和rend()兩個(gè)方法，它們分別給出了反向遍歷的開始位置和結(jié)束位置。set2.cpp 衡陽師范學(xué)院計(jì)算機(jī)系13元素的刪除遍歷元素的刪除遍歷與插入元素的處理一樣，集合具有高效的刪除處理功能，并自動(dòng)重復(fù)調(diào)整內(nèi)部的紅黑樹的平衡。刪除的對(duì)象可以是某個(gè)迭代器位置上的元素、等于某鍵值的元素、一個(gè)區(qū)間上的元素和清空集合。set3.cpp 衡陽師范學(xué)院計(jì)算機(jī)系14元素的檢索元素的檢索使用find()方法對(duì)集合進(jìn)行搜索，如果找到查找的鍵

5、值，則返回該鍵值的迭代器位置，否則，返回集合最后一個(gè)元素后面的一個(gè)位置，即end()。set4.cpp 衡陽師范學(xué)院計(jì)算機(jī)系15Map映照容器衡陽師范學(xué)院計(jì)算機(jī)系16map容器中的元素?cái)?shù)據(jù)是由一個(gè)鍵值和一個(gè)映照數(shù)據(jù)組成的，鍵值與映照數(shù)據(jù)之間具有一一映照的關(guān)系。插入元素的鍵值不允許重復(fù)，比較函數(shù)只對(duì)元素的鍵值進(jìn)行比較。元素的各項(xiàng)數(shù)據(jù)可通過鍵值檢索出來。衡陽師范學(xué)院計(jì)算機(jī)系17map映照容器的內(nèi)部結(jié)構(gòu)也是平衡二叉檢索樹。元素?cái)?shù)據(jù)按照從小到大的順序排列。衡陽師范學(xué)院計(jì)算機(jī)系18使用map容器，需要頭文件包含聲明“#include”。衡陽師范學(xué)院計(jì)算機(jī)系19Map創(chuàng)建、元素插入和遍歷訪問創(chuàng)建、元素插入

6、和遍歷訪問創(chuàng)建map對(duì)象，鍵值與映照數(shù)據(jù)的類型由自己定義。在沒有指定比較函數(shù)時(shí)，元素的插入位置是按鍵值從小到大的。map1.cpp衡陽師范學(xué)院計(jì)算機(jī)系20刪除元素刪除元素map映照容器用erase()刪除元素函數(shù)可以刪除某個(gè)迭代器位置上的元素、等于某個(gè)鍵值的元素、一個(gè)迭代器區(qū)間上的所有元素，當(dāng)前，也可以用clear()方法清空map映照容器。map2.cpp衡陽師范學(xué)院計(jì)算機(jī)系21元素反向遍歷元素反向遍歷可以用反向迭代器reverse_iterator反向遍歷map映照容器中的數(shù)據(jù)，它需要rbegin()方法和rend()方法指出反向遍歷的起始位置和終止位置。map3.cpp衡陽師范學(xué)院計(jì)算機(jī)

7、系22元素的搜索元素的搜索使用find()方法來搜索某個(gè)鍵值，如果搜索到了，則返回該鍵值所在的迭代器的位置，否則，返回end()迭代器的位置。由于map采用平衡搜索二叉樹數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，所以搜索速度是極快的。map4.cpp衡陽師范學(xué)院計(jì)算機(jī)系23自定義比較函數(shù)自定義比較函數(shù)在定義map的時(shí)候，如果沒有指定比較函數(shù)，那么采用默認(rèn)的比較函數(shù)，即按鍵值由小到大的順序插入元素。在很多情況下，可以根據(jù)需要自己編寫比較函數(shù)。map5.cpp衡陽師范學(xué)院計(jì)算機(jī)系24Vector容器衡陽師范學(xué)院計(jì)算機(jī)系25動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組vector容器容器 動(dòng)態(tài)數(shù)值是指可以根據(jù)需要改變大小的數(shù)組。雖然在C+中數(shù)組的大小在

8、編譯時(shí)是固定的，因?yàn)槌绦蛟谶\(yùn)行時(shí)不能改變數(shù)組的大小來適應(yīng)程序需求。然而，vector可以根據(jù)需要來分配內(nèi)存，從而解決這個(gè)問題。雖然vector是動(dòng)態(tài)的，你仍然可以使用標(biāo)準(zhǔn)的數(shù)組下標(biāo)運(yùn)算來訪問數(shù)組中的元素。衡陽師范學(xué)院計(jì)算機(jī)系26創(chuàng)建一個(gè)創(chuàng)建一個(gè)vector對(duì)象對(duì)象#includeusing namespace std; vector v1; vector v2; vectorv3; 衡陽師范學(xué)院計(jì)算機(jī)系27向向vector對(duì)象中添加數(shù)值對(duì)象中添加數(shù)值 v1.push_back(0); v1.push_back(1); for (i=2; i=10;i+) v1.push_back(i);衡陽師

9、范學(xué)院計(jì)算機(jī)系28獲得獲得vector對(duì)象的大小對(duì)象的大小 v1.size() for (i=0; iv1.size();i+) cout v1i ;衡陽師范學(xué)院計(jì)算機(jī)系29創(chuàng)建創(chuàng)建vector對(duì)象的迭代器對(duì)象的迭代器#includeusing namespace std; vector:iterator p 衡陽師范學(xué)院計(jì)算機(jī)系30獲得獲得vector對(duì)象中第一個(gè)和最后一個(gè)元素對(duì)象中第一個(gè)和最后一個(gè)元素 vector:iterator p = v1.begin(); vector:iterator p = v1.end();衡陽師范學(xué)院計(jì)算機(jī)系31在在vector對(duì)象中插入元素；對(duì)象中插入元素；vector:iterator p = v1.begin(); p = p+2; int a10; v1.insert(p, a , a+10);衡陽師范學(xué)院計(jì)算機(jī)系32在在vector對(duì)象中刪除元素；對(duì)象中刪除元素； v1.erase(p, p+3); v1.pop_back();衡陽師范學(xué)院計(jì)算機(jī)系33修改修改vector對(duì)象中的內(nèi)容；對(duì)象中的內(nèi)容； v11 = v11 * v11 v12 = v12 + 100衡陽師范學(xué)院計(jì)算機(jī)系34使用使用sort排列算法排列算法