软件设计模式课程设计

《软件设计模式课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2008级软件设计模式课程设计（基于迭代器、适配器、策略模式的hashmap设计）指导老师：蒋湘涛小组成员：刘应华（20083848）王紫龙（20083855）陈理平（20083837）王旭（20083854）教师意见：2011年7月4日12一、目的及简要介绍大家都知道，C++为广大爱好者提供了诸如Iterator、list等容器供大家使用，大大的方便了大家处理数据。这里，我们同样为大家提供一个满足STL要求的容器来供大家使用，让大家在数据处理的过程中能更方便快捷。C++标准对容器提出了许多需求，只有满足这些需求，才能算得上是

2、STL容器。基本hashmap(散列表)：STL中的最大的疏忽吗？在STL中，没有定义hashmap容器，这里我们实现了。散列表在平均情况下可以提供常量时间的插入、删除和查找。散列表并不是将元素有序地存储，而是把各元素散列(hash)或映射至某个桶(bucket)。只要所存储的元素个数不比桶数大太多，插入、删除和查找操作都能在常量时间内运行。Hashmap也存储键/值对，它提供的操作与map几乎一样，这个hashmap实现使用链式散列（也称开放散列），而且没有提供诸如再散列等高级操作。二、程序实现Hashmap的访问操作：标准

3、要求为键比较和值比较对象提供访问方法：Operator[]与STL中的map的原型相似。如果原来的hashmap中没有该键对应的值，则会插入一个，它会调用被映射的元素的默认构造函数进行填充，并且反回这个值。模板的分离编译：在模板类的声明文件(一般是.h文件)的最后添加一个include语句，将模板类的实现文件包含进来，例如：#include“template_class_implement.cpp”将模板类的实现类文件从项目中移除(使工程中不含模板的实现文件.cpp),但并不从磁盘上移除，不改变其路径。使它不能显示的参与编译。

4、在声明main函数的文件中包含要使用的模板类的声明文件。三、设计模式四、相关内容1、Hashmap应当允许客户指定自己的散列函数和桶数，而针对特定工作负载制定散列行为。另一方面，客户如果没有这种需求，或者没有能力来编写一个好的散列函数及选择桶数，也应该能够不做任何定制地直接使用容器。一种解决方案是允许客户在hashmap构造函数中提供散列函数和桶数，并为之提供默认值。另外，把散列函数和桶数包装在一个散列类中也是一种合理的做法:12Hash()的实现要难一些，部分原因在于它必须应用于任何类型的键，它要把键映射至某个mNumBuc

5、kets桶。此函数使用了除留余数法来完成散列，即键所对应的桶（号）是键对桶数取余后得到的一个整数值。遗憾的是，前面的方法无法应用于string，因为不同的string对象可能包含相同的string值。因此相同的string值就可能散列到不同的桶中。这样一来，可以想到，专门针对string提供DefaultHash类的一个部分特殊化。2、它支持3个基本操作：插入、删除、查找。比较器：hashmap允许客户指定比较类型作为模板参数，并且能在构造函数中传递该类的一个特定比较对象。Hashmap不会按键对元素排序，而是必须比较键的相等

6、性。因此，它使用的是equal_to，比较对象只是用于检测是否试图向容器中插入重复键。散列器：允许客户定义自己的类，以便构造此类对象传入构造函数，此时必须明确如何在构造函数中指定该参数的类型。散列模板参数：使用typedef定义：键类型，值类型，比较类型，散列类型3、基本散列表结构通常包括固定数目桶，每个桶可以存储一个或多个元素。应当能够基于一个bucket-id在常量时间内访问桶。因此vector是对桶最为适合的容器。每个桶必须存储一个元素列表，因此STLlist可以用作桶类型。查找操作使用findElement帮助完成查找

7、工作：findElement()首先使用散列对象将键散列至一个特定的桶。然后，在该桶中查找是否有元素的键与给定键匹配。所存储的元素是键/值对，所以具体的比较会在元素第一个字段上进行。构造函数中指定的比较函数对象就是用于完成这个比较。List需要完成线性查找来寻找匹配的元素，因此可以使用find()算法而不是一个显式的for循环。Insert操作必须首先检查hashmap中是否已经存在此键的元素。如果没有，会把元素插入到适当的桶中的list。需要说明，findElement()会按引用返回散列到的那个桶，即在该桶中并没有找到此键

8、的元素。4、将hashmap作为容器有关typedef的容器需求类型名说明Value_type容器中存储的元素类型Reference容器中存储的元素类型的一个引用Const_reference容器中存储的const元素类型的一个引用Iterator迭代处理容器中元素的“智能指