【關聯容器 Associated Containers】

Presentation on theme: "【關聯容器 Associated Containers】"— Presentation transcript:

1 【關聯容器 Associated Containers】
所謂關聯式容器，觀念上類似關聯式資料庫：每個元素都有一 個鍵值（key）和一個實值（value）。當元素被插入到關聯式容器 中時，容器內部結構便依照其鍵值的大小，以某種特定規則將這個 元素放置於特定的位置。關聯式容器沒有所謂的頭尾，所以不會有 push_back()、push_front()、pop_back()、pop_front()的操作。 關聯式容器分為兩大類：map和set以及他們的衍生容器 multimap和multiset。他們的底層採用的是一種比較高效的特殊的 平衡檢索二元樹 - 紅黑樹結構，因為紅黑樹提供了很好的搜索效 率。

2 【常見的關聯容器】 set： set內部元素依其值自動排序，每個元素值只出現一次，不允許重複。
multiset： multiset和set相同，只不過它允許重複元素，也就是說multiset 可包括多個數值相同的元素。 map： map的元素都是“實值/鍵值”所形成的一對對組。每個元素有一個鍵，是排序基準的基礎。每一個鍵只出現一次，不允許重複。map 可被視為關聯式陣列，也就是具有任意索引型別的陣列。 multimap： multimap和map相同，但允許重複元素，也就是說multimap允許多個鍵值相同的元素。multimap常被當作「字典」使用。

3 【map的主要功能】 map的主要功能如下： 自動建立key - value的對應。key 和 value可以是任意你需要的資料型態。
根據key值快速查詢記錄，查詢的複雜度基本是logn，如果有1000個記錄，最多查詢10次， 個記錄，最多查詢20次。 快速插入key - value記錄。 快速刪除記錄。 根據key修改value記錄。 遍歷所有記錄。

4 【 map 定義與宣告】 map是一種關聯式容器，其內部定義了很多基本操作。相關之操作與成員函式定義在標題檔<map>中：
#include <map> map的基本宣告語法：map<key資料型態, value資料型態> map名稱; map宣告方法如下： (1) 宣告一個空的map，key為int，value為string。 map<int, string> m0 ; (2) 宣告一個map，並以另一個map指定初值 map<int, string> m1 ; map<int, string> m2(m1) ;

5 【map的成員函式】 成員函式 功能說明 m.begin() 傳回迭代器的第一個元素。 m.clear() 移除容器中所有資料。
m.count() 傳回某個鍵值的個數，只有0和1兩種狀況。 m.empty() 判斷容器是否為空。 m.end() 指向迭代器中的最後一個資料位址。 m.equal_range() 傳回map中與指定值相等的上下限的兩個迭代器。 m.erase() 刪除map中的資料。 m.find() 搜尋map中的資料。 m.insert() 在map中插入元素。 key_comp() 傳回鍵值的比較結果 lower_bound() 傳回鍵值>=大於某個值元素的迭代器 m.max_size() 傳回容器中最大資料的數量。 m.rbegin() 傳回map的最後一個元素的逆向迭代器。 m.rend() 傳回map的第一個元素的逆向迭代器。 m.size() 傳回map中實際資料的個數。 swap(m1,m2) 將m1和m2的內容互換。 upper_bound() 傳回大於某個值元素的迭代器 value_comp() 傳回一個用於比較元素間的值的函式

6 【 map 說明範例 】 // 05ac_03map.cpp map說明範例 #include <map>
#include <string> #include <iostream> using namespace std; int main() { //1. 宣告及設定初值 map<int, string> m; map<int, string>::iterator iter, beg, end; //2. 添加元素，共有三種方法，以下是常見的兩種方法 //(1)陣列：具有覆蓋功能，相同的key，會取最後一個value //(2)pair：沒有覆蓋功能，無法插入，相同的key，會取第一個value m[0] = "student_one"; m[1] = "student_two"; m[2] = "student_three"; m.insert(pair<int, string>(5, "Fear Kubrick")); m.insert(pair<int, string>(2, "Akemi Homura")); m.insert(pair<int, string>(-1, "Eren Jaeger")); m.insert(pair<int, string>(99, "lin")); cout << m.size() << endl;

