文档介绍：这几天我在用map做一些小小的应用,其中我就要用到用wstring作为key的一些map,以前总是存在一些问题,编译有些问题
当时我没有用心去留意这方面的知识,原因是项目太紧,我用其它的方案替代了这个,今天我有一点时间,特地将这部分知识
弄明白,看一下map方面的资料, map是基于hash原理建立起来的一个key-value数据对。在建立自己的key时,一般要实现
以下两个内容:
1、key的hash函数。
2、key的比较函数,为了确保key在map中的唯一性。
在map中,由于存储结构为红黑树, 所以key的hash函数已经为用户设计好,关于怎么设计,目前我不没有研究这方面的内容。
用户只需要实现key的比较函数,在这里只需实现operator<函数,即小于函数。
例如:
struct TSWord{
TSWord(unsigned short *buf);
friend operator <(TSWord const &k1, TSWord const &k2);
unsigned short buf[50];
};
operator <(TSWord const &k1, TSWord const &k2)
{
return wcscmp((wchar_t *), (wchar_t *)) < 0;
}
这样才实现一个map的正常key的要求,经常我测试上面完全没有问题。
后来,我阅读了相关资料, 针对此类问题有了更加清晰的认识:
Hash_map相关资料
0 为什么需要hash_map
用过map吧?map提供一个很常用的功能,那就是提供key-value的存储和查找功能。例如,我要记录一个人名和相应的存储,而且随时增加,要快速查找和修改:
岳不群-华山派掌门人,人称君子剑张三丰-武当掌门人,太极拳创始人东方不败-第一高手,葵花宝典...
这些信息如果保存下来并不复杂,但是找起来比较麻烦。例如我要找"张三丰"的信息,最傻的方法就是取得所有的记录,然后按照名字一个一个比较。如果要速度快,就需要把这些记录按照字母顺序排列,然后按照二分法查找。但是增加记录的时候同时需要保持记录有序,因此需要插入排序。考虑到效率,这就需要用到二叉树。讲下去会没完没了,如果你使用STL 的map容器,你可以非常方便的实现这个功能,而不用关心其细节。关于map的数据结构细节,感兴趣的朋友可以参看学习STL map, STL set之数据结构基础。看看map的实现:
#include <map>#include <string>using namespace std;...map<string, string> namemap;//增加。。。namemap["岳不群"]="华山派掌门人,人称君子剑";namemap["张三丰"]="武当掌门人,太极拳创始人";namemap["东方不败"]="第一高手,葵花宝典";...//查找。。if(("岳不群") != ()){ ...}
不觉得用起来很easy吗?而且效率很高,100万条记录,pare的比较,就能找到你要找的记录;200万条记录事,也只要用21次的比较。
速度永远都