Map容器,顧名思義,地圖,是用來進行索引的一個容器。
在定義Map容器之前,c++首先定義了一個pair類型,這個類型有兩個參數pair<T1,T2>。
pair類型的對象通過點号(.)通路其成員(都是公有成員)first與second。
pair類型可以通過make_pair()函數來進行初始化。
下面定義map類型的對象
map<string ,int> objmap;//這個語句定義了一個空的map對象,其中string類型的為索引,int類型的為其值。
對于自定義類型作為鍵類型,特别要注意的是自定義類型必須定義<這個操作符。并且必須是嚴格弱排序。也即兩個鍵比較時,不能出現互相小于的情況。
在map類型下面定義了三個類型。
map<K,V>::key_type //在map容器中,作為索引的鍵的類型
map<K,V>::mapped //在map容器中,鍵所關聯的值的類型
map<K,V>::value_type //他是個pair類型
我們需要注意的是map的疊代器類型解引用将産生一個pair類型的對象
如
map<K,V>::iterator map_it = mapobj.begin();
map_it->second;//這個便是通路pair類型的第二個值
給map中添加元素,有兩種方法。
第一:
用下标通路元素時,如果map中已經存在了這個索引,則不做任何操作,但是如果索引中沒有這個下标時,會将這個下标添加到索引中,并且将索引的值預設進行初始化。
1 mapobj["gaoteng"];
假如map中沒有"gaoteng"這個索引的話,會将"gaoteng"加入到map中,同時将“gaoteng”所訓示的值初始化。
需要強調的是:下标操作傳回的是map<K,V>::mapped_type,而疊代器傳回的是pair對象,這個特性與順序容器不同。
第二:
用map對象的成員insert()函數來插入。
用這個函數特别要注意的是他的傳回值類型。
在形參中是pair類型的insert版本,将傳回一個值,這個值是pair對象,他包含一個指向插入元素的疊代器和一個bool類型的表示是否插入的變量。
如:
pari<map<K,V>::iterator,bool> ret = mapobj.insert(make_pair(k,v));
最後提供兩個檢查map元素的方法:
m.count(k) //統計m中k出現的次數
m.find(k)//傳回指向k索引的疊代器,如果沒找到,傳回超出末端的疊代器
從map中删除對象
與順序容器不同的是,erase()成員函數傳回void,而順序容器則傳回一個指向被删除元素的後一個疊代器。
與順序容器一樣,也可以通過 m.begin()與m.end()擷取疊代器然後進行周遊,隻不過周遊方式是按索引的升序排列的。
map映照容器的元素資料是一個鍵值和一個映照資料組成的,鍵值與映照資料之間具有一一映照的關系。
map映照容器的資料結構是采用紅黑樹來實作的,插入鍵值的元素不允許重複,比較函數隻對元素的鍵值進行比較,元素的各項資料可通過鍵值檢索出來。
使用map容器需要頭檔案包含語句“#include<map>”, map檔案也包含了對multimap多重映照容器的定義。
1、map建立、元素插入和周遊通路
建立map對象,鍵值與映照資料的類型由自己定義。在沒有指定比較函數時,元素的插入位置是按鍵值由小到大插入到黑白樹中去的,下面這個程式詳細說明了如何操作map容器。
1
#include <map>
2
#include < string>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
int main()
11
{
12
//定義map對象,目前沒有任何元素
13
map<string,float> m ;
14
15
//插入元素,按鍵值的由小到大放入黑白樹中
16
m["Jack"] = 98.5 ;
17
m["Bomi"] = 96.0 ;
18
m["Kate"] = 97.5 ;
19
20
//先前周遊元素
21
map<string,float> :: iterator it ;
22
for(it = m.begin() ; it != m.end() ; it ++)
23
{
24
cout << (*it).first << " : " << (*it).second << endl ;
25
}
26
27
return 0 ;
28
}
29
運作結果:
Bomi :96
Jack :98.5
Kate :97.5
程式編譯試,會産生代号為“warning C4786” 的警告, “4786” 是标記符超長警告的代号。可以在程式的頭檔案包含代碼的前面使用"#pragma waring(disable:4786)" 宏語句,強制編譯器忽略該警告。4786号警告對程式的正确性和運作并無影響。
2、删除元素
map映照容器的 erase() 删除元素函數,可以删除某個疊代器位置上的元素、等于某個鍵值的元素、一個疊代器區間上的所有元素,當然,也可使用clear()方法清空map映照容器。
下面這個程式示範了删除map容器中鍵值為28的元素:
1
#include <map>
2
#include < string>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
int main()
11
{
12
//定義map對象,目前沒有任何元素
13
map<int, char> m ;
14
//插入元素,按鍵值的由小到大放入黑白樹中
15
m[25] = 'm' ;
16
m[28] = 'k' ;
17
m[10] = 'x' ;
18
m[30] = 'a' ;
19
//删除鍵值為28的元素
20
m.erase(28) ;
21
//向前周遊元素
22
map<int, char> :: iterator it ;
23
for(it = m.begin() ; it != m.end() ; it ++)
24
{
25
//輸出鍵值與映照資料
26
cout << (*it).first << " : " << (*it).second << endl ;
27
}
28
return 0 ;
29
}
30
運作結果:
10 : x
25 : m
30 : a
3、元素反向周遊
可以用反向疊代器reverse_iterator反向周遊map映照容器中的資料,它需要rbegin()方法和rend()方法指出反向周遊的起始位置和終止位置。
1
#include <map>
2
#include < string>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
int main()
11
{
12
//定義map對象,目前沒有任何元素
13
map<int, char> m ;
14
//插入元素,按鍵值的由小到大放入黑白樹中
15
m[25] = 'm' ;
16
m[28] = 'k' ;
17
m[10] = 'x' ;
18
m[30] = 'a' ;
19
//反向周遊元素
20
map<int, char> :: reverse_iterator rit ;
21
for( rit = m.rbegin() ; rit != m.rend() ; rit ++)
22
{
23
//輸入鍵值與映照資料
24
cout << (*rit).first << " : " << (*rit).second << endl ;
25
}
26
return 0 ;
27
}
28
運作結果:
30 : a
28 : k
25 : m
10 : x
4、元素的搜尋
使用find()方法來搜尋某個鍵值,如果搜尋到了,則傳回該鍵值所在的疊代器位置,否則,傳回end()疊代器位置。由于map采用黑白樹資料結構來實作,是以搜尋速度是極快的。
下面這個程式搜尋鍵值為28的元素:
1
#include <map>
2
#include < string>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
int main()
11
{
12
//定義map對象,目前沒有任何元素
13
map<int, char> m ;
14
//插入元素,按鍵值的由小到大放入黑白樹中
15
m[25] = 'm' ;
16
m[28] = 'k' ;
17
m[10] = 'x' ;
18
m[30] = 'a' ;
19
map<int, char> :: iterator it ;
20
it = m.find(28) ;
21
if(it != m.end()) //搜尋到該鍵值
22
cout << (*it).first << " : " << ( *it ).second << endl ;
23
else
24
cout << "not found it" << endl ;
25
return 0 ;
26
}
27
5、自定義比較函數
将元素插入到map中去的時候,map會根據設定的比較函數将該元素放到該放的節點上去。在定義map的時候,如果沒有指定比較函數,那麼采用預設的比較函數,即按鍵值由小到大的順序插入元素。在很多情況下,需要自己編寫比較函數。
編寫方法有兩種。
(1)如果元素不是結構體,那麼,可以編寫比較函數。下面這個程式編寫的比較規則是要求按鍵值由大到小的順序将元素插入到map中
1
#include <map>
2
#include < string>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
// 自定義比較函數 myComp
11
struct myComp
12
{
13
bool operator() (const int &a, const int &b)
14
{
15
if(a != b) return a > b ;
16
else return a > b ;
17
}
18
} ;
19
20
int main()
21
{
22
//定義map對象,目前沒有任何元素
23
map<int, char> m ;
24
//插入元素,按鍵值的由小到大放入黑白樹中
25
m[25] = 'm' ;
26
m[28] = 'k' ;
27
m[10] = 'x' ;
28
m[30] = 'a' ;
29
//使用前向疊代器中序周遊map
30
map<int, char,myComp> :: iterator it ;
31
for(it = m.begin() ; it != m.end() ; it ++)
32
cout << (*it).first << " : " << (*it).second << endl ;
33
return 0 ;
34
}
35
運作結果:
30 :a
28 :k
25 :m
10 :x
(2)如果元素是結構體,那麼,可以直接把比較函數寫在結構體内。下面的程式詳細說明了如何操作:
1
#include <map>
2
#include < string>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
struct Info
11
{
12
string name ;
13
float score ;
14
//重載 “<”操作符,自定義排列規則
15
bool operator < (const Info &a) const
16
{
17
//按score由大到小排列。如果要由小到大排列,使用“>”号即可
18
return a.score < score ;
19
}
20
} ;
21
22
int main()
23
{
24
//定義map對象,目前沒有任何元素
25
map<Info, int> m ;
26
//定義Info結構體變量
27
Info info ;
28
//插入元素,按鍵值的由小到大放入黑白樹中
29
info.name = "Jack" ;
30
info.score = 60 ;
31
m[info] = 25 ;
32
info.name = "Bomi" ;
33
info.score = 80 ;
34
m[info] = 10 ;
35
info.name = "Peti" ;
36
info.score = 66.5 ;
37
m[info] = 30 ;
38
//使用前向疊代器中序周遊map
39
map<Info,int> :: iterator it ;
40
for(it = m.begin() ; it != m.end() ; it ++)
41
{
42
cout << (*it).second << " : " ;
43
cout << ((*it).first).name << " : " << ((*it).first).score << endl ;
44
}
45
return 0 ;
46
}
47
運作結果:
10 :Bomi 80
30 :Peti 66.5
25 :Jack 60
6、用map實作數字分離
對數字的各位進行分離,采用取餘等數學方法是很耗時的。而把數字當成字元串,使用map的映照功能,很友善地實作了數字分離。下面這個程式将一個字元串中的字元當成數字,并将各位的數值相加,最後輸出各位的和。
1
#include < string>
2
#include <map>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
int main()
11
{
12
//定義map對象,目前沒有任何元素
13
map<char, int> m ;
14
15
//指派:字元映射數字
16
m['0'] = 0 ;
17
m['1'] = 1 ;
18
m['2'] = 2 ;
19
m['3'] = 3 ;
20
m['4'] = 4 ;
21
m['5'] = 5 ;
22
m['6'] = 6 ;
23
m['7'] = 7 ;
24
m['8'] = 8 ;
25
m['9'] = 9 ;
26
32
string sa, sb ;
33
sa = "6234" ;
34
int i ;
35
int sum = 0 ;
36
for ( i = 0 ; i < sa.length() ; i++ )
37
sum += m[sa[i]] ;
38
cout << "sum = " << sum << endl ;
39
return 0 ;
40
}
41
7、數字映照字元的map寫法
在很多情況下,需要實作将數字映射為相應的字元,看看下面的程式:
1
#include < string>
2
#include <map>
3
#include <iostream>
4
5
using std :: cout ;
6
using std :: endl ;
7
using std :: string ;
8
using std :: map ;
9
10
int main()
11
{
12
//定義map對象,目前沒有任何元素
13
map<int, char> m ;
14
15
//指派:字元映射數字
16
m[0] = '0' ;
17
m[1] = '1' ;
18
m[2] = '2' ;
19
m[3] = '3' ;
20
m[4] = '4' ;
21
m[5] = '5' ;
22
m[6] = '6' ;
23
m[7] = '7' ;
24
m[8] = '8' ;
25
m[9] = '9' ;
26
32
int n = 7 ;
33
string s = "The number is " ;
34
cout << s + m[n] << endl ;
35
return 0 ;
36
}
37
運作結果:
The number is 7