Chinaunix首页 | 论坛 | 博客
  • 博客访问: 544512
  • 博文数量: 252
  • 博客积分: 6057
  • 博客等级: 准将
  • 技术积分: 1635
  • 用 户 组: 普通用户
  • 注册时间: 2009-12-21 10:17
文章分类

全部博文(252)

文章存档

2013年(1)

2012年(1)

2011年(32)

2010年(212)

2009年(6)

分类: C/C++

2010-06-12 23:57:22

在“使用 库创建关联容器” 一文中,我们讨论了标准库中的 map 关联容器。但那只是 map 容器的一部分。标准库还定义了一个 multimap 容器,它与 map 类似,所不同的是它允许重复键。这个属性使得 multimap 比预想的要更有用:比如在电话簿中相同的人可以有两个以上电话号码,文件系统中可以将多个映射到相同的物理文件,或DNS服务器可以将几个URLs映射到相同的IP地 址。在这些场合,你可以象下面这样:
// 注: 伪码
multimap phonebook;
phonebook.insert("Harry","8225687"); // 家里电话
phonebook.insert("Harry","555123123"); // 单位电话
phonebook.insert("Harry"," 2532532532"); // 移动电话

  在 multimap 中能存储重复键的能力大大地影响它的接口和使用。那么如何创建非唯一键的关联容器呢?答案是使用在 库中定义的 multimap 容器。

提出问题
  与 map 不同,multimap 可以包含重复键。这就带来一个问题:重载下标操作符如何返回相同键的多个关联值?以下面的伪码为例:

string phone=phonebook["Harry];

  设计者的解决这个问题方法是从 multimap 中去掉下标操作符。因此,需要用不同的方法来插入和获取元素以及和进行错误处理。

插入
   假设你需要开发一个 DNS 后台程序(也就是 Windows 系统中的服务程序),该程序将 IP 地址映射匹配的 URL 串。你知道在某些情况下,相同的 IP 地址要被关联到多个 URLs。这些 URLs 全都指向相同的站点。在这种情况下,你应该使用 multimap,而不是 map。例如:

#include 
#include
multimap DNS_daemon;

  用 insert() 成员函数而不是来插入元素。insert()有一个 类型的参数。在“使用 库创建关联容器”中我们示范了如何使用 make_pair() 辅助函数来完成此任务。你也可以象下面这样使用它:

DNS_daemon.insert(make_pair("213.108.96.7","cppzone.com"));

  在上面的 insert()调用中,串 “213.108.96.7”是键,“cppzone.com”是其关联的值。以后插入的是相同的键,不同的关联值:

DNS_daemon.insert(make_pair("213.108.96.7","cppluspluszone.com"));

  因此,DNS_daemon 包含两个用相同键值的元素。注意 multimap::insert() 和 map::insert() 返回的值是不同的。

typedef pair  value_type;
iterator
insert(const value_type&); // #1 multimap
pair
insert(const value_type&); // #2 map

   multimap::insert()成员函数返回指向新插入元素的迭代指针,也就是 iterator(multimap::insert()总是能执行成功)。但是 map::insert() 返回 pair,此处 bool 值表示插入操作是否成功。

查找单个值
   与 map 类似,multimap 具备两个版本重载的 find()成员函数:

iterator find(const key_type& k);
const_iterator find(const key_type& k) const;

find(k) 返回指向第一个与键 k 匹配的 pair 的迭代指针,这就是说,当你想要检查是否存在至少一个与该键关联的值时,或者只需第一个匹配时,这个函数最有用。例如:

typedef multimap  mmss;
void func(const mmss & dns)
{
mmss::const_iterator cit=dns.find("213.108.96.7");
if (cit != dns.end())
cout <<"213.108.96.7 found" < else
cout <<"not found" < }

处理多个关联值
  count(k) 成员函数返回与给定键关联的值得数量。下面的例子报告了有多少个与键 “213.108.96.7” 关联的值:

cout<            <<" elements associated"<

  为了存取 multimap 中的多个值,使用 equal_range()、lower_bound()和 upper_bound()成员函数:
equal_range(k):该函数查找所有与 k 关联的值。返回迭代指针的 pair,它标记开始和结束范围。下面的例子显示所有与键“213.108.96.7”关联的值:

typedef multimap ::const_iterator CIT;
typedef pair Range;
Range range=dns.equal_range("213.108.96.7");
for(CIT i=range.first; i!=range.second; ++i)
cout << i->second << endl; //output: cpluspluszone.com
// cppzone.com

   lower_bound() 和 upper_bound():lower_bound(k) 查找第一个与键 k 关联的值,而 upper_bound(k) 是查找第一个键值比 k 大的元素。下面的例子示范用 upper_bound()来定位第一个其键值大于“213.108.96.7”的元素。通常,当键是一个字符串时,会有一个词典编纂比较:

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<second<

如果你想显示其后所有的值,可以用下面这样的循环:

// 插入有相同键的多个值
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<second<    ++cit;
}
结论
  虽然 map 和 multimap 具有相同的接口,其重要差别在于重复键,设计和使用要区别对待。此外,还要注意每个容器里 insert()成员函数的细微差别。
