第五章STL容器容器分類、特點(diǎn)、共性序列容器：向量vector序列容器：雙端隊(duì)列deque序列容器：鏈表list關(guān)聯(lián)容器：集合set關(guān)聯(lián)容器：映射map關(guān)聯(lián)容器：Hash集合關(guān)聯(lián)容器：Hash映射容器適配器1／73容器Container存放同類型元素的類模板：容器分類標(biāo)準(zhǔn)容器(通用容器)容器適配器(特殊容器)容器順序容器關(guān)聯(lián)容器vectordequelistset,multisetmap,multimaphash_set,hash_multisethash_map,hash_multimapstackqueuepriority_queue2／73順序容器：元素有序ordered，但未排序sorted關(guān)聯(lián)容器：元素按關(guān)鍵字(key)排序，快速查找容器適配器：修改容器接口，具備新特點(diǎn)順序容器SequenceContainersvector<T>

向量——應(yīng)用廣泛動(dòng)態(tài)數(shù)組：大小自動(dòng)調(diào)整隨機(jī)訪問：連續(xù)存放，常量時(shí)間插入刪除：末端快，其他位置慢（移動(dòng)元素）重新分配空間：保留內(nèi)存不夠時(shí)，空間加倍——

元素復(fù)制如對(duì)象需構(gòu)造和析構(gòu)選擇容器：順序容器特點(diǎn)3／73deque<T>

雙端隊(duì)列(double-endedqueue)存儲(chǔ)格式：塊內(nèi)順序+塊間鏈表，邏輯上連續(xù)隨機(jī)訪問：速度遠(yuǎn)不如

vector（嚴(yán)重缺點(diǎn)）插入刪除：兩端快（優(yōu)點(diǎn)），其他位置慢空間分配：無保留空間(reserved)，增加一塊連續(xù)

空間連入即可，速度比vector快很多l(xiāng)ist<T>鏈表存儲(chǔ)結(jié)構(gòu)：雙向循環(huán)鏈表每個(gè)結(jié)點(diǎn)放一個(gè)元素順序訪問元素雙向，不能隨機(jī)訪問不能用[],at()不存在空間不夠：無容量和內(nèi)存重新分配函數(shù)任何位置上插入刪除效率高（優(yōu)點(diǎn)）選擇容器：順序容器特點(diǎn)4／73關(guān)聯(lián)容器AssociatedContainers——快速查找容器元素:

<key,value>對(duì),按key有序數(shù)據(jù)結(jié)構(gòu)：平衡二叉樹BBTBalancedBinaryTree

紅黑樹RB-Tree——快速查找set<key>

集合

只一個(gè)查找鍵key，且唯一相等multiset<key>

多重集合只一個(gè)查找鍵key，可重復(fù)map<key,value>

映射

key–value對(duì)，key唯一multimap<key,value>

多重映射

key–value對(duì)，key可重復(fù)選擇容器：關(guān)聯(lián)容器特點(diǎn)按key排序5／73有些編譯器VC2005增加了4種關(guān)聯(lián)容器類型：數(shù)據(jù)結(jié)構(gòu)：散列表

Hash表查找時(shí)間效率更高h(yuǎn)ash_set<key>

散列集

#include<hash_set>hash_multiset<key>

散列多重集

#include<hash_set>hash_map<key,value>

散列映射

#include<hash_map>hash_multimap<key,value>

散列多重映射

#include<hash_map>選擇容器：關(guān)聯(lián)容器特點(diǎn)key無序過時(shí)的，淘汰的MSDN6／73容器適配器ContainerAdapter修改原容器basecontainer，具備新特點(diǎn)容器適配器：不提供迭代器stack 棧

STL:deque 后進(jìn)先出LIFOqueue 隊(duì)列

STL:deque先進(jìn)先出FIFOpriority_queue優(yōu)先隊(duì)列

STL:

vector優(yōu)先：每個(gè)元素有一個(gè)優(yōu)先值=key名為隊(duì)列，實(shí)非隊(duì)列：不滿足FIFO堆heap

：max-heap,min-heap

復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)

