关联容器

C++ Primer 笔记 第十一章

---

关联容器（Associative Container）指使用 Key 进行元素存取的容器。这种存取方式使得关联容器的查询效率非常高。

关联容器拥有两种类型：Map 和 Set：

• Map 中的元素成对出现，包括一个 Key 与其对应的存储内容
• Set 中的 Key 就是元素

从应用上来讲，需要快速查找指定内容的情形可以使用 Map，比如字典：字就是 key，而解释就是存储的内容。而利用 Set 可以实现高效的文字过滤。

STL 提供的关联容器分为 8 种，主要以三个方面来划分：

• 是 set 或 map
• Key 是否唯一
• 是否按顺序存储元素（Key 是不是有序）

允许重复 Key 的关联容器以 multi 开头；不按顺序存储元素的关联容器以 unordered 开头。比如：

unordered_multmap

指的是一个元素内容成对出现的、Key 可以重复的、内容不按顺序存储的关联容器。所有容器的类型如下图：

• map 与 multimap 类型定义于 <map> 头文件中
• set 与 multiset 类型定义于 <set> 头文件中
• 对应的 unordered 版本分别定义于 <unordered_map> / <unordered_set> 头文件中

Map 用于存储一系列 key-value pair；这种元素的结构可以被视作从 Key 到 value 的映射。通常 Map 被视作关联容器中的 Array，只是其下标不再是 int，而是 Key 的值。Map 中的值是通过 Key 进行查找；比如查找对应人员的电话就可以写成：

person[name];

Set 用于存储一系列的 key。 Key 本身即为 Set 的元素。Set 在对已有信息进行筛选的任务中非常有用。

一个比较经典的用法使用 Map 检测某个词输入了多少次：

首先，Map 的定义需要指定 key 与 value 的类型：

map<string, size_t> word_count; 
//other def
string word;

其次，map可以通过 map_name[key_name] 的方式对 key 对应的 value 进行修改。我们这里对输入的 key（也就是输入的词，变量名 word）进行输出次数的累加，累加的值存入 key 对应的 value 里：

while(cin >> word)
	++word_count[word];

需要注意的是，当通过新的 key（word）创建 pair 的时候， value 的初始值为 0。

当输入完成以后，使用循环将信息打印出来。Map 也可以使用 range for 打印：

for(const auto &w : word_count)
	cout << w.first << " occurs " 
		 << w.second << ((w.second > 1) ? "times" : "time")
	     << endl;

打印 pair 的时候需要分开打印。 first 成员保存 key, second 成员保存 value，也就是对应 key 的出现次数。

Set 常用于过滤关键词。比如下面的例子，我们将使用 Set 定义屏蔽词列表，使 Map 只统计未被屏蔽的关键词输入次数。

首先定义 Set。由于 Set 只包含 key，因此只需要指定 key 的类型：

set<string> exclude ={"The", "But", "And", "Or", "An", "A",
					  "the", "but", "and", "or", "an", "a"};
//other def
map<string, size_t> word_count; 
string word;

接下来使用循环输入数据。这里我们通过两个 set 成员 find() 与 end() 实现条件的判断：

while (cin >> word)
	if(exclude.find(word) == exclude.end())
		++word_count[word];

find() 会接收一个 Key，并在调用它的对象中寻找是否有匹配的 Key。如果找到，返回指向该 Key 的迭代器；如果没有找到，则返回 off-the-end 迭代器，也就是这里的 exclude.end()。因此，上面的程序实际上意味着，只要 map 中的词不存在于黑名单中，则对其累加一次计数。

关联容器与顺序容器都支持一般的容器操作 （见 Container Operations）；但也有一些例外，比如：

• 由于关联容器基于 Key 实现存储，因此不支持基于位移的顺序容器操作，比如 push_back()。
• 关联容器不支持构造、插入 pair 类型数据的操作。

除此之外，C++ 还提供了一些关联容器专属的操作和 type alias，并且，针对 unodered 系列的关系容器，C++ 提供了针对性的优化版本（基于 Hash 的优化版本）。

Map 与 Set 初始化只要求 initializer 的类型满足要求即可。Map 与 Set 的默认初始化会得到一个空的关联容器。此外，Map 与 Set 都可以进行列表初始化；需要注意 Map 的写法稍微有些特别：

//default initialization
map<string, size_t> word_count; 
set<string> bad_check;

