C++ 關聯容器map 類型小結

關聯容器與順序容器

關聯容器通過鍵（key）存儲和讀取元素，而順序容器則通過元素在容器中的位置順序存儲和訪問元素。

關聯容器（Associative containers）支持通過鍵來高效地查找和讀取元素。兩個基本的關聯容器類型是 map 和 set。 其中map 的元素以鍵－值（key-value）對的形式組織：鍵用作元素在 map 中的索引，而值則表示所存儲和讀取的數據。set 僅包含一個鍵，並有效地支持關於某個鍵是否存在的查詢。

關聯容器類型

一般來說，如果希望有效地存儲不同值的集合，那麼使用 set 容器比較合適，而 map 容器則更適用於需要存儲（乃至修改）每個鍵所關聯的值的情況。在做某種文本處理時，可使用 set 保存要忽略的單詞。而字典則是 map 的一種很好的應用：單詞本身是鍵，而它的解釋說明則是值。 set 和 map 類型的對象所包含的元素都具有不同的鍵，不允許為同一個鍵添加第二個元素。如果一個鍵必須對應多個實例，則需使用 multimap 或 multi set，這兩種類型允許多個元素擁有相同的鍵。

C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm

讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm

讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm

讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm

將C語言梳理一下，分布在以下10個章節中：

1. Linux-C成長之路（一）：Linux下C編程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
2. Linux-C成長之路（二）：基本數據類型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
3. Linux-C成長之路（三）：基本IO函數操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
4. Linux-C成長之路（四）：運算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
5. Linux-C成長之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
6. Linux-C成長之路（六）：函數要義 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
7. Linux-C成長之路（七）：數組與指針 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
8. Linux-C成長之路（八）：存儲類，動態內存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
9. Linux-C成長之路（九）：復合數據類型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
10. Linux-C成長之路（十）：其他高級議題

注意：關聯容器根據鍵排列元素！所以，在迭代遍歷訪問容器時，是按照鍵的順序訪問元素，而與元素在容器中的存放位置無關！

基礎pair類型

在utility頭文件定義。

map類型

map類型的定義

map 是鍵－值對的集合。map 類型通常可理解為關聯數組（associative array）：可使用鍵作為下標來獲取一個值，正如內置數組類型一樣。而關聯的本質在於元素的值與某個特定的鍵相關聯，而並非通過元素在數組中的位置來獲取。
map對象的構造函數即定義方法：
在實際應用中，鍵類型必須定義 < 操作符，比如list<> 容器的類型則不能作為鍵。
在使用關聯容器時，它的鍵不但有一個類型，而且還有一個相關的比較函數。 所用的比較函數必須在鍵類型上定義嚴格弱排序（strict weak ordering）。所謂的嚴格弱排序可理解為鍵類型數據上的“小於”關系。當用於一個鍵與自身的比較時，肯定會導致 false 結果。如果它們相互之間都不存在“小於”關系，則容器將之視為相同的鍵。用做 map 對象的鍵時，可使用任意一個鍵值來訪問相應的元素。這與下面的添加元素時行為有一定的對應

map定義的類型

其中：其 value_type 是存儲元素的鍵以及值的 pair 類型，而且鍵為 const。

// count number of times each word occurs in the input
map<string, int> word_count; // empty map from string to int
// get an iterator to an element in word_count
map<string, int>::iterator map_it = word_count.begin(); // *map_it is a reference to a pair<const string, int> objectcout << map_it->first; // prints the key for this element
cout << " " << map_it->second; // prints the value of the element

map_it->first = "new key"; <span ><strong>// error: key is const</strong></span>

++map_it->second; // ok: we can change value through an iterator

對迭代器進行解引用將獲得一個pair對象，其first成員具有const map<K, V>::key_type 類型即存放鍵，而 second成員則為map<K,V>::mapped_type 類型，即存放值。

map元素添加

一、下標添加

當編寫以下代碼時：

map <string, int> word_count; // empty map
// insert default initialzed element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;

將發生：

1.在 word_count 中查找鍵為 Anna 的元素，沒有找到。
2.將一個新的鍵－值對插入到 word_count 中。它的鍵是 const string 類型的對象，保存 Anna。而它的值則采用值初始化，這就意味著在本例中值為 0。
3.將這個新的鍵－值對插入到 word_count 中。
4.讀取新插入的元素，並將它的值賦為 1。
使用下標訪問 map 與使用下標訪問數組或 vector 的行為截然不同：用下標訪問不存在的元素將導致在 map 容器中添加一個新元素，它的鍵即為該下標值。
PS：下標操作符返回值的使用
通常來說，下標操作符返回左值。它返回的左值是特定鍵所關聯的值。可如下讀或寫元素：

// count number of times each word occurs in the input
map<string, int> word_count; // empty map from string to int
string word;
while (cin >> word)
++word_count[word];

二、insert添加

map上的insert操作
1.添加元素

// if Anna not already in word_count,inserts new element with value 1
word_count.insert(map<string, int>::value_type("Anna", 1));

上面語句的實參可以簡化如下兩種方法：

（1） word_count.insert(make_pair("Anna", 1)); （2）使用 typedef

typedef map<string,int>::value_type valType;
word_count.insert(valType("Anna", 1));

2、insert的返回值

There can be only one element with a given key in a map. If we attempt to insert an element with a key that is already in the map, then insert does nothing. The versions of insert that take an iterator or iterator pair do not indicate whether or how many elements were inserted.
但是，帶有一個鍵－值 pair 形參的 insert 版本將返回一個值：包含一個迭代器和一個 bool 值的 pair 對象，其中迭代器指向 map 中具有相應鍵的元素，而 bool 值則表示是否插入了該元素。如果該鍵已在容器中，則其關聯的值保持不變，返回的 bool 值為 false。在這兩種情況下，迭代器都將指向具有給定鍵的元素。

查找以及讀取map中的元素

一、下標讀取

map<string,int> word_count;
int occurs = word_count["foobar"];

但是：使用下標存在一個很危險的副作用：如果該鍵不在 map 容器中，那麼下標操作會插入一個具有該鍵的新元素。

更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-07/104619p2.htm