STL

默認(rèn)：max-heap

優(yōu)先值最高(大)者先“出隊(duì)”選擇容器：容器適配器特點(diǎn)7／73似容器almostcontainer，擬容器——像容器，但與真正容器不盡相同string

字符串元素類型：不像容器可選擇各種數(shù)據(jù)類型專門優(yōu)化：用法與容器有差別valarray<T>

值數(shù)組為數(shù)值計(jì)算而優(yōu)化的向量提供數(shù)值運(yùn)算和數(shù)學(xué)函數(shù)bitset<N>

位集合提供二進(jìn)制位集合位數(shù)N的各種操作方便二進(jìn)制位運(yùn)算選擇容器：似容器特點(diǎn)8／73缺省構(gòu)造函數(shù)：容器類的默認(rèn)初始化拷貝構(gòu)造函數(shù)：生成現(xiàn)有容器的副本析構(gòu)函數(shù)：

不需要容器時(shí)整理內(nèi)存empty()

容器中元素個(gè)數(shù)=0返回truemax_size()

返回容器最多能容納的元素個(gè)數(shù)size()

返回容器中當(dāng)前元素個(gè)數(shù)容器賦值：=

一個(gè)容器賦給另一個(gè)容器容器比較：<<=>>===!=

兩個(gè)容器比較，條件成立返回true

不適于priority_queueswap() 交換兩個(gè)容器的元素容器共性一般不關(guān)心9／73begin()

返回(const_)iterator

指向第一個(gè)元素end()

返回(const_)iterator

指向最后一個(gè)元素之后rbegin()

返回(const_)reverse_iterator

指向最后一個(gè)元素rend()

返回(const_)reverse_iterator

指向第一個(gè)元素之前erase()

刪除若干個(gè)元素clear()

刪除全部元素標(biāo)準(zhǔn)容器共性10／73例：vector構(gòu)造與初始化string數(shù)組頭文件v4有幾個(gè)元素？類型？v5有幾個(gè)元素？類型？問題11／73例：vector容量230-1capacity()：???重新分配內(nèi)存前的最大容量下頁12／73例：vector容量想一想：怎么顯示vector中的每個(gè)元素？13／73

下標(biāo)操作符vt[index] 返回：index元素的引用

可讀可寫成員函數(shù)vt.at(index) 返回：index元素的引用vt.front() 返回：第一個(gè)元素的引用vt.back() 返回：最后一個(gè)元素的引用迭代器位置指示iterator

vt.begin()reverse_iteratorvt.rbegin()iteratorvt.end()

reverse_iteratorvt.rend()vector訪問元素vector<typenameT>vt14／73例：vector訪問元素15／73例：vector判空初始化向量v逐個(gè)添加元素結(jié)構(gòu)體逐個(gè)讀取元素逐個(gè)刪除元素capacity=?刪除操作自動(dòng)減少vector的容量嗎？16／73例：vector插入元素//下頁容器內(nèi)元素變化使迭代器失效插入元素自動(dòng)增加vector容量17／73例：vector插入元素回顧18／73元素賦值voidassign(size_type_Count,constType&_Val); _Count:_Val個(gè)數(shù)，_Val:容器元素值(賦值)template<classIterator>//輸入型迭代器voidassign(Iterator_First,Iterator_Last);//區(qū)間刪除元素iteratorerase(const_iterator_Where);//刪除位置iteratorerase(const_iterator_First,const_iterator_Last);voidpop_back(); //erase(end()-1,end())voidclear(); //erase(begin(),end())交換元素voidswap(vector<Type,Allocator>&_Right);friendvoidswap(vector<Type,Allocator>&_Left, vector<Type,Allocator>&_Right);vector元素：賦值刪除交換19／73賦值（一）賦值（二）元素地址交換的是什么？元素值？地址？earse()怎么用？20／73deque

特點(diǎn)接近于vector與vector比較選擇容器優(yōu)點(diǎn)：兩端插入刪除很快，提供相應(yīng)的成員函數(shù)不用的內(nèi)存即釋放。刪除即釋放，需要?jiǎng)t分配內(nèi)存分配速度快分塊存儲(chǔ)，無

