MAP原理及其在MFC中的实现
7页1、MAP原理及其在MFC中的实现2009-12-23 14:02一、 Map的基本知识映射(Map),又称为字典(Dictionary),是由关键字(Key)及其对应的元素值(Value)所组成的元素单元(Element)的表单式集合。通常,对于Map而言,使用给定的Key,可以迅速地从单元集合中检索到相应的元素。因此,在需要对大量数据进行查找操作而查找的性能又占据重要地位的场合,Map无疑是一种较理想的容器。譬如,在MFC中,使用Map来实现HandleMaps(句柄映射),以及其他的一些内部数据结构。同时,MFC也提供了公共Map类。使用公共Map类,MFC程序员可以轻易地高效地根据自身的需求实现程序中自定义的映射。通常,当一个Map对象被删除时,或者,当其中的元素被移除时,关键字和元素值也将被完全删除。从数据结构的角度分析,有关Map的典型操作有:1、向Map中插入具有给定关键字的元素单元。2、在Map中查找具有给定关键字的元素单元。3、在Map中删除具有给定关键字的元素单元。4、枚举(遍历)Map中的所有元素单元。MFC中的各种Map实现,都提供了实现上述操作的成员函数。为了方便
2、讨论,我们以CMap为代表,进行讲解。一旦你已经向Map中插入了一个关键字-元素值组合对(Key-Value pair)单元,就可以利用关键字访问Map,从而有效地检索、添加或者删除元素单元,也可以遍历Map中的所有单元。对MFC中的CMap等,除了关键字访问方法之外,还有另一种不同的类型-POSITION,也可以作为访问元素单元的辅助方式,可以使用一个POSITION来记住一个元素单元或者对Map进行枚举操作。你可能认为这种使用POSITION实现的遍历等同于使用关键字来进行的Map遍历,事实上并非如此,确切的说,两种检索的等价性是不确定的。MFC中的提供了基于模板的CMap类。利用CMap模板类,可以处理特定的数据类型,例如用户自定义的类或结构体等。同时,MFC也提供了基于指定数据类型的非模板类,其中包括: 类名关键字类型元素值类型CMapWordToPtrWORDSVoid pointersCMapPtrToWordVoidpointers WORDSCMapPtrToPtrVoid pointersVoid pointersCMapWordToObWORDSObjectsCMa
3、pStringToObStringsObjectsCMapStringToPtrStringsVoid pointersCMapStringToStringStringsString二、 Map的工作原理使用Map的最大优势是它的快速查找的优秀性能,而取得最优性能的关键在于尽量使得在检索周期内所需进行的元素检查(比对)次数达到最少。顺序查找的性能是最差的,因为如果使用顺序查找算法在包含n个元素单元的Map中查找某个元素,可能(最坏情况下)需要进行n次独立的比较运算。二元查找(折中查找)的性能表现要稍好一些,可是,一个不容忽视的问题是-二元查找要求待查序列为有序排列,这无疑会降低Map自身的操作灵活性。在我们的理解中,所谓的最佳算法应当是不论元素单元数目的多少,也不论元素是以什么顺序进行排列,查找过程都无需任何额外的比对操作,而能够仅仅通过简单的计算方法,就可以直接指向最终的相应元素的快速、高效算法。这听起来有些玄乎,但事实上,这种算法的确是有可能实现的(而且,我相信,Map可以做得到)。在MFC的CMap及其相关的Map类中,只要对Map进行正确设置,Lookup函数通常能够一次到位的
4、查找到任意元素,而很少需要进行两次或者三次以上的查找比对。那么,这种高效的查找是如何实现的呢?不失一般性,以MFC中的CMap模板类为例。在Map被创建之后(通常是恰恰在第一个元素被插入之前的瞬间),系统会为一个指向CAssoc结构体的指针数组的哈希表分配内存。MFC使用CAssoc结构体描述元素值和关键字的组合对。CAssoc结构体描述如下:struct CAssocCAssoc* pNext;UINT nHashValue;CString key;CString value; 无论何时,只要有一个元素值-关键字单元被加入到Map中,就会随之创建一个新的CAssoc结构体,并根据单元中的关键字的实际值来计算出相应的哈希值。同时,拷贝一个指向CAssoc结构体的指针并将其插入到哈希表中索引值为i的位置中。其中,i的计算公式如下:i=nHashValue%nHushTableSize式中,nHashValue是由关键字Key的实际值计算出来的哈希值;nHashTableSize是哈希表中元素的数目(默认情况下,哈希表的大小为17)。如果在哈希表中的索引值为i的位置已经容纳了一个CAsso
《MAP原理及其在MFC中的实现》由会员夏**分享,可在线阅读,更多相关《MAP原理及其在MFC中的实现》请在金锄头文库上搜索。
新河小学有效课堂教学活动实施方案
CM6132机床主轴箱结构设计全套CAD图纸
河北油品添加剂项目可行性研究报告(DOC 92页)
三年级音乐教学工作计划(三篇).doc
湛江密封垫片项目实施方案参考范文
教育专题:第二章合并同类项的反思性说课
如何为幼儿创设一个保教结合的户外活动环境
大学英语试题
电脑组装配置参考表
应用金属有机骨架化合物去除饮用水中砷、氟的基础研究
半夏的功效与作用半夏的现代研究
观飞越老人院有感
2022年关于活动策划方案合集十篇
农业产业化出口蔬菜标准化生产基地扩建项目
建筑工程造价专业实习报告1
各贸易术语买卖双方承担的主要责任、费用及风险
银行财务工作总结与计划(二篇).doc
办公楼等级标准参考
检察机关应加强对“另案处理”的法律监督论文.doc
测量实习报告总结范文
2024-02-12 4页
2023-07-13 7页
2023-01-28 6页
2023-06-09 12页
2023-01-26 29页
2022-08-05 3页
2023-07-12 6页
2023-07-07 37页
2023-01-22 3页
2023-05-03 3页