关联容器支持高效的关键字查找和访问操作。2个主要的关联容器（associative-container）类型是map和set。
-
map中的元素是一些键值对（key-value）：关键字起索引作用，值表示与索引相关联的数据。 -
set中每个元素只包含一个关键字，支持高效的关键字查询操作：检查一个给定关键字是否在set中。
标准库提供了8个关联容器，它们之间的不同体现在三个方面：
-
是
map还是set类型。 -
是否允许保存重复的关键字。
-
是否按顺序保存元素。
允许重复保存关键字的容器名字都包含单词multi；无序保存元素的容器名字都以单词unordered开头。
-
有序容器：
类型 特性 map保存键值对的关联数组 set只保存关键字的容器 multimap关键字可重复出现的 mapmultiset关键字可重复出现的 set -
无序容器：
类型 特性 unordered_map用哈希函数管理的 mapunordered_set用哈希函数管理的 setunordered_multimap关键字可重复出现的 unordered_mapunordered_multiset关键字可重复出现的 unordered_set
map和multimap类型定义在头文件map中；set和multiset类型定义在头文件set中；无序容器定义在头文件unordered_map和unordered_set中。
map类型通常被称为关联数组（associative array）。
从map中提取一个元素时，会得到一个pair类型的对象。pair是一个模板类型，保存两个名为first和second的公有数据成员。map所使用的pair用first成员保存关键字，用second成员保存对应的值。
// count the number of times each word occurs in the input
map<string, size_t> word_count; // empty map from string to size_t
string word;
while (cin >> word)
++word_count[word]; // fetch and increment the counter for word
for (const auto &w : word_count) // for each element in the map
// print the results
cout << w.first << " occurs " << w.second
<< ((w.second > 1) ? " times" : " time") << endl;set类型的find成员返回一个迭代器。如果给定关键字在set中，则迭代器指向该关键字，否则返回的是尾后迭代器。
定义map时，必须指定关键字类型和值类型；定义set时，只需指定关键字类型。
初始化map时，提供的每个键值对用花括号{}包围。
map<string, size_t> word_count; // empty
// list initialization
set<string> exclude = { "the", "but", "and" };
// three elements; authors maps last name to first
map<string, string> authors =
{
{"Joyce", "James"},
{"Austen", "Jane"},
{"Dickens", "Charles"}
};map和set中的关键字必须唯一，multimap和multiset没有此限制。
对于有序容器——map、multimap、set和multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来进行比较操作。
用来组织容器元素的操作的类型也是该容器类型的一部分。如果需要使用自定义的比较操作，则必须在定义关联容器类型时提供此操作的类型。操作类型在尖括号中紧跟着元素类型给出。
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() < rhs.isbn();
}
// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);pair定义在头文件utility中。一个pair可以保存两个数据成员，分别命名为first和second。
pair<string, string> anon; // holds two strings
pair<string, size_t> word_count; // holds a string and an size_t
pair<string, vector<int>> line; // holds string and vector<int>pair的默认构造函数对数据成员进行值初始化。
在C++11中，如果函数需要返回pair，可以对返回值进行列表初始化。早期C++版本中必须显式构造返回值。
pair<string, int> process(vector<string> &v)
{
// process v
if (!v.empty())
// list initialize
return { v.back(), v.back().size() };
else
// explicitly constructed return value
return pair<string, int>();
}关联容器定义了类型别名来表示容器关键字和值的类型。
| 类型 | 含义 |
|---|---|
key_type |
容器的关键字类型 |
mapped_type |
map的值类型 |
value_type |
对于set，与key_type相同对于 map，为pair<const key_type, mapped_type> |
对于set类型，key_type和value_type是一样的。set中保存的值就是关键字。对于map类型，元素是键值对。即每个元素是一个pair对象，包含一个关键字和一个关联的值。由于元素关键字不能改变，因此pair的关键字部分是const的。另外，只有map类型（unordered_map、unordered_multimap、multimap、map）才定义了mapped_type。
set<string>::value_type v1; // v1 is a string
set<string>::key_type v2; // v2 is a string
map<string, int>::value_type v3; // v3 is a pair<const string, int>
map<string, int>::key_type v4; // v4 is a string
map<string, int>::mapped_type v5; // v5 is an int解引用关联容器迭代器时，会得到一个类型为容器的value_type的引用。对map而言，value_type是pair类型，其first成员保存const的关键字，second成员保存值。
// get an iterator to an element in word_count
auto map_it = word_count.begin();
// *map_it is a reference to a pair<const string, size_t> object
cout << map_it->first; // prints the key for this element
cout << " " << map_it->second; // prints the value of the element
map_it->first = "new key"; // error: key is const
++map_it->second; // ok: we can change the value through an iterator虽然set同时定义了iterator和const_iterator类型，但两种迭代器都只允许只读访问set中的元素。类似map，set中的关键字也是const的。
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end())
{
*set_it = 42; // error: keys in a set are read-only
cout << *set_it << endl; // ok: can read the key
}map和set都支持begin和end操作。使用迭代器遍历map、multimap、set或multiset时，迭代器按关键字升序遍历元素。
通常不对关联容器使用泛型算法。
使用insert成员可以向关联容器中添加元素。向map和set中添加已存在的元素对容器没有影响。
通常情况下，对于想要添加到map中的数据，并没有现成的pair对象。可以直接在insert的参数列表中创建pair。
// four ways to add word to word_count
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));insert或emplace的返回值依赖于容器类型和参数：
-
对于不包含重复关键字的容器，添加单一元素的
insert和emplace版本返回一个pair，表示操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值。如果关键字已在容器中，则insert直接返回，bool值为false。如果关键字不存在，元素会被添加至容器中，bool值为true。 -
对于允许包含重复关键字的容器，添加单一元素的
insert和emplace版本返回指向新元素的迭代器。
与顺序容器不同，关联容器提供了一个额外的erase操作。它接受一个key_type参数，删除所有匹配给定关键字的元素（如果存在），返回实际删除的元素数量。对于不包含重复关键字的容器，erase的返回值总是1或0。若返回值为0，则表示想要删除的元素并不在容器中。
| 操作 | 含义 |
|---|---|
c[k] |
返回关键字为k的元素；若k不存在，则向c中添加并进行值初始化 |
c.at(k) |
返回关键字为k的元素；若k不存在，则抛出out_of_range异常 |
map下标运算符接受一个关键字，获取与此关键字相关联的值。如果关键字不在容器中，下标运算符会向容器中添加该关键字，并值初始化关联值。
由于下标运算符可能向容器中添加元素，所以只能对非const的map使用下标操作。
对map进行下标操作时，返回的是mapped_type类型的对象；解引用map迭代器时，返回的是value_type类型的对象。
| 操作 | 含义 |
|---|---|
c.find(k) |
返回指向第一个关键字为k的元素的迭代器或尾后迭代器 |
c.count(k) |
返回关键字为k的元素的数量 |
c.lower_bound(k) |
返回指向第一个关键字不小于k的元素的迭代器 |
c.upper_bound(k) |
返回指向第一个关键字大于k的元素的迭代器 |
c.equal_range(k) |
返回一个迭代器pair，表示关键字为k的元素范围 |
如果multimap或multiset中有多个元素具有相同关键字，则这些元素在容器中会相邻存储。
multimap<string, string> authors;
// adds the first element with the key Barth, John
authors.insert({"Barth, John", "Sot-Weed Factor"});
// ok: adds the second element with the key Barth, John
authors.insert({"Barth, John", "Lost in the Funhouse"});
string search_item("Alain de Botton"); // author we'll look for
auto entries = authors.count(search_item); // number of elements
auto iter = authors.find(search_item); // first entry for this author
// loop through the number of entries there are for this author
while(entries)
{
cout << iter->second << endl; // print each title
++iter; // advance to the next title
--entries; // keep track of how many we've printed
}lower_bound和upper_bound操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，lower_bound返回的迭代器会指向第一个匹配给定关键字的元素，而upper_bound返回的迭代器则指向最后一个匹配元素之后的位置。如果关键字不在multimap中，则lower_bound和upper_bound会返回相等的迭代器，指向一个不影响排序的关键字插入位置。因此用相同的关键字调用lower_bound和upper_bound会得到一个迭代器范围，表示所有具有该关键字的元素范围。
// definitions of authors and search_item as above
// beg and end denote the range of elements for this author
for (auto beg = authors.lower_bound(search_item),
end = authors.upper_bound(search_item);
beg != end; ++beg)
cout << beg->second << endl; // print each titlelower_bound和upper_bound有可能返回尾后迭代器。如果查找的元素具有容器中最大的关键字，则upper_bound返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则lower_bound也返回尾后迭代器。
equal_range操作接受一个关键字，返回一个迭代器pair。若关键字存在，则第一个迭代器指向第一个匹配关键字的元素，第二个迭代器指向最后一个匹配元素之后的位置。若关键字不存在，则两个迭代器都指向一个不影响排序的关键字插入位置。
// definitions of authors and search_item as above
// pos holds iterators that denote the range of elements for this key
for (auto pos = authors.equal_range(search_item);
pos.first != pos.second; ++pos.first)
cout << pos.first->second << endl; // print each title新标准库定义了4个无序关联容器（unordered associative container），这些容器使用哈希函数（hash function）和关键字类型的==运算符组织元素。
无序容器和对应的有序容器通常可以相互替换。但是由于元素未按顺序存储，使用无序容器的程序输出一般会与有序容器的版本不同。
无序容器在存储上组织为一组桶，每个桶保存零或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。因此无序容器的性能依赖于哈希函数的质量和桶的数量及大小。
默认情况下，无序容器使用关键字类型的==运算符比较元素，还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。标准库为内置类型和一些标准库类型提供了hash模板。因此可以直接定义关键字是这些类型的无序容器，而不能直接定义关键字类型为自定义类类型的无序容器，必须先提供对应的hash模板版本。