STL實用入門教程第七講

STL實用入門教程第七講主講人：闕海忠VC知識庫網(wǎng)站()拍攝制作本講要點用STL解決本教程最初提到的問題，STL綜合題：歌唱比賽STL綜合題：歌唱比賽某學(xué)校舉行一場唱歌比賽，共有24個人參加，按參加順序設(shè)置參賽號(參賽號為100至123)。

每個選手唱完一首歌之后，由10個評委分別打分。該選手的最終得分是去掉一個最高分和一個最低分，求得剩下的8個評分的平均分。STL綜合題：歌唱比賽比賽共三輪，前兩輪為淘汰賽，第三輪為決賽。選手的名次按得分降序排列，若得分一樣，按參賽號升序排名。第一輪分為4個小組，根據(jù)參賽號順序依次劃分，比如100-105為一組，106-111為第二組，依次類推，每組6個人，每人分別按參賽號順序演唱。當小組演唱完后，淘汰組內(nèi)排名最后的三個選手，然后繼續(xù)下一個小組的比賽。STL綜合題：歌唱比賽

第二輪分為2個小組，每組6人，每個人分別按參賽號順序演唱。當小組演唱完后，淘汰組內(nèi)排名最后的三個選手，然后繼續(xù)下一個小組的比賽。 第三輪只剩下6個人，本輪為決賽，不淘汰選手，本輪目的是賽出每個人的名次。該6人按參賽號順序分別演唱。請用STL解答以下問題請打印出所有選手的名字與參賽號，并以參賽號的升序排列。請打印出第1輪和第2輪淘汰賽中，各小組選手的名字與選手得分，并以名次的順序排列。請用STL解答以下問題請打印出第1輪淘汰賽中被淘汰的歌手的名字(不要求打印順序)。請打印出第2輪淘汰賽中被淘汰的歌手的分數(shù)，并以名次的降序排列。【題目分析】講解綱要一、總體分析所需要的結(jié)構(gòu)體，類，類的外部接口，類的成員變量；二、報名參加比賽的具體分析；三、第一輪淘汰賽的分析；四、第二輪淘汰賽的分析；五、決賽的分析?！绢}目分析】定義歌手結(jié)構(gòu)體//在文件Singer.h中定義歌手的結(jié)構(gòu)體structSinger{ stringstrName; //名字

intiLatestScore; //最新得分};【題目分析】定義歌唱比賽類//類的聲明在SingingCompetition.h中，類的實現(xiàn)在SingingCompetition.cpp中//以下為對外開放的類成員方法(類的外部接口)，我們主要要實現(xiàn)以下四個方法。classCSingingCompetition{public: //報名參加比賽

voidJoinCompetition(); //第一輪淘汰賽

voidFirstKnockout(); //第二輪淘汰賽

voidSecondKnockout(); //決賽

voidFinals();};【題目分析】

歌唱比賽類的成員變量 map<int,Singer>

m_mapSinger; //所有的參賽ID與歌手的映射集合。//int:參賽ID，Singer:參加比賽的歌手。為什么選擇map?而不選擇其他容器呢？ 答：每個歌手只想在內(nèi)存中保存一份對象實例。另外我們希望能很快通過參賽ID來找到歌手和他的相關(guān)信息。從這里可以看出，我們選擇關(guān)聯(lián)性的容器是比較合適的。所以序列性的容器（Vector、List、Deque）都被排除了。關(guān)聯(lián)性的容器有Set和Map兩種。而Set是沒有映射功能，而我們這邊需要有映射關(guān)系的容器，所以只有Map類的容器才可以。而MultiMap的鍵值是可以重復(fù)的，但我們這邊的ID是不能重復(fù)的，所以最后我們選擇map容器來作為存放歌手的容器?！绢}目分析】

歌唱比賽類的成員變量 list<int>m_lstRemainingID;

//剩余歌手(沒被淘汰的歌手)的參賽ID的集合。//int:剩余歌手的參賽ID。 為什么要選用list<int>，其它容器代替合適嗎？ 答：這個容器，是需要頻繁地從容器的不確定位置刪除元素的。List內(nèi)部的每個節(jié)點都是通過指針值的指向位置來相連接，在list中刪除元素或插入元素，不會浪費或移動存儲空間，只需要修改相應(yīng)元素的指針指向值。vector或deque在中間或頭部刪除元素，將移動大量的空間，set與map是屬于關(guān)聯(lián)性容器，本身是排序的，而排序在這里是多余的，它們的內(nèi)部實現(xiàn)比list復(fù)雜，刪除的效率也沒有l(wèi)ist的刪除效率高。【題目分析】

