======关联容器======
C++ Primer 笔记 第十一章\\
----
**关联容器**（//Associative Container//）指使用 //Key// 进行元素存取的容器。这种存取方式使得关联容器的**查询效率非常高**。\\ \\
关联容器拥有两种类型：//Map// 和 //Set//：
  * Map 中的元素成对出现，包括一个 //Key// 与其对应的存储内容
  * Set 中的 //Key// 就是元素
从应用上来讲，需要快速查找指定内容的情形可以使用 //Map//，比如字典：字就是 key，而解释就是存储的内容。而利用 //Set// 可以实现高效的文字过滤。\\ \\ 
STL 提供的关联容器分为 8 种，主要以三个方面来划分：
  * 是 set 或 map
  * Key 是否唯一
  * 是否**按顺序**存储元素（Key 是不是有序）
允许重复 Key 的关联容器以 ''multi'' 开头；不按顺序存储元素的关联容器以 ''unordered'' 开头。比如：
<code cpp>
unordered_multmap
</code>
指的是一个//元素内容成对出现的、Key 可以重复的、内容不按顺序存储的//关联容器。所有容器的类型如下图：
\\ \\ 
{{ cs:programming:cpp:cpp_primer:acontainers.svg?500 |}}
==关联容器的头文件==
  * ''map'' 与 ''multimap'' 类型定义于 ''<map>'' 头文件中
  *  ''set'' 与 ''multiset'' 类型定义于 ''<set>'' 头文件中
  * 对应的 //unordered// 版本分别定义于 ''<unordered_map>'' / ''<unordered_set>'' 头文件中
====使用关联容器====

//Map// 用于存储一系列 //key-value// pair；这种元素的结构可以被视作从 Key 到 value 的映射。通常 //Map// 被视作关联容器中的 //Array//，只是其下标不再是 ''int''，而是 Key 的值。//Map// 中的值是通过 Key 进行查找；比如查找对应人员的电话就可以写成：
<code cpp>
person[name];
</code>
//Set// 用于存储一系列的 key。 Key 本身即为 //Set// 的元素。//Set// 在对已有信息进行筛选的任务中非常有用。
===使用 Map===
一个比较经典的用法使用 //Map// 检测某个词输入了多少次：\\ \\ 
首先，//Map// 的定义需要指定 key 与 value 的类型：
<code cpp>
map<string, size_t> word_count; 
//other def
string word;
</code>
其次，map可以通过 ''map_name[key_name]'' 的方式对 key 对应的 value 进行修改。我们这里对输入的 key（也就是输入的词，变量名 ''word''）进行输出次数的累加，累加的值存入 key 对应的 value 里：
<code cpp>
while(cin >> word)
	++word_count[word]; 
</code>
需要注意的是，当通过新的 key（word）创建 pair 的时候， value 的初始值为 ''0''。\\ \\ 
当输入完成以后，使用循环将信息打印出来。//Map// 也可以使用 //range for// 打印：
<code cpp>
for(const auto &w : word_count)
	cout << w.first << " occurs " 
		 << w.second << ((w.second > 1) ? "times" : "time")
	     << endl;
</code>
打印 pair 的时候需要分开打印。 ''first'' 成员保存 key, ''second'' 成员保存 value，也就是对应 key 的出现次数。
===使用 Set===
Set 常用于**过滤关键词**。比如下面的例子，我们将使用 //Set// 定义屏蔽词列表，使 //Map// 只统计未被屏蔽的关键词输入次数。\\ \\ 
首先定义 //Set//。由于 //Set// 只包含 key，因此只需要指定 key 的类型：
<code cpp>
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;
</code>
接下来使用循环输入数据。这里我们通过两个 set 成员 //find()// 与 //end()// 实现条件的判断：
<code cpp>
while (cin >> word)
	if(exclude.find(word) == exclude.end())
		++word_count[word];