//list initialization
map<string, string> authors = { {"Joyce", "James"},
								{"Austen", "Jane"}, 
								{"Dickens", "Charles"} };

set<string> exclude = {"the", "but", "and", "or", "an", "a",
					   "The", "But", "And", "Or", "An","A"};

上例中，Map 的单个元素通过另外一对 curly braces 来表示，即：

{key, value}

与 Map 和 Set 不同，在 Multimap 与 Multiset 中，Key 的映射关系变得不再唯一，多个 value 可以同时对应一个 Key（比如字典中，某个词有多种不同解释）。比如下面的例子，使用了相同的 vector 对 set 和 multiset 进行初始化：

// define a vector with 20 elements, holding two copies of each number from 0 to 9
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
    ivec.push_back(i);
    ivec.push_back(i);  // duplicate copies of each number
}
// iset holds unique elements from ivec; miset holds all 20 elements
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl;    // prints 20
cout << iset.size() << endl;    // prints 10
cout << miset.size() << endl;   // prints 20
cout << miset.size() << endl; // prints 20

由于 set 中的 key 是唯一的，因此其元素要比 multiset 少一半。

有序关联容器使用 Key 对元素进行排序。因此，有序关联容器的 Key 需要定义关系运算（该要求与排序算法要求的可调用对象相同）。关联容器默认的比较操作为 <。

与在排序算法中自定义比较策略类似，我们也可以按自定义的规则对 Key 进行排序。该规则需要需要 Key 类型满足 Strict weak ordering 的标准：

// two keys cannot both be "less than" each other
1) if F(key1, key2) == true, then F(key1, key2) == false

// k1 "less than" k2  and k2 ""less than k3, then k1 must be "less than" k3.
2) if F(key1, key2) == true, F(key2, key3) ==true, then F(key1, key3) == true

//definition of equivalent, and transitivity of the equivalent
3) if F(key1, key2) == false && F(key2, key1) == false, then key1 == key2 
4) if key1 == key2 && key2 == key3, then key1 == key3

可以看出≤、≥ 并不满足第一条与第三条。因此需要注意避免在规则中使用这两个关系运算。

当在 map 中使用 key 的时候，若两个 key 等价，则只允许有一个 value 与这些 key 相关，且通过这些 key 访问到的都是该相关的 value。

Refs:

• 容器比较器的严格弱序约束
• Operator< and strict weak ordering

先明确几个理解：

• 用于组织容器内元素的操作（比如排序），也属于容器类型的一部分，需要在声明的时候在三角括号内写上
• 该类型的操作通常通过函数来实现
• 传递该类型则通过函数指针来实现

默认情况下，有序关联容器通过 < 操作排序。如果元素没有定义该操作，我们可以通过以函数的方式来定义（或重定义）该操作。比如之前的 Sales_data 类，我们可以通过比较其 isbn 来对其进行排序：

//The comparison must meet the requirements of the Stirct Weak Ordering.
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs) {
    return lhs.isbn() < rhs.isbn();
}

我们通过函数指针将其作为类型参数传递给 set。需要注意的是：

• 传递函数类型时，一般通过函数指针传递。
• 普通列表项目如果此时使用 decltype，则 * 是一定要加上的，因为 decltype 会返回函数的类型。
• 由于 ISBN 相同的书可能存在多个交易记录，因此使用 multiset 。
• multiset bookstore 的构造函数使用的初始值 compareIsbn，无论带不带取地址符 &，最终都将会被转化为指向该函数的指针。

// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*>
    bookstore(compareIsbn);

代表策略的函数 compareIsbn 存储于 bookstore 中。上述的初始化建立了一个名为 bookstore 的，key 的比较策略为 compareIsbn 的空 multiset。

更多 multiset 的构造函数用法：链接

Pair 类型是一种 STL 定义的模板类型，定义于 <utility> 头文件中。Pair 拥有两个成员，在定义的时候需要分别指定两个成员的类型。成员的类型不需要一致：

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 的默认构造函数为其成员提供值初始化；同时，也可以通过提供初始值初始化 pair:

pair<string, string> author{"James", "Joyce"};

Pair 的两个数据成员均为 public，可以通过其成员 first / second 进行访问：

cout << w.first << w.second << endl;

一些 pair 类型相关的操作：

当需要以 Pair 类型做为返回值的时候，有几种方法可以使用：

• list intialize the return value（C++ 11）