歌唱比賽類的成員變量multimap<int,int,greater<int>>

m_mltmapCurGroup;

//當前演唱小組的歌手分數(shù)與歌手參賽ID的映射集合。 //第一個int:歌手分數(shù) //第二個int:歌手參賽ID //greater<int>:函數(shù)對象，用于歌手分數(shù)的降序排列 為什么要采用multimap，選用其它容器合適嗎? 答：我們要記錄小組成員得分情況，而得分情況需要降序排序，我們就需要選一個容器，可以降序排列分數(shù)。這時我們可以選擇set,multiset,map,multimap這些關(guān)聯(lián)性容器，我們又需要從排序后的分數(shù)映射出分數(shù)的主人，也就是參賽ID，所以，我們排除了set,multiset，而歌手的分數(shù)是可能一樣的，所以，排除了map，而選擇了multimap?！绢}目分析】

歌唱比賽類的成員變量vector<int>m_vecIDBeEliminatedInFirstRound; //第一輪淘汰賽中被淘汰的歌手名字的集合。

//int:歌手的參賽號 為什么選擇vector，其它容器合適嗎？ 答：按題目的要求，這邊的容器只要存儲數(shù)據(jù)就行，沒有刪除元素的操作，沒有排序的操作，選vector剛剛夠用，且vector支持隨機存儲是最好的，數(shù)據(jù)也在內(nèi)存中也是連續(xù)的。deque的第一個元素的位置不確定，隨機存儲性沒vector好，而且deque的push_front與pop_back也是多余的，我們選擇容器，夠用就好。list不支持隨機存儲，要找到元素的下一個元素，時間久，且它提供的插入刪除操作在這這是多余的。set的排序是多余的，不支持隨機存儲。map的排序也是多余的，映射也是多余的?！绢}目分析】

歌唱比賽類的成員變量multiset<int>m_mltsetScoreBeEliminatedInSecondRound; //第二輪淘汰賽中被淘汰的歌手分數(shù)的集合。

//int:歌手的分數(shù) 為什么選用multiset？其它容器合適嗎？ 答：由于這里需要排序，又不需要映射，所以，可以選set與multiset，不過分數(shù)是可能重復(fù)的，所以，選用multiset?！绢}目分析】

歌唱比賽類的成員變量intm_iRound; //第幾輪比賽，值為1：第一輪；值為2：第二輪；值為3：第三輪?！绢}目分析】歌唱比賽類初始化CSingingCompetition::CSingingCompetition(void){ //還沒開始比賽，比賽輪數(shù)設(shè)置為0 m_iRound=0; //設(shè)置隨機種子

srand((unsigned)time(0));}【題目分析】講解綱要一、總體分析所需要的結(jié)構(gòu)體，類，類的外部接口，類的成員變量；二、報名參加比賽的具體分析；三、第一輪淘汰賽的分析；四、第二輪淘汰賽的分析；五、決賽的分析。【題目分析】生成24位歌手并讓他們報名參加比賽stringstrNameBaseSource("ABCDEFGHIJKLMNOPQRSTUVWXYZ");//名字組成元素的來源//隨機排序名字組成元素的來源random_shuffle(strNameBaseSource.begin(),strNameBaseSource.end());for(inti=0;i<24;++i){ //獲取參加比賽的歌手名字

stringstrExt(1,strNameBaseSource[i]);

//構(gòu)造歌手對象 Singersinger; singer.iLatestScore=0; singer.strName="選手";

singer.strName+=strExt;

//錄入?yún)⒓颖荣惖母枋? m_mapSinger.insert(pair<int,Singer>(i+100,singer)); m_lstRemainingID.push_back(i+100);}報名參加比賽時的容器值map<int,Singer>m_mapSingerlist<int>m_lstRemainingID【題目分析】打印歌手名字與參賽號//打印參加比賽的歌手名字與參賽號for(map<int,Singer>::iteratorit=m_mapSinger.begin();it!=m_mapSinger.end();++it){ TRACE("%s，參賽號：%d\n",it->second.strName

