優(yōu)秀網(wǎng)站的必備要素使用 ahrefs 進(jìn)行 seo 分析
在了解map之前,我們先看看兩個場景,通過這兩個場景的對比,讓我們知道為什么要存在存儲雙關(guān)鍵字的容器
場景一:判斷一堆字符串中,某一個字符串是否出現(xiàn)過
在沒學(xué)set容器之前,我們只能想到把這一堆字符串存到一個字符型數(shù)組里面,從前往后遍歷每一個字符,判斷某一個字符串是否出現(xiàn)過,這個時間復(fù)雜度是O(N)級別的,如果我們學(xué)過set的話,我們就可以把這一堆字符串存到set容器里面,判斷某一字符串是否出現(xiàn)過的時候直接調(diào)用里面的count接口就可以了,時間復(fù)雜度是O(logN)級別的,所以我們用set特解決場景一問題的時候,時間復(fù)雜是更優(yōu)的
場景二:找出一堆字符串中,某一個字符串出現(xiàn)的次數(shù)
如果找的是次數(shù),那么set容器就用不了了,set容器存儲的是單關(guān)鍵字,而且里面是不能有重復(fù)元素的,大家可能想到有multiset,它可以存儲重復(fù)的元素,因此要判斷某一個字符串出現(xiàn)的次數(shù),直接調(diào)用multiset里面的count不就完了嗎?其實還有一個問題,如果這一堆字符串中,所有的字符全都長一樣,比如有10,000個字符串里面的每個字符都是a,當(dāng)我想找“aa”這個字符串出現(xiàn)的次數(shù)的時候,用multiset來解決的話是要遍歷整個紅黑樹一遍的,要全部把它掃描一遍才能統(tǒng)計出a次數(shù),此時它的時間復(fù)雜度是O(N)級別的,那和數(shù)組存儲沒有任何的差別,所以我們想判斷某一個字符串出現(xiàn)的次數(shù)是不能用set容器的
此時存儲雙關(guān)鍵字的map就登場了,它可以做到存儲雙關(guān)鍵字,它把兩個關(guān)鍵詞綁定在一起,存到紅黑樹里面的,比如在這個問題里面,我想統(tǒng)計某一個字符串出現(xiàn)的字?jǐn)?shù),map綁定的兩個關(guān)鍵字可以設(shè)置成,第一個是string第二個是int,它的意思是把字符串和出現(xiàn)的次數(shù)綁定在一起,放進(jìn)紅黑樹里面的一個一個節(jié)點中,也就是說紅黑樹的節(jié)點存的是一個結(jié)構(gòu)體,結(jié)構(gòu)體的第一個關(guān)鍵字是字符串,第二個是字符串出現(xiàn)的次數(shù),此時在查找某一個字符串出現(xiàn)的次數(shù)的時候,直接在這個紅黑中找出對應(yīng)的字符串,拿到它出現(xiàn)的次數(shù)就可以了,至于如何解決這樣的一個問題,我們學(xué)完map的方式之后,在一起編寫代碼
map / multimap?
map 與 multimap 的區(qū)別: map 不能存相同元素, multimap 可以存相同的元素,其余的使??式完全?致。因此,這?只練習(xí)使? map 。?map 與 set 的區(qū)別: set ??存的是?個單獨的關(guān)鍵字,也就是存?個 int 、 char 、?double 或者 string 。? map ??存的是?個 pair<key, value> ,(k-v 模型)不僅有?個關(guān)鍵字,還會有?個與關(guān)鍵字綁定的值,?較?式是按照 key 的值來?較。?也就是中序遍歷的結(jié)果是按照第一個關(guān)鍵字的的大小來做比較的;可以這樣理解:紅?樹???個?個的結(jié)點都是?個結(jié)構(gòu)體,??有兩個元素分別是 key 和?value 。插?、刪除和查找的過程中,?較的是 key 的值。?
- 存 <int, int> ,來統(tǒng)計數(shù)字出現(xiàn)的次數(shù);?
- 存 <string, int> ,來統(tǒng)計字符串出現(xiàn)的次數(shù);?
- 存 <string, string> ,表??個字符串變成另?個字符串;?
- 甚?存 <int, vector<int>> 來表??個數(shù)后?跟了若?個數(shù)......,可以用來存儲樹,就是一個根結(jié)點,后面跟了一堆孩子,int表示根,vector<int>存它的一堆孩子,但用map存儲樹的效率不高,因為查找的時間復(fù)雜是O(logN),后面我們在學(xué)習(xí)哈希表的時候,可以給大家演示一下如何用這個東西存儲樹,因為用哈希表來存儲這樣的形式,查找是很快的
1 創(chuàng)建 map?
#include <iostream>?
#include <vector>?
#include <map>?
using namespace std;?
int main()?
{?map<int, int> mp1;?map<int, string> mp2;?map<string, int> mp3;?map<int, vector<int>> mp4; // 甚?可以掛?個 vectorreturn 0;
}
2 size / empty
- size :求紅?樹的??。時間復(fù)雜度: O(1) 。
- empty :判斷紅?樹是否為空。時間復(fù)雜度: O(1) 。
3 begin / end
- 迭代器,可以使?范圍 for 遍歷整個紅?樹。
- 遍歷是按照中序遍歷的順序,因此是?個有序的序列。
4 insert
- 向紅?樹中插??個元素。這?需要插??個 pair,可以? {} 形式。?如: mp.insert({1,?2}) 。時間復(fù)雜度: O(log N) 。
5 operator []
- 重載 [] ,使得?map 可以像數(shù)組?樣使?。
- 這是 map 最好?的接?,有了這個重載,map 的使?就變得特別輕松,不?寫很多冗余的代碼。
- 它的底層其實就是調(diào)?了 insert 函數(shù),并且會返回 val 的引?。我們?前就先學(xué)會使?即可。
6 erase
- 刪除?個元素。時間復(fù)雜度: O(log N) 。
7 find / count
- find :查找?個元素,返回的是迭代器。時間復(fù)雜度: O(log N) 。
- count :查詢元素出現(xiàn)的次數(shù),?般?來判斷當(dāng)前元素是否在紅?樹中。時間復(fù)雜度:O(log N) 。
8 lower_bound / upper_bound
- lower_bound :?于等于 x 的最?元素,返回的是迭代器。時間復(fù)雜度: O(log N) 。
- upper_bound :?于 x 的最?元素,返回的是迭代器。時間復(fù)雜度: O(log N) 。
代碼:
#include <iostream>
#include <map>
#include <string>
using namespace std;//傳引用使得mp不需要拷貝
void print(map<string, int>& mp)
{//&避免拷貝//雙關(guān)鍵字用auto提取出來的是一個pair類型,所以打印要用first、secondfor (auto& p : mp){cout << p.first << " " << p.second << endl;}
}void test1()
{map<string, int> mp;//插入mp.insert({ "張三", 1 });mp.insert({ "李四", 2 });mp.insert({ "王五", 3 });print(mp); //打印出來的結(jié)果按第一個關(guān)鍵字作比較,后面的關(guān)鍵字只起到綁定作用//李四 2//王五 3//張三 1//operator[] 可以讓 map 像數(shù)組一樣使用int a[2] = { 1,2 };a[1] = 4;cout << a[1] << endl; //4cout << mp["張三"] << endl; //1mp["張三"] = 110;cout << mp["張三"] << endl; //110// 注意事項:operator[] 有可能會向 map 中插入本不想插入的元素if (mp["趙六"] == 4) cout << "yes";else cout << "no" << endl; //no//雖然我們只是想判斷趙六存不存在,但是一旦調(diào)用了[],就把趙六插入進(jìn)來了// [] 里面的內(nèi)容如果不存在 map 中,會先插入,然后再拿值// 插入的時候:第一個關(guān)鍵字就是 [] 里面的內(nèi)容,第二個關(guān)鍵字是一個默認(rèn)值print(mp);//李四 2//王五 3//張三 110//趙六 0//這樣的邏輯去寫就沒有插入張飛,從mp.count("張飛")這句話就斷掉了//后面的語句沒有執(zhí)行了,此時打印張飛是不存在map里的if (mp.count("張飛") && mp["趙六"] == 4) cout << "yes" << endl;else cout << "no" << endl; //noprint(mp);cout << endl;//李四 2//王五 3//張三 110//趙六 0//刪除mp.erase("張三");print(mp);cout << endl;//李四 2//王五 3//趙六 0//auto x = mp.lower_bound("李四");map<string, int>::iterator x = mp.lower_bound("李四");cout << x->first << " " << x->second << endl; //李四x = mp.upper_bound("李四");cout << x->first << " " << x->second << endl; //王五
}// 統(tǒng)計一堆字符串中,每一個字符串出現(xiàn)的次數(shù)
void fun()
{string s;map<string, int> mp; // <字符串,字符串出現(xiàn)的次數(shù)>for (int i = 1; i <= 5; i++){cin >> s;mp[s]++; // 體現(xiàn)了 operator 的強大,s字符串不存在會先插入 }print(mp);//輸入//sdf//aa//dd//aa//dd//輸出//aa 2//dd 2//sdf 1
}int main()
{test1();//fun();return 0;
}