7 【 map 說明範例 】 //3. 遍歷：可用陣列走訪，但對於不存在的鍵值，該操作會將此鍵值加入map!
//3. 遍歷：可用陣列走訪，但對於不存在的鍵值，該操作會將此鍵值加入map! for (iter = m.begin(); iter != m.end(); iter++) cout << iter->first << " " << iter->second << endl; //4. 查詢 //可以像3中那樣使用陣列，但如果該key不在map中 //，此操作將會插入一個具有該key的新元素 //用find(key)最好 iter = m.find(1); if (iter != m.end()) cout << iter->second << endl; else cout << -1 << endl; iter = m.find(6);

8 【 map 說明範例 】 //5. 刪除 //單鍵刪除 iter = m.find(1);
  //5. 刪除 //單鍵刪除 iter = m.find(1); if (iter != m.end()) m.erase(iter); cout << m.size() << endl; for (iter = m.begin(); iter != m.end(); iter++) cout << iter->first << " " << iter->second << endl; //範圍刪除 beg = m.find(-1); end = m.find(5); if (beg != m.end() && end != m.end()) m.erase(beg, end);//刪除beg到end之前的元素，不包括end //若想刪除end的鍵值，可以這麼寫：m.erase(beg, ++end); //或者將上面的改為end = m.upper_bound(5); //6. 判空與清空 if (!m.empty()) m.clear(); cin.get(); return 0; }

9 Zerojudge a743 (Uva10420 - List of Conquests)
【map解題範例】 Zerojudge a743 (Uva List of Conquests) 在「唐．喬凡尼」歌劇第一幕中，僕人雷波雷諾(Leporello)拿著一本小冊子告訴唐納．愛爾維拉(Donna Elvira)有關他的主人的風流事蹟： 「這本小冊子記錄著每位與我的主人交往過的女子芳名，你瞧瞧，在義大利有640位，在德國有231位，法國100位，91位在土耳其，在西班牙甚至超過1000位，各國、各年齡層、各社會階層的婦女都有。」 這本冊子上的人名是以時間順序來記錄，每次雷波雷諾要告訴別人他主人的作風時都很麻煩，因為以國別來分類時都必須重新算一遍。你必須寫程式幫助他做計算。 【輸入】：輸入最多2000列，第一列為整數n，表示接下來有n列，每一列最多75個字元，記錄著每一位婦女的國別與姓名，你可以假設第一個字組為國名，之後的字串為婦人的名字。 【輸出】：請在每一列輸出國名及該國婦人的總數，以空白字元隔開，並以國名字母的順序依序輸出。

10 Zerojudge a743 (Uva10420 - List of Conquests)
【map解題範例】 Zerojudge a743 (Uva List of Conquests) // 05ac_05map_ex.cpp Zerojudge a743 List of Conquests #include <iostream> #include <map> #include <sstream> using namespace std; map<string,int> m; map<string,int>::iterator it; int main () { int n; string s,ns; cin >> n; cin.get(); while(n--) getline(cin, s); stringstream ss(s); ss >> ns; if(m.find(ns) == m.end()) m[ns] = 1; else m[ns]++; } for(it=m.begin();it!=m.end();it++) cout << it->first << " " << it->second << endl; return 0;

11 【 map 練習範例】 zerojudge b162 NOIP2007 1.统计数字 zerojudge d244 一堆石頭
zerojudge b198 C. 計票程式 zerojudge d217 (Uva Hangman Judge ) zerojudge d492 (Uva Hardwood Species ) zerojudge a743 (Uva List of Conquests ) Uva Anagrams(II) Uva Uva Stack 'em Up Uva Babelfish Uva Hay Points Uva Virtual Friends

12 To be Continue… 回目錄頁