STL模板中的map的使用與例題 - chengxs－IT工程師數位筆記本

文章出處

最近的計分賽，記得自己的都只是過了兩題。遇到了兩次map，自己在寒假看了一點的map，只知道在字符串匹配的時候可以用的到。但是自己對map的使用還是不夠熟練使用，這回在第一次和第二次的計分賽中都遇到可以用map快速寫出的AC題目。而且代碼精簡。

map是一種二叉樹的數據存儲結構。map內部自建一顆紅黑樹(一種非嚴格意義上的平衡二叉樹)，這顆樹具有對數據自動排序的功能，所以在map內部所有的數據都是有序的。

     map的特點:  1、存儲Key-value對
              2、支持快速查找，查找的復雜度基本是Log(N)
          3、快速插入，快速刪除，快速修改記

一、map的構造函數

map共提供了6個構造函數，這塊涉及到內存分配器這些東西，不太清楚，在下面我們將接觸到一些map的構造方法，這里要說下的就是，我們通常用如下方法構造一個map：

map<string,int>mp;     //這里的mp就是自己取的名字。定義map類型的變量mp

還可以自己定義的map<int.int>mp;

map<string ,int>mapstring; map<int,string >mapint;
map<sring,char>mapstring; map< char ,string>mapchar;
map<char,int>mapchar; map<int ,char>mapint；

二、數據的插入(與插入的循序無關，自動排序)

第一種：用insert函數插入pair數據。

#include <iostream>
#include<string.h>
#include<map>
using namespace std;

int main()
{
    map<int,string>mp;
    mp.insert(pair<int,string>(3,"student_three"));
    mp.insert(pair<int,string>(1,"student_one"));
    mp.insert(pair<int,string>(2,"student_two"));


    map<int,string>::iterator iter;
    for(iter=mp.begin();iter!=mp.end();iter++)
         cout<<iter->first<<"   "<<iter->second<<endl;
    return 0;
}

第二種：用數組方式插入數據，下面舉例說明

#include <map>
#include <string.h>
#include <iostream>
using namespace std;
int main()
{
       map<int, string> mp;
       mp[1]= "student_one";
       mp[2]= "student_two";
       mp[3]= "student_three";
       map<int, string>::iterator  iter;
       for(iter=mapStudent.begin(); iter!= mapStudent.end();iter++)
       {
          cout<<iter->first<<"   "<<iter->second<<endl;
       }
}

三、map的大小

在往map里面插入了數據，我們怎么知道當前已經插入了多少數據呢，可以用size函數，用法如下：

int nSize = mapStudent.size();

四、數據的遍歷

這里也提供多種方法，對map進行遍，目前自己只學會其中一種。

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
       map<int, string> mapStudent;
       mapStudent.insert(pair<int, string>(1, "student_one"));
       mapStudent.insert(pair<int, string>(2, "student_two"));
       mapStudent.insert(pair<int, string>(3, "student_three"));
       map<int, string>::reverse_iterator  iter;
       for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
       {
          cout<<iter->first<<"   "<<iter->second<<endl;
       }
}

五、例題

（1）MD5算法

MD5是一種信息摘要算法，它可以對任意大小的文件產生等長的密鑰，當你在A主機使用MD5得到文件X的密鑰后，在B主機同樣對文件X使用MD5所得到密鑰一定與A主機所得到的密鑰相同。然后請實現MD5算法。
是的，我在開玩笑。
恩，我實現了一個MD6算法，它可以實現類似的功能。

本題包含多組樣例。
輸入第一行為數字N和Q，N為映射的行數，Q為詢問的行數。
映射中每行包含一個字符串A(0<alen<30),和字符串A使用MD6算法對應的數字。
詢問每行包含一個字符串A。

輸出每個詢問行中每個字符串使用MD6算法對應的數字。

5 3
fs3fwe 3
4838fdeewerwer 54
irjfhid 888
847hhhh 1
0000 0
0000
847hhhh
fs3fwe

0
1
3

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

int main()
{
    map<string,int>mp;
    int N,M,i,num;
    string str1,str2;;
    while(scanf("%d%d",&N,&M)!=-1)
    {
        mp.clear();    //一定不要忘記了把map清空
        for(i=0;i<N;i++)
            {
                cin>>str1>>num;
                mp[str1]=num;
            }
            for(i=0;i<M;i++)
            {
                cin>>str2;
                cout<<mp[str2]<<endl;
            }
    }
    return 0;
}

（2）例2