.c_str(),it->first);}【題目分析】講解綱要一、總體分析所需要的結(jié)構(gòu)體，類，類的外部接口，類的成員變量；二、報名參加比賽的具體分析；三、第一輪淘汰賽的分析；四、第二輪淘汰賽的分析；五、決賽的分析?！绢}目分析】第一輪淘汰賽voidCSingingCompetition::FirstKnockout(){ if(m_iRound==0) { m_iRound=1;

//進行淘汰賽

Knockout(); TRACE("第%d輪淘汰賽中被淘汰的歌手的名字：\n",m_iRound); for(vector<int>::iteratorit=m_vecIDBeEliminatedInFirstRound.begin();it!=m_vecIDBeEliminatedInFirstRound.end();++it) { TRACE("%s",m_mapSinger[*it].strName.c_str()); } TRACE("\n"); TRACE("\n"); }}【題目分析】淘汰賽規(guī)則//淘汰賽voidCSingingCompetition::Knockout(){ TRACE("*************第%d輪淘汰賽：*************\n",m_iRound); intiSingerIndex=0; //第幾個歌手正在演唱，1代表第一個歌手，2代表第二個歌手。。。

for(list<int>::iteratorit=m_lstRemainingID.begin();it!=m_lstRemainingID.end();) { ++iSingerIndex;

//生成歌手的分數(shù)

MakeScore(m_mapSinger[*it]); //記錄當前演唱小組歌手的得分情況，按分數(shù)降序排列

m_mltmapCurGroup.insert(pair<int,int>(m_mapSinger[*it].iLatestScore,*it)); if(iSingerIndex%6==0) { //小組演唱完畢，打印小組得分情況，淘汰刪除歌手

...... } else { ++it; } }}【題目分析】生成歌手的分數(shù)voidCSingingCompetition::MakeScore(Singer&singer){ deque<int>deqScore; //為什么選用deque?其它容器呢？

//vector在去掉一個最高分，一個最低分時，需要從頭部移除一個元素，效率低。

//list不支持隨機索引，在下面的accumulate的計算也比較慢。

//set/multiset一開始就排序，按流程來說的十個評委評分過程是不排序的，然后評分后再排序去掉最高分最低分。如果不考慮流程，在這程序中可以使用multiset（分數(shù)可能一樣，set不行），使一開始就排序好，不過在accumulate的計算中，也比較慢。

//map/multimap是映射，在這邊不需要。

//十個評委分別對歌手打分，打分過程沒要求排序

for(inti=0;i<10;++i) { intiScore=60+rand()%40; deqScore.push_back(iScore); } //為十個評委的打分排序

sort(deqScore.begin(),deqScore.end());

//去掉一個最高分，去掉一個最低分

deqScore.pop_front(); deqScore.pop_back(); //求八個評委打分的總和

intiScoreSum=accumulate(deqScore.begin(),deqScore.end(),0); //求八個評委打分的平均分

intiScoreAverage=(int)(iScoreSum/deqScore.size()); //給歌手設(shè)置得分

singer.iLatestScore=iScoreAverage;}【題目分析】淘汰賽規(guī)則//淘汰賽voidCSingingCompetition::Knockout(){ TRACE("*************第%d輪淘汰賽：*************\n",m_iRound); intiSingerIndex=0; //第幾個歌手正在演唱，1代表第一個歌手，2代表第二個歌手。。。

for(list<int>::iteratorit=m_lstRemainingID.begin();it!=m_lstRemainingID.end();) { ++iSingerIndex; //生成歌手的分數(shù)

MakeScore(m_mapSinger[*it]);

//記錄當前演唱小組歌手的得分情況，按分數(shù)降序排列

m_mltmapCurGroup.insert(pair<int,int>(m_mapSinger[*it].iLatestScore,*it)); if(iSingerIndex%6==0) { //小組演唱完畢，打印小組得分情況，淘汰刪除歌手

...... } else { ++it; } }}第一輪第一個小組得分記錄multimap<int,int,greater<int>>m_mltmapCurGroup【題目分析】淘汰賽規(guī)則//淘汰賽voidCSingingCompetition::Knockout(){ TRACE("*************第%d輪淘汰賽：*************\n",m_iRound); intiSingerIndex=0; //第幾個歌手正在演唱，1代表第一個歌手，2代表第二個歌手。。。

