本章介紹4種關(guān)聯(lián)容器set、map、unordered_set、unordered_map。

1.順序容器是同構(gòu)元素在容器中的位置訪問元素；關(guān)聯(lián)容器是通過關(guān)鍵字來保存和訪問元素。

2.set用于保存關(guān)鍵字；map用于保存鍵值對，每個鍵值對都用一個pair類型存儲，其中first成員存儲關(guān)鍵字，second成員存儲值。

3.注意在關(guān)聯(lián)容器中，關(guān)鍵字唯一，即關(guān)鍵字不可重復出現(xiàn)。

（有關(guān)鍵字可重復的關(guān)聯(lián)容器，但在此不介紹）

關(guān)聯(lián)容器概述

1. 關(guān)聯(lián)容器是根據(jù)所存儲的關(guān)鍵字來保存和訪問容器中的元素的。

2. 關(guān)聯(lián)容器可以分為有序關(guān)聯(lián)容器set、map和無序關(guān)聯(lián)容器unordered_set、unordered_map。

3. 有序關(guān)聯(lián)容器的底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，因此查找和訪問元素的時間復雜度為O(log n)；無序關(guān)聯(lián)容器的底層數(shù)據(jù)結(jié)構(gòu)為哈希表，查找和訪問元素的時間復雜度為O(1)。

4. 關(guān)聯(lián)容器對象的定義和初始化與順序容器相似。例如：

關(guān)聯(lián)容器共有的操作

map和unordered_map的下標操作

若定義map或unordered_map類型的對象m，則m[k]將返回關(guān)鍵字k的元素對應(yīng)的值的引用；若關(guān)鍵字k不在m中，則m中會自動添加一個關(guān)鍵字為k的元素，并對其值做值初始化。

因set和unordered_set本身就是存儲關(guān)鍵字，因此不支持下標運算符。

有序關(guān)聯(lián)容器的二分查找操作

自定義有序關(guān)聯(lián)容器和priority_queue的關(guān)鍵字/元素比較方法

1.重載小于運算符（同泛型算法章節(jié)中介紹的寫法）

2.函數(shù)對象/仿函數(shù)寫法（創(chuàng)建有序關(guān)聯(lián)容器時可傳遞一個函數(shù)對象作為參數(shù)指定關(guān)鍵字/元素的比較方法）

因為priority_queue是一個容器適配器，需要使用一個底層容器實現(xiàn)，所以第二個參數(shù)需要指定實現(xiàn)的底層容器（一般用vector）。

1）函數(shù)對象類（重載函數(shù)調(diào)用運算符，見泛型算法章節(jié)）

2）greater和less（例：priority_queue<int,vector<int>,greater<int>>、map<int,int,greater<int>>）

自定義無序關(guān)聯(lián)容器的關(guān)鍵字哈希函數(shù)

其中Hash為自定義哈希函數(shù)，可以通過編寫函數(shù)對象類實現(xiàn)哈希函數(shù)。如下定義了一個hash(key)=key mod m（m為表長）的哈希函數(shù)：