关联容器支持高效的关键字查找和访问。两个主要的关联容器的类型是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>()()调用该对象。