pair<string, int>
process(vector<string> &v)
{
     // process v
     if (!v.empty())
         return {v.back(), v.back().size()}; // list initialize
     else
         return pair<string, int>(); // explicitly constructed return value
}

• 构造并返回 pair （早期版本）

if (!v.empty())
    return pair<string, int>(v.back(), v.back().size());

• 使用 make_pair() 返回一个新的 Pair

if (!v.empty())
    return make_pair(v.back(), v.back().size());

关联容器还定义了一些属于自己的类型：

• key_type，用于表示 key 的类型
• mapped_type，map 类型专属，用于表示 map 中 key 对应的 value 的类型
• value_type，一个泛化的类型：
  • 在 set 中表示 key_type
  • 在 map 中表示 pair<const key_type, mapped_type>

由于 map 的元素是以 key-value 的 pair 形式存在，且我们无法改变 key 的值；因此 pair 中的 key 部分是 const：

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

type 的写法与顺序容器中的自定义类型一致，需要组合 scope 操作符使用：

map<string, int>::key_type

对关联容器迭代器的解引用运算会返回指向 value_type 的引用。由于 map 的 value_type 对应 pair，因此可以使用迭代器访问其 first 和 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

需要注意的是，迭代器只能修改 Map 中元素的 value。

无论 set 的迭代器是 non-const 还是 const，我们都只能通过该迭代器进行只读操作。这是因为 set 中的 key 依然是不可更改的：

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() 成员函数，用于获取器的起始位置和 off-the-end 位置。我们可以利用这些成员遍历容器：

/ get an iterator positioned on the first element
auto map_it = word_count.cbegin();
// compare the current iterator to the off-the-end iterator
while (map_it != word_count.cend()) {
// dereference the iterator to print the element key--value pairs
    cout << map_it->first << " occurs "
         << map_it->second << " times" << endl;
    ++map_it; // increment the iterator to denote the next element
}

上面的打印结果会根据字母表排序。实际上，使用迭代器遍历 map / set，得出的排序会按照 key 的升序来排列。

不推荐对关联容器使用泛型算法：

• 由于 key 是 const，要求写的泛型算法无法在关联容器上使用。
• 泛型算法的读取与查找是序列性的，并不适用于关联容器的数据结构。

如果非要使用：

• 将关联容器当做源序列，比如拷贝关联容器的内容到别的序列中
• 使用 Inserter 的方式对关联容器进行算法的应用

关联容器可以通过成员 insert 和 emplace 向容器中添加元素。相关的操作如下：

<html>

</html>

需要注意的是，Map 与 set 添加元素的时候，均会验证 key 的唯一性。对于已存在的 key，无论是插入操作还是构造操作，都是无效的。一些例子：

vector<int> ivec = {2,4,6,8,2,4,6,8}; // ivec has eight elements
set<int> set2; // empty set
set2.insert(ivec.cbegin(), ivec.cend()); // set2 has four elements
set2.insert({1,3,5,7,1,3,5,7}); // set2 now has eight elements

只要是 pair 类型的元素，都可以向 map 里添加。添加方式有 4 种：

• 初始化列表
• 使用 make_pair() 创建要插入的元素
• 显式的使用 argument_list 构造元素
• 使用 value_type 构造元素

// four ways to add word to word_count
word_count.insert({word, 1}); //list 
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1)); //argument list
word_count.insert(map<string, size_t>::value_type(word, 1)); // value_type

对于像 Map 与 Set 这样 Key 是独一无二的容器，insert 成员的指定调用形式会返回一个 pair ，用于告知插入是否成功。该 pair 由一个迭代器与一个 bool 类型组成；迭代器指代的是插入元素所在的 key 的位置，而 bool 类型则用于说明插入的状态。如果当前容器已经存在相同而对 key， 则 insert 操作无效，bool 返回 false 的值。

该 bool 返回值也可以用于计算输出词的频率：

// more verbose way to count 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) {
    // inserts an element with key equal to word and value 1;
    // if word is already in word_count, insert does nothing
    auto ret = word_count.insert({word, 1});
    if (!ret.second)         // word was already in word_count
        ++ret.first->second; // increment the counter
}

总的逻辑是，如果插入操作返回的 bool 数为假，则证明该词已经被插入过了（出现过了），因此增加一次该词的累积次数。

++ret.first→second 怎么解释？