capacity概念缺點(diǎn)：支持隨機(jī)訪問元素，但速度遠(yuǎn)不如vector除首尾元素外，其他位置插入刪除速度也很慢*如需頻繁在首尾外位置插入刪除元素，應(yīng)用list順序容器：雙端隊(duì)列回顧21／73deque:頭插與刪頭22／73deque與vector內(nèi)存分配deque←這兩句的區(qū)別？23／73自編FIFO

隊(duì)列類構(gòu)思：隊(duì)列數(shù)據(jù)存儲(chǔ)？構(gòu)思：FIFO隊(duì)列操作限制？需要哪些成員函數(shù)？參數(shù)和返回值？怎么自編隊(duì)列？24／73list特點(diǎn)特有成員函數(shù)voidremove(constT&x);刪除所有元素值=x

元素voidremove_if(T

pr); 刪除符合條件謂詞pr的元素voidsort(); 所有元素排序默認(rèn)升序less<int>()voidsort(Tpr); 按條件謂詞pr

排序voidunique(); 相鄰的重復(fù)元素預(yù)排序僅留一個(gè)voidsplice(iteratorit,list&L);

合并兩個(gè)list:插入Lvoidsplice(iteratorit,list&L,iteratoritL);插一個(gè)元素voidsplice(iteratorit,list&L,iteratorfirstL,iteratorlastL);voidmerge(list&x); 不如splice靈活voidmerge(list&x,Tpr);voidreverse(); 反轉(zhuǎn)元素的位序順序容器：鏈表回顧詳細(xì)用法，下頁舉例函數(shù)對(duì)象25／73例：list基本函數(shù)sortsort26／73list:splice()用法例L1和L3并入L2用list迭代器將L4并入L2展開初始化L1~L427／73特有成員函數(shù)

int

count(Key&key);返回：值=key的元素個(gè)數(shù)

iterator

find(Key&key);返回迭代器：值等于key；不滿足返回end()

iterator

lower_bound(Key&key);>=key

iterator

upper_bound(Key&key);>key返回迭代器：>=key或>key,

不滿足返回end()

pair<first,second>

equal_range(Key&key);返回兩個(gè)迭代器：first=lower,second=upper

void

swap(set&s); 交換單集合元素

void

swap(multiset&s); 交換多集合元素?zé)opop和push系列函數(shù)，用insert()

和erase()關(guān)聯(lián)容器：set／multiset回顧用法舉例：下頁最末一個(gè)元素后面28／73multiset構(gòu)造集合的構(gòu)造方法29／73set與multiset成員函數(shù)個(gè)數(shù)集合的成員函數(shù)30／73template<classKey, //排序鍵(sortkey)類型classType, //映射值value類型classTraits

=less<Key>,//key比較，缺省(升序)，可改變

classAllocator=allocator<pair<constKey,Type>>//用缺省

>

class

map

;

//類模板//----------------------------------------------------------------------------template

<classKey,classType,classTraits=less<Key>,

classAllocator=allocator<pair<constKey,Type>>>

class

multimap;

//類模板關(guān)聯(lián)容器：map／multimap定義回顧模板參數(shù)31／73

typedef

typedefpair<Key,Type>

value_type;

將兩個(gè)數(shù)據(jù)(key,value)構(gòu)成一個(gè)key-vlaue對(duì)成員函數(shù)見msdn

multimap&

operator=(multimap&_Right);

Aftererasinganyexistingelementsinamultimap,

perator=eithercopiesormovesthecontentsof_Rightintothemultimap.map／multimup對(duì)象賦值：=右端賦值給=左端iteratoremplace(val);插入元素val并返回指向val的迭代器若插入key-vlaue，不需構(gòu)成<key-vlaue>對(duì)類型關(guān)聯(lián)容器：map／multimap32／73multimap構(gòu)造int改char*???int改string???省略，只能進(jìn)行簡單的string處理33／73multimap構(gòu)造按key排序34／73multimap構(gòu)造(2)比較上例上例：int35／73multimap構(gòu)造(2)比較上例<key–value>36／73multimap構(gòu)造：插入和賦值不需pail<key,value>比較上例37／73multimap成員函數(shù)

