【知識點】
1、Set是一種關聯容器，它用于存儲資料，并且能從一個資料集合中取出資料。它的每個元素的值必須唯一，而且系統會根據該值來自動将資料排序。每個元素的值不能直接被改變。【重點】内部結構采用紅黑樹的平衡二叉樹。multiset 跟set 類似，唯一的差別是允許鍵值重複！！！
Map是c++的一個标準容器，她提供了很好一對一的關系，在一些程式中建立一個map可以起到事半功倍的效果，總結了一些map基本簡單實用的操作！
2、map的功能
自動建立Key － value的對應。key 和 value可以是任意你需要的類型。
根據key值快速查找記錄，查找的複雜度基本是Log(N)，如果有1000個記錄，最多查找10次，1,000,000個記錄，最多查找20次。
快速插入Key -Value 記錄。
快速删除記錄
根據Key 修改value記錄。
周遊所有記錄。
3、使用map
使用map得包含map類所在的頭檔案
#include <map> //注意，STL頭檔案沒有擴充名.h
map對象是模闆類，需要關鍵字和存儲對象兩個模闆參數：
std:map<int,string> personnel;
這樣就定義了一個用int作為索引,并擁有相關聯的指向string的指針.
為了使用友善，可以對模闆類進行一下類型定義，
typedef map<int,CString> UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumMap;
4、在map中插入元素
改變map中的條目非常簡單，因為map類已經對[]操作符進行了重載
enumMap[1] ="One";
enumMap[2] ="Two";
.....
這樣非常直覺，但存在一個性能的問題。插入2時,先在enumMap中查找主鍵為2的項，沒發現，然後将一個新的對象插入enumMap，鍵是2，
值是一個空字元串，插入完成後，将字元串賦為"Two";該方法會将每個值都賦為預設值，然後再賦為顯示的值，如果元素是類對象，則開銷比較大。
我們可以用以下方法來避免開銷：
enumMap.insert(map<int,CString> :: value_type(2,"Two"))
enumMap.insert(pair<int,string>(102,"aclive"));
5、查找并擷取map中的元素
下标操作符給出了獲得一個值的最簡單方法：
CString tmp =enumMap[2];
但是,隻有當map中有這個鍵的執行個體時才對，否則會自動插入一個執行個體，值為初始化值。
我們可以使用Find()和Count()方法來發現一個鍵是否存在。
查找map中是否包含某個關鍵字條目用find()方法，傳入的參數是要查找的key，在這裡需要提到的是begin()和end()兩個成員，
分别代表map對象中第一個條目和最後一個條目，這兩個資料的類型是iterator.
int nFindKey= 2;//要查找的Key
//定義一個條目變量(實際是指針)
UDT_MAP_INT_CSTRING::iterator it=enumMap.find(nFindKey);
if(it== enumMap.end()) {
//沒找到
}
else {
//找到
}
通過map對象的方法擷取的iterator資料類型是一個std::pair對象，包括兩個資料 iterator->first和 iterator->second分别代表關鍵字和存儲的資料
6.從map中删除元素
移除某個map中某個條目用erase（）
該成員方法的定義如下：
iterator erase（iterator it);//通過一個條目對象删除
iterator erase（iterator first，iterator last）//删除一個範圍
size_type erase(const Key&key);//通過關鍵字删除
clear()就相當于enumMap.erase(enumMap.begin(),enumMap.end());
7.map中的swap用法
Map中德swap不是一個容器中的元素交換，而是兩個容器的交換；
8.map中的sort問題
Map中的元素是自動按Key升序排序，是以不能對map用sort函數；
9. map的基本操作函數：
C++ Maps是一種關聯式容器，包含“關鍵字/值”對
begin() 傳回指向map頭部的疊代器
clear(） 删除所有元素
count() 傳回指定元素出現的次數
empty() 如果map為空則傳回true
end() 傳回指向map末尾的疊代器
equal_range() 傳回特殊條目的疊代器對
erase() 删除一個元素
find() 查找一個元素
get_allocator() 傳回map的配置器
insert() 插入元素
key_comp() 傳回比較元素key的函數
lower_bound() 傳回鍵值>=給定元素的第一個位置
max_size() 傳回可以容納的最大元素個數
rbegin() 傳回一個指向map尾部的逆向疊代器
rend() 傳回一個指向map頭部的逆向疊代器
size() 傳回map中元素的個數
swap() 交換兩個map
upper_bound() 傳回鍵值>給定元素的第一個位置
value_comp() 傳回比較元素value的函數
今天看到map的時候想到了二維圖，然後一時忘了怎麼創。。。哎，居然寫成了map<map<string,string>,int>;怎麼說呢，這個其實并不是二位圖，還是等于map<struct T,int>，so...真正的二維圖：map<string,map<string,int> >;
要練手的可以做下經典題：
連結： http://acm.hdu.edu.cn/showproblem.php?pid=1263
水果
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7191 Accepted Submission(s): 2817
Problem Description 夏天來了~~好開心啊,呵呵,好多好多水果~~
Joe經營着一個不大的水果店.他認為生存之道就是經營最受顧客歡迎的水果.現在他想要一份水果銷售情況的明細表,這樣Joe就可以很容易掌握所有水果的銷售情況了.
Input 第一行正整數N(0<N<=10)表示有N組測試資料.
每組測試資料的第一行是一個整數M(0<M<=100),表示工有M次成功的交易.其後有M行資料,每行表示一次交易,由水果名稱(小寫字母組成,長度不超過80),水果産地(小寫字母組成,長度不超過80)和交易的水果數目(正整數,不超過100)組成.
Output 對于每一組測試資料,請你輸出一份排版格式正确(請分析樣本輸出)的水果銷售情況明細表.這份明細表包括所有水果的産地,名稱和銷售數目的資訊.水果先按産地分類,産地按字母順序排列;同一産地的水果按照名稱排序,名稱按字母順序排序.
兩組測試資料之間有一個空行.最後一組測試資料之後沒有空行.
Sample Input
1
5
apple shandong 3
pineapple guangdong 1
sugarcane guangdong 1
pineapple guangdong 3
pineapple guangdong 1
Sample Output
guangdong
|----pineapple(5)
|----sugarcane(1)
shandong
|----apple(3)
Source 浙江工業大學第四屆大學生程式設計競賽
寫了兩個，真假二維圖了，/汗
//注意：兩組測試資料之間有一個空行.最後一組測試資料之後沒有空行.
#include<cstring>
#include<string>
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
int main()
{
int N,M;
scanf("%d",&N);
while(N--)
{
scanf("%d",&M);
string addr,future;
int num=0;
map<map<string,string>,int> salesInfo;
for(int i=0;i<M;i++)
{
cin>>future>>addr>>num;
map<string,string> info;
info[addr] = future;
salesInfo[info] += num;
}
map<map<string,string>,int>::iterator iter;
addr = "";
for(iter = salesInfo.begin();iter!=salesInfo.end();iter++)
{
//cout<<"("<<iter->second<<")"<<endl;
map<string,string> info(iter->first);
map<string,string>::iterator itm;
itm = info.begin();
if(addr != (*itm).first)
{
addr = (*itm).first;
cout<<addr<<endl;
}
cout<<" |----"<<(*itm).second<<"("<<iter->second<<")"<<endl;
}
if(N) cout<<endl;
}
return 0;
}
二維map的應用
//真正二維map...
#include<cstring>
#include<string>
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
int main()
{
int N,M;
scanf("%d",&N);
while(N--)
{
scanf("%d",&M);
string addr,future;
int num=0;
map<string,map<string,int> > salesInfo;//這才是真的二維map
for(int i=0;i<M;i++)
{
cin>>future>>addr>>num;
salesInfo[addr][future] += num;
}
map<string,map<string,int> >::iterator iter;
for(iter = salesInfo.begin();iter!=salesInfo.end();iter++)
{
cout<<iter->first<<endl;
map<string,int>::iterator itm;
for(itm = (iter->second).begin();itm != (iter->second).end();itm++)
{
cout<<" |----"<<(*itm).first<<"("<<(*itm).second<<")"<<endl;
}
}
if(N) cout<<endl;
}
return 0;
}
練的不過瘾，可以溫習下下面兩題
Let the Balloon Rise
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 122783 Accepted Submission(s): 48360
Problem Description Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.
This year, they decide to leave this lovely job to you.
Input Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.
A test case with N = 0 terminates the input and this test case is not to be processed.
Output For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.
Sample Input
5
green
red
blue
red
red
3
pink
orange
pink
0
Sample Output
red
pink
/題意：給N個氣球，求出現最多次數的顔色，保證答案唯一，N=0 break;
//解：map<string,int> 即可
#include<map>
#include<cstring>
#include<string>
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
if(N==0) break;
map<string,int> color;
string str,MoreColor;
int mmax = -1;
for(int i=0;i<N;i++)
{
cin>>str;
color[str]++;
if(color[str] > mmax)
{
mmax = color[str];
MoreColor = str;
}
}
cout<<MoreColor<<endl;
}
return 0;
}
What Are You Talking About
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/204800 K (Java/Others)
Total Submission(s): 23494 Accepted Submission(s): 7875
Problem Description Ignatius is so lucky that he met a Martian yesterday. But he didn't know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?
Input The problem has only one test case, the test case consists of two parts, the dictionary part and the book part. The dictionary part starts with a single line contains a string "START", this string should be ignored, then some lines follow, each line contains two strings, the first one is a word in English, the second one is the corresponding word in Martian's language. A line with a single string "END" indicates the end of the directory part, and this string should be ignored. The book part starts with a single line contains a string "START", this string should be ignored, then an article written in Martian's language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation, if you can't find the word in the dictionary you do not have to translate it, and just copy the old word to your translation. Space(' '), tab('\t'), enter('\n') and all the punctuation should not be translated. A line with a single string "END" indicates the end of the book part, and that's also the end of the input. All the words are in the lowercase, and each word will contain at most 10 characters, and each line will contain at most 3000 characters.
Output In this problem, you have to output the translation of the history book.
Sample Input
START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END
Sample Output
hello, i'm from mars.
i like earth!
Hint
Huge input, scanf is recommended.
題意：是翻譯。START--END 中間是字典翻譯和需要翻譯的原文； 翻譯成英文，字典裡沒有的原樣輸出
//用map<string,string>做一個轉換表
這裡要注意是：整個book行數比較多之前我是開string[10005]數組的，結果一直RE後來我一句句輸出，不存才過，之後我又存了個vector<string> 也過得了，看需求吧~
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<string>
using namespace std;
int main()
{
string sta;
cin>>sta;
if(sta.compare("START") == 0)
{
map<string,string> dictionary;//火星文字典...
string eng,marks;
while(cin>>eng)
{
if(eng.compare("END") == 0) break;
cin>>marks;
dictionary[marks] = eng;
}
string str, essay;// 這裡essay不好定長度,之前定[1005]開小了，//ACCESS_VIOLATION
char ch[15];
gets(ch);//吸收回車
int cnt = 0;
while(getline (cin, str, '\n'))
{
//cout<<"essay["<<cnt<<"] = "<<str<<endl;
if(str.compare("END") == 0) break;
if(str.compare("START") == 0) continue;
int len = str.size();
//str[len] = '\n';
str.append("\n");
//cout<<"len = "<<len<<endl;
string tmp("");
for(int i=0;i<=len;i++)
{
if(!(str[i] >= 'a' && str[i] <= 'z' || str[i] == '\''))//标點 空格 換行 标簽 (隻有小寫字母)
{
//cout<<"tmp = "<<tmp<<" ["<<str[i]<<"]"<<endl;
if(tmp!="" && dictionary[tmp] != "") tmp = dictionary[tmp];
essay += tmp + str[i];
tmp.clear();
}
else
tmp += str[i];
}
cout<<essay;
essay.clear();
//cout<<"essay["<<cnt<<"] = "<<essay[cnt]<<endl;
cnt++;
}
//for(int i=0;i<cnt;i++)
//{
// cout<<essay[i]<<endl;
//}
}
return 0;
}
解法二：
#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
int main()
{
string sta;
cin>>sta;
if(sta.compare("START") == 0)
{
map<string,string> dictionary;//火星文字典...
string eng,marks;
while(cin>>eng)
{
if(eng.compare("END") == 0) break;
cin>>marks;
dictionary[marks] = eng;
}
string str, essay;// 這裡essay不好定長度,之前定[1005]開小了，//ACCESS_VIOLATION
vector<string> book;//統一輸出
char ch[15];
gets(ch);//吸收回車
int cnt = 0;
while(getline (cin, str, '\n'))
{
//cout<<"essay["<<cnt<<"] = "<<str<<endl;
if(str.compare("END") == 0) break;
if(str.compare("START") == 0) continue;
int len = str.size();
//str[len] = '\n';
str.append("\n");
//cout<<"len = "<<len<<endl;
string tmp("");
for(int i=0;i<=len;i++)
{
if(!(str[i] >= 'a' && str[i] <= 'z' || str[i] == '\''))//标點 空格 換行 标簽 (隻有小寫字母)
{
//cout<<"tmp = "<<tmp<<" ["<<str[i]<<"]"<<endl;
if(tmp!="" && dictionary[tmp] != "") tmp = dictionary[tmp];
essay += tmp + str[i];
tmp.clear();
}
else
tmp += str[i];
}
//cout<<essay;
book.push_back(essay);
essay.clear();
//cout<<"essay["<<cnt<<"] = "<<essay[cnt]<<endl;
cnt++;
}
for(vector<string>::iterator iter = book.begin();iter != book.end();iter++)
{
cout<<*iter;
}
}
return 0;
}
另外還有更快的解法。字典樹
也附一份代碼
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node
{
struct node *child[26];
char *str;
};
struct node *root = new struct node;
void Init()
{
for(int i =0;i <26; i++)
root->child[i] = 0;
}
void Insert(char *c1,char *c2)
{
int len = strlen(c2);
struct node *cur;
cur = root;
for(int i =0;i <len;i ++){
if(cur ->child[c2[i] - 'a'] != 0){
cur = cur ->child[c2[i] - 'a'];
}
else{
struct node *newnode = new struct node;
cur ->child[c2[i] - 'a'] = newnode;
for(int j =0; j <26; j++){
newnode ->child[j] = 0;
}
newnode ->str = NULL; //相當重要啊!!!!!
cur = newnode;
}
}
cur->str = (char *)malloc(15 * sizeof(char));
strcpy(cur->str, c1);
}
void Print(char *c2)
{
int len = strlen(c2);
struct node *cur;
cur = root;
if(!len) return ;
for(int i =0;i <len; i++){
if(c2[i] < 'a' || c2[i] > 'z' || cur ->child[c2[i] - 'a'] == 0){
printf("%s",c2);
return ;
}
else{
cur = cur ->child[c2[i] - 'a'];
}
}
if(cur ->str != NULL)
printf("%s",cur ->str);
else
printf("%s",c2);
}
int main()
{
char s[15],temp[3005],c1[15],c2[15];
Init();
scanf("%s", temp);
while(scanf("%s", c1) && strcmp(c1, "END")!=0){
scanf("%s", c2);
Insert( c1, c2);
}
scanf("%s", temp);
getchar();
while(gets(temp) && strcmp(temp,"END")!=0)
{
int len = strlen(temp);
int start = -1, end = 0;
int num = 0;
for(int i =0; i<len; i++){
if(temp[i] >= 'a' && temp[i] <= 'z'){
if(start == -1){
start = i;
}
s[num++] = temp[i];
}
else{
if(start > -1){
start = -1;
s[num] = '\0';
num = 0;
Print(s);
}
printf("%c", temp[i]);
}
}
if(start > -1)
{
s[num] = '\0';
Print(s);
if(temp[len - 1] < 'a' || temp[len - 1] > 'z')
printf("%c", temp[len - 1]);
}
printf("\n");
}
return 0;
}
![STL 六大元件概要[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)