• ret: 存储插入操作返回值，即一个迭代器与 bool 组成的 pair
• ret.first: 返回 pair 中的迭代器，指向元素 {word, 1}
• ret.first→second: 元素 {word, 1} 的 value，1，也就是 word 当前累积出现的次数
• ++ret.first→second：增加一次 word 出现的次数

这里的迭代器的类型是基于 map 类型的。本例中的迭代器类型是：

map<string, size_t>::iterator

multimap / multiset 的元素添加不受 key 的限制；也就是说，一个 key 可以对应多个 value。很多应用可以基于这样的结构实现：比如某个作者写了很多本书，则作者可以作为 key 值，他写的书可以做为 value。通过对 multimap 进行元素添加，我们可以把作者与他的书关联起来：

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"});

该插入操作返回一个迭代器，指向最新添加的元素。

关联容器使用 erase 成员删除元素。erase 可以通过 key、单个迭代器和迭代器范围来指定容器中需要被移除的元素：

<html>

</html>

使用 key_type 类型作为参数的版本会移除所有 key 值相同的元素值，并返回移除元素的数量。该功能可以作为条件，判断是否进行了元素的移除：

// erase on a key returns the number of elements removed
if (word_count.erase(removal_word))
cout << "ok: " << removal_word << " removed\n";
else cout << "oops: " << removal_word << " not found!\n";

当操作容器具有唯一的 key 时，该返回值永远是 0 或 1。如果容器允许多个 key 存在，则可以获得移除的元素：

auto cnt = authors.erase("Barth, John"); // cnt = 2

关系容器中，只有 map 接受下标 [] 操作（以及对应的 at()）。该操作接受一个 key，返回 Key 对应的 value。该操作详情如下：

<html>

</html>

Set 不接受该操作，因为 set 中只存在 Key 值；Mulitmap（以及其 Unordered 版本）也不支持该操作，因为 Key 对应的 value 不唯一。除此之外还需要注意：

• 通过下标访问 map 中不存在的元素时，会直接创建一个对应 key 的新元素。该元素的值会被值初始化。
• 生成新元素的操作是 insert() 操作，因此当 map 是 const 的时候不可使用。

map <string, size_t> word_count; // empty map
// insert a value-initialized element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;

需要注意的是：然而在 map 中，解引用与下标操作的返回值是不同的：

• 通过下标访问 map ，返回的值是 map_type 的对象
• 对 map 迭代器解引用，返回的值是 value_type 的对象

除此之外，使用下标访问的返回值是 lvalue。我们可以利用该性质对对应元素进行写操作：

cout << word_count["Anna"]; // fetch the element indexed by Anna; prints 1
++word_count["Anna"];       // fetch the element and add 1 to it
cout << word_count["Anna"]; // fetch the element and print it; prints 2

关联容器提供了如下的方式供使用者访问元素：

<html>

</html>

如何使用上述的操作取决于应用对象，比如：

• find 主要用于确认容器内是否存在主要元素
• count 在 key 对应元素不唯一的情况下可以做更多事情

一些例子：

set<int> iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1); // returns an iterator that refers to the element with key == 1
iset.find(11); // returns the iterator == iset.end()
iset.count(1); // returns 1
iset.count(11); // returns 0

find 成员访问不存在的元素时，不会将其添加到 map。如果只想确认 map 中是否存在某个 key，使用 find：

if (word_count.find("foobar") == word_count.end())
cout << "foobar is not in the map" << endl;

以 Multimap 为例。 multimap 中，一个 key 可能对应多个 value，因此寻找 multimap 中的元素需要通过几个变量配合使用来完成。比如，如果想找出一个作者对应的所有出版书籍，我们可以通过如下的逻辑来进行查找和输出：

1. 定义要查找的 key, 也就是作者的名字
2. 定义要搜寻的次数，也就是作者著作的数量，可以使用 count(key) 计算出
3. 该元素在容器中所处的位置，使用 find 成员即可获得指向第一本书籍位置的迭代器
4. 使用搜寻的次数做为循环，循环中：
   1. 打印当前的书籍
   2. 将迭代器自增移动，指向下一本书籍
   3. 将搜寻次数自减，意味着一本书籍已经搜索完成

string author_name("Alain de Botton");
auto entries = authors.count(author_name); //number of books
auto iter = authors.find(author_name); //the position of the first book