返回地址即迭代器升序注意比較注意比較注意比較將容器清空38／73bucket（桶）存儲(chǔ)元素：hash(key)值相同沖突的元素存入同一個(gè)桶桶的數(shù)量：容器里有若干個(gè)桶,bucket_count()插入元素：桶數(shù)量自動(dòng)增加必要時(shí),rehash()

指定最小值元素順序：先插入的元素在前，key相等元素邏輯相鄰intbucket_count() 返回：容器中桶的數(shù)量intbucket(key) 返回：桶的編號(hào)，存放元素keyintbucket_size(n) 返回：編號(hào)n的桶中元素?cái)?shù)量iterator

emplace(val)

插入val，返回指向val的迭代器Hashhash_function() 返回：hash函數(shù)對(duì)象void

rehash(n) 重建hash表，桶數(shù)>=nfloat

load_factor() 平均裝填因子=元素?cái)?shù)量/桶數(shù)量floatmax_load_factor()最大裝填因子裝滿=1，改變無意義unordered_set／_multiset類特殊成員函數(shù)回顧39／73hash_set／hash_multiset

構(gòu)造方法回顧與multiset比較復(fù)習(xí)：哈希函數(shù)沖突解決40／73unordered_multiset構(gòu)造方法回顧hash_multiset41／73unordered_multiset類成員函數(shù)unordered_multiset成員函數(shù)42／73unordered_multiset高級(jí)#include<unordered_set>9/649/12843／73unordered_map／_multimap回顧44／73unordered_map／_multimap比較前例45／73multimap查找刪除比較前例key無序46／73multimap查找刪除修改元素<key,value>清空容器47／73棧基本概念

復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)順序棧：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)綏＃烘準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)容器適配器：stack和queue固定數(shù)組存儲(chǔ)動(dòng)態(tài)數(shù)組存儲(chǔ)NULL單向鏈表存儲(chǔ)雙向鏈表存儲(chǔ)48／73隊(duì)列基本概念

復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)順序隊(duì)列：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)疥?duì)列：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)容器適配器：stack和queue…隊(duì)尾對(duì)頭固定數(shù)組存儲(chǔ)動(dòng)態(tài)數(shù)組存儲(chǔ)單向鏈表存儲(chǔ)雙向鏈表存儲(chǔ)邏輯結(jié)構(gòu)49／73基本容器

(有條件)在已有容器基礎(chǔ)上修改，具備新特點(diǎn)stack基本容器具有

size,empty,push_back,pop_back,front,back等函數(shù)——

vector

,deque,listqueue基本容器具有

size,empty,push_back,pop_front,front,back等函數(shù)——deque,list容器適配器：stack和queue回顧vector沒有自編隊(duì)列例順序鏈?zhǔn)芥準(zhǔn)?0／73template

<classType,classContainer=deque<Type>>classstack

{…}//-----------------------------------------------template

<classType,classContainer=deque<Type>>classqueue{…}STL:stack和queue定義51／73例：STLstack52／73例：STLstack創(chuàng)建棧v1,v2,v3

進(jìn)棧讀棧頂元素:top()出?；驈棗?pop()清空棧iota()生成v1,v2,v353／73例：STLqueue入隊(duì)s1,s2,s3,s4讀隊(duì)尾元素(類型)？讀隊(duì)頭讀隊(duì)頭出隊(duì)全部出隊(duì)輸出屏幕54／73優(yōu)先隊(duì)列：

就是堆，或者用堆實(shí)現(xiàn)的優(yōu)先值排序：

堆排序max-heap

復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)：具有父母優(yōu)勢的一棵完全二叉樹父母優(yōu)勢：任意父母結(jié)點(diǎn)key≥子女結(jié)點(diǎn)key

容器適配器：priority_queue回顧最大堆最小堆不是堆975481完全二叉樹55／73滿二叉樹FullBinaryTree,FBT定義：設(shè)樹高h(yuǎn)，結(jié)點(diǎn)總數(shù)

