STL的multimap使用(一对多索引)

野性酷女 2022-08-01 18:13 122阅读 0赞

<table style="table-layout: fixed; width: 100%;"> 
 <tbody> 
 <tr> 
 <td> 
 <div>
 在“ 
 <a href="http://www.vckbase.com/document/viewdoc/?id=1377" rel="nofollow">使用 &lt;map&gt; 库创建关联容器</a>” 一文中，我们讨论了标准库中的 map 关联容器。但那只是 map 容器的一部分。标准库还定义了一个 multimap 容器，它与 map 类似，所不同的是它允许重复键。这个属性使得 multimap 比预想的要更有用：比如在电话簿中相同的人可以有两个以上电话号码，文件系统中可以将多个 
 <a href="http://www.opengroup.org/onlinepubs/009695399/functions/symlink.html" rel="nofollow">符号链接</a>映射到相同的物理文件，或DNS服务器可以将几个URLs映射到相同的IP地址。在这些场合，你可以象下面这样： 
 <pre>// 注: 伪码 multimap &lt;string, string&gt; phonebook; phonebook.insert("Harry","8225687"); // 家里电话 phonebook.insert("Harry","555123123"); // 单位电话 phonebook.insert("Harry"," 2532532532"); // 移动电话</pre> 
 　　在 multimap 中能存储重复键的能力大大地影响它的接口和使用。那么如何创建非唯一键的关联容器呢？答案是使用在 &lt;map&gt; 库中定义的 multimap 容器。 提出问题 　　与 map 不同，multimap 可以包含重复键。这就带来一个问题：重载下标操作符如何返回相同键的多个关联值？以下面的伪码为例： 
 <pre>string phone=phonebook["Harry];</pre> 
 　　<a href="http://www.sgi.com/tech/stl/table_of_contents.html" rel="nofollow">标准库</a>设计者的解决这个问题方法是从 multimap 中去掉下标操作符。因此，需要用不同的方法来插入和获取元素以及和进行错误处理。 插入 　 　假设你需要开发一个 DNS 后台程序（也就是 Windows 系统中的服务程序），该程序将 IP 地址映射匹配的 URL 串。你知道在某些情况下，相同的 IP 地址要被关联到多个 URLs。这些 URLs 全都指向相同的站点。在这种情况下，你应该使用 multimap，而不是 map。例如： 
 <pre>#include &lt;map&gt; #include &lt;string&gt; multimap &lt;string, string&gt; DNS_daemon;</pre> 
 　　用 insert() 成员函数而不是<a href="http://www.vckbase.com/bbs/prime/viewprime.asp?id=644" rel="nofollow">下标操作符</a>来插入元素。insert()有一个 <a href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html" rel="nofollow">pair</a> 类型的参数。在“<a href="http://www.vckbase.com/document/viewdoc/?id=1377" rel="nofollow">使用 &lt;map&gt; 库创建关联容器</a>”中我们示范了如何使用 make_pair() 辅助函数来完成此任务。你也可以象下面这样使用它： 
 <pre>DNS_daemon.insert(make_pair("213.108.96.7","cppzone.com"));</pre> 
 　　在上面的 insert()调用中，串 “213.108.96.7”是键，“cppzone.com”是其关联的值。以后插入的是相同的键，不同的关联值： 
 <pre>DNS_daemon.insert(make_pair("213.108.96.7","cppluspluszone.com"));</pre> 
 　　因此，DNS_daemon 包含两个用相同键值的元素。注意 multimap::insert() 和 map::insert() 返回的值是不同的。 
 <pre>typedef pair &lt;const Key, T&gt; value_type; iterator insert(const value_type&amp;); // #1 multimap pair &lt;iterator, bool&gt; insert(const value_type&amp;); // #2 map</pre> 
 　 　multimap::insert()成员函数返回指向新插入元素的迭代指针，也就是 iterator（multimap::insert()总是能执行成功）。但是 map::insert() 返回 pair&lt;iterator, bool&gt;，此处 bool 值表示插入操作是否成功。 查找单个值 　　与 map 类似，multimap 具备两个版本重载的 find()成员函数： 
 <pre>iterator find(const key_type&amp; k); const_iterator find(const key_type&amp; k) const;</pre> 
 find(k) 返回指向第一个与键 k 匹配的 pair 的迭代指针，这就是说，当你想要检查是否存在至少一个与该键关联的值时，或者只需第一个匹配时，这个函数最有用。例如： 
 <pre>typedef multimap &lt;string, string&gt; mmss; void func(const mmss &amp; dns) {
 mmss::const_iterator cit=dns.find("213.108.96.7"); if (cit != dns.end()) cout &lt;&lt;"213.108.96.7 found" &lt;&lt;endl; else cout &lt;&lt;"not found" &lt;&lt;endl; }</pre> 
 处理多个关联值 　　count(k) 成员函数返回与给定键关联的值得数量。下面的例子报告了有多少个与键 “213.108.96.7” 关联的值： 
 <pre>cout&lt;&lt;dns.count("213.108.96.7") //output: 2 &lt;&lt;" elements associated"&lt;&lt;endl;</pre> 
 　　为了存取 multimap 中的多个值，使用 equal_range()、lower_bound()和 upper_bound()成员函数： equal_range(k)：该函数查找所有与 k 关联的值。返回迭代指针的 pair，它标记开始和结束范围。下面的例子显示所有与键“213.108.96.7”关联的值： 
 <pre>typedef multimap &lt;string, string&gt;::const_iterator CIT; typedef pair&lt;CIT, CIT&gt; Range; Range range=dns.equal_range("213.108.96.7"); for(CIT i=range.first; i!=range.second; ++i) cout &lt;&lt; i-&gt;second &lt;&lt; endl; //output: cpluspluszone.com // cppzone.com</pre> 
 　 　lower_bound() 和 upper_bound()：lower_bound(k) 查找第一个与键 k 关联的值，而 upper_bound(k) 是查找第一个键值比 k 大的元素。下面的例子示范用 upper_bound()来定位第一个其键值大于“213.108.96.7”的元素。通常，当键是一个字符串时，会有一个词典编纂比较： 
 <pre>dns.insert(make_pair("219.108.96.70", "pythonzone.com")); CIT cit=dns.upper_bound("213.108.96.7"); if (cit!=dns.end()) //found anything? cout&lt;&lt;cit-&gt;second&lt;&lt;endl; //display: pythonzone.com</pre> 
 如果你想显示其后所有的值，可以用下面这样的循环： 
 <pre>// 插入有相同键的多个值 dns.insert(make_pair("219.108.96.70","pythonzone.com")); dns.insert(make_pair("219.108.96.70","python-zone.com")); // 获得第一个值的迭代指针 CIT cit=dns.upper_bound("213.108.96.7"); // 输出: pythonzone.com，python-zone.com while(cit!=dns.end()) {
 　　　cout&lt;&lt;cit-&gt;second&lt;&lt;endl; 　　　++cit; }</pre> 
 结论 
 　　虽然 map 和 multimap 具有相同的接口，其重要差别在于重复键，设计和使用要区别对待。此外，还要注意每个容器里 insert()成员函数的细微差别。 
 </div> </td> 
 </tr> 
 </tbody> 
</table>