while(entries) {
	cout << iter->second << endl; //print each book
	++iter; //to the next book
	--entries; 
}

迭代器实现版本

上述循环可以通过两个成员的返回结果来实现：

• lower_bound(k)：返回一个迭代器，指代不小于 k 的 key 中的第一个元素；如果 key 不存在，则返回 off-the-end 迭代器。
• upper_bound(k)：返回一个迭代器。如果当前有 key 正好大于 k，则返回 key 中的第一个元素。如果 k 最大，则返回 off-the-end 迭代器。

利用上述成员的功能，如果使用当前的 key，也就是作者的名字作为 k 值，就可以建立遍历作者所有书籍的循环：

curr_iter = lower_bound(curr_key); // curr_iter denotes the first element of curr_key
next_iter = upper_bound(curr_key); // next_iter denotes the first element of next_key

<html>

</html>
因此，实现代码可以写成：

auto curr_book = authors.lower_bound(author_name);
auto next_book = authors.upper_bound(author_name);

for (curr_book; curr_book != next_book; ++curr_book)
	cout << curr_book->second << endl;

如果查询不到该作者，则两个成员都会返回指向 of-the-end 的迭代器；这种情况下循环不会被执行。

equal_range 函数版本

比上述版本更简便的写法是使用 equal_range() 成员函数。该成员返回一个 pair 的迭代器。如果 key 存在，则第一个迭代器与 lower_bound 的结果一致，第二个迭代器与 lower_bound 的返回值一致。因此，我们只需通过 equal_range 就能建立起循环的范围：

for (auto pos = equal_range(author_name).first; 
	 pos != equal_range(author_name).second; ++pos) {
		cout << pos->second << endl;
	 }

词的转换是一个很好的 Map 应用。它利用了 Map 元素中， Key-value 的一一对应性质，使用 value 中的长词汇来替换检测到的 key 中的缩写。比如 key 值 为 k，value 值为 okay，那么检测到输入中存在 k，就会替换成 okay。

一个简单的实现方案大致分为三部分：

• buildMap 函数，将指定的规则数据转换为 map，供主程序调用。
• transform 函数，一个以词为单位，以指定 map 中的规则进行词转换的函数。
• wordTransform 主函数，接收 / 处理 / 打印数据。

<html>

</html>

wordTransform 函数主要的功能是：

• 接收 map 数据，并调用 buildMap 生成规则 map
• 接收 input 的数据，并对数据进行拆分；将拆分好的数据交由 tansform 处理，并格式化输出打印结果：

void wordTransform(ifstream &mapData, ifstream &inputData)
{
	//build the tranform map
	auto transMap = buildMap(mapData);
	string line;

	while(getline(inputData, line))
	{
		std::istringstream wordStream(line);
		//output the result by word
		for(string word; wordStream >> word; )
			cout << transform(word, transMap) << " ";
		cout << endl;
	}	
}

这里通过了 getline() 接收每一行数据，并使用 istringstream 读取每一个词进行处理。每读取一个词，就使用 transform 函数对其判断并转化。

buildMap 的功能很简单，读取文本数据并转化为对应的 map。几个要点：

• 文本数据的单位为 key + space + value 的形式，因此需要分成两段进行读取。
• 替换的时候需要检测 value 的值是否合法。本程序的主要目的是将缩写替换为全写，这里设定小于 1 的全写（value）不合法。
• 在第二阶段读取 value 的时候，会将中间的空格一并读取；因此输出的时候需要使用 substr() 去掉。

const map<string, string> buildMap(ifstream &mapData)
{
	map<string, string> transMap;
	string abbr;
	string fullName;

	//reading data
	while(mapData >> abbr && getline(mapData, fullName))
	{
		if(fullName.size() > 1) // check that there is a transformation
			transMap[abbr] = fullName.substr(1); 
			//transMap.insert({abbr, fullName.substr(1)});
		else
			throw std::runtime_error("No rule for " + abbr); 
	}
	return transMap;
}

还有一点需要注意的是，本程序使用了下标的方法添加元素到 Map。 如果 key（缩写） 重名，则其对应的 value (全写) 将会被覆盖掉。如果希望保留旧的规则，可以替换使用 insert() 成员添加元素（方法如注释）。

transform 函数接收指定的词。如果该词是 map 中定义的缩写，则将其按照 map 中的对应关系换成全写：