for(list<int>::iteratorit=m_lstRemainingID.begin();it!=m_lstRemainingID.end();) { ++iSingerIndex; //生成歌手的分數(shù)

MakeScore(m_mapSinger[*it]); //記錄當前演唱小組歌手的得分情況，按分數(shù)降序排列

m_mltmapCurGroup.insert(pair<int,int>(m_mapSinger[*it].iLatestScore,*it)); if(iSingerIndex%6==0) {

//小組演唱完畢，打印小組得分情況，淘汰刪除歌手

...... } else { ++it; } }}【題目分析】淘汰賽規(guī)則 if(iSingerIndex%6==0) { //小組演唱完畢，打印小組得分情況

PriteGroupScore(); //在當前小組中淘汰歌手

EraseInCurGroup(); //在剩余歌手中刪除歌手

EraseInRemainingID(it++); } else { ++it; }【題目分析】淘汰賽規(guī)則 if(iSingerIndex%6==0) { //小組演唱完畢，打印小組得分情況

PrintGroupScore();

//在當前小組中淘汰歌手

EraseInCurGroup(); //在剩余歌手中刪除歌手

EraseInRemainingID(it++); } else { ++it; }【題目分析】打印當前小組的分數(shù)//打印當前小組的分數(shù)voidCSingingCompetition::PrintGroupScore(){ TRACE("小組得分情況：\n"); for(multimap<int,int,greater<int>>::iteratorit=m_mltmapCurGroup.begin();it!=m_mltmapCurGroup.end();++it) { TRACE("%s的得分：%d\n",m_mapSinger[it->second].strName.c_str(),it->first); } TRACE("\n");}【題目分析】淘汰賽規(guī)則 if(iSingerIndex%6==0) {

//小組演唱完畢，打印小組得分情況

PriteGroupScore(); //在當前小組中淘汰歌手

EraseInCurGroup(); //在剩余歌手中刪除歌手

EraseInRemainingID(it++); } else { ++it; }【題目分析】在當前小組中淘汰歌手voidCSingingCompetition::EraseInCurGroup(){ intiSingerLastIndexInGroup=0; //組內(nèi)歌手的倒數(shù)索引

while(iSingerLastIndexInGroup<3) { //獲取當前演唱小組的最后一個元素的迭代器

multimap<int,int,greater<int>>::iteratorit=m_mltmapCurGroup.end();

--it; ++iSingerLastIndexInGroup; if(m_iRound==1) { //記錄第一輪淘汰賽中被淘汰的歌手的參賽號

m_vecIDBeEliminatedInFirstRound.push_back(it->second); } elseif(m_iRound==2) { //記錄第二輪淘汰賽中被淘汰的歌手的分數(shù)

m_mltsetScoreBeEliminatedInSecondRound.insert(m_mapSinger[it->second].iLatestScore); }

//從當前演唱小組的集合容器中刪除最后一個元素

m_mltmapCurGroup.erase(it); }}【題目分析】淘汰賽規(guī)則 if(iSingerIndex%6==0) {

//小組演唱完畢，打印小組得分情況

PriteGroupScore();

//在當前小組中淘汰歌手

EraseInCurGroup();

//在剩余歌手中刪除歌手

EraseInRemainingID(it++); } else { ++it; }【題目分析】在剩余歌手中刪除歌手voidCSingingCompetition::EraseInRemainingID(list<int>::iteratorit){ intiSingerReverseIndexInGroup=0; //逆向遍歷的索引

while(iSingerReverseIndexInGroup<6) { //查找逆向遍歷迭代器所指的參賽ID所對應(yīng)歌手的{分數(shù)，參賽ID}是否在當前演唱小組中

multimap<int,int,greater<int>>::iteratoritMltmapScoreToID= find(m_mltmapCurGroup.begin(),m_mltmapCurGroup.end(), multimap<int,int,greater<int>>::value_type(m_mapSinger[*it].iLatestScore, *it)); if(itMltmapScoreToID==m_mltmapCurGroup.end()) { //沒找到，從剩余歌手集合中刪除該歌手的參賽號

it=m_lstRemainingID.erase(it); } //逆向遍歷的索引自增

++iSingerReverseIndexInGroup; //防止對容器的begin()迭代器進行--操作。

if(it!=m_lstRemainingID.begin()) { --it; } } //清除該組的比賽記錄存儲，以便下一組比賽記錄的存儲

m_mltmapCurGroup.clear();}【題目分析】淘汰賽規(guī)則 if(iSingerIndex%6==0) {

//小組演唱完畢，打印小組得分情況

PriteGroupScore();

//在當前小組中淘汰歌手

EraseInCurGroup(); //在剩余歌手中刪除歌手

EraseInRemainingID(it++); //不可用++it代替，因為要轉(zhuǎn)入自增之前的迭代器

} else { ++it; }第一輪第一個小組比賽完后容器的變化multimap<int,int,greater<int>>m_mltmapCurGroupvector<int>m_vecIDBeEliminatedInFirstRoundlist<int>m_lstRemainingID第一輪第二個小組比賽完后容器的變化multimap<int,int,greater<int>>m_mltmapCurGrouplist<int>m_lstRemainingIDvector<int>m_vecIDBeEliminatedInFirstRound第一輪四組全部比賽完后容器的變化list<int>m_lstRemainingIDvector<int>m_vecIDBeEliminatedInFirstRound【題目分析】第一輪淘汰賽//第一輪淘汰賽voidCSingingCompetition::FirstKnockout(){ if(m_iRound==0) { m_iRound=1; //進行淘汰賽

