What & How & Why

您在这里: start » cs » programming » cpp » cpp_primer » 11_acontainers

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:programming:cpp:cpp_primer:11_acontainers [2024/01/14 13:46] – 移除 - 外部编辑 (未知日期) 127.0.0.1cs:programming:cpp:cpp_primer:11_acontainers [2024/01/14 13:47] (当前版本) – ↷ 链接因页面移动而自动修正 codinghare
行 1: 行 1:
 + ======关联容器======
 +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>