const string& 
transform(const string &s, const map<string, string> &mss)
{
	auto mapIter = mss.find(s);
	//if a transformable word 's' is found in rule data
	//return its fullname
	if(mapIter != mss.cend())
		return mapIter->second;
	else
		return s; // otherwise return the original unchanged
}

这里对不在 map 中的词做了不修改的处理。

新标准中定义了四种无序关联容器。这些关联容器使用 == 或者指定的哈希函数（Hash function）来组织管理元素。无序关联容器主要使用在：

• 当 key 不需要有序的情况下
• 当 key 的排序代价很高的情况下

但总的说来，尽管通过哈希函数来管理元素可以提供更好的平均性能，但对哈希函数的设计、测试与修改给我们带来了更多的工作量。因此，默认情况下，使用有序关联容器往往拥有更好的表现。

除了与哈希管理相关的成员，无序容器提供了与有序容器基本上一样的操作。不过因为其无序性，因此在输出的顺序上会与有序容器的输出有差别。

无序容器通过一系列的桶（Bucket，也被侯捷老师称为篮子）来管理组织元素。每一个桶都拥有 0 个或更多的元素。无序容器通过哈希函数将元素分配进不同的桶内。哈希函数为每个桶都标记了指定的哈希值；当需要访问元素的时候，根据哈希值去对应的桶里搜寻元素。

当容器允许一个 key 对应多个元素的时候，所有与某个 key 相关的元素都会放到同一个桶中。因此，无序容器的性能依赖如两个要求：

• 哈希函数是如何设计的
• 桶里的元素有多少

当使用相同的 key 调用哈希函数的时候，哈希函数会确保返回同样的值。虽然在理想状态下，哈希函数应该为每一个元素都分配一个独立的哈希值；但由于容器允许 key 与 value 存在一对多的关系，因此很可能存在将同 key 下的 value 放入同一个桶中的情况。由于对单个桶中的元素查找是通过顺序查找的方式来进行的，这带来了一个问题：尽管通过 key 找元素对应的桶依然很快，但桶内的元素过多，会严重影响无序容器的性能。

无序容器提供了如下的成员对桶进行管理：

<html>

</html>

默认情况下，无序容器使用 == 运算符来比较 Key（key_type）. 我们也可以通过使用哈希值（hash<key_type> 类型）来对元素进行比较。标准库提供了 std::hash 模板函数来生成哈希值。该函数支持 building-in 类型，某些标准库类型（比如string、smart pointer）等等。

不过，该模板函数并不能直接对自定义类型使用。计算自定义类型的哈希值有两种方法：

• 创建自定义的哈希模板（之后的内容）
• 使用哈希函数计算自定义类型中的某个受其支持的成员，并使用该成员来做为自定义类型的比较标准。

拿之前提到的 Sales_data 类作为例子。我们使用一个 multiset 来存放该类型的元素。multiset 的模板定义实际上允许我们指定哈希函数，以及比较相等性的函数：

template<
    class Key, //element type
    class Hash = std::hash<Key>,  //specified hash function
    class KeyEqual = std::equal_to<Key>, //fucntion that comparing equalty 
    class Allocator = std::allocator<Key>,  //allocator type
    > class unordered_multiset;

本例中，我们使用 std::hash 对类的 isbn 成员计算哈希值，并以此来进行元素分配。同时，我们也规定类相等的规则是其 isbn 相等：

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();
}

因此，我们的 multiset 可以定义为：

std::unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*> bookstore(42, hasher, eqOp);

当然，最好使用 alias 简化写法：

using SdMultiset = std::unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>
SdMultiset bookstore(42, hasher, eqOp);

这里使用了函数指针作为传递的参数，与之前有序容器中使用自定义的 compareIsbn 函数用法相同。同时，我们为 bookstore 的构造提供了 3 个初始值，分别是桶的默认数量，哈希函数，比较函数。

关于 multiset 的构造函数列表：

上例使用的该构造函数进行初始化。

unordered_multiset ( size_type n,
                     const hasher& hf = hasher(),
                     const key_equal& eql = key_equal(),
                     const allocator_type& alloc = allocator_type() );

其他构造方式可以参考下面的引用。

Ref:std::unordered_multiset::unordered_multiset

如果类中已经定义了 == 运算，只提供哈希函数也可以：比如下例，我们不再需要提供 eqOp() 去定义 == 运算了：

// use FooHash to generate the hash code; Foo must have an == operator
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);