Knockout(); TRACE("第%d輪淘汰賽中被淘汰的歌手的名字：\n",m_iRound); for(vector<int>::iteratorit=m_vecIDBeEliminatedInFirstRound.begin();it!=m_vecIDBeEliminatedInFirstRound.end();++it) { TRACE("%s",m_mapSinger[*it].strName.c_str()); } TRACE("\n"); TRACE("\n"); }}【題目分析】講解綱要一、總體分析所需要的結(jié)構(gòu)體，類，類的外部接口，類的成員變量；二、報名參加比賽的具體分析；三、第一輪淘汰賽的分析；四、第二輪淘汰賽的分析；五、決賽的分析。第二輪比賽前l(fā)ist<int>m_lstRemainingID【題目分析】第二輪淘汰賽voidCSingingCompetition::SecondKnockout(){ if(m_iRound==1) {

m_iRound=2; //進行淘汰賽

Knockout(); //邏輯與第一輪差不多，區(qū)別在下頁

TRACE("第%d輪淘汰賽中被淘汰的歌手的分數(shù)：\n",m_iRound); for(multiset<int>::iteratorit=m_mltsetScoreBeEliminatedInSecondRound.begin();it!=m_mltsetScoreBeEliminatedInSecondRound.end();++it) { TRACE("%d",*it); } TRACE("\n"); TRACE("\n"); }}【題目分析】在當前小組中淘汰歌手voidCSingingCompetition::EraseInCurGroup(){ intiSingerLastIndexInGroup=0; //組內(nèi)歌手的倒數(shù)索引

while(iSingerLastIndexInGroup<3) { //獲取當前演唱小組的最后一個元素的迭代器

multimap<int,int,greater<int>>::iteratorit=m_mltmapCurGroup.end(); --it; ++iSingerLastIndexInGroup; if(m_iRound==1) { //記錄第一輪淘汰賽中被淘汰的歌手的參賽號 m_vecIDBeEliminatedInFirstRound.push_back(it->second); } elseif(m_iRound==2) { //記錄第二輪淘汰賽中被淘汰的歌手的分數(shù) m_mltsetScoreBeEliminatedInSecondRound.insert(m_mapSinger[it->second].iLatestScore); } //從當前演唱小組的集合容器中刪除最后一個元素

m_mltmapCurGroup.erase(it); }}第二輪兩組比賽完后容器的變化list<int>m_lstRemainingIDmultiset<int>_mltsetScoreBeEliminatedInSecondRound【題目分析】講解綱要一、總體分析所需要的結(jié)構(gòu)體，類，類的外部接口，類的成員變量；二、報名參加比賽的具體分析；三、第一輪淘汰賽的分析；四、第二輪淘汰賽的分析；五、決賽的分析?！绢}目分析】決賽voidCSingingCompetition::Finals(){ if(m_iRound==2) { m_iRound=3; //第三輪決賽

for(list<int>::iteratorit=m_lstRemainingID.begin();it!=m_lstRemainingID.end();++it) {

//生成歌手的分數(shù)

MakeScore(m_mapSinger[*it]); //記錄當前小組歌手的得分情況，按分數(shù)降序排列

m_mltmapCurGroup.in