MAP容器
1）概念：map 是一個容器,它用於儲存數據並且能從一個數據集合中取出數據。它的數據組成包含兩項,一個是它的數據值,一個是用於排序的關鍵字。其中關鍵字是惟一的,它用於將數據自動排序。而每個元素的數據值與關鍵字無關,可以直接改變。
【重點】內部結構采用RB_TREE(紅黑樹)。查找復雜度：O(log2N)
2）使用
需加載的頭文件: #include<map>
using namespace std;
模板原型:
template <
class Key, //關鍵字的數據類型
class Type, //數據值的數據類型
class Traits = less<Key>, //提 供 比 較 兩 個 元 素 的 關 鍵 字 來 決 定 它 們 在 map容器中的相對位置。它是可選的,它的默認值是 less<key>
class Allocator=allocator<pair <const Key, Type> > //代表存儲管理設備。它是可選的,它的默認值為allocator<pair <const Key, Type> >
>
3）map 容器特點:
(1)是一個相關聯的容器,它的大小可以改變,它能根據關鍵字來提高讀取數據能力。
(2)提供一個雙向的定位器來讀寫取數據。
(3)已經根據關鍵字和一個比較函數來排好序。
(4)每一個元素的關鍵字都是惟一的。
(5)是一個模板,它能提供一個一般且獨立的數據類型。
4）有關map最詳細的介紹詳見資源
STL MAP詳細資源下載
5）結合map方法給出了一個綜合測試代碼：
[html]
#include <cstdlib>
#include <map>
#include <iostream>
using namespace std;
map <int,char> ctr;
int print_one_item(map <int,char>::const_iterator cp)//用於打印 map 的一個元素
{
cout<<"("<<cp->first<<" , "<<cp->second<<") ";
return 0;
}
void test_equal_range()//測試equal_range()的功能
{
//pair第一個迭代器返回第一個大於或等於給定的關鍵字的元素
//pair第二個迭代器返回第一個比給定的關鍵字大的元素。
pair <map <int,char>::const_iterator, map <int,char>::const_iterator> p;
p=ctr.equal_range(2);
if(p.first!=ctr.end())
{
cout<<"The first element which key >= 2 is: ";
//cout<<"("<<p.first->first<<" , "<<p.first->second<<") ";
print_one_item(p.first); //調用子程序來打印一項
cout<<endl;
}
if(p.second!=ctr.end())
{
cout<<"The first element which key > 2 is: ";
cout<<"("<<p.second->first<<" , "<<p.second->second<<") ";
cout<<endl;
}
}
void creat_map()
{
ctr.insert(pair <int,char>(1,'a'));
ctr.insert(pair <int,char>(2,'b'));
ctr.insert(pair <int,char>(3,'b'));
ctr.insert(pair <int,char>(4,'c'));
ctr.insert(pair <int,char>(5,'d'));
ctr.insert(pair <int,char>(1,'c'));
}
void erase_map()//刪除某一個元素
{
map <int,char>::iterator cp=ctr.find(2);
ctr.erase(cp);//刪除關鍵值等於 2 的元素
}
void clear_map()
{
ctr.clear();//清空 map 容器（刪除全部元素）
if(ctr.empty())//map 容器為空時
cout<<"The container is empty"<<endl;
else
cout<<"The container is not empty"<<endl;
}
int print()//用於打印一個 map 容器
{
map<int,char>::const_iterator cp;
for(cp=ctr.begin();cp!=ctr.end();cp++)//讓 cp 從 c 的開始到結束打印 cp 對應的值
print_one_item(cp); //調用子程序來打印一個元素
return 0;
}
void print_first_element()
{
map <int,char>::iterator cp;//迭代器
cp=ctr.begin(); //定位到 ctr 的開始位置
cout<<"The first element is:"<<cp->second<<endl;//打印出第一個元素
}
void key_compare_map() //key_comp取得一個比較對象的副本以對 map 容器中的元素進行排序。
{
map <int,int> c;
map <int, int, less<int> >::key_compare kc = c.key_comp() ;
if(kc( 1, 2 ))
cout<<"kc(1,2) is true"<<endl;
else
cout<<"kc(1,2) is false"<<endl;
if(kc( 2, 1 ))
cout<<"kc(2,1) is true"<<endl;
else
cout<<"kc(2,1) is false"<<endl;
}
void lower_bound_map()
{
map <int,char>::iterator cp;
/* 返回一個指向第一個關鍵字的值是大於等於一個給定值的元素的定位器,或者返回指向 map 容
器的結束的定位器
*/
cp=ctr.lower_bound(2);//返回第一個 大於等於2的元素的定位器
if(cp!=ctr.end())
{
cout<<"The first element which key >= 2 is: ";
print_one_item(cp);//調用子程序來打印一項
cout<<endl;
}
}
void compare_map()
{
map <int,char> ctr1,ctr2;
int i;
for(i=0;i<3;i++)
{
ctr1.insert(pair <int,char>(i,'a'+i));
ctr2.insert(pair <int,char>(i,'A'+i));
}
if(ctr1!=ctr2)//當 ctr1 與 ct2 不同時
cout<<"They are not equal"<<endl;
else//當 ctr1 與 ctr2 相同時
cout<<"They are equal"<<endl;
}
void comp_map()//兩個 map 容器的大小比較是基於第一個不相同的元素的大小比較。
{ //兩個 map 容器相等,當且僅當它們的元素個數相等且同一個位置上的值相等
map <int,char> ctr1,ctr2;
int i;
for(i=0;i<3;i++)//下面給 ctr1 和 ctr2 賦值
{
ctr1.insert(pair <int,char>(i,i));
ctr2.insert(pair <int,char>(i,i+1));
}
if(ctr1<ctr2)
cout<<"ctr1<ctr2"<<endl;
else
cout<<"ctr1>=ctr2"<<endl;
}
void reverse_map()//打印 反向 map rbegin() rend()跟 reverse_iterator同時使用
{
map <int,char>::reverse_iterator rcp;
for(rcp=ctr.rbegin();rcp!=ctr.rend();rcp++)
cout<<"("<<rcp->first<<" , "<<rcp->second<<") ";
}
void swap_map()
{
map <int,int> ctr1, ctr2;
map <int,int>::const_iterator cp;
int i;
for(i=0;i<3;i++)//下面先給 ctr1 和 ctr2 賦值
{
ctr1.insert(pair <int,int>(i,i));
ctr2.insert(pair <int,int>(i,i+10));
}
cout<<"Before exchange with ctr2 the ctr1 is:";
for(cp=ctr1.begin();cp!=ctr1.end();cp++)//讓 cp 從 c 的開始到結束打印 cp 對應的值
cout<<"("<<cp->first<<" , "<<cp->second<<") ";
cout<<endl;
cout<<"After exchange with ctr2 the ctr1 is:";
ctr1.swap(ctr2);//讓 ctr1 的內容與 ctr2 交換
for(cp=ctr1.begin();cp!=ctr1.end();cp++)//讓 cp 從 c 的開始到結束打印 cp 對應的值
cout<<"("<<cp->first<<" , "<<cp->second<<") ";
cout<<endl;
}
int main()
{
creat_map();
int i;
cout<<"1，測試begin()"<<endl;
cout<<"2，測試count()求某關鍵字個數"<<endl;
cout<<"3，測試test_equal_range()"<<endl;
cout<<"4，測試erase()"<<endl;
cout<<"5，測試key_compare_map()"<<endl;
cout<<"6，測試lower_bound_map()"<<endl;
cout<<"7，測試map size和 max_size(最大可能長度)"<<endl;
cout<<"8，測試符號 [] 的作用"<<endl;
cout<<"9，測試符號 ！= 的作用"<<endl;
cout<<"10,測試符號 < 的作用"<<endl;
cout<<"11,打印反向map"<<endl;
cout<<"12,交換兩個map 的值"<<endl;
while(1)
{
cin>>i;
switch(i)
{
case 1: print_first_element(); break;
case 2: int j;
j=ctr.count(1);//求出關鍵字為 1 的元素的個數(由於map 容器的關鍵字是惟一的,故它只能取 0 或者 1)
cout<<"The number of key 1 is: "<<j<<endl;break;
case 3: test_equal_range(); break;
case 4: erase_map();break;
case 5: key_compare_map();break;
case 6: lower_bound_map();break;
case 7: cout<<"the size of ctr is:"<<ctr.size()<<endl;
cout<<"the max_size of ctr is:"<<ctr.max_size()<<endl;break;
case 8: cout<<"before change map is:"<<endl;
print();
ctr[1]='W';//將關鍵字為 1的對應值變為 W
ctr[7]; //添加一個關鍵字為7 值為0的項
cout<<"\nafter change map is:"<<endl;
print();break;
case 9:compare_map();break;
case 10:comp_map();break;
case 11:reverse_map();break;
case 12:swap_map(); break;
}
}
map <int,char>::iterator end;//迭代器
end=ctr.end(); //這裡定位到Map 中最後一個元素後面位置，所以什麼都不打印
//end--;//這定位到最後一個元素 d 除去了重復關鍵字 c
cout<<"The last element is:"<<end->second<<endl;
clear_map();
return 0;
}
摘自 小田的專欄
