使用 <map> 库创建关联容器
使用 <map> 库创建关联容器
作者：Danny Kalev
编译：MTT 工作室
原文出处：Use the <map> Library to Create Associative Containers
摘要：当索引是整型，那么将值与之关联并不难，但如果数据的关联值对是其它数据类型怎么办呢？<map>库具备一个关联容器，使用它可以很方便地关联所有类型的数据对。本文将讨论
<map> 库的使用方法和技巧。
关系数据库，科学计算应用以及基于Web的系统常常需要类似 vector
的容器，其索引可以是如何数据类型，不一定是整数。这样的容器叫关联容器，或者
map。例如，目录服务应用可以将私人姓名作为索引来存储，电话号码作为其关联的值：directory["Harry"]=8225687;// 插入 "Harry" 并与他的电话号码关联
iterator it=directory.find("Harry");// 获取 Harry 的电话号码
其它关联容器的应用还包括将 URLs 映射到 IP 的 DNS
服务器，字典，库存清单，工资表等等。那么如何突破整型索引的局限，实现用其它数据类型作为索引的关联容器呢？答案是：使用 <map>
库创建和处理关联容器。
Pair 和 Map
最近的一篇文章中，我介绍了
tuple 的概念，它是不同类型元素的集合。在这篇文章中，有一个内容没有提到，那就是 C++98 标准库已经具备一个特殊的
tuple 类型——pair。它将键值（也就是第一个元素）与某个值（第二个值）关联。例如：
#include <utility> //definition of pair
#include <string>
pair <string, string> prof_and_course("Jones", "Syntax");
pair <int, string> symbolic_const (0, "false");
标准库还定义了一个辅助函数，方便 pair 类型的创建：
string prof;
string course;
make_pair(prof,course);//returns pair <string,string>
第一步：构造和初始化一个 map 对象
假设你正在开发一个地址簿程序，地址簿包含姓名和 e-mail 地址。类模板 map 在 <map> 中定义i，它是一个使用类型对的关联容器，第一个元素是索引，第二个元素是关联的值。使用方法如下：
#include <map>
map <string, string> addresses;
为了添加元素，使用下标算符：
addresses["Paul W."]="paul@mail.com";
这里，串“Paul W.”是索引或键值，“paul@mail.com”是其关联的值。如果该 map
已经包含了此键值，那么当前所关联的值不会改变：addresses["Paul W."]=
"newaddr@com.net"; // 不起作用
第二步：搜索
在不插入元素的情况下，如果你想检查某个元素是否存在，可以使用 find()成员函数。find()有两个重载的版本：
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
通常，用
typedef 可以使代码更可读一些：
typedef map <string, string>::const_iterator CIT;
CIT cit=addresses.find("Paul W.");
if (cit==addresses.end())
cout << "sorry, no such key" << endl;
else
cout << cit->first << ''\t'' << cit->second << endl;
表达式中 cit->first 和 cit->second 分别返回键值及其关联的值。
第三步：元素遍历
现在让我们看一个更现实的情况。假设你正在经营一家旅行社，每一个代理做一单业务都可以获得奖金。这些代理的信息存储在某个文件中，其格式如下：
Bob 35
Bob 90
Jane 80.25
Sue 100
Jane 65.5
你的应用程序必须汇总所有代理的奖金并将每个代理的奖金总数显示出来.首先，创建一个 map，然后读取该数据文件：
map <string, double> bonuses;
string agent;
double bonus=0;
ifstream bonusfile("bonuses.dat");
if(!bonusfile)
{
// 报告出错信息并终止程序
}
while (bonusfile >> agent >> bonus)
{
bonuses[agent]+=bonus;// 累加每个代理的奖金
}
不管理相不相信，就这么简单！且让我们来分析一下该循环。打开数据文件之后，while 循环读取每个值对，并将其存入 agent 和
bouns 对象。接着，它将 agent 和 bouns 插入到该 map。此处的关键技巧是：如果键值（agent）已经存在，那么 +=
操作符便将最新读取的 bouns 累加到存储在 map 中当前的 bouns 中。因为表达式：
map[key]
返回与键值关联的值。当重载的 += 操作符被调用时，该值便被累加到新读取的 bouns 中。最后累加的和覆盖 map
中旧的关联值。记住：当你使用下标算符机制时，纯粹的赋值操作并不会改写现有的值，只有重载的 += 才这么做。
幸运的是，map 并不包含一个必须要初始化的键值，表达式：
map[key]
返回默认的初始化 T，而 T 在上述例子中是 double 类型。默认的初始值为 0。至此，map 包含代理及其奖金汇总值对。下面的循环用来显示这些值对，输出如图一所示：
for(CIT p=bonuses.begin(); p!=bonuses.end(); ++p)
{
cout << p->first <<''\t'' << p->second <<endl;
}
图一 代理奖金汇总数
散列的关联容器
标准库目前还不提供散列关联容器。这种容器可以大大改进性能，因为它们使用散列算法从原来的字符串索引派生短键值。但是，许多
IDEs 提供非标准散列容器扩展。值得庆幸的是，新的 C++0X 标准弥补了这一点，在 C++ 中添加了一组散列容器和与之相关的算法。
Danny Kalev 是一名通过认证的系统分析师，专攻 C++ 和形式语言理论的软件工程师。1997 年到 2000
年期间，他是 C++ 标准委员会成员。最近他以优异成绩完成了他在普通语言学研究方面的硕士论文。
业余时间他喜欢听古典音乐，阅读维多利亚时期的文学作品，研究 Hittite、Basque 和 Irish Gaelic
这样的自然语言。其它兴趣包括考古和地理。Danny 时常到一些 C++ 论坛并定期为不同的 C++
网站和杂志撰写文章。他还在教育机构讲授程序设计语言和应用语言课程。