</code>
//find()// 会接收一个 Key，并在调用它的对象中寻找是否有匹配的 Key。如果找到，返回指向该 Key 的迭代器；如果没有找到，则返回 //off-the-end// 迭代器，也就是这里的 ''exclude.end()''。因此，上面的程序实际上意味着，只要 map 中的词不存在于黑名单中，则对其累加一次计数。
====关联容器概述====
关联容器与顺序容器都支持一般的容器操作 （见** [[cs:programming:cpp:cpp_primer:9_containers#标准库容器概况|Container Operations]]**）；但也有一些例外，比如：
  * 由于关联容器基于 Key 实现存储，因此不支持**基于位移的顺序容器操作**，比如 //push_back()//。
  * 关联容器不支持构造、插入 pair 类型数据的操作。
除此之外，C++ 还提供了一些关联容器专属的操作和 type alias，并且，针对 //unodered// 系列的关系容器，C++ 提供了针对性的优化版本（基于 Hash 的优化版本）。\\ \\ 
<WRAP center round info 100%>
关联容器使用**双向迭代器**。
</WRAP>
===定义关联容器===
//Map// 与 //Set// 初始化只要求 initializer 的**类型**满足要求即可。//Map// 与 //Set// 的**默认初始化**会得到一个**空的**关联容器。此外，//Map// 与 //Set// 都可以进行列表初始化；需要注意 //Map// 的写法稍微有些特别：
<code cpp>
//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"};
</code>
上例中，//Map// 的**单个元素**通过另外一对 curly braces 来表示，即：
<code cpp>
{key, value}
</code>
==定义 multimap 或 multiset==
与 //Map// 和 //Set// 不同，在 //Multimap// 与 //Multiset// 中，Key 的**映射关系变得不再唯一**，多个 value 可以同时对应一个 Key（比如字典中，某个词有多种不同解释）。比如下面的例子，使用了相同的 vector 对 set 和 multiset 进行初始化：
<code cpp>
// 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
</code>
由于 set 中的 key 是唯一的，因此其元素要比 multiset 少一半。
===对 Key 的要求===
有序关联容器使用 Key 对元素进行排序。因此，有序关联容器的 Key 需要**定义关系运算**（该要求与排序算法要求的可调用对象相同）。关联容器默认的比较操作为 ''<''。

==有序关联容器中对 Key 的类型要求==
与在排序算法中自定义比较策略类似，我们也可以按自定义的规则对 Key 进行排序。该规则需要需要 Key 类型满足 //Strict weak ordering// 的标准：
<code cpp>
// 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
</code>
可以看出''≤''、''≥'' 并不满足第一条与第三条。因此需要注意避免在规则中使用这两个关系运算。\\ \\ 
当在 map 中使用 key 的时候，若两个 key 等价，则只允许**有一个** value 与这些 key 相关，且通过这些 key 访问到的都是该相关的 value。
<WRAP center round tip 100%>
从实现上来说，为 key 类型定义一个行为正常的 $<$ 关系运算是非常重要的。
</WRAP>
**Refs**:
  * [[https://www.zhihu.com/search?type=content&q=%E4%B8%A5%E6%A0%BC%E5%BC%B1%E5%BA%8F|容器比较器的严格弱序约束]]
  * [[https://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering|Operator< and strict weak ordering]]

==为容器元素的排序指定比较策略==
先明确几个理解：
  * 用于组织容器内元素的操作（比如排序），**也属于容器类型的一部分**，需要在声明的时候在三角括号内写上
  * 该类型的操作通常通过函数来实现
  * 传递该类型则通过函数指针来实现
默认情况下，有序关联容器通过 ''<'' 操作排序。如果元素没有定义该操作，我们可以通过以函数的方式来定义（或重定义）该操作。比如之前的 ''Sales_data'' 类，我们可以通过比较其 ''isbn'' 来对其进行排序：
<code cpp>
//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();
}
</code>
我们通过**函数指针**将其作为类型参数传递给 set。需要注意的是：
  * 传递函数类型时，一般通过函数指针传递。
  * 普通列表项目如果此时使用 ''decltype''，则 ''*'' 是一定要加上的，因为 ''decltype'' 会返回函数的类型。
  * 由于 ISBN 相同的书可能存在多个交易记录，因此使用 //multiset// 。
  * //multiset// ''bookstore'' 的构造函数使用的初始值 ''compareIsbn''，无论带不带取地址符 ''&''，最终都将会被转化为指向该函数的指针。
<code cpp>
// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*>
    bookstore(compareIsbn);
</code>

代表策略的函数 ''compareIsbn'' 存储于 ''bookstore'' 中。上述的初始化建立了一个名为 ''bookstore'' 的，key 的比较策略为 ''compareIsbn'' 的空 multiset。\\ \\ 
更多 multiset 的构造函数用法：[[https://en.cppreference.com/w/cpp/container/multiset/multiset|链接]]
===Pair 类型===
//Pair// 类型是一种 STL 定义的**模板**类型，定义于 ''<utility>'' 头文件中。//Pair// 拥有两个成员，在定义的时候需要**分别指定**两个成员的类型。成员的类型**不需要一致**：
<code cpp>
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>
</code>
//Pair// 的默认构造函数为其成员提供**值初始化**；同时，也可以通过提供初始值初始化 pair:
<code cpp>
pair<string, string> author{"James", "Joyce"};
</code>
//Pair// 的两个数据成员均为 ''public''，可以通过其成员 ''first'' / ''second'' 进行访问：
<code>
cout << w.first << w.second << endl;
</code>
一些 pair 类型相关的操作：
\\ \\ {{ cs:programming:cpp:cpp_primer:std_pair.svg?650 |}} \\ \\

==返回 pair 类型==
当需要以 //Pair// 类型做为返回值的时候，有几种方法可以使用：
  * list intialize the return value（C++ 11）
<code cpp>
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
}
</code>
  * 构造并返回 pair （早期版本）
<code cpp>
if (!v.empty())
    return pair<string, int>(v.back(), v.back().size());
</code>
  * 使用 ''make_pair()'' 返回一个新的 Pair
<code cpp>
if (!v.empty())
    return make_pair(v.back(), v.back().size());
</code>
====关联容器的操作====
关联容器还定义了一些属于自己的类型：
  * ''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：
<code cpp>
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
</code>
type 的写法与顺序容器中的自定义类型一致，需要组合 scope 操作符使用：
<code cpp>
map<string, int>::key_type
</code>
===关联容器的迭代器===
对关联容器迭代器的解引用运算会返回指向 //value_type// 的**引用**。由于 map 的 //value_type// 对应 pair，因此可以使用迭代器访问其 ''first'' 和 ''second'' 成员：
<code cpp>
// 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
</code>
需要注意的是，迭代器只能修改 Map 中元素的 value。
==set 的迭代器都是只读的==
无论 set 的迭代器是 non-const 还是 const，我们都只能通过该迭代器进行**只读**操作。这是因为 set 中的 key 依然是**不可更改**的：
<code cpp>
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
}

</code>
==使用迭代器对关联容器进行遍历==
//Map// 与 //Set// 也提供了 ''begin()'' 和 ''end()'' 成员函数，用于获取器的起始位置和 //off-the-end// 位置。我们可以利用这些成员遍历容器：
<code cpp>
/ 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
}
</code>
上面的打印结果会根据字母表排序。实际上，使用迭代器遍历 map / set，得出的排序会按照 key 的**升序**来排列。
==关联容器与泛型算法==
**不推荐**对关联容器使用泛型算法：
  * 由于 key 是 const，要求写的泛型算法无法在关联容器上使用。
  * 泛型算法的读取与查找是序列性的，并不适用于关联容器的数据结构。
如果非要使用：
  * 将关联容器当做源序列，比如拷贝关联容器的内容到别的序列中
  * 使用 Inserter 的方式对关联容器进行算法的应用
===添加元素===
关联容器可以通过成员 //insert// 和 //emplace// 向容器中添加元素。相关的操作如下：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/ac_insert_1.svg"  width="650"> </div> </html> \\ \\
需要注意的是，//Map// 与 //set// 添加元素的时候，均会验证 key 的唯一性。对于**已存在的 key**，**无论是插入操作还是构造操作，都是无效的**。一些例子：
<code cpp>
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
</code>
==向 map 中添加元素==
只要是 pair 类型的元素，都可以向 map 里添加。添加方式有 4 种：
  * 初始化列表
  * 使用 ''make_pair()'' 创建要插入的元素
  * 显式的使用 argument_list 构造元素
  * 使用 //value_type// 构造元素
<code cpp>
// 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
</code>

==测试 insert 的返回值==
对于像 //Map// 与 //Set// 这样 Key 是独一无二的容器，//insert// 成员的指定调用形式会返回一个 pair ，用于告知插入是否成功。该 pair 由一个迭代器与一个 bool 类型组成；迭代器指代的是插入元素所在的 key 的位置，而 bool 类型则用于说明插入的状态。如果当前容器已经存在相同而对 key， 则 //insert// 操作无效，bool 返回 ''false'' 的值。\\ \\ 
该 bool 返回值也可以用于计算输出词的频率：
<code cpp>
// 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
}
</code>
总的逻辑是，如果插入操作返回的 bool 数为假，则证明该词已经被插入过了（出现过了），因此增加一次该词的累积次数。
\\ \\ <color #666>//**++ret.first->second 怎么解释？**//</color>
  * ''ret'': 存储插入操作返回值，即一个迭代器与 bool 组成的 pair
  * ''ret.first'': 返回 pair 中的迭代器，指向元素 ''{word, 1}''
  * ''ret.first->second'': 元素 ''{word, 1}'' 的 value，''1''，也就是 ''word'' 当前累积出现的次数
  * ''++ret.first->second''：增加一次 ''word'' 出现的次数
这里的迭代器的类型是基于 map 类型的。本例中的迭代器类型是：
<code cpp>
map<string, size_t>::iterator
</code>
==向 multimap / multiset 中添加元素==
multimap / multiset 的元素添加不受 key 的限制；也就是说，一个 key 可以对应多个 value。很多应用可以基于这样的结构实现：比如某个作者写了很多本书，则作者可以作为 key 值，他写的书可以做为 value。通过对 multimap 进行元素添加，我们可以把作者与他的书关联起来：
<code cpp>
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"});
</code>
该插入操作返回一个迭代器，指向**最新添加的元素**。
===删除元素===
关联容器使用 //erase// 成员删除元素。//erase// 可以通过 key、单个迭代器和迭代器范围来指定容器中需要被移除的元素：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/ac_erase.svg"  width="650"> </div> </html> \\ \\
使用 //key_type// 类型作为参数的版本会移除**所有 key 值相同的元素值**，并**返回移除元素的数量**。该功能可以作为条件，判断是否进行了元素的移除：
<code cpp>
// 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";
</code>
当操作容器具有唯一的 key 时，该返回值永远是 ''0'' 或 ''1''。如果容器允许多个 key 存在，则可以获得移除的元素：
<code cpp>
auto cnt = authors.erase("Barth, John"); // cnt = 2
</code>
===使用下标访问 map===
关系容器中，只有 map 接受下标 ''[]'' 操作（以及对应的 //at()//）。**该操作接受一个 key，返回 Key 对应的 value**。该操作详情如下：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/ac_sub.svg"  width="500"> </div> </html> \\ \\

//Set// 不接受该操作，因为 set 中只存在 Key 值；//Mulitmap//（以及其 //Unordered// 版本）也不支持该操作，因为 Key 对应的 value 不唯一。除此之外还需要注意：
  * 通过下标访问 map 中**不存在**的元素时，会直接**创建**一个对应 key 的新元素。该元素的值会被**值初始化**。
  * 生成新元素的操作是 //insert()// 操作，因此当 map 是 const 的时候**不可使用**。
<code cpp>
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;
</code>
==如何使用下标访问的返回值==
需要注意的是：然而在 map 中，解引用与下标操作的返回值是**不同**的：
  * 通过下标访问 map ，返回的值是 //map_type// 的对象
  * 对 map 迭代器解引用，返回的值是 //value_type// 的对象
除此之外，使用下标访问的返回值是 //lvalue//。我们可以利用该性质对对应元素进行写操作：
<code cpp>
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
</code>
<WRAP center round tip 100%>
下标操作会添加不存在的元素。如果只是想查看容器是否包含指定元素，请不要使用下标访问该元素。
</WRAP>
===访问元素===
关联容器提供了如下的方式供使用者访问元素：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/ac_access_1.svg"  width="600"> </div> </html> \\ \\
如何使用上述的操作取决于应用对象，比如：
  * //find// 主要用于确认容器内是否存在主要元素
  * //count// 在 key 对应元素不唯一的情况下可以做更多事情
一些例子：
<code cpp>
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
</code>
==使用 find 取代下标==
//find// 成员访问不存在的元素时，不会将其添加到 map。如果只想确认 map 中是否存在某个 key，使用 //find//：
<code cpp>
if (word_count.find("foobar") == word_count.end())
cout << "foobar is not in the map" << endl;
</code>
==multimap / set 中的元素寻找==
以 //Multimap// 为例。  multimap 中，一个 key 可能对应多个 value，因此寻找 multimap 中的元素需要通过几个变量配合使用来完成。比如，如果想找出一个作者对应的所有出版书籍，我们可以通过如下的逻辑来进行查找和输出：
  - 定义要查找的 key, 也就是作者的名字
  - 定义要搜寻的次数，也就是作者著作的数量，可以使用 //count(key)// 计算出
  - 该元素在容器中所处的位置，使用 //find// 成员即可获得指向第一本书籍位置的迭代器
  - 使用搜寻的次数做为循环，循环中：
    - 打印当前的书籍
    - 将迭代器自增移动，指向下一本书籍
    - 将搜寻次数自减，意味着一本书籍已经搜索完成
<code cpp>
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; 
}
</code>
 <color #666>**迭代器实现版本**</color> \\ \\ 
上述循环可以通过两个成员的返回结果来实现：
  * //lower_bound(k)//：返回一个迭代器，指代不小于 k 的 key  中的第一个元素；如果 key 不存在，则返回 //off-the-end// 迭代器。
  * //upper_bound(k)//：返回一个迭代器。如果当前有 key 正好大于 k，则返回 key 中的第一个元素。如果 k 最大，则返回 //off-the-end// 迭代器。
利用上述成员的功能，如果使用当前的 key，也就是作者的名字作为 k 值，就可以建立遍历作者所有书籍的循环：
<code>
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
</code>
\\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/ac_bound_iter_loop_1.svg"  width="500"> </div> </html> \\
因此，实现代码可以写成：
<code cpp>
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;
</code>
如果查询不到该作者，则两个成员都会返回指向 //of-the-end// 的迭代器；这种情况下循环不会被执行。\\ \\ 
<color #666>**equal_range 函数版本 **</color> \\ \\ 
比上述版本更简便的写法是使用 //equal_range()// 成员函数。该成员返回一个 pair 的迭代器。如果 key 存在，则第一个迭代器与 //lower_bound// 的结果一致，第二个迭代器与 //lower_bound// 的返回值一致。因此，我们只需通过 //equal_range// 就能建立起循环的范围：
<code cpp>
for (auto pos = equal_range(author_name).first; 
	 pos != equal_range(author_name).second; ++pos) {
		cout << pos->second << endl;
	 }
</code>
===实例：使用 Map 实现词转换===
词的转换是一个很好的 Map 应用。它利用了 Map 元素中， Key-value 的一一对应性质，使用 value 中的长词汇来替换检测到的 key 中的缩写。比如 key 值 为 ''k''，value 值为 ''okay''，那么检测到输入中存在 ''k''，就会替换成 ''okay''。\\ \\ 
一个简单的实现方案大致分为三部分：
  * //buildMap// 函数，将指定的规则数据转换为 map，供主程序调用。
  * //transform// 函数，一个以词为单位，以指定 map 中的规则进行词转换的函数。
  * //wordTransform// 主函数，接收 / 处理 / 打印数据。
<html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/word_trans_1.svg"  width="250"> </div> </html> \\ \\
==wordTransform 函数的实现==
//wordTransform// 函数主要的功能是：
  * 接收 map 数据，并调用 //buildMap// 生成规则 map
  * 接收 input 的数据，并对数据进行拆分；将拆分好的数据交由 tansform 处理，并格式化输出打印结果：
<code cpp>
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;
	}	
}
</code>
这里通过了 ''getline()'' 接收每一行数据，并使用 ''istringstream'' 读取每一个词进行处理。每读取一个词，就使用 //transform// 函数对其判断并转化。
<WRAP center round tip 100%>
个人意见：书中对于空格的判定是多余的，正常输出即可打印出正确结果。
</WRAP>

