STL模闆中的map的使用與例題

最近的計分賽，記得自己的都隻是過了兩題。遇到了兩次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

#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行每行一個自然數。

輸入

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

TCCCCC

0 0

Sample Output

可以使用正常的結構體

#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;
 }

文中有錯誤的地方希望指出，共同進步

STL模闆中的map的使用與例題

繼續閱讀

POJ_1985_Cow Marathon(樹的直徑)

CF1394C 計算幾何

leetcode_17.Letter Combinations of a Phone Number

HDU 1286 找新朋友（歐拉函數模闆）

hdu 1286 找新朋友（歐拉函數）

哈理工oj Touring （最短路 dij算法鄰接表 + 隊列）

HDU 1286 找新朋友(歐拉函數)找新朋友

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

CF-346 D. Robot Control(反向建圖spfa)

ACMer成長之路

pat（B）1009. 說反話（逆疊代器）

關于多項式的一點研究及其在ACM競賽中的應用關于多項式的一點研究及其在ACM競賽中的應用

codeforces 838D D. Airplane Arrangements 構造法推公式

HDU Reorder the Books

POJ 1284 Primitive Roots (歐拉函數&原根定理)

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004