STL--map - acm1314 @ IT工程師數位筆記本

文章出處

map--概述：

　　映射（Map）和多重映射（Multimap）是基于某一類型Key的鍵集的存在，提供對TYPE類型的數據進行快速和高效的檢索。

l對Map而言，鍵只是指存儲在容器中的某一成員。

lMultimap允許重復鍵值，Map不允許。

lMap和Multimap對象包涵了鍵和各個鍵有關的值，鍵和值的數據類型是不相同的，這與Set不同。

Map內部數據的組織是一顆紅黑樹（一種非嚴格意義上的平衡二叉樹），這顆樹具有對數據自動排序的功能，所以在Map內部所有的數據Key都是有序的。

map c	產生一個空的map/multimap，其中不含任何元素
map c (op)	以op為排序準則，產生一個空的map/multimap
map c1(c2)	產生某個map/multimap的副本，所有元素均被復制
map c (beg, end)	以區間[beg; end]內的元素產生一個map/multimap
map c (beg, end, op)	以op為排序準則，利用[beg; end]內的元素生成一個map/multimap
c.~map()	銷毀所有元素，釋放內存

元素的訪問

1.定義迭代器（iterator）：map<string,float>::iterator pos;

l其中map<string, float>表明這個迭代器的類型，聲明一個迭代器pos，迭代器的角色類似于C/C++中的指針。

2.當迭代器pos指向map容器中某個元素：

l表達式pos－＞first獲得該元素的key；

l表達式pos－＞second獲得該元素的value。

題目：

（會陸續添加）

1.不能再裸啦！再裸就不見一絲啦！

http://acm.hdu.edu.cn/showproblem.php?pid=2192

 1 #include<iostream>
 2 #include<map>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n, ans, a, T;
 8     cin>>T;
 9     while(T--)
10     {
11         ans = 0;
12         scanf("%d", &n);
13         map<int,int> m;
14         for(int i=0; i<n; i++)
15         {
16             scanf("%d",&a);
17             m[a]++;
18             if(m[a]>ans)
19                 ans=m[a];
20         }
21         printf("%d\n", ans);
22         
23     }
24     return 0;
25 }

View Code

3.裸裸裸裸，，，，，，，，，，切著玩吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1800

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;

int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        int i, max =-1, q;
        map<int, int> M;
        for(i=0; i<n; i++)
        {
            scanf("%d", &q);
            M[q]++;
            if(max<M[q])
            max=M[q];
        } 
        printf("%d\n", max);
    }
    return 0;
}

View Code

2.我就是喜歡“裸體”。來一發！

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2104

 1 #include <iostream>
 2 #include <map>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main() 
 7 {
 8     //freopen( "in.txt", "r", stdin );
 9     //freopen( "out.txt", "w", stdout );
10     int n;
11     while (cin>>n && n) 
12     {
13         map <string, int> Balloon;
14         string s;
15         for (int i=0; i<n; i++)  
16         {
17             cin>>s;
18             Balloon[s]++;
19         }
20         int iMax = 0;
21         map <string, int>::iterator point, loc;
22         for (point=Balloon.begin(); point!=Balloon.end(); point++)
23             if (iMax<point->second) 
24             {
25                 iMax = point->second;
26                 loc = point;
27             }
28         cout<<loc->first<<endl;
29     }
30     return 0;
31 }

View Code

3.此題較難一點，草灘小恪讀懂題意都很費勁（英語渣的悲哀！哭，哭，哭，）。

#include<iostream>
#include<map>
#include<set>
using namespace std;

typedef map<int, multiset<int> >line;
map<int, multiset<int> >mx;
map<int, multiset<int> >my;

int bomb(line &x, line &y, int pos)
{
    int ret = x[pos].size();
    multiset<int>::iterator it;
    for(it=x[pos].begin(); it!=x[pos].end(); it++)
    y[*it].erase(pos);
    x[pos].clear();
    return ret;
} 

int main()
{
    int n, m, c, d, tx, ty;
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        if(n==0&&m==0) break;
        mx.clear();
        my.clear();
        for(int i=0; i<n; i++)
        {
            scanf("%d%d", &tx, &ty);
            mx[tx].insert(ty);
            my[ty].insert(tx);
        }
        for(int i=0; i<m; i++)
        {
            scanf("%d%d", &c, &d);
            int ans;
            if(c==0) ans = bomb(mx, my, d);
            else ans = bomb(my, mx, d);
            printf("%d\n", ans);
        }
        printf("\n");
    }
    return 0;
}

View Code

4.這個題不太難，就是需要些巧妙地讀入處理技巧。

http://acm.hdu.edu.cn/showproblem.php?pid=1075

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
using namespace std;

map<string,string>mp;
int main()
{
   // freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);
    mp.clear();
    string str1,str2;
    cin>>str1;
    while(cin>>str1)
    {
        if(str1=="END")break;
        cin>>str2;
        mp[str2]=str1;
    }
    cin>>str1;
    char ch;
    ch=getchar();
    str1="";
    while(1)
    {
        while(1)
        {
            scanf("%c",&ch);
            if(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')))break;
            str1+=ch;
        }
        if(str1=="END")break;
        if(mp.find(str1)==mp.end())cout<<str1;
        else cout<<mp[str1];
        str1="";
        printf("%c",ch);
    }
    return 0;
}