n=

2h-1

的二叉樹。圖示n=20+21+22+…+2h-1

=2h-1特點(diǎn)：不存在單分支度=1結(jié)點(diǎn)不缺葉結(jié)點(diǎn)只出現(xiàn)在最底層不缺滿二叉樹h=4層數(shù)完全二叉樹CompletedBinaryTree,CBT特點(diǎn)：滿二叉樹最底層從右至左、連續(xù)缺若干個(gè)葉子完全二叉樹的特例：滿二叉樹葉結(jié)點(diǎn)只出現(xiàn)在最底兩層上完全二叉樹k=1k=2k=3k=4n結(jié)點(diǎn)完全二叉樹的樹高證明：完全二叉樹高h(yuǎn)，結(jié)點(diǎn)數(shù)n=2h-1→完全二叉樹結(jié)點(diǎn)數(shù)n:介于樹高=h-1和樹高=h

的兩棵滿二叉樹之間：

2h-1

-1<n≤

2h-1

——各項(xiàng)都是整數(shù)

→

2h-1≤n<

2h兩邊取對(duì)數(shù):

h-1≤log2n<h因h為整數(shù)，有：完全二叉樹：重要性質(zhì)對(duì)數(shù)關(guān)系對(duì)任一結(jié)點(diǎn)i父母：左子女：右子女：左兄弟：右兄弟：如此編號(hào)：整棵樹的結(jié)構(gòu)關(guān)系均可計(jì)算出來！完全二叉樹的性質(zhì)圓圈內(nèi)數(shù)字：結(jié)點(diǎn)編號(hào)i，上→下,左→右124589101136712確定父母結(jié)點(diǎn)編號(hào)區(qū)間？且為奇數(shù)且為偶數(shù)注意條件父母：i≤

n/2

完全二叉樹：存儲(chǔ)結(jié)構(gòu)順序124589101136712i為奇數(shù)i為偶數(shù)按編號(hào)序存入數(shù)組H[i]編號(hào)i0123456789101112值H[i]e1e2e3e4e5e6e7e8e9e10e11e12父母區(qū)葉子區(qū)父母：i≤

n/2

計(jì)算而非存儲(chǔ)：相關(guān)結(jié)點(diǎn)的關(guān)系堆的存儲(chǔ)結(jié)構(gòu)堆——具有父母優(yōu)勢的完全二叉樹堆：存儲(chǔ)結(jié)構(gòu)9754210123456-975241數(shù)組存儲(chǔ)非葉子區(qū)葉子區(qū)可放置限位器(觀察哨)樹高完全二叉樹完全二叉樹和數(shù)組一一對(duì)應(yīng)構(gòu)造堆——下推算法篩選法、值交換法舉例：對(duì)序列{2,9,7,6,5,8}

構(gòu)造max-heap構(gòu)造堆：下推算法297568297568298567298567928567968527-297658邏輯結(jié)構(gòu)堆排序：算法策略構(gòu)造堆：max-heap,min-heap刪除根：max,min反復(fù)執(zhí)行上述兩步(n-1)次，刪除元素的順序：有序根刪除：算法策略刪除原則刪除后依然是堆，不改變堆的性質(zhì)替換法刪除根后，最后的葉子與根交換，作為新根替換后：新根滿足父母優(yōu)勢？No: ——下推至合適位置

問：其他的父母結(jié)點(diǎn)需要下推嗎？堆排序：算法策略邏輯結(jié)構(gòu)描述：根刪除過程最差時(shí)間效率T(n)：最差情況：新根下推至最底層的葉結(jié)點(diǎn)，樹高h(yuǎn)比較次數(shù)：T(n)=2h

=2log2(n+1)∈Θ(logn)存儲(chǔ)結(jié)構(gòu)描述：根刪除過程堆的存儲(chǔ)結(jié)構(gòu)：數(shù)組(STL:vector)堆排序：邏輯過程986521186529816529856129堆排序：物理過程297568堆排序{2,9,7,6,5,8}-752869-756829-756892-75