软件设计模式课程设计--基于迭代器、适配器、策略模式的hashmap设计.docVIP

2008级软件设计模式课程设计 （基于迭代器、适配器、策略模式的hashmap设计） 指导老师： 小组成员： ） 教师意见： 2011年7月4日 目的及简要介绍 大家都知道，C++为广大爱好者提供了诸如Iterator、list等容器供大家使用，大大的方便了大家处理数据。这里，我们同样为大家提供一个满足STL要求的容器来供大家使用，让大家在数据处理的过程中能更方便快捷。 C++标准对容器提出了许多需求，只有满足这些需求，才能算得上是STL容器。 基本hashmap(散列表)：STL中的最大的疏忽吗？在STL中，没有定义hashmap容器，这里我们实现了。 散列表在平均情况下可以提供常量时间的插入、删除和查找。散列表并不是将元素有序地存储，而是把各元素散列(hash)或映射至某个桶(bucket)。只要所存储的元素个数不比桶数大太多，插入、删除和查找操作都能在常量时间内运行。 Hashmap也存储键/值对，它提供的操作与map几乎一样，这个hashmap实现使用链式散列（也称开放散列），而且没有提供诸如再散列等高级操作。 程序实现 Hashmap的访问操作： 标准要求为键比较和值比较对象提供访问方法： Operator[]与STL中的map的原型相似。如果原来的hashmap中没有该键对应的值，则会插入一个，它会调用被映射的元素的默认构造函数进行填充，并且反回这个值。 模板的分离编译： 在模板类的声明文件(一般是.h文件)的最后添加一个include语句，将模板类的实现文件包含进来，例如： #include “template_class_implement.cpp” 将模板类的实现类文件从项目中移除(使工程中不含模板的实现文件 .cpp),但并不从磁盘上移除，不改变其路径。使它不能显示的参与编译。 在声明main函数的文件中包含要使用的模板类的声明文件。 设计模式 相关内容 1、Hashmap应当允许客户指定自己的散列函数和桶数，而针对特定工作负载制定散列行为。另一方面，客户如果没有这种需求，或者没有能力来编写一个好的散列函数及选择桶数，也应该能够不做任何定制地直接使用容器。一种解决方案是允许客户在hashmap构造函数中提供散列函数和桶数，并为之提供默认值。另外，把散列函数和桶数包装在一个散列类中也是一种合理的做法: Hash()的实现要难一些，部分原因在于它必须应用于任何类型的键，它要把键映射至某个mNumBuckets桶。此函数使用了除留余数法来完成散列，即键所对应的桶（号）是键对桶数取余后得到的一个整数值。 遗憾的是，前面的方法无法应用于string，因为不同的string对象可能包含相同的string值。因此相同的string值就可能散列到不同的桶中。这样一来，可以想到，专门针对string提供DefaultHash类的一个部分特殊化。 2、它支持3个基本操作：插入、删除、查找。 比较器：hashmap允许客户指定比较类型作为模板参数，并且能在构造函数中传递该类的一个特定比较对象。Hashmap不会按键对元素排序，而是必须比较键的相等性。因此，它使用的是equal_to，比较对象只是用于检测是否试图向容器中插入重复键。 散列器：允许客户定义自己的类，以便构造此类对象传入构造函数，此时必须明确如何在构造函数中指定该参数的类型。 散列模板参数：使用 typedef 定义： 键类型，值类型，比较类型，散列类型 3、基本散列表结构通常包括固定数目桶，每个桶可以存储一个或多个元素。应当能够基于一个bucket-id在常量时间内访问桶。因此vector是对桶最为适合的容器。每个桶必须存储一个元素列表，因此STL list可以用作桶类型。 查找操作使用findElement帮助完成查找工作：findElement()首先使用散列对象将键散列至一个特定的桶。然后，在该桶中查找是否有元素的键与给定键匹配。所存储的元素是键/值对，所以具体的比较会在元素第一个字段上进行。构造函数中指定的比较函数对象就是用于完成这个比较。List需要完成线性查找来寻找匹配的元素，因此可以使用find()算法而不是一个显式的for循环。 Insert操作必须首先检查hashmap中是否已经存在此键的元素。如果没有，会把元素插入到适当的桶中的list。需要说明，findElement()会按引用返回散列到的那个桶，即在该桶中并没有找到此键的元素。 将hashmap作为容器 有关typedef 的容器需求 类型名 说明 Value_type 容器中存储的元素类型 Reference 容器中存储的元素类型的一个引用 Const_reference 容器中存储的const元素类型的一个引用