【专业技术】hash_map使用(二)

上次说完了简单类型的hash_map使用,现在说说用户自定义类型:比如对象类型,结构体的hash_map使用。

这种情况比价复杂,我们先说简单的,对于C++标准库的string类。 庆幸的是,微软为basic_string(string类的基类)提供了hash方法,这使得使用string对象做索引简单了许多。值得注意(也值得郁闷)的是,虽然支持string的hash,string类却没有重载比较运算符,所以标准的hash_compare仿函数依旧无法工作。我们继续重写less仿函数。

struct string_less : public binary_function<const string, const string, bool>

{

public:

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

{

return(_Left.compare(_Right) < 0 ? true : fase);

}

};

好了,我们可以书写如下代码:

hash_map<string, int, hash_compare<string, string_less> > StringHash;

StringHash["a"] = 123;

StringHash["b"] = 456;

string strKey = "a";

int val = CharHash[strKey];

这样就可以了。 对于另外的一个常用的字符串类CString(我认为微软的CString比标准库的string设计要洒脱一些)更加复杂一些。很显然,标准库里不包含对于CString的支持,但CString却重载了比较运算符(郁闷)。我们必须重写hash_compare仿函数。值得一提的是,在Virtual Stdio 2003中,CString不再是MFC的成员,而成为ATL的成员,使用#include <atlstr.h>就可以使用。我没有采用重写hash_compare仿函数的策略,而仅仅是继承了它,在模版库中的继承是没有性能损耗的,而且能让我偷一点懒。

首先重写一个hash_value函数:

inline size_t CString_hash_value(const CString& str)

{

size_t value = _HASH_SEED;

size_t size = str.GetLength();

if (size > 0) {

size_t temp = (size / 16) + 1;

size -= temp;

for (size_t idx = 0; idx <= size; idx += temp) {

value += (size_t)str[(int)idx];

}

}

return(value);

}

其次重写hash_compare仿函数:

class CString_hash_compare : public hash_compare<CString>

{

public:

size_t operator()(const CString& _Key) const

{

return((size_t)CString_hash_value(_Key));

}

bool operator()(const CString& _Keyval1, const CString& _Keyval2) const

{

return (comp(_Keyval1, _Keyval2));

}

};

上面的重载忽略了基类对于less仿函数的引入,因为CString具备比较运算符,我们可以使用默认的less仿函数,在这里映射为comp。好了,我们可以声明新的hash_map对象如下:

hash_map<CString, int, CString_hash_compare> CStringHash;

其余的操作一样一样的。

下来就说说对于自定义对象的使用方法:首先定义

struct IHashable

{

virtual unsigned long hash_value() const = 0;

virtual bool operator < (const IHashable& val) const = 0;

virtual IHashable& operator = (const IHashable& val) = 0;

};

让我们自写的类都派生自这里,有一个标准,接下来定义我们的类:

class CTest : public IHashable