阅读(1350) | 评论(4) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-06-13 09:28:14

STL HASH_MAP简单应用 http://www.cppblog.com/newplan/archive/2009/04/24/48912.html /* *用来测试STL hash_map *简单例子2008.5.5 */ #include #include #include #include /*因为hash_map暂不为CPP标准所以没办法写为*/ /*-------------------------------------------*/ using std::cout; using std::endl; using std::string; /*-------------------------------------------*/ /*函数类 *作为hash_map的hash函数 *string没有默认的hash函数 */ class str_hash{ public:

chinaunix网友2010-06-13 00:03:11

http://hi.baidu.com/asmcvc/blog/item/c45eb90060a69d1b728b65f0.html

chinaunix网友2010-06-13 00:02:47

STL中map与hash_map容器的选择 首先,要说的是这两种数据结构的都提供了KEY-VALUE的存储和查找的功能.但是实现是不一样的,map是用的红黑树,查询时间复杂度为 log(n),而hash_map是用的哈希表.查询时间复杂度理论上可以是常数,但是消耗内存大,是一种以存储换时间的方法. 就应用来说,map已经是STL标准库的东西,可是hash_map暂时还未进入标准库,但也是非常常用也非常重要的库. map查找,在总查找效率上比不上hash表,但是它很稳定,它的算法复杂度不会出现波动。在一次查找中,你可以断定它最坏的情况下其复杂度不会超过 O(log2N)。而hash表就不一样,是O(1),还是O(N),或者在其之间,你并不能把握。假若你在开发一个供外部调用的接口,其内部有关键字的查找,但是这个接口调用并不频繁,你是会希望其调用速度快、但不稳定呢,还是希望其调用时间平均、且稳定呢。反之假若你的程序需要查找一个关键字,这个操作非常频繁,你希望这些操作在总体上的时间较短,那么hash表查询在总时间上会比其他要短,平均操作时间也会短。这里就需要权衡了。

chinaunix网友2010-06-13 00:00:18

映射(map)和多重映射类 http://hi.baidu.com/asmcvc/blog/item/c45eb90060a69d1b728b65f0.html 1、映射和多重映射类: 它们提供了操作与关键字相关联的映射值(mapped value)的方法。 映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字,而映射只允许存放与映射值一一对应的单一关键字。 多重映射和映射关联容器类用于快速存储和读取关键字与相关值(关键字/数值对,key/value pair)。 如果保存学生的简明资料,要求按学号排序,使用映射关联容器(因为不会重号)是最合适的。如用姓名排序,因姓名可能重复,使用多重映射更为合适。使用时要用头文件。 2、映射(map)类模板声明: template, typename A = allocator> > class map; 3、 map容器有多种构造函数: map ()