《C++ STL-數(shù)據(jù)結(jié)構(gòu)與算法實現(xiàn)》課件第5章 容器

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

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

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

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

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

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

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

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

集合

只一個查找鍵key，且唯一相等multiset<key>

多重集合只一個查找鍵key，可重復map<key,value>

映射

key–value對，key唯一multimap<key,value>

多重映射

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

Hash表查找時間效率更高hash_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>選擇容器：關聯(lián)容器特點key無序過時的，淘汰的MSDN6／73容器適配器ContainerAdapter修改原容器basecontainer，具備新特點容器適配器：不提供迭代器stack 棧

STL:deque 后進先出LIFOqueue 隊列

STL:deque先進先出FIFOpriority_queue優(yōu)先隊列

STL:

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

：max-heap,min-heap

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

STL

默認：max-heap

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

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

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

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

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

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

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

返回容器中當前元素個數(shù)容器賦值：=

一個容器賦給另一個容器容器比較：<<=>>===!=

兩個容器比較，條件成立返回true

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

返回(const_)iterator

指向第一個元素end()

返回(const_)iterator

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

返回(const_)reverse_iterator

指向最后一個元素rend()

返回(const_)reverse_iterator

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

刪除若干個元素clear()

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

下標操作符vt[index] 返回：index元素的引用

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

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

reverse_iteratorvt.rend()vector訪問元素vector<typenameT>vt14／73例：vector訪問元素15／73例：vector判空初始化向量v逐個添加元素結(jié)構(gòu)體逐個讀取元素逐個刪除元素capacity=?刪除操作自動減少vector的容量嗎？16／73例：vector插入元素//下頁容器內(nèi)元素變化使迭代器失效插入元素自動增加vector容量17／73例：vector插入元素回顧18／73元素賦值voidassign(size_type_Count,constType&_Val); _Count:_Val個數(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

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

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

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

元素voidremove_if(T

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

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

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

int

count(Key&key);返回：值=key的元素個數(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);返回兩個迭代器：first=lower,second=upper

void

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

void

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

和erase()關聯(lián)容器：set／multiset回顧用法舉例：下頁最末一個元素后面28／73multiset構(gòu)造集合的構(gòu)造方法29／73set與multiset成員函數(shù)個數(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;

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

typedef

typedefpair<Key,Type>

value_type;

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

multimap&

operator=(multimap&_Right);

Aftererasinganyexistingelementsinamultimap,

perator=eithercopiesormovesthecontentsof_Rightintothemultimap.map／multimup對象賦值：=右端賦值給=左端iteratoremplace(val);插入元素val并返回指向val的迭代器若插入key-vlaue，不需構(gòu)成<key-vlaue>對類型關聯(lián)容器：map／multimap32／73multimap構(gòu)造int改char*???int改string???省略，只能進行簡單的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（桶）存儲元素：hash(key)值相同沖突的元素存入同一個桶桶的數(shù)量：容器里有若干個桶,bucket_count()插入元素：桶數(shù)量自動增加必要時,rehash()

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

emplace(val)

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

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

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

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

復習數(shù)據(jù)結(jié)構(gòu)順序棧：順序存儲結(jié)構(gòu)鏈式棧：鏈式存儲結(jié)構(gòu)容器適配器：stack和queue固定數(shù)組存儲動態(tài)數(shù)組存儲NULL單向鏈表存儲雙向鏈表存儲48／73隊列基本概念

復習數(shù)據(jù)結(jié)構(gòu)順序隊列：順序存儲結(jié)構(gòu)鏈式隊列：鏈式存儲結(jié)構(gòu)容器適配器：stack和queue…隊尾對頭固定數(shù)組存儲動態(tài)數(shù)組存儲單向鏈表存儲雙向鏈表存儲邏輯結(jié)構(gòu)49／73基本容器

(有條件)在已有容器基礎上修改，具備新特點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沒有自編隊列例順序鏈式鏈式50／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

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

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

堆排序max-heap

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

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

n=

2h-1

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

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

的兩棵滿二叉樹之間：

2h-1

-1<n≤

2h-1

——各項都是整數(shù)

→

2h-1≤n<

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

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

n/2

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

n/2

計算而非存儲：相關結(jié)點的關系堆的存儲結(jié)構(gòu)堆——具有父母優(yōu)勢的完全二叉樹堆：存儲結(jié)構(gòu)9754210123456-975241數(shù)組存儲非葉子區(qū)葉子區(qū)可放置限位器(觀察哨)樹高完全二叉樹完全二叉樹和數(shù)組一一對應構(gòu)造堆——下推算法篩選法、值交換法舉例：對序列{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反復執(zhí)行上述兩步(n-1)次，刪除元素的順序：有序根刪除：算法策略刪除原則刪除后依然是堆，不改變堆的性質(zhì)替換法刪除根后，最后的葉子與根交換，作為新根替換后：新根滿足父母優(yōu)勢？No: ——下推至合適位置

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

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