11、C++ Primer 4th 筆記，關聯容器(1)

1、關聯容器和順序容器的本質差别在于：關聯容器通過鍵（key）存儲和讀取元素，而順序容器則通過元素在容器中的位置順序存儲和通路元素。

2、map 的元素以鍵－值（key-value）對的形式組織：鍵用作元素在 map 中的索引，而值則表示所存儲和讀取的資料。

3、關聯容器類型

map

關聯數組：元素通過鍵來存儲和讀取

set

大小可變的集合，支援通過鍵實作的快速讀取

multimap

支援同一個鍵多次出現的 map 類型

multiset

支援同一個鍵多次出現的 set 類型

4、pair類型

pairs 類型提供的操作

pair<T1, T2> p1;

建立一個空的 pair 對象，它的兩個元素分别是 T1 和 T2類型，采用值初始化

pair<T1, T2> p1(v1, v2);

建立一個 pair 對象，它的兩個元素分别是 T1 和T2 ，其中 first 成員初始化為 v1，而 second 成員初始化為 v2

make_pair(v1, v2)

以v1和v2值建立一個新pair對象，其元素類型分别是v1和v2的類型

p1 < p2

兩個 pair 對象之間的小于運算，其定義遵循字典次序：如果 p1.first < p2.first 或者!(p2.first < p1.first) && p1.second < p2.second，則傳回 true

p1 == p2

如果兩個 pair 對象的 first 和 second 成員依次相等，則這兩個對象相等。該運算使用其元素的 == 操作符

p.first

傳回 p 中名為 first 的（公有）資料成員

p.second

傳回 p 的名為 second 的（公有）資料成員

5、map構造函數

map<k, v> m;

建立一個名為 m 的空 map 對象，其鍵和值的類型分别為 k 和 v

map<k, v> m(m2);

建立 m2 的副本 m，m 與 m2 必須有相同的鍵類型和值類型

map<k, v> m(b,e);

建立 map 類型的對象 m，存儲疊代器 b 和 e 标記的範圍内所有元素的副本。元素的類型必須能轉換為 pair<const k, v>

6、所有比較函數必須在鍵類型上定義嚴格弱排序，即鍵類型必須定義 < 操作符。

7、map定義的類型

map<K, V>::key_type

在 map 容器中，用做索引的鍵的類型

map<K, V>::mapped_type

在 map 容器中，鍵所關聯的值的類型

map<K, V>::value_type

一個pair類型，它的 first 元素具有 const map<K, V>::key_type類型，而 second 元素則為 map<K,V>::mapped_type 類型；它的值成員可以修改，但鍵成員不能修改。

    map疊代器進行解引用将産生pair類型的對象。用下标通路不存在的元素将導緻在map容器中添加一個新的元素，它的鍵即為該下标值；類類型的元素用預設構造函數初始化，而内置類型的元素則初始化為0。

8、map 疊代器傳回 value_type 類型的值——包含 const key_type 和mapped_type 類型成員的 pair 對象；下标操作符則傳回一個 mapped_type 類型的值。

9、map插入資料

m.insert(e) 

e 是一個用在 m 上的 value_type 類型的值。如果鍵（e.first）不在 m 中，則插入一個值為 e.second 的新元素；如果該鍵在 m 中已存在，則保持 m 不變。該函數傳回一個pair 類型對象，包含指向鍵為 e.first 的元素的map疊代器，以及一個bool類型的對象，表示是否插入了該元素

m.insert(beg,end)

beg 和 end 是标記元素範圍的疊代器，其中的元素必須為m.value_type

類型的鍵－值對。對于該範圍内的所有元素，如果它的鍵在 m 中不存在，則将該鍵及其關聯的值插入到 m。傳回 void 類型

m.insert(iter,e)

e 是一個用在 m 上的 value_type 類型的值。如果鍵（e.first）不在 m 中，則建立新元素，并以疊代器 iter 為起點搜尋新元素存儲的位置。傳回一個疊代器，指向 m 中具有給定鍵的元素

示例

10、map查找

m.count(k)

傳回 m 中 k 的出現次數

m.find(k)

如果 m 容器中存在按 k 索引的元素，則傳回指向該元素的疊代器。如果不存在，則傳回超出末端疊代器

11、map删除

m.erase(k)

删除 m 中鍵為 k 的元素。傳回 size_type 類型的值，表示删除的元素個數

m.erase(p)

從 m 中删除疊代器 p 所指向的元素。p 必須指向 m 中确實存在的元素，而且不能等于 m.end()。傳回 void

m.erase(b, e)

從 m 中删除一段範圍内的元素，該範圍由疊代器對 b 和 e 标記。b 和 e 必須标記 m 中的一段有效範圍：即 b 和 e 都必須指向m中的元素或最後一個元素的下一個位置。而且，b 和 e 要麼相等（此時删除的範圍為空），要麼 b 所指向的元素必須出現在 e 所指向的元素之前。傳回 void 類型

12、set

    set容器隻是單純的鍵的集合，當隻想知道一個值是否存在時，使用set很适合。set支援大部分的map操作，如insert,count,find,erase操作等。兩種例外：set不支援下标操作符，而且沒有定義 mapped_type 類型。在 set 容器中，value_type 不是 pair 類型，而是與 key_type 相同的類型。它們指的都是 set 中存儲的元素類型。這一差别也展現了 set 存儲的元素僅僅是鍵，而沒有所關聯的值。與 map 一樣，set 容器存儲的鍵也必須唯一，而且不能修改。

一個例子程式

參考：

<a href="http://blog.163.com/zhoumhan_0351/blog/static/39954227201032392545410/">http://blog.163.com/zhoumhan_0351/blog/static/39954227201032392545410/</a>