網(wǎng)站管理員可控的關(guān)鍵節(jié)點(diǎn)跨境電商怎么開店鋪
我們要開始學(xué)習(xí)map和set的使用,雖然使用更加復(fù)雜,但是STL整體的設(shè)計,本身就具有很強(qiáng)的前瞻性和延續(xù)性,比如說迭代器等,我們順著文檔來看。這也是除了vector之外最重要的容器,當(dāng)然還有unordered_map 和 unord_set,其實(shí)這幾個也是C++里面用的最多的。
Set學(xué)習(xí)
模版參數(shù)
這里的set呢,它只有一個模版參數(shù)可就是T,然后還有一個比較器,默認(rèn)是小于,它給一個比較器呢,就是為了,有些地方默認(rèn)的operator <重載的比較不符合你的要求,假設(shè)你用的是指針,但是指針是按地址比較大小,當(dāng)這個T是一個指針的時候,但是你不想按地址比較大小,那么原生的行為不符合怎么辦,那你是不是就可以傳仿函數(shù)呀,去控制里面的比較規(guī)則呀。在下面就是空間配置器,它是負(fù)責(zé)申請內(nèi)存。
insert()
我們看到函數(shù)參數(shù)中有一個,value_type類型,但是不知道這個是什么類型。我們先寫一個最簡單來看看。
》set s;set 沒有push() ,線性表、鏈表、隊(duì)列等都是線性結(jié)構(gòu),才會有push()接口 。后面非線性結(jié)構(gòu)的都是insert()接口了。我們隨便插入一些數(shù)據(jù)s.insert(4);s.insert(5)…我們插入5個值。然后我們定義一個迭代器,set::iterator it = s.begin();這個set呢,它是一個雙向迭代器,它底層用了特殊的算法迭代,是走的另一種非遞歸,后面也會講,不用像我們在前面的二叉樹OJ那里用棧模擬,但是它這里非遞歸有前提的,前提就是,它要有三叉鏈,它的邏輯底層是有parent成員變量的,反正我們先不管,后面我們才討論底層。
》然后我們while循環(huán)遍歷,while(it != s.end()),cout<< *it << " ";it++然后我們看到,走出來就是有序的!其實(shí)它不僅僅是有序的,它是在有序的情況下還加了一些東西,如果值已經(jīng)有了,它還會不會插入?不會了!所以嚴(yán)格來說,它不是排序,而是一個排序?去重!
》它這塊支持迭代器,是不是有普通迭代器支持可讀可寫,還有const迭代器只讀。然后它還有反向迭代器,就不演示了。
》它既然支持迭代器,那么就會支持范圍for。其實(shí)范圍for和我們迭代器在底層上是一樣的,只是在上層看來有些區(qū)別。
》我們發(fā)現(xiàn),const迭代器和普通迭代器都是不支持修改的 ,雖然一個叫iteratro,一個叫const iterator,但是底層都是用的一個const_iterator來實(shí)現(xiàn)的。
》另外重載的兩個insert()函數(shù)用的很少。平時也很少用在某一個位置插入,這個接口價值很小。
》insert()不會有迭代器失效的問題,不像順序表,挪動數(shù)據(jù)會影響相對關(guān)系,它的erase()是會有迭代器失效的問題。
void test_set1()
{set<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);// 排序 + 去重 set<int>::iterator it = s.begin();while (it != s.end()){//*it = 10;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;
}
empty()/size()/max_size()
erase()/find()—兩個是要配合的
erase()函數(shù)主要有兩種,一種是在某個位置刪除,另外一種是刪除某一個具體的值。第三種刪除特定的區(qū)間,這個用的很少。
》這塊要玩刪除的話,就得配合find()函數(shù)。我們前面插入了很多值,我們隨便set::iterator it = find(2)一個值,那么我們**怎么判斷是找到還是沒找到呢?**如果元素被找到了,是會返回value值對應(yīng)的迭代器,查找失敗就會返回end()迭代器。是不是就是if(pos != s.end())就是找到了呀。
》我們來對比一下,set自帶的find()和算法里面的find()有什么區(qū)別呢? set::iterator it = find(20) 和 pos = find(s.begin(),s,end(),20),算法里面的find,能不能行呢?是行的。它們的區(qū)別很大,數(shù)據(jù)量小還好,數(shù)據(jù)量大就會差別很大。set的find()的效率是logN,而算法的查找效率是O(N),因?yàn)樗惴ǖ氖潜┝Σ檎?。這個算法的find()查找不是給set用的,而是給像vector它們用的。
void test_set2()
{set<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);set<int>::iterator pos = s.find(20); // O(logN)if (pos != s.end()){cout << "set.find找到了" << endl;}pos = find(s.begin(), s.end(), 2); // O(N)if (pos != s.end()){cout << "find找到了" << endl;}
}
》如果我們要erase了呢?,我想將我從鍵盤中輸入的值erase()掉,通過find()查找我們輸入的值再去erase(迭代器)。當(dāng)erase()成功之后,對應(yīng)的位置就不能訪問了,已經(jīng)是失效了。我們可以通過查找進(jìn)行持續(xù)的刪除。我們還可以直接傳參數(shù)去刪除,即erase(3);也就是你可以理解成,這個erase(3),相當(dāng)于調(diào)用了find()?erase(迭代器)。
》前面第一種是先是找到了再去刪除,它們會有什么區(qū)別呢?第二種用法,如果沒有找到直接去刪除是不會報錯的;而你第一種調(diào)用了find()沒有找到,你還是去刪除,是會報錯的。
》size_type erase(value)是會返回一個size_type類型的數(shù)據(jù),他為什么不用bool類型呢,是因?yàn)樗土硗庵v的東西契合起來。我們能夠看到,刪除成功是返回1,刪除失敗是會返回0,為什么是返回這個,而不是返回bool呢?因?yàn)榇龝何覀冞€要學(xué)另外一個版本,另外一個版本是允許冗余的。
void test_set3()
{set<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);cout << s.erase(3) << endl;cout << s.erase(30) << endl;for (auto e : s){cout << e << " ";}cout << endl;set<int>::iterator pos = s.find(3);if (pos != s.end())s.erase(pos);for (auto e : s){cout << e << " ";}cout << endl;/*int x;while (cin >> x){set<int>::iterator pos = s.find(x);if (pos != s.end()){s.erase(pos);cout << "刪除" << x << "成功" << endl;}else{cout << x << "不在set中" << endl;}for (auto e : s){cout << e << " ";}cout << endl;}*/if (s.count(5)){cout << "5在" << endl;}if (s.find(5) != s.end()){cout << "5在" << endl;}
}
swap()
swap()就跟我們以前講的一樣,比如說你要交換兩個set的對象,用算法的swap()直接交換是深拷貝,是樹的拷貝,代價很大,所以set自己有一個swap(),它們交換指針,代價小很多。
count()
count()函數(shù)這個設(shè)計是和一個版本對應(yīng)起來的,就是你給我一個值,我看一下這個值在我set里面有幾個,在這里的set而言,無非就是1個和0個。但是待會兒還有一個對稱的版本。我們說了,有些場景可能需要的不是排序?去重,而只是排序,那么它們就設(shè)計了multile版本,它是多樣性的意思,它是允許冗余的,它們的接口設(shè)計都是保持的一致。
》count()函數(shù)有一個非常有意義的點(diǎn)就是,判斷在不在,比用find()方便。比如說,我要判斷一個值在還是不在,用count()是不是就很方便呀,比如說我要count(3),if(s.count(3))看一下這個3在不在,在的話是會返回1,不在的話,是會返回0。如果用find()的話就沒那么方便了嗎,要這樣if(s.find(3) != s.end())是不是相對來說不太方便了。
lower_bound()函數(shù)
lower_bound()是干嘛呢?比如lower_bound(30)是幫你去找 >= 30的值的迭代器,但是它在這兒又有一點(diǎn)問題,lower_bound()和upper_bound()的返回值還有點(diǎn)不一樣。我們試驗(yàn)一下。
》你看set::iterator lowIt = s.lower_bound(3);如果有3,它會返回3位置的迭代器,沒有就返回 > 3的值,我們插入的值里面是有3的,所以返回的是3 的迭代器。如果是set::iterator lowIt = s.lower_bound(6);我們插入里面沒有6,那它會返回什么呢?返回的是7的迭代器。
》它什么情況下比較有用么,比如說:要求刪除 >= x的所有值,那么你就不用遍歷去刪除了,這里的lower_bound()函數(shù)就可以幫干這件事情,怎么刪除呢?不要忘了,我們的erase()是支持迭代器區(qū)間的刪除!那么erase()左區(qū)間可以給個lowIt變量,右區(qū)間可以給end(),相當(dāng)于是左閉右開【),即erase(lowIt,s.end());
void test_set4()
{set<int> s;s.insert(4);s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(9);// 返回>= val得位置迭代器 3返回3位置 6 返回7位置/*set<int>::iterator lowIt = s.lower_bound(3); 存在lowIt = s.lower_bound(6); 不存在*/for (auto e : s){cout << e << " ";}cout << endl;// 要求刪除>=x的所有值int x;cin >> x;set<int>::iterator lowIt = s.lower_bound(x);s.erase(lowIt, s.end());for (auto e : s){cout << e << " ";}cout << endl;
}
upper_bound()
比如upper_bound(60),如果有60的話,它是不回返回60,而是返回 > 60的值,我們來驗(yàn)證一下。這里我們比如說是,set::iterator upIt = s.upper_bound(5),我們傳一個5,然后再來一個,set::iterator upIt = s.upper_bound(6),我們傳的是6,這兩個區(qū)別就是一個值在我們插入的里面,一個是不存在。我們來看看結(jié)果,我傳的是5,有5它返回5了嗎?答案是:不會的!它返回的是7,我傳的是6,它返回的是7。所以,這里的upper_bound(),它要找的不是 >=的值,它是返回 > x位置的迭代器。
》所以upper_bound和lower_bound,一個是返回 >=,一個是返回 >。其實(shí)他們**兩個可以配合起來并配合ease(),貫徹“左閉右開【)”。**比如說要刪除 x <= [] <=y的區(qū)間,是不是就可以將這兩個配合起來使用了呀。比如auto leftIt = s.lower_bound(x),auto rightIt = s.upper_bound(y),erase(letfIt,rightIt)所以它會刪除【x,y】
void test_set5()
{set<int> s;s.insert(4);s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(9);for (auto e : s){cout << e << " ";}cout << endl;// 返回>x位置的迭代器 -》 都是返回 7位置的迭代器//set<int>::iterator upIt = s.upper_bound(5); // 存在//upIt = s.upper_bound(6); // 不存在// 刪除x <= <= y的區(qū)間 刪除 [x,y]int x, y;cin >> x >> y;auto leftIt = s.lower_bound(x); // [auto rightIt = s.upper_bound(y); // )s.erase(leftIt, rightIt);for (auto e : s){cout << e << " ";}cout << endl;
}
講講multiset版本
multiset它是允許鍵值冗余的,它的用法和set一樣的,但就是要記一下它的名字,比如mutilset mS;它是排序不去重。
》真正有區(qū)別的就是count()函數(shù),比如說你要統(tǒng)計一個值s.count(1);set版本那邊的count沒有給bool類型的返回值,而是給int類型返回值,這其實(shí)是為保證接口的設(shè)計一致。其實(shí)set不需要count,是個bool就行了,但是為了和multiset保持一致,返回值類型也是int。
》同樣的,set版本里面的erase()函數(shù)的返回值不是bool,而是size_type,也是為了和multiset里面的erase()設(shè)計保持一致,可以返回刪除了幾個對應(yīng)的值。
》還有一個區(qū)別就是這里的find()函數(shù),比如我這里有多個同樣的值,那么我auto pos = s.find(3)會返回哪個3的迭代器呢?那么這里就可以做一件事情,它會返回中序的第一個,可以由while(pos != s.end())cout << *pos << " ";++pos驗(yàn)證。我們以后講了搜索樹,會知道,插入的時候,樹是會旋轉(zhuǎn)的,所以同樣的值插入在左邊還是右邊都不影響。
void test_set6()
{multiset<int> s;s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(2);s.insert(1);s.insert(3);s.insert(3);s.insert(3);s.insert(3);// 排序 set<int>::iterator it = s.begin();while (it != s.end()){//*it = 10;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;cout << s.count(1) << endl;cout << s.erase(1) << endl;for (auto e : s){cout << e << " ";}cout << endl;// 多個x的話,find返回中序第一個xauto pos = s.find(3);while (pos != s.end()){cout << *pos << " ";++pos;}cout << endl;
}
看一下題目
題一:
兩個數(shù)組的交集,找交集怎么找呢?是不是可以考慮這樣,你也有,我也有的就是交集。
》最簡單的方案就是,將其中一個數(shù)組放進(jìn)set里面,我直接去你里面找,是不是太慢了。我們可以遍歷將值inser()插入進(jìn)set里面。然后繼續(xù)遍歷另一個數(shù)組,在我們的set里面找對應(yīng)的值,那其中是不是就可以用count()函數(shù)而不必調(diào)用find()函數(shù)呀,然后,存在的話,就將值插入到我們另一個開辟的數(shù)組里面。但是這里有可能過不去,為什么呢?因?yàn)樵谖覀冮_辟的vector來存交集的值,會有重復(fù)!因?yàn)榻患请[形的要求你去重的。
》那你的另一個數(shù)組是不是也用set來去重一下呀。但是這個算法不夠高效,因?yàn)?#xff0c;假設(shè)你set里面有n個元素,那么每調(diào)用一次count()的時間復(fù)雜度是logN,那么總的時間復(fù)雜度是不是N*logN。
》還有一個優(yōu)化算法,這個優(yōu)化算法在很多找交集都能有效。找并集的話,只需要一個set就行了?,F(xiàn)在來說一個交集/差集的優(yōu)化算法,這個算法不一定要set,但是set用在這里剛剛好。
》我們inset()到set之后是不是就相當(dāng)于有序了呀,有了排序就好說。如果你要求并集的話,只要放到一個set里面就行了,它是可以去重的。那么交集和差集怎么搞呢,有些地方需要同步,同步數(shù)據(jù)的話就要找交和差集。
》兩個數(shù)組已經(jīng)是有序了的,然后分別有一個指針先是指向各自的開始。交集的話:兩個相比較的話,1.小的++;2.相等的就是交集,同時++;3.有一個結(jié)束就結(jié)束了。這個優(yōu)化之后就變成了時間復(fù)雜度是2N了。
》這個算法除了可以找交集,還可以找差集。1.相比較,小的就是差集,小的++;2.相等的話,同時++;3.一個走到頭了,另一個剩下的是不是也屬于差集了。
》差集和交集在,服務(wù)器和你網(wǎng)盤需要同步的時候是有用到的。比如你有一個服務(wù)器文件夾和一個本地文件夾,你要將本地文件同步到服務(wù)器文件里面,相當(dāng)于備份嘛,那是不是一方刪除,另一方也會刪除,你添加的,另一方是不是也要添加呀。
map
首先map數(shù)據(jù)結(jié)構(gòu)里面呢,有一個Key和Value。它里面有一個valuse_type類型,它里面不是把數(shù)據(jù)分開存儲的,不像我們前面講的,自己寫的搜索樹里面,單獨(dú)分開定一個key和value,而map,它是將key和value是放在一個結(jié)構(gòu)里面的,這個結(jié)構(gòu)是在C++里面被定義成pair<>類型,pair就是一對一對的意思,在map這里呢叫做鍵值對。
insert()
》我們先用map來存一個字典的例子,map的insert()插入的一個值是value_type類型的,value_type其實(shí)就是pair<>類型的數(shù)據(jù)。pair<>類型呢,有兩個參數(shù),第一個參數(shù)叫做first,第二個參數(shù)叫做second。
》如果我們想插入的話,map<string, string>dict;dict.insert(pair<string,string>(“sort”,“排序”));這是第一種,匿名對象的一種傳參數(shù),用起來比正常的要舒服很多。第二種,正常點(diǎn)是這樣的,pair<string,string>kv(“insert”,“插入”);dict.insert(kv);還有第三種方式,用起來更爽:用到make_pair,make_pair就是制造一個pair對象,即dict.insert(make_pair(“l(fā)eft”,左邊));
》前面第一、第二種都是借用的pair的構(gòu)造函數(shù)來進(jìn)行。第三種,make_pair是一個函數(shù)模版,它的優(yōu)勢是不用聲明參數(shù),讓它自動推導(dǎo)。第四種,還能這么寫,dict.insert({“right”,右邊});雖然知道可以這么寫,但是目前還是不太清楚為什么,這個涉及到C++11點(diǎn)類型轉(zhuǎn)換,C++11再講。
》map的遍歷:map<string,string>::iterator it = dict.begin();我們也說過,如果你清楚的情況下可以用auto讓它自己推導(dǎo)。while(it != dict.end())coyt << it << " ";++it;**發(fā)現(xiàn)不支持it**。有沒有人想過,你直接分別單獨(dú)用變量表示key和value不就好了嘛,為什么要封裝一個pair?這個地方就能看出來,為什么要搞一個pair了。這個map的迭代器和鏈表的迭代器有些相似,它用自定義類型去封裝,封裝節(jié)點(diǎn),只不過在map這里是一個樹的節(jié)點(diǎn),那么解引用是不是去調(diào)用operator呀,那C++是否支持一個函數(shù)返回兩個值呢?這里it本質(zhì)是it->operator(),它是不是要返回節(jié)點(diǎn)里面的數(shù)據(jù)呀,對于set還好,set里面只有一個key,但是map這里是一個key和value,那C++是否支持一次返回兩個值呢?不支持是吧,但是你這里用到了模擬解引用的行為,那就要返回節(jié)點(diǎn),如果你這里分別單獨(dú)用變量表示key和value就沒辦法搞了,所以我把key和value給你打包成一個結(jié)構(gòu)數(shù)據(jù),這個結(jié)構(gòu)數(shù)據(jù)就叫做pait<>類型,所以operator,返回的是節(jié)點(diǎn)數(shù)據(jù),這個節(jié)點(diǎn)數(shù)據(jù)是一個pair<>類型。
》但是你這類型pair<>支不支持流呢,即cout << it嗎?答案是:不支持。有同學(xué)說,我們來支持一下就可以了,但是支持的話是不是就要改庫里面的代碼呀,那么我們換一種方法玩。你不是一個結(jié)構(gòu)嘛,那么我們就是cout << (*it).first << “:” << (*it).second << endl;但是在這種地方,你的迭代器是不是指針的行為呀,那你還用解引用*嗎?不會,而是用迭代器重載的->運(yùn)算符來用*,即cout << it->first << “:” << it->second << endl;
》那這里的范圍for,for(const auto& kv : dict),kv其實(shí)是返回的*解引用后的pair數(shù)據(jù)類型,用kv.first()和kv.second()來訪問。
void test_map1()
{map<string, string> dict;// pair構(gòu)造函數(shù)dict.insert(pair<string, string>("sort", "排序"));pair<string, string> kv("insert", "插入");dict.insert(kv);// make_pairauto ret1 = dict.insert(make_pair("left", "左邊"));auto ret2 = dict.insert(make_pair("left", "剩余"));dict["operator"] = "重載"; // 插入+修改dict["left"] = "左邊、剩余"; // 修改dict["erase"]; // 插入cout << dict["left"] << endl; // 查找// C++11 再講//dict.insert({ "right", "右邊" });// 遍歷//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){//cout << *it << " "; // it->operator*()//cout << (*it).first << ":" << (*it).second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (const auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}
}//mapped_type& operator[] (const key_type& k)
//{
// pair<iterator,bool> ret = insert(make_pair(k, mapped_type()));
//
// //return (*(ret.first)).second;
// return ret.first->second;
//}
那你現(xiàn)在統(tǒng)計水果出現(xiàn)的次數(shù)是不是就很方便了呀,先構(gòu)建一顆map樹,map<string,int> countMap;for(aoto& str : arr)是不是就可以先調(diào)用map的find()函數(shù),auto it = countMap.find(str);如果水果沒有插入到我們的樹里面,那么我們就構(gòu)建一個pair<string,int>,即countMap.insert(make_pair(str,1));如果已經(jīng)存在了,就it->second++;
void test_map2()
{string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };// 17:08繼續(xù)/*map<string, int> countMap;for (auto& str : arr){map<string, int>::iterator it = countMap.find(str);if (it != countMap.end()){it->second++;}else{countMap.insert(make_pair(str, 1));}}*///map<string, int> countMap;//for (auto& str : arr)//{// //pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));// auto ret = countMap.insert(make_pair(str, 1));// if (ret.second == false)// {// ret.first->second++;// }//}map<string, int> countMap;for (auto& str : arr){countMap[str]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}int main()
{//test_set6();test_map1();return 0;
}
其實(shí)map這里最重要的就是剛剛講的,那么剛剛上面講的呢還有優(yōu)化的空間,這個優(yōu)化的空間是要幫我們?nèi)ジ愫竺娴氖虑椤?/p>
map<string, int> countMap;for (auto& str : arr){map<string, int>::iterator it = countMap.find(str);if (it != countMap.end()){it->second++;}else{countMap.insert(make_pair(str, 1));}}
這個代碼其實(shí)是可以改進(jìn)優(yōu)化的。find()這里有這么一個問題,我去find()是不是一直去找,不在的話是不是我就相當(dāng)于從根找到尾了呀,沒有的話,我就得去插入,插入是不是又得去找一次,那是不是重復(fù)了呀,find()找一次,沒找到后,insert又找了一次。其實(shí)不優(yōu)化也無關(guān)痛癢,但是這里講優(yōu)化是為下面做鋪墊,為下面的玩法做鋪墊。
》所以這里就可以用insert()來做一件事情,正常的呢,insert()的返回值是一個pair<>類型的數(shù)據(jù),pair的first數(shù)據(jù)被設(shè)置成為一個iterator迭代器,這個迭代器指向兩種可能,要么指向新插入的元素(插入成功),要么指向與key相等的元素(插入不成功)。意味著是這樣的,我insert()返回的pair<>類型的數(shù)據(jù),first是一個迭代器,這個迭代器呢,一定是指向一個位置的,要么是你新插入元素的迭代器,要么是沒有插入成功,因?yàn)榉慈哂嗟穆?#xff0c;那么itreator就是已經(jīng)有了的元素的迭代器。那么pair<>的second數(shù)據(jù)類型是一個bool,如果是新插入的,那就是true,如果已經(jīng)有相等的了,就是flase。也就是說,它插入成功或者失敗是會返回bool值的。我insert()返回的pair的迭代器不管你是插入成功還是失敗都會返回一個元素的位置,那么就可以利用起來。
》就拿上面統(tǒng)計水果個樹來說,如果水果已經(jīng)存在map里面了,還會插入嗎?不會。**這個待會兒對我們理解"[]"的使用非常重要 。**它insert()返回的pair類型的值非常有意義和我們待會兒要講的“【】”有很大關(guān)系。我們插入atuo ret1 = dict.insert((“l(fā)eft”,左邊))和auto ret2 = dict.insert((“l(fā)eft”,剩余)),按理來說第一次插入的left是成功的,ret1的second數(shù)據(jù)是true,first數(shù)據(jù)是新插入元素的迭代器;第二次插入left,ret2的second數(shù)據(jù)是flase,然后ret2的first數(shù)據(jù)和ret2一樣的。
》我們就可以進(jìn)行對上面代碼改進(jìn),不需要再調(diào)用find()函數(shù)了,就調(diào)用insert()就行。我們不管有沒有插入,都調(diào)用insert()函數(shù),即pair<map<string,int>::iterator,bool> ret = countMap.insert(make_pair(str,1));寫簡單一點(diǎn)就是auto ret = countMap.insert(make_pair<str,1>);有兩種情況,插入成功我用不用管,我不管,也就是第一次出現(xiàn),那么返回的pair的second是一個true;插入失敗,說明水果已經(jīng)有了,那么insert()是不是同時充當(dāng)了find()的作用,因?yàn)樗褜?yīng)的元素的迭代器也給我了。 if(ret.second == false)那就是插入失敗,已經(jīng)有該水果了,所以ret.first->second++;
map<string, int> countMap;for (auto& str : arr){pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));auto ret = countMap.insert(make_pair(str, 1));if (ret.second == false){ret.first->second++;}}
operator[]
》其實(shí)我們統(tǒng)計也不會用這個方法,這個方法太憋屈了,我們**講這個真正的目的是為了玩“【】”**這個重載運(yùn)算符,而且C++里面的map非常喜歡用“【】”,如果說map的話,我們重點(diǎn)學(xué)習(xí)的就是這個“【】”重載運(yùn)算符。我們統(tǒng)計次數(shù)怎么統(tǒng)計,我先寫好:
map<string, int> countMap;for (auto& str : arr){countMap[str]++;}
此書成功統(tǒng)計出來,沒有毛病,這個“【】”很絕。一句代碼統(tǒng)計完次數(shù)!就用了operator []這么一個重載運(yùn)算符。
》operator[]返回值是一個mapped_type&類型。我們想想,我們什么時候重載過operator[]了?我們在vector、string的時候重載了operator[],但是這里map支持隨機(jī)訪問嗎?并不支持,目的也不是。
》其實(shí)這里map的operator[]已經(jīng)改變了[]的意義了,它不是隨機(jī)訪問,它的參數(shù)也不是下標(biāo)。它的參數(shù)是key,返回值是value的引用&。
》那么這里怎么做到一句話就統(tǒng)計了此書呢?insert()都沒有了嗎?我們來看看源碼實(shí)現(xiàn),
這個代碼能把人看崩掉,我們簡化一下代碼,我們先提取出(this->insert(make_pair(K,mapped_type()))).first,這一串其實(shí)是誰呢?實(shí)際上就是調(diào)用了insert()嘛。
》insert的返回值是不是pair<map<>::iterator,bool>類型數(shù)據(jù)呀,即pair<map<>::iterator,bool> ret = insert(make_pair(K,mapped_type())),然后它取了ret的first數(shù)據(jù),first是個什么呢,不就是指向節(jié)點(diǎn)的迭代器嘛。
》所以一開始的代碼就可以理解成
pair<map<>::iterator,bool> ret = insert(make_pair(K,mapped_type()))
return (*(ret.first)).second;
》其實(shí)這個也繞了一點(diǎn),其實(shí)等價于:
pair<map<>::iterator,bool> ret = insert(make_pair(K,mapped_type()))
return (ret.first)->second;
我們在“【】”里面給的是key值,有兩種情況:1.Key在map對象中;2.Key不在map對象中。這里是精華,很多面試中都會考這里。
》第一種,Key在map對象中,我們要進(jìn)行插入,make_pair(k,mapped_type())中的mapped_type()是個啥?我們先來看看mapped_type是誰?是不是T類型,就是Value的類型呀,也就是第二個模版參數(shù)的類型,第一個模版參數(shù)的類型是key的類型,K嘛。那么mapped_type()是不是用Value類型進(jìn)行構(gòu)造的匿名對象呀!
》也就是說,你來了一個Key,我不管你在不在,我先insert(0。假設(shè)第一種情況,Key是存在的,那么插入失敗,那么insert()也就會插入失敗,那么你pair<map<>::iterator,bool> ret = insert(make_pair(K,mapped_type()))中的ret的second數(shù)據(jù)bool類型就是flase!first數(shù)據(jù)就是Key所在節(jié)點(diǎn)的迭代器。然后return (*(ret.first)).second;可能早期沒有支持“->”這個符號,所以我們現(xiàn)在支持,就這樣寫:ret.first->second------>這個是不是就是節(jié)點(diǎn)的Value值呀。并且不要忘了**,我operator[]的返回值,是Value的引用&!引用的作用是:1.減少拷貝;2.支持修改!**
》所以此時operato[]的作用有兩層:1.查找K對應(yīng)的Value;2.修改K對應(yīng)的Value值。
》第一種情況,插入失敗,insert()完全沒有起作用,它反而充當(dāng)?shù)氖遣檎业淖饔?/strong>。它這里的operator[]返回值只用的是insert()返回值的first,即返回節(jié)點(diǎn)的迭代器。插入成功還是失敗無所謂呀,為什么呢?如果Key在map對象中,肯定插入失敗嘛;
》第二種情況,如果Key不在對象中,那么insert()是不是插入成功,operator[]的返回值是不是節(jié)點(diǎn)的迭代器中的Value值的引用&呀,這個值一開始是匿名構(gòu)造的對象,上面有說(如果Value是stirng類型就是空串,如果是int類型就是0,如果是指針類型就是空nullptr)。我返回的Value值的引用,那也就意味著充當(dāng)著 插入 和 修改兩層作用,你可以修改,也可以不修改。
》我們再來分析一下,我們寫的代碼:
countMap[str]++;
水果要是第一次出現(xiàn),那會先插入,插入的時候節(jié)點(diǎn)的個數(shù)是intt類型,它內(nèi)部會匿名構(gòu)造int類型對象就是0,但是operator[]會返回這個int的引用,我們在外面用了++,所以0會++;如果水果已經(jīng)有了,它們operator[]不會插入成功,它會返回水果所在節(jié)點(diǎn)的Value值的引用,然后Value值++。
》我們再從另外一個角度,我們知道這個之后呢,有些人插入字典就不會像我們一開始那樣寫了,而是這樣寫:
auto ret1 = dict.insert(make_pair("left", "左邊"));
auto ret2 = dict.insert(make_pair("left", "剩余"));
dict["operator"] = "重載"; // 插入+修改
dict["left"] = "左邊、剩余"; // 查找 + 修改
dict["erase"]; // 插入
cout << dict["left"] << endl; // 查找
所以operator[]是一個多元化功能,map的其他函數(shù)參考set就行了。
multimap
它和map不同的是,它是允許冗余的,它是可以插入Key相同的鍵值對的,哪怕你的Value值相同也是可以的,其他的東西和map其實(shí)是一樣的。
multimap<string,string> dict;
dict.insert(make_pair("left",“左邊”));
dict.insert(make_pair("left",“剩余”));
》相比map ,multimap使用函數(shù)接口最大的區(qū)別是什么?multimap不支持operator[];為什么呢?如果對于map你給一個Key,我是不是要么有,要么沒有,有的話,我就返回對應(yīng)的Value,沒有的話我好可以插入。但是mutiple有多個Key的時候,那么Key是不是面臨一對多的關(guān)系呀,所以不支持operator []也是情理之中的。
題目:前K個高頻單詞
這個題目是一個統(tǒng)計次數(shù)?topK的問題。我們不管三七二十一,先把各個單詞出現(xiàn)的次數(shù)統(tǒng)計出來,當(dāng)然可以用map來幫我們做KV映射,map<string, int> countMap;然后將words遍歷一遍就可以得到各個單詞出現(xiàn)的次數(shù)。
》接下來就是TopK的問題了。我們以前應(yīng)該是講過,如果建堆來解決,我們是不是要建小堆來解決是吧,但是我們不考慮用堆來解決,其實(shí)優(yōu)先級也就是堆,因?yàn)閮?yōu)先級隊(duì)列就是用堆來封裝的。因?yàn)槿绻枚训脑?#xff0c;選出K個之后還需要進(jìn)行排隊(duì)。
》我們的map<string, int>它所插入的值,是按照string來進(jìn)行排序的,但是我們要的是按int來進(jìn)行排序。sort()能對map進(jìn)行排序嗎?答案是:不能!因?yàn)閟ort()要求的是隨機(jī)迭代器,map顯然不滿足。那我們是不是要將map里面的值放到vector里面,然后就可以用sort()來進(jìn)行排序了呀,當(dāng)然vector存放的元素類型就是pair<string, int>了呀,即vrctor<pair<string, int>> vSort;
》當(dāng)然也可以不放pair類型,而是vector<map<string, int>::iterator> v;這和我們放pair<string, int>有什么區(qū)別呢?這種方案行不行呢? 大家想想待會兒用sort()是不是必然要自己控制比較方式呀,如果要自己控制比較方式的話,你放pair<>我要寫仿函數(shù),我放迭代器你是不是也得控制比較方式呀。大家想一想,我在vector里面放迭代器iterator后,能不能訪問到里面的Key和Value?是可以的。但是區(qū)別在哪里呢?如果你放的是pair<string, int>你待會兒得拷貝,把map里面的每一個數(shù)據(jù)都拷貝到pair里面,而我iterator迭代器就是一個指針,所以針對于拷貝的代價,我們還是選擇迭代器iterator比較好。
》由于迭代器寫出來很長,我們先typedef一下,typedef map<string, int>::iterator countIrer;然后我們就是遍歷map,將每一個節(jié)點(diǎn)的iterator都插入到vector里面。
》接下來就是用到sort()函數(shù)進(jìn)行排序了。 sort(v.begin(), v.end())這個時候能不能支持排序呢?是不能支持到,因?yàn)関ector的迭代器v.begin()解引用之后是map節(jié)點(diǎn)的迭代器,那么它支持排序嗎?不支持。不支持怎么辦?我們是不是得寫一個仿函數(shù)來控制排序使其支持呀。
》所以我們來寫一個仿函數(shù),struct IteCompare{}在其里面支持一個bool operator() (countIter ite1, countIter ite2)這里是支持迭代器進(jìn)行比較。大家想清楚,因?yàn)関ector里面的每一個數(shù)據(jù)是迭代器,我們將vector的迭代器傳給sort,sort解引用*是map節(jié)點(diǎn)pair的迭代器,所以是迭代器比較;那么迭代器比較,要用仿函數(shù)來控制比較并使其能支持比較,所以我們寫了bool operator() (countIter ite1, countIter ite2),然后函數(shù)體內(nèi)寫:return ite1->second > ite2->second;然后我們的仿函數(shù)就完成了。
》接下來就是將仿函數(shù)一并傳給sort(),即sort(v.begin,v.end(),IterCompare);記住IterCompare是類型,我們應(yīng)該傳一個對象給sort(),所以是用到匿名對象IteComapre(),即sort(v.begin,v.end(),IterCompare());
》然后我們排序好了,我們還得取出前K個,是不是還得再來一個vector ret;然后將排完序后的vector循環(huán)K次呀,并且將值push_bacnk()進(jìn)我們的ret里面。
》但是光光這樣還是不能提交成功,因?yàn)槲覀兊倪x出來的K個words單詞順序不對,因?yàn)槿绻麊卧~出現(xiàn)的次數(shù)相同的話,還得進(jìn)行ASICC碼排序,將出現(xiàn)次數(shù)相同的單詞進(jìn)行排序。
》按道理,一開始我們的countMap是按string的大小(也就是按照Key去排序的)進(jìn)行將每一個節(jié)點(diǎn)插入的,所以一開始就是將按string將words排序好了,然后緊接著我們再遍歷將每一個節(jié)點(diǎn)的迭代器放入vector了呀,此時也是按照words的string來進(jìn)行排序的,但是我們后面用了sort()之后,sort()是一個不穩(wěn)定的排序,它會將我們原來的words正確順序給打亂的。所以,你sort()完之后,選出來了K個,但是words的順序你還得再排一次,除非你用一個穩(wěn)定的排序。
》在sort()文檔里面它有告訴你,它sort()是一個不穩(wěn)定排序,它提供了一個stable_sort()是能夠保證穩(wěn)定性的。所以,我們將sort()換成stable_sort()試一下能不能通過,是能通過的。
》或者還有方法,你如果提前考慮到了這點(diǎn)的話,你可以在仿函數(shù)階段也將words的順序也控制好,即(ite1->second > ite2->second || ite1->second == ite2->second && ite1->first > ite2->first),所以我認(rèn)為次數(shù)大的肯定大,如果次數(shù)相等,再比較words來進(jìn)行排序。這樣就可以調(diào)用sort()了。這不是改變sort()的穩(wěn)定性,而是改變了比較的規(guī)則。但是會有一些性能的影響。
》我們還有別的方法,如果要排序,除了用sort(),是不是map本身也支持排序呀,只不過一開始是對string來排序的,我再定義一個map<int, string> sortMap;那么就是遍歷一遍countMap,然后sortMap.insert(make_pair(kv.second,kv.string));就是將K和V調(diào)個位置,但是map會進(jìn)行去重,所以我們還得用mutilmap才行,即mutilmap<int, string> sortMap;然后我們再去sortMap里面去取元素就行了,即for()循環(huán)K次,然后ret.push_back(it->second) ++it。但是取出來K個之后,它是按升序來的,顯然不符合我們的要求,此時我們的map、mutilmap都是支持自己定義比較方式的,這不就體現(xiàn)出來了嗎,所以,我們在定義sortMap的時候,還得傳入另外一個參數(shù),mutilmap<int, string, greater> sortMap;要傳入一個greater來進(jìn)行控制比較方式。
》最靠譜的還是sort或者srable_sort,因?yàn)槿绻胢ap的太依賴其底層的實(shí)現(xiàn)了。