==buildMap 函数的实现==
//buildMap// 的功能很简单，读取文本数据并转化为对应的 map。几个要点：
  * 文本数据的单位为 ''key + space + value'' 的形式，因此需要分成两段进行读取。
  * 替换的时候需要检测 value 的值是否合法。本程序的主要目的是将缩写替换为全写，这里设定小于 ''1'' 的全写（value）不合法。
  * 在第二阶段读取 value 的时候，会将中间的空格一并读取；因此输出的时候需要使用 ''substr()'' 去掉。
<code cpp>
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;
}
</code>
还有一点需要注意的是，本程序使用了下标的方法添加元素到 Map。 如果 key（缩写） 重名，则其对应的 value (全写) 将会被**覆盖**掉。如果希望**保留**旧的规则，可以替换使用 //insert()// 成员添加元素（方法如注释）。
==transform 函数的实现==
//transform// 函数接收指定的词。如果该词是 map 中定义的缩写，则将其按照 map 中的对应关系换成全写：
<code cpp>
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
}
</code>
这里对不在 map 中的词做了不修改的处理。
====无序关联容器====
新标准中定义了四种无序关联容器。这些关联容器使用 ''=='' 或者指定的**哈希函数**（//Hash function//）来组织管理元素。无序关联容器主要使用在：
  * 当 key 不需要**有序**的情况下
  * 当 key 的**排序代价很高**的情况下