{

public:

int m_value;

CString m_message;

public:

CTest() : m_value(0) {}

CTest(const CTest& obj)

{

m_value = obj.m_value;

m_message = obj.m_message;

}

public:

virtual IHashable& operator = (const IHashable& val) {

m_value = ((CTest&)val).m_value;

m_message = ((CTest&)val).m_message;

return(*this);

}

virtual unsigned long hash_value() const {

// 这里使用类中的m_value域计算hash值,也可以使用更复杂的函数计算所有域总的hash值

return(m_value ^ 0xdeadbeef

}

virtual bool operator < (const IHashable& val) const {

return(m_value < ((CTest&)val).m_value);

}

};

用这个类的对象做为hash索引准备工作如下,因为接口中规定了比较运算符,所以这里可以使用标准的less仿函数,所以这里忽略:

template<class _Tkey>

class MyHashCompare : public hash_compare<_Tkey>

{

public:

size_t operator()(const _Tkey& _Key) const {

return(_Key.hash_value());

}

bool operator()(const _Tkey& _Keyval1, const _Tkey& _Keyval2) const {

return (comp(_Keyval1, _Keyval2));

}

};

下来就这样写:

CTest test;

test.m_value = 123;

test.m_message = "This is a test";

MyHash[test] = 2005;

int val = MyHash[test];

可以看到正确的数字被返回。 关于hash_map的思考: 1、性能分析:采用了内联代码和模版技术的hash_map在效率上应该是非常优秀的,但我们还需要注意如下几点: * 经过查看代码,字符串索引会比简单类型索引速度慢,自定义类型索引的性能则和我们选择hash的内容有很大关系,简单为主,这是使用hash_map的基本原则。 * 可以通过重写hash_compair仿函数,更改里面关于桶数量的定义,如果取值合适,也可以得到更优的性能。如果桶数量大于10,则牢记它应该是一个质数。 * 在自定义类型是,重载的等号(或者拷贝构造)有可能成为性能瓶颈,使用对象指针最为索引将是一个好的想法,但这就必须重写less仿函数,理由同使用字符串指针作为索引。

自己使用上面的方法成功解决了使用PTCHAR作为Key的使用,其解决方法如下:

inline size_t PTCHAR_hash_value(const PTCHAR str)

{

size_t value = _HASH_SEED;

size_t size = _tcslen(str);

if (size > 0) {

size_t temp = (size/16) + 1;

size -= temp;

for (size_t idx=0; idx<=size; idx+=temp) {

value += (size_t)str[(int)idx];

}

}

return value;

}

class PTCHAR_hash_compare : public stdext::hash_compare<PTCHAR>

{

public:

size_t operator()(const PTCHAR _Key) const {

return ((size_t)PTCHAR_hash_value(_Key));

}

bool operator()(const PTCHAR _Keyval1, const PTCHAR _Keyval2) const {

return (_tcscmp(_Keyval1, _Keyval2));

}

};

stdext::hash_map<PTCHAR, long, PTCHAR_hash_compare > myHash;

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

UVA10305 | 拓扑排序

John has n tasks to do. Unfortunately, the tasks are not independent and the exe...

832
来自专栏PHP在线

mysql函数

四、日期和时间函数 //返回当前的日期 curdate()或current_date() select curdate(); // 2014-12-05 ...

2833
来自专栏刘望舒

设计模式(九)模版方法模式

1.模版方法模式简介 模版方法模式介绍 在软件开发中,有时会遇到类似的情况,某个方法的实现需要多个步骤,其中有些步骤是固定的,而有些步骤并不固定,存在可变性。为...

2056
来自专栏做全栈攻城狮

电脑小白自学软件编程-.Net语法基础之循环语句,纯技巧干货

课程总目录:因头条无法自定义目录,大家关注:“做全栈攻城狮”微信公众号。回复“.net目录”,即可获取。微信公众号也包含大量学习教程,等你来~

1393
来自专栏CDA数据分析师

Python数据统计:分组的一些小技巧

最近在用python做数据统计,这里总结了一些最近使用时查找和总结的一些小技巧,希望能帮助在做这方面时的一些童鞋。有些技巧是很平常的用法,平时我们没有注意,但是...

2505
来自专栏xingoo, 一个梦想做发明家的程序员

MFC中注释含义

下面是 CStdioFile 类的部分列表,其中使用了 MFC 在其类中按类成员的用法划分它们时所采用的大多数标准注释: class CStdioFile :...

1997
来自专栏happyJared

设计模式入门:原型模式

  实际应用中,原型模式可以简单理解为克隆操作。在大多数面向对象编程语言中,实现克隆操作并不复杂,对于Java,我们只需继承Cloneable接口,并重写Obj...

702
来自专栏C/C++基础

nvarchar,nchar,vchar,nvchar,char…

nvarchar,nchar,vchar,nvchar,char,ntext,text区别详解 联机帮助上的:

1412
来自专栏智能大石头

深度解析C++拷贝构造函数

自2003年开始,断断续续用了12年C++,直到这两年做物联网嵌入式开发,感觉对C++的掌握仅有10%左右。 习惯了C#开发,C++倒显得难以下手!今天就一个函...

2209
来自专栏好好学java的技术栈

一文看透java8新特性

毫无疑问,Java 8发行版是自Java 5(发行于2004,已经过了相当一段时间了)以来最具革命性的版本。Java 8 为Java语言、编译器、类库、开发工具...

1282

扫码关注云+社区

领取腾讯云代金券