關聯容器支持高效的關鍵字查找和訪問。兩個主要的關聯容器的類型是map和set。其中map中的元素是一些關鍵字-值（key-value）對。set中每個元素只包含一個關鍵字。

標準庫中提供8個關聯容器。分別體現在3個維度上：

• 每種容器要么是map，要么是set；
• 是否允許存在重復的關鍵字，允許重復通常以multi開頭；
• 是否有序，無序通常以unordered開頭；

因此unorderd_multiset是一個允許重復的無序集合。set則是一個要求不重復的有序集合。

使用關聯容器

統計輸入的單詞出現次數，并剔除一些不重要的詞匯。

map<string, size_t> wordCount;
set<string> exclude = {"the", "but", "and", "or", "an", "a"};string word;
while(cin >> word)
{if(exclude.find(word) == exclude.end())map[word]++;
}

定義關聯容器

map<string, string> authors = {{"key", "value"}, {{"key", "value"}, {{"key", "value"}}; //初始化一個map時，必須提供key, value并包含在花括號中。//定義一個包含20個元素的vec，保持0-9每個整數的兩個拷貝
vector<int> ivec;
for(vector<int>::size_type i = 0; i < 10; ++i)
{ivec.push_back(i);ivec.push_back(i);
}set<int> iset(ivec.begin(), ivec.end()); //size = 10;
multiset<int> miset(ivec.begin(), ivec.end()); //size = 20;

關鍵字類型的要求

對于有序容器，關鍵字的類型必須定義元素比較的方法。默認情況下關鍵字類型的<運算符來比較兩個關鍵字。也可以提供自定義的比較操作：

bool compareIsbn(const Sales_data & lhs, const Sales_data &rhs)
{return lhs.isbn() < rhs.isbn();
}multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

為了定義自己的操作，在定義multiset的時候，必須提供兩個類型：關鍵字類型以及比較操作類型（函數指針類型）。這里使用decltype來獲得函數指針類型。對象初始化的時候還得傳入比較函數指針。

pair類型

pair的默認構造函數對數據成員進行值初始化。map的元素是pair。

用作返回類型

pair<string, int> process(vector<string> &v)
{if(!v.empty()){return {v.back(), v.back().size()}; //列表初始化}else{return pair<string, int>(); //隱式構造返回值，make_pair("", 0);}
}

關聯容器上的操作

set<string>::key_type v1; //string
set<string>::value_type v2; //string
map<string, int>::key_type v3; //string
map<string, int>::mapped_type v4; //int
map<string, int>::value_type v5; //pair<const string, int>

關聯容器的迭代器

解引用一個關聯容器的迭代器時，會得到一個類型為容器的value_type的值的引用。*

• map對應一個pair類型，其first保存const關鍵字，second保存值；
• set雖然同時定義了iterator和const_iterator，但兩種類型都只允許讀set中的元素，都是const屬性的。

auto map_it = word_count.cbegin();
while(map_it != word_count.cend())
{cout << map_it->first << map_it->second << endl;++map_it;
}

因為其實有序的，因此這里打印輸出也是有序的。

關聯容器和算法

通常不對關聯容器使用泛型算法。鍵的const的屬性不適用于大多數泛型算法。

添加元素

有序容器中，insert(p, v)其中p只是一個hint，不一定有效。
insert或emplace的返回值依賴于容器類型何參數。對于不包含重復關鍵字的容器，添加單一元素會返回一個pair，其first成員是一個迭代器，指向給定關鍵字的元素；second成員是一個bool，表示元素是否插入（若關鍵字已經存在，則不插入）。

• set：對于一個給定的關鍵字，只有第一個帶此關鍵字的元素被插入到容器中

vector<int> ivec = {2, 4, 6, 8, 2, 4, 6, 8};
set<int> set2;
set2.insert(ivec.begin(), ivec.end()); //4個元素
set2.insert({2, 4, 6, 8}); //4個元素

• map

word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, int>(word, 1));
word_count.insert(map<string, int>::value_type(word, 1));

• multimap、multiset：關鍵字允許重復，因此插入操作總會插入元素。即時接受單個元素的插入操作，也只會返回一個指向該元素的迭代器。

刪除元素

map的下標操作

訪問元素

其中lower_bound、upper_bound、equal_range只適用于有序容器。

有這么一個應用場景，打印輸出一個作者的所有書籍，數據存儲在一個multimap中。可以通過以下三種方式實現：

string search_item("Alain de Botton");
//1
auto entries = authors.count(search_item);
auto iter = authors.find(search_item);
while(entries)
{cout << iter->second << endl;entries--;iter++;
}//2
for(auto beg = author.lower_bound(search_item), end = author.upper_bound(search_item); beg != end; beg++)cout << iter->second << endl;//3
for(auto pos = authors.equal_range(search_item); pos.first != pos.second; pos.first++)cout << pos.first->second << endl;

無序容器

無序容器使用hash函數和關鍵字類型的==來組織元素。其在存儲上組織為一組桶，使用hash函數將元素映射到桶。為了訪問一個元素，容器首先計算元素的hash值，它指出該搜索哪個桶。當一個桶中包含多個元素時，需要順序搜索這些元素值來找到我們想要的那個。

無序容器提供了一組管理桶的函數：

對關鍵字的要求

對于內置類型、string、智能指針等可以直接當作關鍵字。當要把自定義類型作為關鍵字時，需要提供自定義的hash、和==函數。

size_t hasher(const Sales_data &sd)
{return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{return lhs.isbn() == rhs.isbn();
}using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;//參數桶大小，hash，==
SD_multiset bookstore(42, hasher, eqOp);

如果類定義了==運算符，則可以只重載hash函數：

#include <iostream>
#include <unordered_map>struct Point {int x;int y;// 相等比較：unordered_map 要求bool operator==(const Point& other) const {return x == other.x && y == other.y;}
};// 自定義哈希函數
struct PointHash {std::size_t operator()(const Point& p) const {return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);}
};int main() {std::unordered_map<Point, std::string, PointHash> umap;umap[{1, 2}] = "A";umap[{3, 4}] = "B";umap[{1, 2}] = "C"; // 會覆蓋前面的 "A"for (const auto& pair : umap) {std::cout << "(" << pair.first.x << "," << pair.first.y << ") = "<< pair.second << '\n';}
}

其中std::hash<int>()創建一個臨時對象，std::hash<int>()()調用該對象。