但总的说来，尽管通过哈希函数来管理元素可以提供更好的平均性能，但对哈希函数的设计、测试与修改给我们带来了更多的工作量。因此，默认情况下，使用有序关联容器往往拥有更好的表现。
<WRAP center round tip 100%>
如果 Key 的无序是固有的，或者通过哈希函数管理元素可以解决性能的问题，使用无序关联容器。
</WRAP>
===使用无序容器===
除了与哈希管理相关的成员，无序容器提供了与有序容器基本上一样的操作。不过因为其无序性，因此在输出的**顺序**上会与有序容器的输出有差别。
==桶的管理==
无序容器通过一系列的**桶**（//Bucket//，也被侯捷老师称为篮子）来管理组织元素。每一个桶都拥有 ''0'' 个或更多的元素。无序容器通过**哈希函数**将元素分配进不同的桶内。哈希函数为每个桶都标记了指定的**哈希值**；当需要访问元素的时候，根据哈希值去对应的桶里搜寻元素。
\\ \\ 
当容器允许一个 key 对应多个元素的时候，所有与某个 key 相关的元素都会放到同一个桶中。因此，无序容器的性能依赖如两个要求：
  * 哈希函数是如何设计的
  * 桶里的元素有多少
当使用相同的 key 调用哈希函数的时候，哈希函数会确保返回同样的值。虽然在理想状态下，哈希函数应该为每一个元素都分配一个独立的哈希值；但由于容器允许 key 与 value 存在一对多的关系，因此很可能存在将同 key 下的 value 放入同一个桶中的情况。由于**对单个桶中的元素查找是通过顺序查找的方式来进行的**，这带来了一个问题：尽管通过 key 找元素对应的桶依然很快，但**桶内的元素过多，会严重影响无序容器的性能**。
\\ \\ 
无序容器提供了如下的成员对桶进行管理：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/unordered_ac_op.svg"  width="450"> </div> </html> \\ \\
==无序容器对 key 的要求==
默认情况下，无序容器使用 ''=='' 运算符来比较 Key（//key_type//）. 我们也可以通过使用**哈希值**（//hash<key_type>// 类型）来对元素进行比较。标准库提供了 ''std::hash'' 模板函数来生成哈希值。该函数支持 //building-in// 类型，某些标准库类型（比如string、smart pointer）等等。\\ \\ 
不过，该模板函数并不能直接对自定义类型使用。计算自定义类型的哈希值有两种方法：
  * 创建自定义的哈希模板（之后的内容）
  * 使用哈希函数计算自定义类型中的某个受其支持的成员，并使用该成员来做为自定义类型的比较标准。