某次張國慶腦袋抽筋時想到了n個自然數，每個數均不超過1500000000（1.5*109）。已知不相同的數不超過10000個，現在需要統計這些自然數各自出現的次數，并按照自然數從小到大的順序輸出統計結果。

    輸入包含n+1行：
    第1行是整數n，表示自然數的個數。
    第2~n+1行每行一個自然數。

輸入
8
2
4
2
4
5
100
2
100

輸出
2 3
4 2
5 1
100 2

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

int main()
{
    map<int,int>mp;
    long long n,num1;
    cin>>n;
    while(n--)
   {
       cin>>num1;
       mp[num1]++;
   }
   map<int,int>::iterator iter;
   for(iter=mp.begin();iter!=mp.end();iter++)
      cout<<iter->first<<" "<<iter->second<<endl;

    return 0;
}

同時題解給出了常規求出

#include <iostream>
#include <algorithm>

using namespace std;

long f[200010];

int main()
{
    long n;
    cin >> n;
    for (long i=0;i<n;++i)
        cin >> f[i];
    f[n] = -1;
    long num = 1;
    sort(f, f + n);
    for (long i=0;i<n;++i)
    {
        if (f[i] == f[i + 1])
            ++num;
        else {
            cout << f[i] << " " << num << endl;
            num = 1;
        }
    }
    return 0;
}

（3）例三

Description

得克薩斯州的一個小鎮Doubleville，被外星人攻擊。他們綁架了當地人并把他們帶到飛船里。經過一番（相當不愉快的）人體實驗，外星人克隆了一些受害者，并釋放了其中的多個副本回Doubleville。所以，現在有可能發生有6個人：原來的人和5個復制品都叫做Hugh F. Bumblebee。現在FBUC美國聯邦調查局命令你負責確定每個人被復制了多少份，為了幫助您完成任務，FBUC收集每個人的DNA樣本。同副本和原來的人具有相同的DNA序列，不同的人有不同的序列（我們知道，城里沒有同卵雙胞胎，這不是問題）

Input

輸入中含有多組數據，每一組以一行n m開始，表示共有n個人1 ≤ n ≤ 20000，其中DNA序列長度為m, 1 ≤ m ≤ 20. 接下來的n行為DNA序列：每行包含m個字符，字符為'A'，'C'，'G'或'T'。輸入以n=m=0 結尾。

Output

每一組數據應輸出n行，每行一個整數。第一行表示有幾個人沒有被復制，第二行表示有幾個人只被復制一次（也就是說有兩個相同的人），第三行表示有幾個是被復制兩次，依次類推，第i行表示其中有i個相同的人的共有幾組。舉例來說，如果有11個樣本，其中之一是John Smith，和所有其余的都是從Joe Foobar復制來的副本，那么你必須打印第一行和第10行輸出1，其余行輸出0。

Sample Input

9 6
AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC
0 0

Sample Output

1
2
0
1
0
0
0
0
0

可以使用常規的結構體

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct dna
{
  char ch[21];      
}
 DNA[21000];
 
int cnt[21000];
 
int cmp(const void *a,const void *b)
{
  struct dna *x = (struct dna *)a;
  struct dna *y = (struct dna *)b;
  return strcmp(x->ch,y->ch);   
}
 
int main()
{
  int num,len,i,t;
     
    while(scanf("%d%d",&num,&len)&& (num + len))
    {
        for(i= 0 ; i < num ; ++i)
        {
              scanf("%s",DNA[i].ch);                             
              cnt[i+1]= 0;
        } 
         
        qsort(DNA,num,sizeof(DNA[0]),cmp);
         
        t = 1;
        for(i= 1 ; i < num ; ++i)
        {
            if(!strcmp(DNA[i].ch,DNA[i-1].ch))     
            ++t;
            else
            {
               cnt[t]++;
               t= 1;     
            } 
        }        
        cnt[t]++;
        for(i= 1 ; i <= num ; ++i)
        printf("%d\n",cnt[i]);
    }
     
    return 0;
}

這個可以想到的是map；STL中提供的map相當不錯。

#include <iostream>
#include<map>
#include<string>
#include <cstdio>
 using namespace std;
  
 map<string,int>m;
 int cnt[21000];
  
 int main()
 {
       string str;
       int i,num,len;
        
       while(scanf("%d%d",&num,&len)&&( num + len ))        
       {
          for(i = 0 ; i < num ; ++i)
          {
                cin>>str;                             
                m[str]++;
                cnt[i+1] = 0;
                str.clear();//一定要清空
          }             
           
          map<string,int>::iterator it; 
           
          for( it = m.begin();it != m.end(); ++it)
           cnt[it->second]++;
          
          for(i= 1 ; i <= num ; ++i)
          printf("%d\n",cnt[i]);
          m.clear();
       }
       return 0;
 }