【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。

hash_map类在头文件hash_map中,和所有其它的C++标准库一样,头文件没有扩展名。如下声明:

class hash_map<class _Tkey, class _Tval>

{

private:

typedef pair<_Tkey, _Tval> hash_pair;

typedef list<hash_pair> hash_list;

typedef vector<hash_list> hash_table;

};

hash_map是一个聚合类,它继承自_Hash类,包括一个vector,一个list和一个pair,其中vector用于保存桶,list用于进行冲突处理,pair用于保存key->value结构,简要地伪码如下:

class hash_map<class _Tkey, class _Tval>

{

private:

typedef pair<_Tkey, _Tval> hash_pair;

typedef list<hash_pair> hash_list;

typedef vector<hash_list> hash_table;

};

当然,这只是一个简单模型,C++标准库的泛型模版一向以嵌套复杂而闻名,初学时看类库,无疑天书啊。微软的hash_map类还聚合了hash_compare仿函数类,hash_compare类里又聚合了less仿函数类,乱七八糟的。

下面说说使用方法:

一、简单变量作为索引:整形、实性、指针型 其实指针型也就是整形,算法一样。但是hash_map会对char*, const char*, wchar_t*, const wchar_t*做特殊处理。 这种情况最简单,下面代码是整形示例:

hash_map<int, int> IntHash;

IntHash[1] = 123;

IntHash[2] = 456;

int val = IntHash[1];

int val = IntHash[2];

实型和指针型用法和整形一样,原理如下: 1、使用简单类型作索引声明hash_map的时候,不需要声明模版的后两个参数(最后一个参数指名hash_map节点的存储方式,默认为pair,我觉得这就挺好,没必要修改),使用默认值就好。 2、对于除过字符串的其它简单类型,hash_map使用模版函数 size_t hash_value(const _Kty& _Keyval) 计算hash值,计算方法是经典的掩码异或法,自动溢出得到索引hash值。微软的工程师也许开了一个玩笑,这个掩码被定义为0xdeadbeef(死牛肉,抑或是某个程序员的外号)。 3、对于字符串指针作索引的时候,使用定类型函数inline size_t hash_value(const char *_Str)或inline size_t hash_value(const wchar_t *_Str)计算hash值,计算方法是取出每一个字符求和,自动溢出得到hash值。对于字符串型的hash索引,要注意需要自定义less仿函数。 因为我们有理由认为,人们使用hash表进行快速查找的预期成本要比在hash表中插入的预期成本低得多,所以插入可以比查找昂贵些;基于这个假设,hash_map在有冲突时,插入链表是进行排序插入的,这样在进行查询冲突解决的时候就能够更快捷的找到需要的索引。 但是,基于泛型编程的原则,hash_map也有理由认为每一种类型都支持使用"<"来判别两个类型值的大小,这种设计恰好让字符串类型无所适从,众所周知,两个字符串指针的大小并不代表字符串值的大小。见如下代码:

hash_map<const char*, int> CharHash;

CharHash["a"] = 123;

CharHash["b"] = 456;

char szInput[64] = "";

scanf("%s", szInput);

int val = CharHash[szInput];

最终的结果就是无论输入任何字符串,都无法找到对应的整数值。因为输入的字符串指针是szInput指针,和"a"或"b"字符串常量指针的大小是绝对不会相同。解决方法如下: 首先写一个仿函数CharLess,继承自仿函数基类binary_function(当然也可以不继承,这样写只是符合标准,而且写起来比较方便,不用被类似于指针的指针和指针的引用搞晕。

struct CharLess : public binary_function<const char*, const char*, bool>

{

public:

result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const

{

return(stricmp(_Left, _Right) < 0 ? true : false);

}

};

很好,有了这个仿函数,就可以正确的使用字符串指针型hash_map了。如下:

hash_map<const char*, int, hash_compare<const char*, CharLess> > CharHash;

CharHash["a"] = 123;

CharHash["b"] = 456;

char szInput[64] = "";

scanf("%s", szInput);

int val = CharHash[szInput];

现在就可以正常工作了。至此,简单类型的使用方法介绍完毕。

未完待续

转自:http://blog.csdn.net/sdhongjun/article/details/4517325

原文发布于微信公众号 - 程序员互动联盟(coder_online)

原文发表时间:2016-02-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

C语言干货,新手入门必看,基础知识大汇总!

习C语言始终要记住“曙光在前头”和“千金难买回头看”,“千金难买回头看”是学习知识的重要方法,就是说,学习后面的知识,不要忘了回头弄清遗留下的问题和加深理解前面...

2835
来自专栏程序员互动联盟

【C语言系列】C语言概念--基本数据类型简介

1.概述   C 语言包含的数据类型如下图所示: ? 2.各种数据类型介绍 2.1整型   整形包括短整型、整形和长整形。 2.1.1短整形   short ...

4428
来自专栏aCloudDeveloper

一个交换程序的通用版本

Author:bakari   Date:2012.9.3       交换程序是每个开始学习编程的人必学习的一个初级算法。算法思想很简单,就是为两个交换的双方...

1766
来自专栏编程

C语言/C加加新手入门学习经验资料分享,基础知识大汇总!

C语言是面向过程的,而C++是面向对象的 相信这么努力的你 已经置顶了我 学习C语言始终要记住“曙光在前头”和“千金难买回头看”,“千金难买回头看”是学习知识的...

2219
来自专栏后端技术探索

从头到尾解析Hash 表算法

问题描述 百度面试题: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。 假设目前有一千万个记...

1504
来自专栏老司机的简书

老司机出品——包教包会之玩转正则表达式

结束了CoreAnimation系列之后,老司机心里仿佛也轻松了许多。今天说说开发中的一个利器吧,正则表达式。

1693
来自专栏数据结构与算法

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2926
来自专栏青蛙要fly的专栏

Android技能树 — 排序算法基础小结

现在安卓面试,对于算法的问题也越来越多了,要求也越来越多,特别是排序,基本必考题,而且还动不动就要手写,所以陆续要写算法的文章,也正好当自己学习。o(╥﹏╥)o

872
来自专栏老九学堂

C语言干货,新手入门必看,基础知识大汇总!

学习C语言始终要记住“曙光在前头”和“千金难买回头看”,“千金难买回头看”是学习知识的重要方法,就是说,学习后面的知识,不要忘了回头弄清遗留下的问题和加深理解前...

41011
来自专栏工科狗和生物喵

【计算机本科补全计划】C++ Primer 第二章 【变量和基本类型】

正文之前 C++的数据类型包括 算术类型(int double等)和空类型(void),今天发生了一些很可怕的事情,详情请看正文之后!!我好害怕!! 正文 1、...

38911

扫码关注云+社区

领取腾讯云代金券