拿之前提到的 //Sales_data// 类作为例子。我们使用一个 multiset 来存放该类型的元素。multiset 的模板定义实际上允许我们指定哈希函数，以及比较相等性的函数：
<code cpp>
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;
</code>
本例中，我们使用 ''std::hash'' 对类的 isbn 成员计算哈希值，并以此来进行元素分配。同时，我们也规定类相等的规则是其 isbn 相等：
<code cpp>
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();
}
</code>
因此，我们的 multiset 可以定义为：
<code cpp>
std::unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*> bookstore(42, hasher, eqOp);
</code>
当然，最好使用 alias 简化写法：
<code cpp>
using SdMultiset = std::unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>
SdMultiset bookstore(42, hasher, eqOp);
</code>
这里使用了函数指针作为传递的参数，与之前有序容器中使用自定义的 compareIsbn 函数用法相同。同时，我们为 ''bookstore'' 的构造提供了 3 个初始值，分别是桶的默认数量，哈希函数，比较函数。

\\ \\ <color #666>**关于 multiset 的构造函数列表：**</color> \\ \\ 
上例使用的该构造函数进行初始化。
<code cpp>
unordered_multiset ( size_type n,
                     const hasher& hf = hasher(),
                     const key_equal& eql = key_equal(),
                     const allocator_type& alloc = allocator_type() );
</code>
其他构造方式可以参考下面的引用。\\ \\ 
**Ref:**[[https://en.cppreference.com/w/cpp/container/unordered_multiset/unordered_multiset|std::unordered_multiset::unordered_multiset]] \\ \\ 
如果类中已经定义了 ''=='' 运算，只提供哈希函数也可以：比如下例，我们不再需要提供 ''eqOp()'' 去定义 ''=='' 运算了：
<code cpp>
// use FooHash to generate the hash code; Foo must have an == operator
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);
</code>